Miller-Rabin-Test

Der Miller-Rabin-Test ist eine Verschärfung des Fermat-Tests und dient ebenfalls der Bestimmung von Primzahlen ( $p$ ). Dieser hat allerdings im Vergleich zum Fermat-Test eine wesentlich höhere Trefferwahrscheinlichkeit in Bezug auf die Bestimmung von Primzahlen.
Beim Miller-Rabin-Test handelt es sich um einen probilistischen Primzahltest. Dies bedeutet, dass die Basis $n$ auf welcher die Exponentation durchgeführt wird zufällig innerhalb des Intervalls $]1, \ p-1] \in \mathbb{Z}$ gewählt wird. Anders als beim Fermat-Test werden beim Miller-Rabin-Test mehrere Basen $n$ als sogenannte Zeugen verwendet.

Eine Basis $n$ gilt als Belastungszeuge für $p$ , wenn $n^2 \ mod \ p=1$ ist, aber $n \neq 1$ und $n \neq p-1$ .
Die Begründung hierfür ist folgende:

Ist $p$ eine Primzahl, dann ist $\mathbb{Z}_p$ ein Körper. In einem mathematischen Körper hat jede quadratische Gleichung höchstens zwei unterschiedliche Lösungen. Nun hat aber in $\mathbb{Z}_p$ die quadratische Gleichung $n^2=1$ schon die beiden Lösungen $n=1$ und $n=-1=p-1$ . Da $p>2$ vorausgesetzt werden kann, sind diese auch verschieden. Gibt es nun noch eine weitere Lösung, dann kann $\mathbb{Z}_p$ kein Körper sein. Dann kann auch $p$ keine Primzahl sein.

Beispiel:
Vermutete Primzahl $p=37 \longrightarrow p-1=36=b_i$
Ausgehend vom Satz von Fermat: $n^{p-1} \ mod \ p=1$
$p-1$ wird solange durch zwei dividiert bis ein ungerader Wert $b_1 \in \mathbb{Z}$ entsteht:
36 : 2 = 18
18 : 2 = 9
Diese Werte $b_{1...i} \in \mathbb{Z}$ werden anschleißend in eine Tabelle eingetragen und die Berechnungen $n^{b_{1...i}} \ mod \ p$ durchgeführt. Die Basis $n$ für die Exponentation liegt im Intervall $]1, \ p-1]$ .

$n$	$n^9 \ mod \ 37$	$n^{18} \ mod \ 37$	$n^{36} \ mod \ 37$
5	6	36	1
12	1	1	1
15	31	36	1

Aus den 1-sen in der letzten Spalte kann nun geschlossen werden, dass es sich bei $p=37$ mit hoher Wahrscheinlichkeit um eine Primzahl handelt.

Mit Hilfe der Programmiersprache Python, kann der Miller-Rabin-Test wie folgt beschrieben werden:

from random import randint

def millerRabin(prim):
    tmp = prim - 1
    wPrim = True
    i = 0
    while i < 20:
        basis = randNumber(tmp)
        while tmp % 2 == 0:
            if basis**tmp % prim == 1:
                wPrim = True
                break
            else:
                wPrim = False
            tmp = tmp // 2
        if not wPrim:
            break
        i += 1
    if wPrim:
        print("wahrscheinlich Primzahl.")
    else:
        print("Keine Primzahl.")
        
    
def randNumber(wert):
    return randint(2, wert)

def isgerade(zahl):
    if zahl == 2:
        print("wahrscheinlich Primzahl.")
    elif zahl % 2 == 0 and zahl > 2:
        print("Keine Primzahl.")
    else:
        if millerRabin(zahl):
            print("wahrscheinlich Primzahl.")
        else:
            print("Keine Primzahl")

if __name__ == '__main__':
    prim = 561
    isgerade(prim)

Im obigen Programm wird, anders als beim Fermat-Test, die 561 (Pseudoprimzahl) als nicht Primzahl durch den Miller-Rabin-Test erkannt. Um ein besseres Laufzeitverhalten zu gewährleisten, kann die Anzahl der Schleifendurchläufe und die Anzahl der zu testenden Basen reduziert werden. Dies geht allerdings auf Kosten der Treffergenauigkeit. Man sollte demzufolge eine gute Balance zwischen Treffergenauigkeit und Laufzeitverhalten finden.

IT-Sicherheit

IT- und Systemsicherheit

Schreibe einen Kommentar Antworten abbrechen