Talk:AKS primality test

WikiProject India (Rated C-class, Mid-importance)
C  This article has been rated as C-Class on the project's quality scale.
Mid  This article has been rated as Mid-importance on the project's importance scale.
WikiProject Mathematics (Rated Start-class, Mid-importance)
This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of Mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Mathematics rating:
 Start Class
 Mid Importance
Field: Number theory

formula cleanup

Added request for help cleaning up the mathematical formulae on Wikipedia talk:WikiProject Mathematics. Hv 13:41, 10 August 2005 (UTC)

variables need to be defined 68.6.112.70 03:48, 21 November 2005 (UTC)
Which variables? -- Jitse Niesen (talk) 11:05, 21 November 2005 (UTC)
x and a need to be defined 140.211.137.232 21:04, 4 March 2006 (UTC)

For the original paper: try http://www.cse.iitk.ac.in/users/manindra/primality_original.pdf

(mod n, x^r-1)??

I understand modular arithmetic but why are there two values in the modulo, n and x^r-1, I only know how to use modulo when there is only one value.

It means that things are equivalent if they differ by a multiple n, of xr - 1, or by a sum of two of these. You could do the same thing in the integers, but mod (10, 12) would be equivalent to mod (2), where 2 is the greatest common divisor. Integer polynomials don't work quite the same way. Septentrionalis 22:40, 4 April 2006 (UTC) (and we should put in a link to principal ideal domain.

Two questions, one name a fast algorithm for calculating these. Also, mod(10, 12) wouldn't be equivalent to mod (2), take an example, (2=0 mod 2) but the same isn't true for mod(10, 12).(Unless negative multiples are allowed, I guess they are)

Yes, negative multiples are allowed; they are in 0 = 2 (mod 2), which is true because 0 = 2 - 2. (For simple ideals, they're not necessary, if you are allowed both sides of the equation,) See Ideal (ring theory). Septentrionalis 04:22, 5 April 2006 (UTC)

Thank you, how would a computer calculate this?

This is getting a little off topic, I suggest you read a textbook on algorithmic number theory which should explain in enough detail how one would do that or most books on applied cryptography. JoshuaZ 20:45, 6 April 2006 (UTC)

ok, sry, just for me getting this right, (mod 9,11) would be same as (mod 1) because 5*9 - 4*11 = 1 , right? --Sur3 00:37, 7 August 2008 (MEZ) —Preceding unsigned comment added by 131.234.130.35 (talk)

Yes, in general for two integers, $\pmod{a_1,\ldots,a_n}$ is the same as $\pmod{\gcd(a_1,\ldots,a_n)}$ --Nick

Is

$(x - a)^{n} \equiv (x^{n} - a) \pmod{n, x^{r} - 1}$

equivalent to that for each x

$((x - a)^{n} \mod{(x^{r} - 1)}) \mod{n} = ((x^{n} - a) \mod{(x^{r} - 1)}) \mod{n}$

where the $(...)\mod{(x^{r} - 1)}$ is polynomial long division remainder

and $(...) \mod{n}$ is arithmetic division (mathematics) remainder?

Maksim-e (talk) 20:10, 13 May 2008 (UTC)

Both should be polynomial divisions. — Emil J. (formerly EJ) 10:14, 8 August 2008 (UTC)

confusion over "mod a, b" meaning

I can't see anywhere on Wikipedia that officially explains the (mod a, b) syntax. I would have intuited this as (mod lcm(a, b)), so I think it would be better to disambiguate this. If it actually means (mod gcd(a, b)), I think we should change it to say that.

On a side note, it's hard to tell from the article what "r" is supposed to be. Is it supposed to be "all r", "any r within a certain range", "a single specific r", etc? CountingPine (talk) 14:31, 12 November 2008 (UTC)

There is no explanation because it is obvious. Note that the authors of the original paper also do not bother to define it. I don't understand why are you trying to complicate matters by inserting there those lcm or gcd. The congruence
$x\equiv y\pmod a\,$
is defined as
$\exists u\,(x=y+ua),$
and the generalization to more moduli
$x\equiv y\pmod{a_1,\dots,a_k}\,$
is therefore naturally introduced as
$\exists u_1,\dots,u_k\,(x=y+u_1a_1+\dots+u_ka_k).$
How else could it be defined in a sensible way? Even more generally, one sometimes encounters
$x\equiv y\pmod I\,$
meaning
$x-y\in I,$
where I is an arbitrary ideal. — Emil J. 14:54, 12 November 2008 (UTC)
Maybe it is obvious... But I am coming to this page as someone who's not an expert in the subject matter, and as far as I can tell a sensible way would be to define it as a stronger statement, rather than a weaker one, i.e. in a rough equivalence to your syntax, I would naturally introduce it as
$\exists u_1,\dots,u_k\,(x=y+u_1a_1, x=y+u_2a_2,\dots,x=y+u_ka_k).$
I think this is equally "obvious". Having no other examples of the syntax, the only clue that it means the weaker form is that with the weaker stronger form the n expression would probably have been omitted, since it's given earlier, and it would be an understatement to call it a "related" equivalence.
Despite this, and despite what you've said, I don't think the meaning is obvious, and I can't find an official definition of it anywhere on WP. Perhaps this is an issue that should be addressed on the Modular arithmetic page though...
Anyway, I hope that we can find a reasonable solution to this, because it seems like a page that could be understandable by people without too much grounding in the subject, but it just seems a little too easy to get lost on this bit. CountingPine (talk) 10:47, 15 November 2008 (UTC)
Aha, now I can see where you got the lcm, you read "$x\equiv y\pmod{a,b}$" as a shorthand for "$x\equiv y\pmod a$ and $x\equiv y\pmod b$". Well, that would be a pointless notation as it would be indeed equivalent to the simple $x\equiv y\pmod{lcm(a,b)}$. But I can see now that it is potentially confusing. It can't hurt to define the notation in the article after all. — Emil J. 14:13, 17 November 2008 (UTC)
Thanks for changing that, and for bearing with me. Are the polynomials f and g in x? CountingPine (talk) 16:17, 17 November 2008 (UTC)
Yes, all the polynomials are in x. — Emil J. 17:04, 17 November 2008 (UTC)

Just for some clarity. $x\equiv y\pmod{a,b}$ is equivalent to $x\equiv y\pmod{\gcd (a,b)}$. For example $1\equiv 3\pmod{4,6}$, since $1=3+4\cdot (1)+6\cdot(-1)$ and we have $1\equiv 3\pmod 2$. This comes from the fact that we are doing modulo over the ideal generated by $a$ and $b$, which in a Principal ideal domain is the same ideal that the one generated by $\gcd(a,b)$. The $lcm$ is used to satisfy several congruences simultaneously, but that is another matter. 193.144.198.250 (talk) 12:51, 11 March 2014 (UTC)

Worked Example

Would it be possible for someone to provide a worked example, like has been done for the Miller–Rabin primality test? It'll be much appreciated. Thanks in advance. Gulliveig (talk) 15:17, 15 June 2009 (UTC)

The worked example provided for n=31 is the smallest prime to make it through to Step 5. Although the gain from (x+a)31 (mod x29-1) is only a reduction of the poly from a degree 31 to degree 28, n=31 does demonstrate the implementation of the full algorithm. Moreover while a bigger choice of n would show a more significant reduction of (x+a)n (mod xr-1), it would also make showing the expansion of (x+a)n a bit unwieldy.

Also my intent for an Example 2 was to find a n that is not prime which also gets past Step 3. Unfortunately n = 74,513 = 269*277, r = 263 is the first composite to get to Step 5, and wolframalpha.com will not currently run PolynomialMod[PolynomialRemainder[(x+a)74513, x263-1, x], 74513] for free... However if you choose to ignore the results of Step 3 for n=11*5=55, r=10 (Step 3: gcd(5,55)=5), then n=55,r=10 passes Step 4 (55>10) and you can see what it looks like for Step 5 to determine that n is composite.
Step 5: n=55, r=10
(x+a)55 (mod x10-1, 55) =
11a5+22a25+a55 +5a44x +10a33x2 +10a22x3 +5a11x4 +(22a30+11a50+1)x5

plugging in a={1, 2, 3, ..., max = $\scriptstyle\lfloor$log2 (55)$\scriptstyle\sqrt{\varphi(10)}\rfloor$ = 11} and modding by 55 results in the following polynomials:
34+5x+10x2+10x3+5x4+34x5
54+25x+25x2+40x3+10x4+23x5
1+20x+50x2+35x3+15x4+23x5
1+15x+35x2+50x3+20x4+34x5
45+45x+40x2+30x3+25x4+x5
54+45x+15x2+30x3+30x4+34x5
54+15x+20x2+50x3+35x4+23x5
21+20x+5x2+35x3+40x4+23x5
1+25x+30x2+40x3+45x4+34x5
10+5x+45x2+10x3+50x4+x5
44+34x5

none of which are mod 55 congruent to x5+a = x55+a (mod x10-1)
71.211.195.249 (talk) 01:17, 10 February 2014 (UTC)

Finding r

In the section "algorithm" it's said: Find the smallest r such that or(n) > log2(n). That condition is not sufficient, because with only that limitation also Charmichael numbers outputs prime. The correct condition on r is: Find the smallest r such that or(n) > log2(n) and n-1 is not divisible by r. Kaluppollo (talk) 13:28, 15 November 2009 (UTC)

I don't understand your reasoning with Carmichael numbers, but at any rate if r divides n − 1, then the multiplicative order of n modulo r is 1, which is not greater than log2(n), hence your extra condition is redundant. — Emil J. 13:20, 16 November 2009 (UTC)

New Algorithm Version error

It is stated in the article: "Again the AKS algorithm consists of two parts, and the first step is to find a suitable r; however, in the new version r is the smallest number such that or(n) > log2(n)." However, it seems to me that that is the same as what is listed in the original algorithm in Step 2. Perhaps I am incorrect, but if not that sentence needs to be changed at the very least because it implies that the step was updated when in fact it appears not to be. I propose that the sentence be reworded or deleted. —Preceding unsigned comment added by Jessemv (talkcontribs) 06:17, 20 November 2009 (UTC)

The algorithm incorrectly described as the "original algorithm" in the article is actually the new one. I think we should stick to that new version of the algorithm as it is the published version, but reduce the discussion of the preliminary version and its updates to a history section or something like that. — Emil J. 11:36, 20 November 2009 (UTC)
Done. — Emil J. 12:29, 20 November 2009 (UTC)
Better. Nice job EmilJ. However, I think the article should state the original algorithm somewhere, although you are correct in sticking with the new algorithm. Also, are you sure the Big-O notation is the "soft-O" symbol? The mathematics is a little too complicated for me to handle, but I would still like to make sure that the symbol is used correctly. The Big-O notation seems to differ between the algorithm versions. Jessemv (talk) 01:22, 23 November 2009 (UTC)
I see no reason to bother with an outdated preliminary version of an algorithm, and generally speaking, I don't understand why is it that this article seems to be pathologically obsessed with the old algorithm. This normally never happens in computer science or mathematics, people just refer to the final published version of a result in case of any differences. As for the big-O notation, all versions of the paper I've seen use O-tilde for the time bounds (and this is pretty much unavoidable, the extra polylog factors come from the time complexity of multiplication). Sometimes they write it as $\tilde O$ and sometimes as $O^\sim\,$, but that's only a typographic change. — Emil J. 13:00, 23 November 2009 (UTC)
Ok. Guess you're right about the algorithm. I just thought it would be a credit the original creators more to show what they thought up, but I now agree with you that the final version is more important. Thanks for the followup. Jessemv (talk) 22:41, 23 November 2009 (UTC)

Formula Update

The algorithm was updated and improved shortly after release, but is not shown here: http://teal.gmu.edu/courses/ECE746/project/F06_Project_resources/Salembier_Southerington_AKS.pdf

In addition, (x a)^n x^n a (mod n) was changed to (x a)^n x^n a (mod x^r 1, n) — Preceding unsigned comment added by Cable729 (talkcontribs) 20:36, 23 March 2011 (UTC)

History and running time

log^12(x) is log(log(...(x)...))

log(x)^12 is (log x)^12

Please synchronize formulas and textual description. Which is meant?--134.130.183.101 (talk) 08:35, 20 July 2011 (UTC)

log^12(x) can also mean (log x)^12. That's what's meant in this article. --Roentgenium111 (talk) 14:25, 6 October 2011 (UTC)

Must r be prime?

In the external link to Scott Aaranson's paper, it states "The way they speed things up is to work, not only mod N, but also mod a polynomial XR − 1 (where R is a reasonably small prime)." The restriction of r being prime is not in the Wikipedia article. Which is right? Gaohoyt (talk) 18:41, 17 August 2012 (UTC)

There’s no point in r being prime, and in the published paper, they allow composite r. However, in the first version of the paper, they used prime r, and Aaronson’s paper was presumably written before the update.—Emil J. 19:25, 17 August 2012 (UTC)

practicality

Could the article have some discussion about how fast it works in practice if known, and compare that with other methods? I mean, the article is saying for sufficiently big x: T < M(lnx)^6, but if it suffices for x more than 9!^9!^9!^9!, or if M is similarly large, it may not be practical (or still could be practical). -Richard Peterson198.189.194.129 (talk) 17:00, 19 September 2012 (UTC)

From the implementations I've done and seen, it's very slow in practice. A straightforward by-the-v6-paper AKS implementation is far too slow to be useful for basically any input size. There are lots of optimizations possible (see, for instance the paper of Crandall and Papadopoulos, as well as all the Bernstein variants), but I haven't heard of AKS being used over, say, APR-CL or ECPP. For numbers <= 2^64, use deterministic M-R (no more than 7 tests needed) or BPSW. Pocklington-Lehmer or its improvement BLS75 work pretty well for numbers <= ~ 2^128, are easy to write if you have half-decent factoring code, and are much faster than AKS for this input size. APR-CL (e.g. Pari 2.3+) and ECPP (e.g. PRIMO) are much faster.
This is all rather anecdotal and full of my opinions. One also has to make a distinction between the standard exponent 6+o(1) algorithm and the various exponent 4+o(1) variants (e.g. Bernstein). For a little more reliable evidence, Mathworld states "ECPP is the fastest known general-purpose primality testing algorithm." Bernstein's 2006 paper indicates that at that time he believed ECPP was faster than his exponent 4+o(1) algorithm, but it wasn't clear cut. The AKS article on The Primes Pages says similar things. DAJ NT (talk) 09:03, 28 December 2012 (UTC)

This 2010 presentation by R.P. Brent Uncertainty can be Better than Certainty: Some Algorithms for Primality Testing gives some timing results and estimates, and has in the conclusions, "The AKS algorithm is theoretically significant[...] AKS is not a practical algorithm. ECPP is much faster." His estimates based on Magma implementations show ECPP at ~16 million times faster at ~332-bits (100 digits), and about 1000 million times faster at 1024 bits. My personal experience gives even higher factors, as ECPP can run quite a bit faster.
Also of interest is the time to verify a certificate. n-1 certificates are extremely fast. ECPP certificates are very fast. Both are, in general, much faster to verify than produce. AKS (standard style) doesn't really have certificates -- to verify the results you have to reproduce the entire computation. While the argument goes that this is polynomial time, in practice this is milliseconds vs. years. DAJ NT (talk) 05:25, 27 May 2013 (UTC)

Numberphile video

The numberphile video about the AKS test is completely wrong. I realize the presenter says it is the AKS test, but it is not. It describes Hardy and Wright theorems 75 and 76, not the AKS test. At the 2:26, the presenter waves his hands and says, they actually did something a little different, then moves on. See Agrawal and Biswas "Primality and Identity Testing via Chinese Remaindering" (FOCS 1999, as paper in 2003), or read the actual AKS paper. They are describing Lemma 2.1 of the V6 paper. This is not AKS, it is not polynomial time, and it is not fast.

Please remove the link. DAJ NT (talk) 16:40, 1 March 2014 (UTC)

Having put it there, if others want it gone, I won't put it back a third time. The argument isn't really with me, it's with James Grime of Cambridge. user:JMOprof ©¿©¬ 16:56, 1 March 2014 (UTC)