Dietrich-Bonhoeffer-Gymnasium Wiehl Deutschland


Inhalt
Vorstellung des Kurses
Was sind Primzahlen?
Finden und nachweisen
Perfekte Zahlen
Mersennesche Primzahlen
Primzahlrekorde
Geschichte der Primzahlen
Weitere Links

Verfahren zur Primzahluntersuchung

Diese Seite listet die wichtigsten Methoden zur Primzahlsuche und viele verschiedene Arten von Beweisen auf, die zur schnellen Primzahlbestimmung benutzt werden.


Prüfverfahren für kleine Primzahlen

Die drei folgenden Verfahren sind f¸r kleinen Primzahlprüfungen zwar noch ausreichend schnell, doch die Zeit, die ein Computer f¸r die Prüfung ben–tigt, steigt proportional zu der Anzahl der Stellen der Primzahlen an.

    Sieb des Eratostenes (240 v.Chr.):
    Eine Liste aller Zahlen wird angelegt, in der alle Vielfachen der Primzahlen nacheinander ausgestrichen werden.

    Normale Division:
    Normale Teilung von n durch die Primzahlen bis zur Wurzel aus n.

    Wheel factorization:
    Beim der wheel factorization wird eine Liste angelegt, aus der zuerst alle Zahlen, die sich durch 2, 3 und 5 teilen lassen, herausgestrichen werden. Dann werden die verbleibenden Zahlen durch die kleiste, nicht ausgestrichene Zahl, in diesem Fall die 7, geteilt und so wird das bis zur Wurzel aus n weitergeführt. Läşt sich n dann immer noch nicht teilen, ist es eine Primzahl.

Grundlegende Sätze zur schnellen Primzahlbestimmung

    Fermat's kleiner Satz:
    p ist eine Primzahl; a ist eine beliebige Ganzzahl.
    Dann ist a p = a (mod p).
    In vielen F”llen, wenn p kein Teiler von a ist,
    dann ergibt a p-1 = 1 (mod p).

    Mit Fermat's kleinem Satz kann man sehr schnell beweisen, daş eine bestimmte Zahl keine Primzahl ist (wenn die Bedingung nicht zutrifft). Zu beweisen, daş eine Zahl eine Primzahl ist, wenn sie die Prüfung besteht, ist nicht m–glich, da dieser Satz noch nicht in seiner Umkehrung bewiesen werden konnte.

    Probable-Primality (Mögliche Primzahlen):
    Die zu überprüfende Primzahl n > 1; eine beliebige Ganzzahl a > 1.
    Wenn a n-1 (mod n) = 1 (mod n), dann ist n eine mögliche Primzahl.

    Dieser schnell auszurechnende Satz ist von Fermat's kleinem Satz ¸bernommen und l”şt sich auch genauso schnell berechnen. Der einzige Nachteil liegt darin, daß auch hier nur bewiesen werden kann, daß eine Zahl keine Primzahl ist.

    Beispiele:

    5 24 mod 5 = 1 34 mod 5 = 1 44 mod 5 = 1
    7 26 mod 7 = 1 36 mod 7 = 1 46 mod 6 = 1
    9 28 mod 9 = 4 38 mod 9 = 0 48 mod 8 = 7
    11 210 mod 11 = 1 310 mod 11 = 1 410 mod 11 = 1
    15 214 mod 15 = 4 314 mod 15 = 9 414 mod 15 = 1
    Falsche Annahme
    21 220 mod 21 = 4 320 mod 21 = 9 420 mod 21 = 16



Klassische Tests und Ableitungen von den beiden oben genannten Sätzen

    Proth's Satz:
    n = h.2k+1, wobei 2k > h ist.
    Wenn es nun eine Ganzzahl a gibt, bei der a(n-1)/2 = -1 (mod n), dann ist n eine Primzahl.

    Pepin's Test:
    F(n) ist die n-te Fermatsche Zahl (F(n) = 2 2 n +1) mit n > 1.
    F(n) ist nur dann eine Primzahl, wenn 3 (F(n)-1)/2 = -1 (mod F(n)).

    Pocklington's Satz (1914):
    Angenommen, n-1 = q k R, wobei q eine Primzahl ist und kein Teiler von R ist.
    Gibt es nun eine Ganzzahl a, bei der

    a n-1 = 1 (mod n) und
    bei der der ggT von (a (n-1)/q-1) und n gleich 1 ist (teilerfremd),
    dann hat jeder Primfaktor q von n die Form q kR+1.

    Ein weiterer sehr bekannter Satz:
    Angenommen, n = h.q k+1, wobei q eine Primzahl ist und q k > h ist.
    Wenn es nun eine Ganzzahl a gibt, bei der

    a (n-1) = 1 (mod n) und
    der ggT von (a (n-1)/q-1) und n gleich 1 ist,
    dann ist n eine Primzahl.

    Lucas-Lehmer Test (1930):

    Der Lucas-Lehmer Test ist eine der schnellsten Primzahlpr¸fungen, die es heute gibt. Er wird für die Prüfung von Mersenne-Exponenten, das sind Primzahlen der Form 2 n-1 verwendet. Die rasante Geschwindigkeit dieses Tests wird dadurch unterstrichen, daß alle heutigen Primzahlrekorde dieser Form sind.

    Zuerst legt man eine Tabelle mit den Variablen schritt, u und u2-2 an.
    schritt = 0 und u = 4.
    Nun berechnet man u2-2 mod 2n-1. Dieses Ergebnis übertägt man in die n”chste Zeile, wobei schritt um 1 erh–ht wird. Diese Prozedur wird bis zum schritt (n-2) wiederholt.
    In diesem Beispiel ist n = 5. (25-1 = 31)

    schritt u u2-2 mod 2n-1
    0 4 14 mod 31 = 14
    1 14 194 mod 31 = 8
    2 8 62 mod 31 = 0
    3 0

    M(n) ist genau dann eine Primzahl, wenn im schritt(n-2) u = 0 (mod M(n)).

    Lucas-Lehmer-Test direkt testen


    Top



    © Daniel Schlicker @ DBG Wiehl, den 16.11.98