2.3.4. Lucas Primzahlentest

Der Primzahlentest von Lucas basiert auf folgendem 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.

Für eine schnellere Berechnung ist der kleine Satz von Fermat nützlich:

Sei p eine beliebige Primzahl. Für alle 0<a<p gilt: a^p-1 mod p = 1.

d.h. wir können die Berechnung mit dem Ergebnis "p ist zusammengesetzt" abbrechen, wenn wir ein r gefunden haben, daß die Bedingung 1) nicht erfüllt.

Lucas Algorithmus:

for r=2 to p-1
    if r^p-1 mod p = 1 then
        Berechne alle Primfaktoren Q von p-1
        for (all q in Q) do
            if r^(p-1)/q mod p=1 then
                next r
            else
                next q
            end
        end
        write "p ist eine Primzahl"
        goto ENDE
    else
        write "p ist zusammengesetzt"
        goto ENDE
    end
end
ENDE:

Applet Lucastest:
Das Applet bestimmt zuerst alle r, für die Bedingung 1) zutrifft und stellt sie in der linken Auswahlliste dar. Anschließend können, durch Auswahl eines bestimmten r Werts, in der rechten Liste die Ergebnisse der Bedingung 2) für alle Primfaktoren q von p-1 und gewähltes r angezeigt werden.

Quellcode:
Lucas.java – Appletoberfläche und –steuerung
Prime.java – Primzahlenfunktionen

2.3.5 Pratt Primzahlentest