The factoring problem seems very hard. But to test a number for having factors turns out to be much easier than to find them. It also helps if we supply the computer with a coin-flipping device. We now consider a Monte Carlo algorithm, i.e. one that with high probability rejects any composite number, but never a prime. See: [Rabin 1980], [Miller 1976], [Solovay, Strassen 1977].
denotes the residue of x when divided by p, i.e. 
, 
. 
means 
. Residues
can be added, multiplied and subtracted with the result put back in the range
(by adding an appropriate multiple of p). E.g., -x means
for residues 
. We use 
to mean either x or -x. If
r and p have no common divisors >1 (are mutually prime), division 
is possible, since 
is one-to-one on 
.
Operations 
obey all usual arithmetical laws. 
is the
greatest (and divisible by any other) common divisor of x and y. It can be
found by Euclid's Algorithm: 
; 
,
for y>0. By induction, 
, where integers 
and 
are produced as a byproduct of Euclid's Algorithm.
We will need to compute 
in polynomial time. We cannot multiply
x q times, since it takes 
steps. Instead we compute all numbers
. Then we represent q in
binary, i.e. as a sum of powers of 2 and multiply 
the needed
's.
and prime p says: 
.
Lemma: For each y and prime p, the equation 
has at
most one pair of solutions 
.
Proof: Let 
be two solutions: 
.
Then 
. We have a product of two
integers which is congruent to 0, i.e. divisible by p. Therefore p must
divide at least one of the factors. (Otherwise p is composite, and 
actually gives us its factor). So, either 
or 
i.e. 
. End of proof.
In particular 
implies 
. Note that this
does NOT hold if p is composite, since its factors can be spread between
and 
. Then y could have more than one 
pair of roots.
which
uses given x to prove p is composite. Let 
, with odd q.
T sets 
, 
, 
. If 
, or one of 
is -1, T gives up. If 
, Fermat Test rejects p. Otherwise there is 
, such
that 
. Then the Square Root Test factors p.
First, for each odd composite p, we show that T succeeds with some
x, mutually prime with p. If 
, then 
is good for
, since 
. So the Fermat
Test works. Otherwise 
. Take the greatest 
such that 
, for some x mutually prime with p. Such i exists,
since 
for odd q. If i<k then 
.
Take 
. Check: 
,
while 
. Thus, either 
or 
is not 
.
Now, 
succeeds on step
i with most y: function 
is 1-1 and T cannot fail with both y and
. This test can be repeated
for many randomly chosen x. Each time T fails, we are
twice more sure that p is prime. The probability of 300
failures on a composite p is <2-300, its
inverse exceeds the number of atoms in the known Universe.