2.3.1 Primzahltester

Für den Test, ob gegebene (sehr große) Zahlen prim sind, ist das Sieb des Eratosthenes viel zu langsam.

Der Miller-Rabin-Algorithmus ist ein yes-biased Monte Carlo-Algorithmus für Nicht-Primzahlen, d.h. er erkennt zusammengesetzte Zahlen immer. Seine Fehlerquote bei Primzahlen liegt bei höchstens 1/4.

Miller-Rabin-Primalitätstest für ungerades n:

1.	berechne m in n-1 = 2lm (m ungerade)
2.	wähle zufällig ein x mit 1 <= x < n
3.	x0 = xm mod n
4.	if x0 = 1 or x0 = n-1
5.	then write("n ist eine Primzahl"); goto ENDE
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 ist eine Primzahl"); goto ENDE
11.		else if xi = 1
12.			then write("n ist zusammengesetzt"); goto ENDE
13.			end
14.		end
15.	end
16.	write("n ist zusammengesetzt")
17.	ENDE

Die Java-eigene Methode isProbablePrime() aus der Klasse java.math.BigInteger hat folgende Beschreibung:

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.

Applet in neuem Fenster starten



(Zum deterministischen Miller Algorithmus)

2.3.2 Große Primzahlen erzeugen