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 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)
