2.3.1 Prime Tester

For testing if given (very large) numbers are prime the Sieve of Eratosthenes is far too slow.

The Miller-Rabin agorithm is a yes-biased Monte Carlo algorithm for non-primes, i.e. it always detects composite numbers. Its fault rate on primes is at most 1/4.

Miller-Rabin Primality test for odd n:

1.	determine m in n-1 = 2lm (m odd)
2.	randomly chose a x with 1 <= x < n
3.	x0 = xm mod n
4.	if x0 = 1 or x0 = n-1
5.	then write("n is prime"); goto END
6.	end
7.	for i = 1 to l-1 do
8.		xi = xi-12 mod n
9.		if xi = n-1
10.		then write("n is prime"); goto END
11.		else if xi = 1
12.			then write("n is composite"); goto END
13.			end
14.		end
15.	end
16.	write("n is composite")
17.	END

The Java built-in method isProbablePrime() from the Class java.math.BigInteger has the following description:

public boolean isProbablePrime(int certainty)
Returns true if this BigInteger is probably prime, false if it's definitely composite. The certainty parameter is a measure of the uncertainty that the caller is willing to tolerate: the method returns true if the probability that this number is is prime exceeds 1 - 1/2**certainty. The execution time is proportional to the value of the certainty parameter.

start applet in new window

2.3.2 Generating large Primes