AKS prime number test
- 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
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,
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]
> 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
- 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,Indeed , so true .
> in practice, they can be everything!!!
See my similar point in "Counting in Separate Realms" ,