## AKS prime number test

Expand Messages
• I ve implemented the AKS prime number test. It is slower than any of the standard pseudo prime tests. I ve also extended the AKS test to a potential factoring
Message 1 of 3 , Dec 9, 2010
• 0 Attachment
I've implemented the AKS prime number test.

It is slower than any of the standard pseudo prime tests.

I've also extended the AKS test to a potential factoring algorithm.

For moderately sized numbers, it factors much much slower than other
factoring algorithms.

For example, it required 354 seconds to completely factor 549755813887.

AKS factored z = 549755813887 by initial trial division by prime < 100.
z = 7 is prime < 100.

AKS factored z = 78536544841 by initial trial division by prime < 100.
z = 79 is prime < 100.

AKS: z = 994133479 r = 911

AKS factored z = 994133479 by [ 14 +x]** 994133479 mod(x** 911 -1,
994133479 )

AKS: z = 8191 r = 179

AKS determined that z = 8191 is prime by [ 1 +x]** 8191 equals x**
8191 + 1 mod(x** 179 -1, 8191 ).

AKS: z = 121369 r = 347

AKS determined that z = 121369 is prime by [ 1 +x]** 121369 equals
x** 121369 + 1 mod(x** 347 -1, 121369 ).

[[7, 1], [79, 1], [8191L, 1], [121369L, 1], 353.68099999427795]

Kermit
• ... Nice. ... Indeed, that s the rub. It has a proven polynomial length, but the constants are so large it is easily beat in practice by ECPP (and all other
Message 2 of 3 , Dec 10, 2010
• 0 Attachment
> I've implemented the AKS prime number test.

Nice.

> It is slower than any of the standard pseudo prime tests.

Indeed, that's the rub. It has a proven polynomial length, but the
constants are so large it is easily beat in practice by ECPP (and all
other methods for very small numbers, say a couple hundred digits).
That may always be so (for reasonable sized numbers), or may not. Some
very sharp folks are working on it.

But the key success of AKS was answering the P vs NP question. In
theory the constants do not matter, in practice, they can be
everything!!!

CC
• Hi , all , ... Great , I m very glad to hear this . ... Another point is that AKS is actually a primality test . Many writers have a tendency to omit the
Message 3 of 3 , Dec 10, 2010
• 0 Attachment
Hi , all ,

At 2010-12-10 13:27, "Chris Caldwell" <caldwell@...> wrote :

> Some very sharp folks are working on it.

Great , I'm very glad to hear this .

> But the key success of AKS was answering the P vs NP question.

Another point is that AKS is actually a primality test .
Many writers have a tendency to omit the "pseudo-" from
"pseudo-primality test" when describing a compositeness test .

> In theory the constants do not matter,
> in practice, they can be everything!!!

Indeed , so true .
See my similar point in "Counting in Separate Realms" ,
http://upforthecount.com/math/asymtotes.html

Cheers ,

Walter
Your message has been successfully submitted and would be delivered to recipients shortly.