Talk:AKS primality test

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)

links

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

(Updated: http://www.cse.iitk.ac.in/users/manindra/primality.pdf )

(from Manindra Agrawal's home page, http://www.cse.iitk.ac.in/users/manindra/ )

(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 x^r - 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)

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)

Finding r

In the section "algorithm" it's said: Find the smallest r such that o_r(n) > log²(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 o_r(n) > log²(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 log²(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 (talk • contribs) 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 (talk • contribs) 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)