[REBOL] Re: Fw: prime solution
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."
