Fermat-Test

Mit Hilfe des Fermat-Tests kann mit einer gewissen Wahrscheinlichkeit ausgesagt werden, ob eine gegebene Zahl eine Primzahl ist.
Der fermatsche Primzahlttest beruht auf dem kleinen Satz von Fermat.
Für jede Primzahl $p$ und jede dazu teilerfremde natürliche Zahl $a$ ist folgende Kongruenz erfüllt:

$a^{p-1} \equiv 1 \ mod \ p$

Beispiel:
Man nehme eine zu $p$ teilerfremde natürliche Zahl, zum Beispiel 2, und bilde $2^{p-1} \ mod \ p$ .
Kommt etwas anderes als 1 heraus, so kann $p$ keine Primzahl sein. Kommt 1 heraus, so ist $p$ ziemlich wahrscheinlich eine Primzahl.
Im ersten Fall spielt die Zahl 2 die Rolle eines Belastungszeugen (engl. witness) dafür, dass $p$ zusammengesetzt ist. Im zweiten Fall kann der Zeuge 2 die Zahl $p$ nicht belasten. Somit muss $p$ mangels Beweisen freigesprochen werden. Ob $p$ aber wirklich unschuldig (= Primzahl) ist, bleibt zumindest zweifelhaft.

Der Fermat-Test kann mit Hilfe von Python wie folgt implementiert werden:

def fermat(zeuge, testzahl):
    if zeuge ** (testzahl-1) % testzahl != 1:
        print("Keine Primzahl.")
    else:
        print("wahrscheinlich Primzahl.")

if __name__ == '__main__':
    '''Pseudoprimzahl bezgl. Fermat-Test'''
    testzahl = 561 
    zeuge = 2
    fermat(zeuge, testzahl)

Das obige Phython-Programm liefert als Ergebnis für die Testzahl 561 mit Zuhilfenahme der 2 als Zeuge „wahrscheinlich Primzahl“. Die Testzahl 561 ist allerdings keine Primzahl. Sie lässt sich in die Primfaktoren 17, 11 und 3 ( $3 \cdot 11 \cdot 17 = 561$ ) zerlegen. Hierbei handelt es sich um eine sogenannte Pseudoprimzahl zur Basis 2 bezüglich des Fermat-Tests (genauer gesagt ist die 561 die kleinste Carmichael-Zahl). In der Praxis spielt daher der Fermat-Test, wegen seiner nicht ausreichenden genauen Bestimmung von Primzahlen keine oder kaum eine Rolle.
Hier finden eher Primzahltests mit einer höheren Trefferwahrscheinlichkeit Anwendung (wie z. B. der Miller-Rabin-Test).

IT-Sicherheit

IT- und Systemsicherheit

Schreibe einen Kommentar Antworten abbrechen