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 \mathbb {N}$ ungerade. Ziel ist es zu ermitteln, ob $n$ zusammengesetzt ist. Wähle eine zu $n$ teilerfremde Basis $a$ Berechne $a^{n-1}{\bmod {n}}$ Gilt $a^{n-1}\equiv 1{\bmod {n}}$ , dann ist $n$ mit hoher Wahrscheinlichkeit prim oder zusammengesetzt Gilt $a^{n-1}\not \equiv 1{\bmod {n}}$ (Fall 2), dann ist $n$ nicht prim, sondern zusammengesetzt^[1]
Primzahl
Sei $p\in \mathbb {N}$ mit $p>1$ , dann heißt $p$ Primzahl oder prime Zahl, wenn gilt: $p$ besitzt nur zwei Teiler in $\mathbb {N}$ , 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 $ggT(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 \mathbb {Z}$ und $m\in \mathbb {N}$ , dann gilt $a\equiv b{\bmod {m}}\Leftrightarrow m\mid (a-b)$ ^[5].
Primfaktorzerlegung
Sei $n\in \mathbb {N}$ 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 \mathbb {N}$ . 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{\bmod {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{\bmod {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 \mathbb {Z} /\{3,11,17\}$ gilt

$a^{561-1}\equiv 1{\bmod {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{\bmod {p}}$ ^[7]^[14].
Primzahl
Sei $p\in \mathbb {N}$ mit $p>1$ , dann heißt $p$ Primzahl oder prime Zahl, wenn gilt: $p$ besitzt nur zwei Teiler in $\mathbb {N}$ , 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 $ggT(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 \mathbb {Z}$ und $m\in \mathbb {N}$ , dann gilt $a\equiv b{\bmod {m}}\Leftrightarrow m\mid (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 \mathbb {Z}$ teilerfremd zu $n$ , so gilt eine der Kongruenzen

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

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

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

$g=(n-1)/2^{h}$ und $h=max\{i\in \mathbb {N} \mid 2^{i}{\text{ 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 \mathbb {N}$ 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)$ $ggT(a,n)$
- Ist ${\ce {ggT(a,n) > 1}}$ , dann ist $n$ zusammengesetzt und der Miller-Rabin-Test ist fertig
- Ist $ggT(a,n)=1$ , dann mit Schritt 3 fortfahren
Berechne mit $a^{g}{\bmod {n}}$ $a^{g}{\bmod {n}}$ , wobei $g=(n-1)/2^{h}$ $g=(n-1)/2^{h}$ und $h=max\{i\in \mathbb {N} \mid 2^{i}{\text{ teilt }}n-1\}$ $h=max\{i\in \mathbb {N} \mid 2^{i}{\text{ teilt }}n-1\}$
- Ist $a^{g}\equiv 1{\bmod {n}}$ , dann ist $n$ wahrscheinlich prim und der Miller-Rabin-Test fertig
- Ist $a^{g}\not \equiv 1{\bmod {n}}$ , dann mit Schritt 4 fortfahren
Berechne $a^{2^{i}\cdot g}{\bmod {n}}$ $a^{2^{i}\cdot g}{\bmod {n}}$ , wobei $i\in \{0,1,\dots ,h-1\}$ $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{\bmod {n}}$ , dann ist $n$ wahrscheinlich prim und der Miller-Rabin-Test fertig
- Existiert kein $a^{2^{i}\cdot g}\not \equiv -1{\bmod {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 ${\tfrac {1}{4}}$ . Durch $x$ -faches Wiederholen des Miller-Rabin-Tests, lässt sich die Wahrscheinlichkeit, dass $n$ irrtümlich als prim bezeichnet wird auf $({\tfrac {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{\bmod {n}}$ ^[8]^[18].
Satz Eigenschaft von Primzahlen
Seien $n$ prim und $a\in \mathbb {Z}$ teilerfremd zu $n$ , so gilt eine der Kongruenzen $a^{g}\equiv 1{\bmod {n}}$ oder es existiert ein $i\in \{0,1,\dots ,h-1\}$ mit $a^{2^{i}\cdot g}\equiv -1{\bmod {n}}$ , wobei $g=(n-1)/2^{h}$ und $h=max\{i\in \mathbb {N} :2^{i}{\text{ teilt }}n-1\}$ ^[13].
Primzahl
Sei $p\in \mathbb {N}$ mit $p>1$ , dann heißt $p$ Primzahl oder prime Zahl, wenn gilt: $p$ besitzt nur zwei Teiler in $\mathbb {N}$ , 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 $ggT(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 \mathbb {Z}$ und $m\in \mathbb {N}$ , dann gilt $a\equiv b{\bmod {m}}\Leftrightarrow m\mid (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=max\{i\in \mathbb {N} \mid 2^{i}{\text{ teilt }}n-1\}$ bestimmt werden.

Es gilt für $h=max\{i\in \mathbb {N} \mid 2^{i}{\text{ teilt }}560\}$ :

$2^{1}\mid 560$ ,

$2^{2}\mid 560$ ,

$2^{3}\mid 560$ ,

$2^{4}\mid 560$ ,

$2^{z}\nmid 560$ mit $z\in \mathbb {N}$ 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{\bmod {n}}$ :

$a^{g}\Rightarrow 2^{35}\equiv 263{\bmod {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{\bmod {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{\bmod {5}}61$ ,

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

$2^{8\cdot 35}\equiv 1{\bmod {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 \mathbb {N}$ 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 $ggT(a,n)$ , Ist ${\ce {ggT(a,n) > 1}}$ , dann ist $n$ zusammengesetzt und der Miller-Rabin-Test ist fertig, Ist $ggT(a,n)=1$ , dann mit Schritt 3 fortfahren. Berechne mit $a^{g}{\bmod {n}}$ , wobei $g=(n-1)/2^{h}$ und $h=max\{i\in \mathbb {N} \mid 2^{i}{\text{ teilt }}n-1\}$ , Ist $a^{g}\equiv 1{\bmod {n}}$ , dann ist $n$ wahrscheinlich prim und der Miller-Rabin-Test fertig, Ist $a^{g}\not \equiv 1{\bmod {n}}$ , dann mit Schritt 4 fortfahren. Berechne $a^{2^{i}\cdot g}{\bmod {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{\bmod {n}}$ , dann ist $n$ wahrscheinlich prim und der Miller-Rabin-Test fertig, Existiert kein $a^{2^{i}\cdot g}\not \equiv -1{\bmod {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 ${\tfrac {1}{4}}$ . Durch $x$ -faches Wiederholen des Miller-Rabin-Tests, lässt sich die Wahrscheinlichkeit, dass $n$ irrtümlich als prim bezeichnet wird auf $({\tfrac {1}{4}})^{x}$ minimieren^[17].

Bestimmen Sie mit dem Miller-Rabin-Test und einer Irrtumswahrscheinlichkeit von maximal ${\tfrac {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

{\tfrac {1}{8}}

zu bestimmen, ob

n=733

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

({\tfrac {1}{4}})^{2}={\displaystyle {\tfrac {1}{16}}}

.

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

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

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

Schritt 3: Für $h=max\{i\in \mathbb {N} :2^{i}{\text{ teilt }}n-1\}=max\{i\in \mathbb {N} :2^{i}{\text{ teilt }}732\}$ gilt:

$2^{1}\mid 732$ ,

$2^{2}\mid 732$ ,

$2^{z}\nmid 560$ $z\in \mathbb {N}$ 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}{\bmod {n}}\Rightarrow 141^{183}{\bmod {7}}33$ :

$141^{183}\equiv 732{\bmod {7}}33$

Da $1\not \equiv 732{\bmod {7}}33$ , müssen wir mit Schritt 4 fortfahren.

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

$i=0:$ $a^{2^{0}\cdot g}\equiv a^{g}{\bmod {n}}\Rightarrow 141^{183}\equiv 732\equiv -1{\bmod {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 ${\tfrac {1}{16}}$ zu verringern.

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

Schritt 2: $ggT(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 $233^{183}{\bmod {7}}33$ :

$233^{183}\equiv 380{\bmod {7}}33$ .

Da $1\not \equiv 380{\bmod {7}}33$ , müssen wir mit Schritt 4 fortfahren.

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

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

$i=1:$ $a^{2\cdot g}\equiv a^{g}{\bmod {n}}\Rightarrow 233^{2\cdot 183}\equiv 732\equiv -1{\bmod {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 ${\tfrac {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]