Primzahlentest von Pratt

2.3.5. Pratt Primzahlentest

Der Primzahlentest von Pratt ist dem von Lucas sehr �hnlich. Beide basieren auf dem selben Satz:

Eine Zahl p>1 ist prim, genau dann wenn: Es gibt eine Zahl r mit 1<r<p, so da� gilt
1) r^p-1 mod p = 1
2) f�r alle Primfaktoren q von p-1 gilt: r^(p-1)/q mod p � 1.

Ein Zeuge f�r die Primalit�t von p sieht also folgenderma�en aus: Z(p) = (r; q₁; q₂; ...; q_n).

Um zu testen, ob alle q_i tats�chlich Primzahlen sind, wendet man die Konstruktion rekursiv an.

Z(2) = (1)

Z(p) = (r), falls p-1 prim ist

Z(p) = (r; q₁, Z(q₁); q₂, Z(q₂); ...; q_n, Z(q_n)), sonst.

Man erh�lt also eine Sequenz (r, q₁, Z(q₁₁, Z(q₁₁),...), ..., q_n, Z(q_n1, Z(q_n1), ...). F�r diese werden dann jeweils die Bedingungen des obigen Satzes getestet.

Der Pratt Algorithmus r�t diese Sequenz nichtdeterministisch.

Beispiel:

F�r p=31 r�t der Algorithmus: Z(31) = (3; 2, (1), 3, (2; 2, (1)), 5, (2; 2, (1), 2, (1))

oder etwas �bersichtlicher:

r=3
q₁=2	Z(q₁)=1
q₂=3	r₂=2
	q₂₁=2	Z(q₂₁)=1
q3=5	r₃=2
	q₃₁=2	Z(q₃₁)=1
	q₃₂=2	Z(q₃₂)=1

Dann verifiziert man:

3^31-1 = 1 mod 31	2^3-1 = 1 mod 3	2^5-1 = 1 mod 5
3^30/2 # 1 mod 31	2^2/2 # 1 mod 3	2^4/2 # 1 mod 5
3^30/3 # 1 mod 31
3^30/5 # 1 mod 31

Applet Pratt-Test:

Quellcode:
Pratt.java � Appletoberfl�che und �steuerung
Prime.java � Primzahlenfunktionen

2.4.1 AKS Primzahltest