Kryptologie/Miller-Rabin-Test (Primzahltest 3)

Einleitung

Wie wir in der Lernaufgabe zum Fermat-Test feststellen können, ist die Zahl $561$ nach dem Fermat-Test wahrscheinlich nicht zusammengesetzt. Tatsächlich handelt es sich bei $561$ um eine Pseudoprimzahl, die mit dem Fermat-Test nicht gefunden werden kann. Wir werden gleich einen Primzahltest kennenlernen, mit dem man selbst solche Zahlen als zusammengesetzt identifizieren kann.

Definition Carmichael-Zahl

Fermat-Test, Primzahl, Teilerfremdheit, Kongruenz, Primfaktorzerlegung und Fermatsche Pseudoprimzahl
Fermat-Test
Sei $n \in ℕ$ ungerade. Ziel ist es zu ermitteln, ob $n$ zusammengesetzt ist. Wähle eine zu $n$ teilerfremde Basis $a$ Berechne $a^{n - 1} mod n$ Gilt $a^{n - 1} \equiv 1 mod n$ , dann ist $n$ mit hoher Wahrscheinlichkeit prim oder zusammengesetzt Gilt $a^{n - 1} \equiv̸ 1 mod n$ (Fall 2), dann ist $n$ nicht prim, sondern zusammengesetzt^[1]
Primzahl
Sei $p \in ℕ$ mit $p > 1$ , dann heißt $p$ Primzahl oder prime Zahl, wenn gilt: $p$ besitzt nur zwei Teiler in $ℕ$ , nämlich $1$ und $p$ . Andernfalls heißt $p$ zusammengesetzte Zahl^[2].
Teilerfremdheit
Zwei ganze Zahlen $a$ und $b$ , wobei mindestens einer der beiden Zahlen ungleich Null ist, heißen teilerfremd, wenn $g g T (a, b) = 1$ ^[3]. Betrachten wir mehr als zwei Zahlen, dann nennen wir diese paarweise teilerfremd, wenn je zwei beliebige von diesen Zahlen zueinander teilerfremd sind^[4]^[3].
Kongruenz
Seien $a, b \in ℤ$ und $m \in ℕ$ , dann gilt $a \equiv b mod m \Leftrightarrow m ∣ (a - b)$ ^[5].
Primfaktorzerlegung
Sei $n \in ℕ$ mit $n > 1$ , dann ist $n$ als Produkt von Primzahlen darstellbar und wir nennen diese Primfaktorzerlegung. Es gilt $n = p_{1} \cdot p_{2} \cdot \dots \cdot p_{i}$ mit $i \in ℕ$ . Die Darstellung ist, abgesehen von der Reihenfolge der Faktoren, eindeutig^[6].
Fermatsche Pseudoprimzahl
Eine natürliche Zahl n wird fermatsche Pseudoprimzahl zur Basis $a$ genannt, wenn sie eine zusammengesetzte Zahl ist, die die Kongruenz $a^{n - 1} \equiv 1 mod n$ für eine zu $n$ teilerfremde Basis $a$ erfüllt^[7]^[6].

Eine zusammengesetzte natürliche Zahl $n$ heißt Carmichael-Zahl, falls für alle zu $n$ teilerfremden Zahlen $a$ die folgende Kongruenz erfüllt ist:

$a^{n - 1} \equiv 1 mod n$ ^[8]^[6].

Beispiel Carmichael-Zahl

Betrachten wir die Zahl $561$ .

Es gilt nach der Primfaktorzerlegung

$561 = 3 \cdot 11 \cdot 17$ .

$3$ , $11$ und $17$ sind die einzigen zu $561$ teilerfremden Basen. Für jede andere ganze Zahl $a \in ℤ / {3, 11, 17}$ gilt

$a^{561 - 1} \equiv 1 mod 5 61$ ^[9].

Bedeutung von Carmichael-Zahlen für den Fermat-Test

Ebenso wie bei den fermatschen Pseudoprimzahlen, gibt es unendliche viele Carmichael-Zahlen^[10]. Die Carmichael-Zahlen verhindern, dass, durch mehrfaches Ausführen des Fermat-Tests mit wechselnden Basen, die Wahrscheinlichkeit, dass man versehentlich eine Pseudoprimzahl als prim bezeichnet, nicht beliebig gesenkt werden kann. Der Fermat-Test kann daher in der Praxis nicht empfohlen werden werden. Es wird stattdessen häufig der Miller-Rabin-Test verwendet^[11].

Miller-Rabin-Test

Im Gegensatz zu den zuvor behandelten Primzahltests, ist der Miller-Rabin-Test für die Praxis gut geeignet^[12]. Der Miller-Rabin-Test beruht auf einer Verschärfung des kleinen Satzes von Fermat und kann nach hinreichend vielen Versuchen für jede natürliche Zahl herausfinden, ob diese zusammengesetzt ist^[12].

Der Test umgeht also das Problem des kleinen Satzes von Fermat, indem eine Eigenschaft von Primzahlen betrachtet wird, die Carmichael-Zahlen und andere Pseudoprimzahlen nicht mit echten Primzahlen gemeinsam haben^[13].

Kleiner Satz von Fermat, Primzahl, Teilerfremdheit und Kongruenz
Kleiner 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$ ^[7]^[14].
Primzahl
Sei $p \in ℕ$ mit $p > 1$ , dann heißt $p$ Primzahl oder prime Zahl, wenn gilt: $p$ besitzt nur zwei Teiler in $ℕ$ , nämlich $1$ und $p$ . Andernfalls heißt $p$ zusammengesetzte Zahl^[2].
Teilerfremdheit
Zwei ganze Zahlen $a$ und $b$ , wobei mindestens einer der beiden Zahlen ungleich Null ist, heißen teilerfremd, wenn $g g T (a, b) = 1$ ^[3]. Betrachten wir mehr als zwei Zahlen, dann nennen wir diese paarweise teilerfremd, wenn je zwei beliebige von diesen Zahlen zueinander teilerfremd sind^[4]^[3].
Kongruenz
Seien $a, b \in ℤ$ und $m \in ℕ$ , dann gilt $a \equiv b mod m \Leftrightarrow m ∣ (a - b)$ ^[5].

Der Satz liefert uns die Bedingungen, die wir an

n

stellen müssen, wenn

n

prim sein soll. Es genügt, wenn eine der beiden Bedingungen aus dem Satz erfüllt wird. Gilt keine der beiden Bedingungen für eine Zahl

n

bei Wahl einer teilerfremden Zahl

a

, so ist

n

zusammengesetzt^[13].

Satz Eigenschaft von Primzahlen

Seien $n$ prim und $a \in ℤ$ teilerfremd zu $n$ , so gilt eine der Kongruenzen

$a^{g} \equiv 1 mod n$

oder es existiert ein $i \in {0, 1, \dots, h - 1}$ mit

$a^{2^{i} \cdot g} \equiv - 1 mod n$ , wobei

$g = (n - 1) / 2^{h}$ und $h = m a x {i \in ℕ ∣ 2^{i} teilt n - 1}$ ^[13].

Bemerkung: Der Beweis wird, aufgrund der Komplexität und dem geringen Ertrag für das Thema des Kurses, in diesem Kurs nicht behandelt.

Miller-Rabin-Test

Sei $n \in ℕ$ ungerade. Ziel ist es zu ermitteln, ob $n$ mit hoher Wahrscheinlichkeit prim oder zusammengesetzt ist.

Wähle zufällig und gleichverteilt ein $a \in {2, 3, \dots, n - 1}$
Bestimme ggT(a,n)
- Ist $g g T (a, n) > 1$ , dann ist $n$ zusammengesetzt und der Miller-Rabin-Test ist fertig
- Ist $g g T (a, n) = 1$ , dann mit Schritt 3 fortfahren
Berechne mit agmodn, wobei g=(n−1)/2h und h=max{i∈ℕ∣2i teilt n−1}
- Ist $a^{g} \equiv 1 mod n$ , dann ist $n$ wahrscheinlich prim und der Miller-Rabin-Test fertig
- Ist $a^{g} \equiv̸ 1 mod n$ , dann mit Schritt 4 fortfahren
Berechne a2i⋅gmodn, wobei i∈{0,1,…,h−1}
- Ist mindestens für ein $i \in {0, 1, \dots, h - 1}$ $a^{2^{i} \cdot g} \equiv - 1 mod n$ , dann ist $n$ wahrscheinlich prim und der Miller-Rabin-Test fertig
- Existiert kein $a^{2^{i} \cdot g} \equiv̸ - 1 mod n$ , dann ist $n$ zusammengesetzt und der Miller-Rabin-Test abgeschlossen^[15]^[16]

Bemerkung: Die Wahrscheinlichkeit, dass $n$ zusammengesetzt ist, obwohl der Miller-Rabin-Test "wahrscheinlich prim" ausgibt ist höchstens $\frac{1}{4}$ . Durch $x$ -faches Wiederholen des Miller-Rabin-Tests, lässt sich die Wahrscheinlichkeit, dass $n$ irrtümlich als prim bezeichnet wird auf $(\frac{1}{4})^{x}$ minimieren^[17].

Beispiel

Carmichael-Zahl, Satz Eigenschaft von Primzahlen, Primzahl, Teilerfremdheit und Kongruenz
Carmichael-Zahl
Eine zusammengesetzte natürliche Zahl $n$ heißt Carmichael-Zahl, falls für alle zu $n$ teilerfremden Zahlen $a$ die folgende Kongruenz erfüllt ist: $a^{n - 1} \equiv 1 mod n$ ^[8]^[18].
Satz Eigenschaft von Primzahlen
Seien $n$ prim und $a \in ℤ$ teilerfremd zu $n$ , so gilt eine der Kongruenzen $a^{g} \equiv 1 mod n$ oder es existiert ein $i \in {0, 1, \dots, h - 1}$ mit $a^{2^{i} \cdot g} \equiv - 1 mod n$ , wobei $g = (n - 1) / 2^{h}$ und $h = m a x {i \in ℕ : 2^{i} teilt n - 1}$ ^[13].
Primzahl
Sei $p \in ℕ$ mit $p > 1$ , dann heißt $p$ Primzahl oder prime Zahl, wenn gilt: $p$ besitzt nur zwei Teiler in $ℕ$ , nämlich $1$ und $p$ . Andernfalls heißt $p$ zusammengesetzte Zahl^[2].
Teilerfremdheit
Zwei ganze Zahlen $a$ und $b$ , wobei mindestens einer der beiden Zahlen ungleich Null ist, heißen teilerfremd, wenn $g g T (a, b) = 1$ ^[3]. Betrachten wir mehr als zwei Zahlen, dann nennen wir diese paarweise teilerfremd, wenn je zwei beliebige von diesen Zahlen zueinander teilerfremd sind^[4]^[3].
Kongruenz
Seien $a, b \in ℤ$ und $m \in ℕ$ , dann gilt $a \equiv b mod m \Leftrightarrow m ∣ (a - b)$ ^[5].

Betrachten wir das Beispiel $n = 561$ zu den Carmichael-Zahlen. Mit Hilfe des Satzes Eigenschaft von Primzahlen können wir die Carmichael-Zahl nun erneut darauf prüfen, ob sie zusammengesetzt oder prim ist.

Wir wählen $n = 561$ und $a = 2$ .

Nun muss $h = m a x {i \in ℕ ∣ 2^{i} teilt n - 1}$ bestimmt werden.

Es gilt für $h = m a x {i \in ℕ ∣ 2^{i} teilt 560}$ :

$2^{1} ∣ 560$ ,

$2^{2} ∣ 560$ ,

$2^{3} ∣ 560$ ,

$2^{4} ∣ 560$ ,

$2^{z} ∤ 560$ mit $z \in ℕ$ und $z \geq 5$ .

Somit ist $h = 4$ und $g = (n - 1) / 2^{h} = 560 / 2^{4} = 35$ .

Nun testen wir den ersten Fall: $a^{g} \equiv 1 mod n$ :

$a^{g} \Rightarrow 2^{35} \equiv 263 mod 5 61$ , da $2^{35} = 3 \cdot 5 \cdot 7^{2} \cdot 11 \cdot 17 \cdot 249989 + 263$ .

Die erste Bedingung wird also nicht erfüllt und wir müssen die zweite Bedingung testen, nämlich es existiert ein $i \in {0, 1, \dots, h - 1}$ mit $a^{2^{i} \cdot g} \equiv - 1 mod n .$

Wir haben bereits gezeigt, dass $h = 4$ und somit $i \in {0, 1, 2, 3}$ . Den Fall $i = 0$ haben wir bereits untersucht, da $a^{2^{0} \cdot g} = a^{g}$ .

Wir müssen also nur noch die drei übrigen Elemente von $i$ jeweils in die Bedingung einsetzen:

$2^{2 \cdot 35} \equiv 166 mod 5 61$ ,

$2^{4 \cdot 35} \equiv 67 mod 5 61$ ,

$2^{8 \cdot 35} \equiv 1 mod 5 61$ .

Auch diese erfüllen die Bedingung von Fall 2 nicht. Die Basis $2$ liefert uns also, dass $561$ zusammengesetzt ist^[16]. Dies konnten wir mit Hilfe des Fermat-Tests in der zugehörigen Lernaufgabe noch nicht zeigen!

Lernaufgabe

Aufgabe

Miller-Rabin-Test
Miller-Rabin-Test
Sei $n \in ℕ$ ungerade. Ziel ist es zu ermitteln, ob $n$ mit hoher Wahrscheinlichkeit prim oder zusammengesetzt. Wähle zufällig und gleichverteilt ein $a \in {2, 3, \dots, n - 1}$ . Bestimmte $g g T (a, n)$ , Ist $g g T (a, n) > 1$ , dann ist $n$ zusammengesetzt und der Miller-Rabin-Test ist fertig, Ist $g g T (a, n) = 1$ , dann mit Schritt 3 fortfahren. Berechne mit $a^{g} mod n$ , wobei $g = (n - 1) / 2^{h}$ und $h = m a x {i \in ℕ ∣ 2^{i} teilt n - 1}$ , Ist $a^{g} \equiv 1 mod n$ , dann ist $n$ wahrscheinlich prim und der Miller-Rabin-Test fertig, Ist $a^{g} \equiv̸ 1 mod n$ , dann mit Schritt 4 fortfahren. Berechne $a^{2^{i} \cdot g} mod n$ , wobei $i \in {0, 1, \dots, h - 1}$ , Ist mindestens für ein $i \in {0, 1, \dots, h - 1}$ $a^{2^{i} \cdot g} \equiv - 1 mod n$ , dann ist $n$ wahrscheinlich prim und der Miller-Rabin-Test fertig, Existiert kein $a^{2^{i} \cdot g} \equiv̸ - 1 mod n$ , dann ist $n$ zusammengesetzt und der Miller-Rabin-Test abgeschlossen^[19]^[20]. Bemerkung: Die Wahrscheinlichkeit, dass $n$ zusammengesetzt, obwohl der Miller-Rabin-Test "wahrscheinlich prim" ausgibt ist höchstens $\frac{1}{4}$ . Durch $x$ -faches Wiederholen des Miller-Rabin-Tests, lässt sich die Wahrscheinlichkeit, dass $n$ irrtümlich als prim bezeichnet wird auf $(\frac{1}{4})^{x}$ minimieren^[17].

Bestimmen Sie mit dem Miller-Rabin-Test und einer Irrtumswahrscheinlichkeit von maximal $\frac{1}{16}$ , ob $n = 733$ zusammengesetzt oder prim ist.

Bemerkung: In der Lösung wählen wir $a = 141$ und $a = 233$ . Sie können jedoch beliebige andere $a \in {2, 3, \dots, 732}$ wählen.

Lösung

Um mit einer Irrtumswahrscheinlichkeit von maximal

\frac{1}{8}

zu bestimmen, ob

n = 733

zusammengesetzt oder prim, muss der Miller-Rabin-Test zweimal durchgeführt werden, da

(\frac{1}{4})^{2} = \frac{1}{16}

.

Zunächst bestimmen wir mit einer Irrtumswahrscheinlichkeit von maximal $\frac{1}{4}$ .

Schritt 1: Wir wählen $a_{1} = 141$ .

Schritt 2: $g g T (141, 733) = 1$ , wir müssen also mit Schritt 3 fortfahren.

Schritt 3: Für $h = m a x {i \in ℕ : 2^{i} teilt n - 1} = m a x {i \in ℕ : 2^{i} teilt 732}$ gilt:

$2^{1} ∣ 732$ ,

$2^{2} ∣ 732$ ,

$2^{z} ∤ 560$ $z \in ℕ$ und $z \geq 3$ .

Somit ist $h = 2$ und $g = (n - 1) / 2^{h} = 732 / 2^{2} = 183$ .

Nun testen wir den Fall: $a^{g} mod n \Rightarrow 14 1^{183} mod 7 33$ :

$14 1^{183} \equiv 732 mod 7 33$

Da $1 \equiv̸ 732 mod 7 33$ , müssen wir mit Schritt 4 fortfahren.

Schritt 4: $a^{2^{i} \cdot g} mod n \Rightarrow 14 1^{2^{i} \cdot 183} mod 7 33$ , wobei $i \in {0, 1, \dots, h - 1} = {0, 1}$

$i = 0 :$ $a^{2^{0} \cdot g} \equiv a^{g} mod n \Rightarrow 14 1^{183} \equiv 732 \equiv - 1 mod 7 33$

Nach dem Miller-Rabin-Test für $n = 733$ und $a = 233$ ist $n = 733$ wahrscheinlich prim.

Nun wählen wir ein weiteres zufälliges $a \in {2, 3, \dots, 732}$ , um den Irrtumswahrscheinlichkeit auf maximal $\frac{1}{16}$ zu verringern.

Schritt 1: Wir wählen $a = 233$ .

Schritt 2: $g g T (233, 733) = 1$ , wir müssen also mit Schritt 3 fortfahren.

Schritt 3: Wie bereits bei der ersten Durchführung des Miller-Rabin-Tests für $n = 733$ gezeigt, ist $h = 2$ und $g = 183$ .

Wir überprüfen $23 3^{183} mod 7 33$ :

$23 3^{183} \equiv 380 mod 7 33$ .

Da $1 \equiv̸ 380 mod 7 33$ , müssen wir mit Schritt 4 fortfahren.

Schritt 4: $14 1^{2^{i} \cdot 183} mod 7 33$ , wobei $i \in {0, 1}$

$i = 0 :$ $a^{2^{0} \cdot g} \equiv a^{g} mod n \Rightarrow 23 3^{183} \equiv 380 \equiv - 1 mod 7 33$

$i = 1 :$ $a^{2 \cdot g} \equiv a^{g} mod n \Rightarrow 23 3^{2 \cdot 183} \equiv 732 \equiv - 1 mod 7 33$

Nach dem Miller-Rabin-Test für $n = 733$ und $a = 233$ ist $n = 733$ wahrscheinlich prim und durch die zweifache Ausführung des Miller-Rabin-Tests können wir die Irrtumswahrscheinlichkeit dieser Annahme auf $\frac{1}{16}$ begrenzen.

Lernempfehlung

Kursübersicht
Übergeordnete Lerneinheit
7.1: Schlüsselerzeugung des RSA-Verschlüsselungsverfahrens
Vorherige Lerneinheit	Aktuelle Lerneinheit	Empfohlene Lerneinheit
7.1.3: Fermat-Test (Primzahltest 2)	7.1.4: Miller-Rabin-Test (Primzahltest 3)	7.1.5: Erweiterter euklidischer Algorithmus

Literatur

↑ Buchmann, J. (2016). Einführung in die Kryptographie (6. Aufl.). Springer. S. 157.
↑ ^2,0 ^2,1 ^2,2 Burton, D. M., & Dalkowski, H. (2005). Handbuch der elementaren Zahlentheorie mit über 1000 Übungsaufgaben und ihren Lösungen. Lemgo: Heldermann Verlag. S. 47.
↑ ^3,0 ^3,1 ^3,2 ^3,3 ^3,4 ^3,5 Burton, D. M., & Dalkowski, H. (2005). Handbuch der elementaren Zahlentheorie mit über 1000 Übungsaufgaben und ihren Lösungen. Heldermann Verlag. S. 26.
↑ ^4,0 ^4,1 ^4,2 Seite „Teilerfremdheit“. In: Wikipedia, Die freie Enzyklopädie. Bearbeitungsstand: 26. September 2019, 13:33 UTC. URL: https://de.wikipedia.org/w/index.php?title=Teilerfremdheit&oldid=192615323 (Abgerufen: 10. Januar 2020, 13:56 UTC; Formulierung verändert)
↑ ^5,0 ^5,1 ^5,2 Buchmann, J. (2016). Einführung in die Kryptographie (6. Aufl.). Berlin, Heidelberg: Springer. S. 37.
↑ ^6,0 ^6,1 ^6,2 Ziegenbalg, J. (2015). Elementare Zahlentheorie: Beispiele, Geschichte, Algorithmen (2., überarb. Aufl). Springer Spektrum. S. 66.
↑ ^7,0 ^7,1 Seite „Fermatsche Pseudoprimzahl“. In: Wikipedia, Die freie Enzyklopädie. Bearbeitungsstand: 6. April 2019, 23:17 UTC. URL: https://de.wikipedia.org/w/index.php?title=Fermatsche_Pseudoprimzahl&oldid=187306711 (Abgerufen: 26. Dezember 2019, 13:45 UTC; Formulierung verändert)
↑ ^8,0 ^8,1 Seite „Carmichael-Zahl“. In: Wikipedia, Die freie Enzyklopädie. Bearbeitungsstand: 11. Juli 2019, 07:01 UTC. URL: https://de.wikipedia.org/w/index.php?title=Carmichael-Zahl&oldid=190325777 (Abgerufen: 26. Dezember 2019, 13:55 UTC; Formulierung verändert)
↑ Carmichael, R. D. (1912). On Composite Numbers P Which Satisfy The Fermat Congruence a ^{P -1} ≡1 Mod P. The American Mathematical Monthly, 19(2) (S. 22–27). S. 25.
↑ Burton, D. M., & Dalkowski, H. (2005). Handbuch der elementaren Zahlentheorie mit über 1000 Übungsaufgaben und ihren Lösungen. Lemgo: Heldermann Verlag. S. 388.
↑ Buchmann, J. (2016). Einführung in die Kryptographie (6. Aufl.). Berlin, Heidelberg: Springer. S. 158.
↑ ^12,0 ^12,1 Rabin, M. O. (1980). Probabilistic algorithm for testing primality. Journal of Number Theory, 12(1) (S. 128–138). S. 128.
↑ ^13,0 ^13,1 ^13,2 ^13,3 Buchmann, J. (2016). Einführung in die Kryptographie (6. Aufl.). Berlin, Heidelberg: Springer. S. 159.
↑ Oswald, N., & Steuding, J. (2015). Elementare Zahlentheorie: Ein sanfter Einstieg in die höhere Mathematik. Springer Spektrum. S. 129.
↑ Buchmann, J. (2016). Einführung in die Kryptographie (6. Aufl.). Berlin, Heidelberg: Springer. S. 161.
↑ ^16,0 ^16,1 Rabin, M. O. (1980). Probabilistic algorithm for testing primality. Journal of Number Theory, 12(1) (S. 128–138). S. 133f.
↑ ^17,0 ^17,1 Rabin, M. O. (1980). Probabilistic algorithm for testing primality. Journal of Number Theory, 12(1) (S. 128–138). S. 130.
↑ Ziegenbalg, J. (2015). Elementare Zahlentheorie: Beispiele, Geschichte, Algorithmen (2., überarb. Aufl). Springer Spektrum. S. 66.
↑ Buchmann, J. (2016). Einführung in die Kryptographie (6. Aufl.). Berlin, Heidelberg: Springer. S. 161.
↑ Rabin, M. O. (1980). Probabilistic algorithm for testing primality. Journal of Number Theory, 12(1) (S. 128–138). S. 133f.

[:722-1] Buchmann, J. (2016). Einführung in die Kryptographie (6. Aufl.). Springer. S. 157.

[:1222-2] 2,0 ^2,1 ^2,2 Burton, D. M., & Dalkowski, H. (2005). Handbuch der elementaren Zahlentheorie mit über 1000 Übungsaufgaben und ihren Lösungen. Lemgo: Heldermann Verlag. S. 47.

[:922-3] 3,0 ^3,1 ^3,2 ^3,3 ^3,4 ^3,5 Burton, D. M., & Dalkowski, H. (2005). Handbuch der elementaren Zahlentheorie mit über 1000 Übungsaufgaben und ihren Lösungen. Heldermann Verlag. S. 26.

[:553-4] 4,0 ^4,1 ^4,2 Seite „Teilerfremdheit“. In: Wikipedia, Die freie Enzyklopädie. Bearbeitungsstand: 26. September 2019, 13:33 UTC. URL: https://de.wikipedia.org/w/index.php?title=Teilerfremdheit&oldid=192615323 (Abgerufen: 10. Januar 2020, 13:56 UTC; Formulierung verändert)

[:322-5] 5,0 ^5,1 ^5,2 Buchmann, J. (2016). Einführung in die Kryptographie (6. Aufl.). Berlin, Heidelberg: Springer. S. 37.

[:022-6] 6,0 ^6,1 ^6,2 Ziegenbalg, J. (2015). Elementare Zahlentheorie: Beispiele, Geschichte, Algorithmen (2., überarb. Aufl). Springer Spektrum. S. 66.

[:822-7] 7,0 ^7,1 Seite „Fermatsche Pseudoprimzahl“. In: Wikipedia, Die freie Enzyklopädie. Bearbeitungsstand: 6. April 2019, 23:17 UTC. URL: https://de.wikipedia.org/w/index.php?title=Fermatsche_Pseudoprimzahl&oldid=187306711 (Abgerufen: 26. Dezember 2019, 13:45 UTC; Formulierung verändert)

[:5-8] 8,0 ^8,1 Seite „Carmichael-Zahl“. In: Wikipedia, Die freie Enzyklopädie. Bearbeitungsstand: 11. Juli 2019, 07:01 UTC. URL: https://de.wikipedia.org/w/index.php?title=Carmichael-Zahl&oldid=190325777 (Abgerufen: 26. Dezember 2019, 13:55 UTC; Formulierung verändert)

[9] Carmichael, R. D. (1912). On Composite Numbers P Which Satisfy The Fermat Congruence a ^{P -1} ≡1 Mod P. The American Mathematical Monthly, 19(2) (S. 22–27). S. 25.

[:4-10] Burton, D. M., & Dalkowski, H. (2005). Handbuch der elementaren Zahlentheorie mit über 1000 Übungsaufgaben und ihren Lösungen. Lemgo: Heldermann Verlag. S. 388.

[:6-11] Buchmann, J. (2016). Einführung in die Kryptographie (6. Aufl.). Berlin, Heidelberg: Springer. S. 158.

[:0-12] 12,0 ^12,1 Rabin, M. O. (1980). Probabilistic algorithm for testing primality. Journal of Number Theory, 12(1) (S. 128–138). S. 128.

[:7-13] 13,0 ^13,1 ^13,2 ^13,3 Buchmann, J. (2016). Einführung in die Kryptographie (6. Aufl.). Berlin, Heidelberg: Springer. S. 159.

[:226-14] Oswald, N., & Steuding, J. (2015). Elementare Zahlentheorie: Ein sanfter Einstieg in die höhere Mathematik. Springer Spektrum. S. 129.

[:1-15] Buchmann, J. (2016). Einführung in die Kryptographie (6. Aufl.). Berlin, Heidelberg: Springer. S. 161.

[:2-16] 16,0 ^16,1 Rabin, M. O. (1980). Probabilistic algorithm for testing primality. Journal of Number Theory, 12(1) (S. 128–138). S. 133f.

[:8-17] 17,0 ^17,1 Rabin, M. O. (1980). Probabilistic algorithm for testing primality. Journal of Number Theory, 12(1) (S. 128–138). S. 130.

[:024-18] Ziegenbalg, J. (2015). Elementare Zahlentheorie: Beispiele, Geschichte, Algorithmen (2., überarb. Aufl). Springer Spektrum. S. 66.

[:16-19] Buchmann, J. (2016). Einführung in die Kryptographie (6. Aufl.). Berlin, Heidelberg: Springer. S. 161.

[:27-20] Rabin, M. O. (1980). Probabilistic algorithm for testing primality. Journal of Number Theory, 12(1) (S. 128–138). S. 133f.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

Kryptologie/Miller-Rabin-Test (Primzahltest 3)

Inhaltsverzeichnis

Einleitung

Definition Carmichael-Zahl

Beispiel Carmichael-Zahl

Bedeutung von Carmichael-Zahlen für den Fermat-Test

Miller-Rabin-Test

Satz Eigenschaft von Primzahlen

Miller-Rabin-Test

Beispiel

Lernaufgabe

Aufgabe

Lernempfehlung

Literatur

Navigationsmenü

Kryptologie/Miller-Rabin-Test (Primzahltest 3)

Einleitung

Definition Carmichael-Zahl

Beispiel Carmichael-Zahl

Bedeutung von Carmichael-Zahlen für den Fermat-Test

Miller-Rabin-Test

Satz Eigenschaft von Primzahlen

Miller-Rabin-Test

Beispiel

Lernaufgabe

Aufgabe

Lernempfehlung

Literatur

Navigationsmenü

Suche