Mailing List Archive: 49091 messages
  • Home
  • Script library
  • AltME Archive
  • Mailing list
  • Articles Index
  • Site search
 

Fw: prime solution

 [1/5] from: chalz::earthlink::net at: 10-Aug-2002 18:23


An interesting little something my mother sent along to me. Figured there'd be a few people on this list interested in it. Prime solution wows the math world Scientists say algorithm offers 'foolproof' way to find primes http://www.cse.iitk.ac.in/news/primality.html ASSOCIATED PRESS NEW DELHI, Aug. 9 - Indian computer scientists say they have solved a mathematical problem that has eluded researchers for 2,200 years - and could be crucial in modern times in improving computer configurations. A THREE-MEMBER TEAM of scientists at the Indian Institute of Technology in the northern Indian city of Kanpur have devised a method that will make no mistake in quickly determining a prime number - those that are divisible only by themselves and 1. Prime numbers hold the key to solving many mathematical problems and play an important a role in cryptography. Scientists have long worked on ways to improve methods to identify a prime number. Greek mathematician Eratosthenes was the first to raise this problem around 200 B.C., when he offered one way of determining whether a number is prime. Computer scientists and mathematicians have since devised many faster ways to solve the problem, but all such methods carry a small risk of error. Some methods occasionally fail to detect a prime number, while others may select a nonprime number. "Our algorithm is deterministic; it has no chance of committing any error," said Manindra Agrawal, the principal author of the formula. An algorithm is a set of instructions for solving a specific mathematical problem in a limited number of steps. Agrawal and his two associates - Neeraj Kayal and Nitin Saxena - have written a paper detailing the formula, which was posted on their department's Web site Sunday. Copies of the paper were also dispatched to leading computer scientists and mathematicians across the world. "We have received several responses. All of them have expressed satisfaction with the new algorithm," Agrawal told The Associated Press by telephone. "No one has doubted our claim." The new algorithm will have no immediate applications, however, because current methods used in computers are faster. "We have used more steps than the current methods in use," explains Agrawal. "Our first objective was to find a method that is foolproof. Now, I am sure other researchers, or may be some of us, will start asking how can the number of steps be cut down and make the computation faster."

 [2/5] from: lmecir:mbox:vol:cz at: 14-Aug-2002 18:27


Hi Charles, thanks for the info. Using Rebol I found out, that it is unlikely that the algorithm will be faster than a brute force approach for numbers smaller than 706'044'139 (except for the powers). -L ----- Original Message ----- From: "Charles" <[chalz--earthlink--net]> To: <[rebol-list--rebol--com]> Sent: Sunday, August 11, 2002 12:23 AM Subject: [REBOL] Fw: prime solution An interesting little something my mother sent along to me. Figured there'd be a few people on this list interested in it. Prime solution wows the math world Scientists say algorithm offers 'foolproof' way to find primes http://www.cse.iitk.ac.in/news/primality.html ASSOCIATED PRESS NEW DELHI, Aug. 9 - Indian computer scientists say they have solved a mathematical problem that has eluded researchers for 2,200 years - and could be crucial in modern times in improving computer configurations. A THREE-MEMBER TEAM of scientists at the Indian Institute of Technology in the northern Indian city of Kanpur have devised a method that will make no mistake in quickly determining a prime number - those that are divisible only by themselves and 1. Prime numbers hold the key to solving many mathematical problems and play an important a role in cryptography. Scientists have long worked on ways to improve methods to identify a prime number. Greek mathematician Eratosthenes was the first to raise this problem around 200 B.C., when he offered one way of determining whether a number is prime. Computer scientists and mathematicians have since devised many faster ways to solve the problem, but all such methods carry a small risk of error. Some methods occasionally fail to detect a prime number, while others may select a nonprime number. "Our algorithm is deterministic; it has no chance of committing any error," said Manindra Agrawal, the principal author of the formula. An algorithm is a set of instructions for solving a specific mathematical problem in a limited number of steps. Agrawal and his two associates - Neeraj Kayal and Nitin Saxena - have written a paper detailing the formula, which was posted on their department's Web site Sunday. Copies of the paper were also dispatched to leading computer scientists and mathematicians across the world. "We have received several responses. All of them have expressed satisfaction with the new algorithm," Agrawal told The Associated Press by telephone. "No one has doubted our claim." The new algorithm will have no immediate applications, however, because current methods used in computers are faster. "We have used more steps than the current methods in use," explains Agrawal. "Our first objective was to find a method that is foolproof. Now, I am sure other researchers, or may be some of us, will start asking how can the number of steps be cut down and make the computation faster."

 [3/5] from: anton:lexicon at: 15-Aug-2002 16:21


Are you saying that you implemented the algorithm in rebol? If so, that's pretty clever. Anton.

 [4/5] from: lmecir:mbox:vol:cz at: 15-Aug-2002 16:01


Hi Anton, <<Anton>> Are you saying that you implemented the algorithm in rebol? If so, that's pretty clever. Anton. <</Anton>>
> Hi Charles, > > thanks for the info. Using Rebol I found out, that it is unlikely that the > algorithm will be faster than a brute force approach for numbers smaller > than 706'044'139 (except for the powers). > > -L
Not exactly. I tried to simulate only the While part of the algorithm. I don't know the Fast Fourier Multiplication the article mentioned (though a slower version can be implemented without it). Moreover, the algorithm looks impractical for Rebol - see the number mentioned - and that number is only a lower bound! A more realistic lower bound estimate is: 4,29e9. -L

 [5/5] from: chalz:earthlink at: 22-Aug-2002 23:35


Well, I'm sorry to hear that. I was hoping that REBOL might be able to handle the problem easily. Oh well :/ Here's at least hoping there are some math freaks on the list who got a primal thrill out of the news ;) --Charles