GIven odd N>10 we wish to test for primality. 0. By trial division make sure N has no small prime factors. [If does, stop here.] 1. Generate a random x mod N. If GCD(x,N) is not 1 then you have factored N and are done. 2. Find its square s=x^2 mod N. 3A. Employ the Shanks-Tonelli (randomized) algorithm to find a square root y of s so that y^2 = s mod N. That algorithm is described here http://en.wikipedia.org/wiki/Tonelli–Shanks_algorithm This runs in O( (logN)^2 ) modular multiplications on average for random x mod N, but only O( logN ) multiplications if N-1 is not divisible by a very large power of 2. Also you can make sure the runtime is O(logN) multiplications (regardless of N) by using Cipolla's algorithm instead of Shanks-Tonelli, http://en.wikipedia.org/wiki/Cipolla's_algorithm All the randomness is is in step 2 of wikipedia's version of the ST algorithm (& a similar comment applies to Cipolla): you choose z randomly until finding z such that JacobiSymbol(z|N) = -1, which should succeed (N-1)/(2N) of the time if N is prime. (It also should succeed very nearly half the time if N is composite with no small prime factors.) Thus Wikipedia's step 2 is expected to run in 2 trials on average for either prime or composite N. 3B. I do not recommend this, but alternatively to 3A, one instead could employ the Schoof (deterministic, based on elliptic curves) algorithm to find such a squareroot y. That algorithm is described Rene J. Schoof: Elliptic curves over finite fields and the computation of square roots mod p, Maths. of Comput. 44,170 (1985) 483-494 pdf here: http://www.mat.uniroma2.it/~schoof/ctpts.pdf mucho errrata pdf here: http://www.mat.uniroma2.it/~schoof/schooferr.pdf and Schoof claims it runs in O( (logN)^9 ) bit operations using "slow arithmetic" for both numbers and polynomials as opposed to FFT-based "fast arithmetic" which would speed it up to O( (logN)^6.01 ) bit-ops. 4. Note, Shanks-Tonelli/Cipolla and Schoof both assume that N is prime in order to find the square root. If N is not prime, the "root" they find may be wrong, or at some point inside the algorithm we will do something illegal like divide by 0 or an assert may fail. Either way, "N is definitely composite" and stop. 5. If N is prime, there are exactly two square roots: x and N-x. If N is composite, then there must be at least 4 square roots, and since in step 1, x was random, there is no way for Shanks-Tonelli or Schoof to "know" that x was "the" root, as opposed to whatever root they were instead finding. My point is that they therefore must find a root y other than x and N-x, at least 50% of the time. If that happens then GCD(x-y, N) and/or GCD(x+y, N) will yield a nontrivial factor of N so "N is definitely composite" & stop. 6. If however y=x or y+x=N then we go back to step 1 for another test. 7. After K loop-iterations of steps 1-6, any composite N should have been detected with probability>=1-2^(-K). Therefore either N is prime, or we have been very unlucky in our choice of random numbers. --- This whole test is comparably efficient to a Miller-Rabin test (up to a constant factor) for random N. However, I think the constants are worse for this test than for Miller-Rabin. Does it have any advantages over Miller-Rabin? The only benefit I can see is that in the hard cases for this test, i.e. where the square-rootings succeed, it produces factors of N, which is kind of compensation for the fact that it is having a hard time on that N. This also tells us something that is rather remarkable which I have not seen before: REMARKABLE FACT: Pseudoprimes (i.e. hard cases for our probable-prime test) are easy to factor. One has to wonder what applications this may have... -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)