Talk:AKS primality test

From Wikipedia, the free encyclopedia

[edit] 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)

[edit] 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/ )

[edit] (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)