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