Miller-Rabin-Primzahltest

Eine Verfeinerung des Fermat-Test.

Im Fermat-Test haben wir die Eigenschaften einer Primzahl bzgl des Kleinen Satz von Fermat verwendet um Primzahlen und Pseudoprimzahlen zu bestimmen. Leider gibt es Carmichael-Zahlen, die den Test immer bestehen, man kann diese also nie als zusemmengesetzte Zahlen ausschließen.

Der Miller-Rabin Test verwendet eine weitere Eigenschaft von Primzahlen. Für eine Primzahl pp und eine Zahl aa mit

a2≡1 mod pa^2\equiv 1\bmod p

und

a≢1 mod pa\not\equiv 1\bmod p

gilt

a≡−1 mod p.a\equiv-1\bmod p.

Wir verwenden diese Eigenschaft um folgendes Lemma zu zeigen.

Sei pp eine ungerade Primzahl. Wir zerlegen p−1p-1 in p−1=2lqp-1=2^lq, wobei qq ungerade ist,

ggT(a,p)=1ggT(a,p)=1

und

b=aq mod p.b=a^q\bmod p.

Dann gilt für bb, entweder

b≡1 mod pb\equiv 1\bmod p

oder es gibt ein i≤l−1i\leq l-1 mit

b2i≡−1 mod p.b^{2^i}\equiv -1\bmod p.

Wir sehen, dass zusammengesetzte Zahlen, Pseudoprimzahlen und sogar Carmichael-Zahlen dieses Lemma nicht erfüllen.

Wir verwenden diese Überlegung als Miller-Rabin Test zur Basis aa.

code ...

Leider gibt es auch hier analog zu den Fermat-Pseudoprimzahlen sogenannte Miller-Rabin-Pseudoprimzahlen, die den Test bestehen, obwohl sie keine Primzahlen sind.

Der Miller-Rabin Test wird immer zur Basis a=n−1a=n-1 bestanden. Es macht also Sinn nur für a∈{2,…,n−2}a\in\{2,\dots,n-2\} zu testen.

Außerdem gilt

#E(n)=#{a∈{2,3,…,n−1}:n besteht zur Basis a}<14φ(n)<14n\#E(n)=\#\{a \in\{2,3, \ldots, n-1\}: n \text { besteht zur Basis } a\}<\frac{1}{4} \varphi(n)<\frac{1}{4} n

Die Wahrscheinlichkeit, dass eine ungerade natrüliche Zahl eine Primzahl ist, nach rr bestandenen Miller-Rabin-Tests ist

≥1−(14)r.\geq1-\left(\frac{1}{4}\right)^r.

Wir sprechen auch hier immer noch nur von wahrscheinlichen Primzahlen.