## Prime Numbers

Primality: Given an integer n≥1, is n prime?

Note, knowing a number to be composite (not prime) does not easily
give the factors of n; factorization is a different problem.

A positive integer, n, has 1+⌊log_{b} n⌋ digits
in base b notation, e.g., b=2, one→"1", two→"10",
three→"11", four→"100", ..., seven→"111",
eight→"1000", etc..
We are often interested in integers that are *much* bigger than
can be held in a 32- or 64-bit word.

Until 2002 it was not known if primality was in P. Then Agrawal, Kayal and
Saxena (2002, 2004) gave a polynomial-time algorithm, but at
O((log n)^{12+ε}n)-time, it is not the method of choice.
(Later O((log n)^{6}.log^{2}n)-time,
Lenstra and Pomerance (2009).)

#### Miller, Rabin

Rabin (1976, 1980) gave a *probabilistic algorithm*
to test for primality.
It terminates with one of two conclusions: either
(i) n is (definitely) composite, or
(ii) n is *probably* prime
with probability ≥ 1-4^{-k}.
The uncertainty in the latter case can be made arbitrarily small
by increasing the number of *trials*, k, and
can *easily* be made even smaller than the probability of the computer
executing the algorithm having a hardware fault.

If the number of trials, k, is small, e.g., 1 or 2, results are quite likely to differ from run to run; for serious use k would be much large than 2. You can make 'lo' quite large (but increase it gradually).

A simple implementation of Rabin's algorithm runs in
O(k (log n)^{3})-time.
The complexity can be reduced to
O(k (log n)^{2} log^{2}n log^{3}n)-time
by incorporating, say, the Schonhage-Strassen algorithm for
the fast multiplication
of long integers.

- For a
*prime*, p,**Z**_{p}is a field and - if x
^{2}= 1 mod p then - x
^{2}- 1 = (x+1)(x-1) = 0 mod p - ⇒ x = 1, or x = -1 = (p-1), mod p
- that is, the only square roots of 1 are ±1.
So, finding a non-trivial square root of 1
in
**Z**_{n}would show n to be composite.

*If*n is an odd prime, let n-1 = d.2^{s}where d is odd and s≥1.- Then ∀ w ∈ {1, ..., n-1},
if n is prime,

∀ w≥1, w^{n-1}= 1 mod n

-- Fermat's "little" theorem - w
^{n-1}= w^{d.2s}= (w^{d})^{2s}= 1, so either - w
^{d}= 1 mod n, or - w
^{d.2r}= -1 mod n, for some r ∈ {0, ..., s-1}.

- So,
*if*∃ w ∈ {2, ..., n-2} such that - w
^{d}≠ 1 mod n, and - w
^{d.2r}≠ -1 mod n, ∀ r = 0, ..., s-1, - then w is a
*witness*to n being composite.

- Rabin's algorithm is to repeatedly choose a possible
*witness*, w, at*random*from {2, ..., n-2}. It has been shown that, if n is composite, at least 3/4 of the possible choices are witnesses to the fact. - Miller (1976) gave a deterministic algorithm for primality
but it depends on the generalized Riemann
*hypothesis*(GRH). Rabin's probabilistic algorithm does not depend on the GRH.

- Rabin's algorithm raised interesting practical and philosophical
questions about the nature of algorithms.
Strictly, it is
*not*an algorithm for primality. Rather, it is a*probabilistic*algorithm because it might make a "mistake" -- by declaring a composite to be prime (strictly it declares a number to be "probably prime"). - For
^{ }a given composite n, and a given w ∈ {2, ..., n-2}, whether w is or is not a witness to n's compositeness is a fact, which certainly does not vary randomly with time, say, nor with anything else. So if the algorithm uses a*pseudo*random number generator of candidate witnesses, the values of n for which it makes a "mistake", due to repeatedly generating non-witnesses, are fixed (for a given "seed" and a given number of trials). So in what sense are its errors probabilistic? (Of course "real" random number generators, based on physical processes, do also exist.) - It
^{ }is also interesting to note that by making the number of trials big enough, the probability of the algorithm making an error can easily be made (much) less than the probability of a hardware error.

### References

- [AKS02] M. Agrawal, N. Kayal & N. Saxena, 'Primes is in P', Dept. Comp. Sci. & Eng., Indian Inst. of Tech., Kanpur, August 2002,
- and Annals of Maths, 160(2), pp.781-793, doi:10.4007/annals.2004.160.781, September 2004.
- [LP09] H. W. Lenstra & C. Pomerance, 'Primality testing with Gaussian periods', Dartmouth, [www], 2009,
- and FSTTCS, LNCS vol.2556, doi:10.1007/3-540-36206-1_1, 2002.
- [Mil75] G. L. Miller, 'Riemann's hypothesis and tests for primality', STOC '75, pp.234-239, doi:10.1145/800116.803773, May 1975,
- and JCSS, 13, pp.300-317, 1976,
- [Rab76] M. O. Rabin, 'Probabilistic algorithms', pp.21-39, Algorithms and Complexity, ed. J. F. Traub, Academic Press, 1976.
- [Rab80] M. O. Rabin, 'Probabilistic algorithm for testing primality', J. of Number Theory, 12(1), pp.128-138, doi:10.1016/0022-314X(80)90084-0, February 1980.