|
- Primality: Given an integer n ≥ 2, 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 + ⌈logb n⌉
digits in base b notation.
-
- 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.log2 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.
This 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.
- 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 log2n log3n)-time
by incorporating, say, the Schonhage-Strassen algorithm for
the fast multiplication of long integers.
L o n g Integers
The following FORM
search for primes in {lo, ..., hi},
using the given number of trials for each candidate prime:
You can make both 'lo' and 'hi' very large, but
do not make their difference, hi-lo, too large.
If 'trials' is small, e.g., 1 or 2,
results for given lo and hi may vary from run to run.
- For a prime, p, Zp is a field and
- if x2 = 1 mod p then
- x2 - 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 Zn would show n to be composite.
-
- If n is an odd prime,
let n-1 = d.2s where d is odd and s≥1.
- Then ∀ w ∈ {1, ..., n-1},
if n is prime,
∀ w≥1, wn-1 = 1 mod n
-- Fermat's "little" theorem
|
- wn-1
= wd.2s
= (wd)2s = 1,
so either
- wd = 1 mod n, or
- wd.2r = -1 mod n,
for some r ∈ {0, ..., s-1}.
-
- So, if ∃ w ∈ {2, ..., n-2} such that
- wd ≠ 1 mod n, and
- wd.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.
function witness( n, n_1, d, s, w )
{ var x = powerMod(w, d, n);
if( EQ(x, one) || EQ(x, n_1 ) ) return false;
for( var r = 0; r < s; r ++ )
{ x = mod(times(x, x), n);
if( EQ(x, one) ) return true;
if( EQ(x, n_1) ) return false;
}
return true;
}//witness(n,w)
function prime( n, trials )
{ if( LE(n, three) ) return true; // i.e. 2 or 3
var n_1 = sub(n, one), n_3 = sub(n, three);
var d = n_1, s = 0;
while( even(d) ) { d = half(d); s ++ ; }
for( var trial = 0; trial < trials; trial ++ )
{ var w = plus(random( n_3 ), two); // [2..n-2]
if( witness(n, n_1, d, s, w) )
return false; // certainly!
}//for
return true; // n is probably(!) prime
}//prime(n,trials)
- 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 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.
Sources
Search for [primality]
in the [bibliography].
Also search for [integer multiplication].
|
|