fastest general number primality-proving algorithm?

ixfd64 · 2003-12-16, 02:52

Does anyone know what is the fastest general number primaliy testing algorithm? I've heard that algorithms like APRT-CLE are fast, but I don't know which is the fastest.

Also, does anyone know the algorithm discovered around 4th-Aug-2002?

Thanks.

nfortino · 2003-12-16, 03:27

Quote:

Originally posted by ixfd64

Also, does anyone know the algorithm discovered around 4th-Aug-2002?

I believe the algorithm you speak of is an algorithm that proves/disproves a general number prime in polynomial time. Information about it can be found at http://www.utm.edu/research/primes/prove/prove4_3.html and http://www.cse.iitk.ac.in/primality.pdf. A google search for "primes in p" will net many more documents. AFAIK (which is not very much), nobody has created an efficient implementation of this method.

Xyzzy · 2003-12-16, 05:52

Maybe this?

http://www.mersenneforum.org/showthread.php?threadid=65

ewmayer · 2003-12-17, 17:06

The "2002" algorithm is the one discovered by 3 Indian scientists, and is generally called the AKS algorithm after the initials of the 3 discoverers (Agarwal, Kayal and Saxena). Here is the MathWorld link:

http://mathworld.wolfram.com/AKSPrimalityTest.html

As far as I know, the AKS test has not been shown to be tremendously faster than known algorithms (e.g. APRCL, ECPP, cyclotomy) for real-world primes (though this may change as the algorithm is refined further). The key difference between AKS and every previous general primality-proving algorithm is conceptual: AKS does not require any unproven hypothesis (e.g. RH) to be true in order to be provably polynomial time on all inputs. It is in that sense that it is revolutionary, not so much in the actual-runtime sense.

2003-12-16, 02:52	#1
ixfd64 Bemusing Prompter "Danny" Dec 2002 California 2390₁₀ Posts	fastest general number primality-proving algorithm? Does anyone know what is the fastest general number primaliy testing algorithm? I've heard that algorithms like APRT-CLE are fast, but I don't know which is the fastest. Also, does anyone know the algorithm discovered around 4th-Aug-2002? Thanks.

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Unit Differences for Primality Proving	Trejack	Miscellaneous Math	11	2016-05-12 04:15
Primality proving of DB factors?	jasonp	FactorDB	3	2011-10-17 18:04
Primality proving	CRGreathouse	Software	13	2011-01-30 14:30
New Class of primes - proving algorithm	AntonVrba	Math	2	2008-10-06 00:53
Fastest possible algorithm to calculate the square root of a 10,000,000 digit number	Fusion_power	Math	19	2007-11-02 21:37

2003-12-16, 05:52	#3
Xyzzy "Mike" Aug 2002 3·2,741 Posts	Maybe this? http://www.mersenneforum.org/showthread.php?threadid=65

2003-12-17, 17:06	#4
ewmayer ∂²ω=0 Sep 2002 República de California 11639₁₀ Posts	The "2002" algorithm is the one discovered by 3 Indian scientists, and is generally called the AKS algorithm after the initials of the 3 discoverers (Agarwal, Kayal and Saxena). Here is the MathWorld link: http://mathworld.wolfram.com/AKSPrimalityTest.html As far as I know, the AKS test has not been shown to be tremendously faster than known algorithms (e.g. APRCL, ECPP, cyclotomy) for real-world primes (though this may change as the algorithm is refined further). The key difference between AKS and every previous general primality-proving algorithm is conceptual: AKS does not require any unproven hypothesis (e.g. RH) to be true in order to be provably polynomial time on all inputs. It is in that sense that it is revolutionary, not so much in the actual-runtime sense.