AKS - A polynomial-time algorithm for testing primality.

[Maybeso]

The questions and answers I've found on the web regarding this new method
(see http://www.utm.edu/research/primes/prove/prove4_3.html)
are scattered all over everywhere. So I'm going to post mine here in hopes of attracting the attention of Those Who Know.

Bob Silverman 'explains' and improves the search for (q, r):

Steps 3 to 10 can be done blazingly fast; I estimate only a few millisecs for n near 512 bits. How? You pre-build a table of (q,r) such that q = (r-1)/2 and use the size of n to index into this table to find the smallest q that can work.

Which leaves just the dreaded for loop:

for a = 1 to 2-/r log n[list]if ( (x - a)^n # (x^n - a) (mod (x^r - 1), n)) output COMPOSITE;[/list:u]

So why do we need to try all those a's?
If we start by evaluating (x - 1)^n (mod n) without the (mod x^r - 1), the coefficients are (+/-) nCi -- basically the nth row of pascals triangle w/out the leading/trailing 1's.
If these are # 0, then n is composite and we're done.
If they are == 0, then multiplying all those zero coefficients by various a^(n-i) won't make them non-zero.
So the only 'hole' is when we do the (mod (x^r - 1)) -- either the nCi or the a^(p-i) could be congruent to 0.
Wouldn't it be faster to select 2 suitable (q,r)'s and evaluate each term of nCi mod (x^r1 - 1, n) and nCi mod (x^r2 - 1, n) -- if either is non-zero then n is composite.

m = n-1; x = n; y = n
for i = 2 to n-1/2 {[list]x = x * m / i (mod r1) (mod n)
y = y * m-- / i (mod r2) (mod n)
if (x == 0) || (y == 0) then prime = false; break[/list:u]}

I'm not sure when to terminate the for loop: (n-1)/2, r2, or (r2 - 1)/2

-Bruce

[Maybeso]

ops: Ack! I can't do division on a value that's been 'mod'ed, can I? ops:

Hmm, so how do I do nCi mod r?

-Bruce

[Maybeso]

Ok,

I followed most of the links located on
http://www.utm.edu/research/primes/prove/prove4_3.html

and they helped clear some things up. So I wrote some code, and scribbled on napkins, and now I'll try to wrap my brain around it.

What Agrawal, Kayal and Saxena did was take the congruence:[list](x – a)^n = (x^n – a) mod n, or
(x – a)^n – (x^n – a) = 0 mod n[/list:u]
Which involves evaluating a polynomial with n terms each of size n; and simplify it by 'folding' those n terms down to r using (mod (x^r – 1)).

The key was proving that a suitable r of a certain minimum size always existed and would work.

However, this solution produces another problem: Normally, the n terms of the original vector all* have n as a factor when n is prime; and when n is composite, there are a few terms where n!/i!(n-i)! involves one of n's factors, which get cancelled out, and these terms are not divisable by n. The purpose of evaluating the congruence is to find these terms.
* (the first term is 1*x^n – 1*x^n = 0; the last term is a^n – a == 0 mod n.)

The danger is that all of these terms will get folded in with terms divisable by n and 'disappear'. So they had to make sure there were enough terms, and the terms were folded 'evenly'. They did this by selecting a large enough r with (r – 1) having a large enough prime factor.

But the 'folding' involves addition and subtraction, causing an interaction between the size of a^i and the sizes of n's factors (if they exist). To make sure this interaction doesn't mask the terms we are looking for, the congruence must be evaluated using a minimum number of different values for a.

I would still like to see a comparison between:[list]using one value for r and a large range for a.
using several values for r and a smaller range for a .[/list:u]
I took Silvermans advice and built a table of sophie-germain primes for selecting (q, r), and it looks like there are enough that we could select several. But I guess the overhead of resizing our convolution matrix may be too expensive for any reduction in the range for a.
(In fact, after reading how slow most of the first-try programs were, I toyed with the idea of a progam that asks you for n, finds q and r, writes out optimized convolution code for those parameters, then compiles and calls it.)

I hope I got most of this right, and I hope it helps some.

-Bruce

[Digital Concepts]

I wish I could help. :(

[agschrum]

In AKS, the focus is on

(x ? a)^n ? (x^n ? a) = 0 mod n

and the discussion is vague about over what values of "a" this must be true. But isn't it sufficient to pick any "a", any "x", calculate the value and see if the answer is not 0 and say it is composite?

[agschrum]

I just noticed that my post preview and the actual post don't look the same. The minus signs became question marks. Oh well, let me try again.

I guess what threw me with the AKS statement:

(x - a)^n = (x^n - a) mod n

was the use of "x" and "a" in the statement. Normally, I would think that if "n" is prime, then the statement above would be true always. The conditions under which values of "a" and "x" to use to verify the primality of "n" is the part I'm still fuzzy on. I would like to understand that better if someone could explain that part. It is the "for" loop in the algorithm that I have trouble with: given "a" ranging from 1 to "2*sqrt(r)*log(n)", how do you compute line 12 without knowing "x" ?

In any case, the second point was that if the above equation failed for any selected "x" or "a", would that not say that "n" was composite? The obvious issue might be finding the "x" and "a" to choose, no?

Any insight anyone has would be helpful.

Thanks,

-Allan

I hope you get an answer, .... no one seems to be able to comment. :D

[Maybeso]

Allen,

You are exactly right, if n is prime then
(x - a)^n = (x^n - a) (mod n) or (x - a)^n - (x^n - a) = 0 (mod n) is true for all (x, a).
I think the key to understanding AKS is why the above is true when n is prime.

The short answer is that we want to consider f(x) = (x - a)^n as a function, so we ignore x and look at the coefficents of the n terms. Example, n = 7, a = 1:
(x - a)^n - (x^n - a) = -7x^6 + 21x^5 - 35x^4 + 35x^3 - 21x^2 + 7x
= [-7, 21, -35, 35, -21, 7]
= 7[-1, 3, -5, 5, -3, 1] == 0 (mod 7). Therefore 7 is prime.

Here is the key: If n is not prime, it has a prime factor q. Then the qth term will be (n/q)K instead of (n)K, and we not only know that n is composite, we have all its factors. (the qth and (n/q)th term for each factor q)

Without AKS, we could leave a = 1, and we would be done. However, our little example took approx. n*n operations involving n terms. To reduce the number of operations, AKS reduces the number of terms by evaluating (x - a)^n mod (x^r - 1). This just means you wrap terms beyond the rth term back around using a convolution matrix*.

The problem is, this process adds the intermediate value of one term with that of another at each step, once you exceed r terms. So at the end we don't have n nice clean terms divisible (or not) by n; we have r terms that may all be divisible by n whether n is prime or not. What AKS proved was that if we use a large enough r, where r - 1 has a large enough factor, and we check a = 1 to "2*sqrt(r)*log(n)", at least one term will not be divisible by n.

*I'll go thru a simple convolution matrix and how to evaluate 'a' next.

I hope this has helped,

Bruce

[agschrum]

Hi Bruce,

Thanks for the information. What I lost sight of when checking the equation:
[code:1](x-a)^n mod (x^r - 1)[/code:1]
was that we are only looking at the coefficients and we do not care about what specific value of "x" is used. I am still interested in your example of a convolution matrix. That concept is still a bit sketchy for me.

Regards,

-Allan-

[Maybeso]

Hi Allen,

I'm glad my post was of some use, because after I sent it, I realised it was just a bit more than a cleaner rephrasing of my 3rd post here. (sigh)

The idea of taking one polynomial mod another was very strange to me too. Now if I want to take 19537 mod 19, I just divide by 19 and keep the remainder; but how do I divide one polynomial into another? And what is the remainder, a number, or another polynomial?

So I checked the polynomial section of my College Algebra text and there's a chapter on how to factor polynomials. (I'm not saying how many books I looked in first, or how long it took me to make sense of any of it!)
The short answer is P(x) / D(x) = Q(x) + R(x), and R(x) is a polynomial with fewer terms!

In our case, let's start with (x - a)^4, r = 5, and multiply by (x - a):[code:1](x - a) = [1, -a],
(x - a)^4 = [1, -4a, 6a^2, -4a^3, a^4] (lets skip the a^i, but keep +/-)
(x^r - 1) = (x^5 - 1) = [1, 0, 0, 0, 0, -1]

[1, -4, 6, -4, 1] [1, -a] = [1, -5, 10, -10, 5, -1], now divide by (x^5 - 1)

__[1]_______________________
(x^5 - 1) ) [1, -5, 10, -10, 5, -1]
__[1, 0, 0, 0, 0, -1]__
[-5, 10, -10, 5, 0]

so [1, -5, 10, -10, 5, -1] = [1, 0, 0, 0, 0, -1] [ 1] + [-5, 10, -10, 5, 0]

or [A, B, C, D, E, F] mod [1, 0, 0, 0, 0, -1]
= [B, C, D, E, F+A]

[/code:1]Of course, we want it to be fast, so let's combine the two steps:

[A, B, C, D, E] [1, -a] = [B-Aa, C-Ba, D-Ca, E-Da, A-Ea]

This same method can be extended to squaring a polynomial:[code:1]

[A, B, C, D, E] [ A, B, C, D, E] | now mod (x^5 - 1) =
= [AE, BE, CE, DE, EE] | [AE, BE, CE, DE, EE]
+ [AD, BD, CD, DD, DE] | + [BD, CD, DD, DE, AD]
+ [AC, BC, CC, CD, CE] | + [CC, CD, CE, AC, BC]
+ [AB, BB, BC, BD, BE] | + [BD, BE, AB, BB, BC]
[AA, AB, AC, AD, AE] | + [AE, AA, AB, AC, AD]

= [CC+2(AE+BD), AA+2(BE+CD), DD+2(AB+CE), BB+2(AC+DE), EE+2(AD+BC)]

[/code:1]
As you can see there is a pattern, and you can take advantage of it to optimize your code. The reason I bring up squaring is: you don't want to multiply [1, -a] by itself n times. Use the powering algorithm (or left-to-right binary exponentiation -- ;) impressive, huh?) but apply it to polynomials.
For a really good explanation of the powering algorithm, see Trial Factoring

Also, you will take each term (mod n) as you go; then at the end subtract (x^n - a) and check if all the terms are 0. This means if n has 1,000 digits, then so will each term of your polynomial for most of your calculations!

AKS is not a fast method, or a memory-efficient method. It is special because it works on any n. In other words, if you can represent n as an equation of some form (like n = k*2^p - 2^k +/- 1), then there is probably a better way than AKS to determine if n is prime. What you could do is use a different method to prove the above n is not prime, then keep adding 2 until AKS determines it is prime.

This should get you started, but let me know if I muddied up my explanation. Also, let me know if you write a workable AKS program.

Regards,

Bruce

"AKS is not a fast method, or a memory-efficient method. It is special >because it works on any n. In other words, if you can represent n as an >equation of some form (like n = k*2^p - 2^k +/- 1), then there is >probably a better way than AKS to determine if n is prime. What you >could do is use a different method to prove the above n is not prime, >then keep adding 2 until AKS determines it is prime"


Do you mean an anti-divisor type of formula?