20020907, 01:16  #1  
Aug 2002
Portland, OR USA
2×137 Posts 
AKS  A polynomialtime algorithm for testing primality.
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): Quote:
Quote:
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^(ni) won't make them nonzero. So the only 'hole' is when we do the (mod (x^r  1))  either the nCi or the a^(pi) 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 nonzero then n is composite. Quote:
Bruce 

20020907, 01:29  #2 
Aug 2002
Portland, OR USA
2·137 Posts 
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 
20020909, 20:49  #3 
Aug 2002
Portland, OR USA
100010010_{2} Posts 
My monolog continues. . .
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!(ni)! 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 sophiegermain 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 firsttry 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 
20020910, 05:18  #4 
Aug 2002
66_{8} Posts 
I wish I could help. :(

20021116, 02:37  #5 
Nov 2002
3 Posts 
I'm not sure I understand...
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? 
20021118, 01:35  #6 
Nov 2002
3 Posts 
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 
20021118, 09:45  #7 
607 Posts 
I hope you get an answer, .... no one seems to be able to comment. :D

20021119, 21:01  #8 
Aug 2002
Portland, OR USA
2·137 Posts 
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 
20021120, 00:07  #9 
Nov 2002
3 Posts 
Hi Bruce,
Thanks for the information. What I lost sight of when checking the equation: [code:1](xa)^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 
20021120, 03:23  #10  
Aug 2002
Portland, OR USA
100010010_{2} Posts 
A simple convolution matrix.
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: Quote:
[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 lefttoright 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 memoryefficient 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 

20021120, 20:24  #11 
3×1,433 Posts 
"AKS is not a fast method, or a memoryefficient 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 antidivisor type of formula? 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
18th Test of primality and factorization of Lepore in 5 * log_25 (N) (New Year's algorithm)  Alberico Lepore  Alberico Lepore  2  20180101 21:31 
Yet another new factoring algorithm\primality test:Digital Coding ??  tServo  Miscellaneous Math  3  20140410 18:52 
Polynomial algorithm  diep  Factoring  7  20120929 12:09 
aks algorithm and polynomial  jocelynl  Math  1  20040211 05:20 
fastest general number primalityproving algorithm?  ixfd64  Math  3  20031217 17:06 