Der kleine Satz von Fermat: Unterschied zwischen den Versionen

Aus FunFacts Wiki
Zur Navigation springen Zur Suche springen
(Autoren)
 
(39 dazwischenliegende Versionen von 3 Benutzern werden nicht angezeigt)
Zeile 1: Zeile 1:
 +
'''Der kleine Satz von Fermat''' (auch: "Der kleine Fermat") ist ein Lehrsatz der Zahlentheorie und wurde im 17. Jahrhundert vom französischen Mathematiker Pierre de Fermat formuliert. Er macht folgende Aussage über Primzahlen:
 +
 +
Für jede ganze Zahl <math>a \in\mathbb{Z}</math> und jede Primzahl <math>p</math> gilt:
 +
{| style="font-size: 12pt"
 +
|<math> a^p\ mod\ p=a</math>
 +
|}
 +
Eine äquivalente Schreibweise, die auch im Folgenden vorkommen wird, ist: <math>a^p\equiv a\ mod\ p</math>.
 +
<br>
 +
Dabei bedeutet mod „Teilen mit Rest“ : z.B. ist <math>10\ mod\ 7=3</math>, denn <math>10/7=1\ Rest\ 3</math>.
 +
<br>
 +
Auf den kleinen Satz von Fermat angewendet bedeutet dies, dass der Rest bei ganzzahliger Division von <math>a^{p}/ p</math> genau <math>a</math> ist. Dies ist gleichbedeutend damit, dass <math>(a^p-a)\ mod\ p=0</math>, d.h. dass <math>p</math> die Zahl <math>({a\ }^p\ – a)</math> teilt.
 +
Dies wird auch geschrieben als <math>p|a^p-a\ </math>.
 +
 +
==Beweis==
 +
===Erste Methode: Induktion===
 +
Bewiesen werden kann dieser Satz über vollständige Induktion nach <math>a</math>:
 +
Dabei werden zwei Fälle unterschieden:
 +
<br>
 +
1.Fall: <math>a\geq0</math>
 +
:: '''Induktionsanfang:''' <math>a\ =\ 0</math>
 +
:::::{| style="width: 30%"
 +
|-
 +
| style="width: 35%" align="center" |<math>p|a^p-a</math>
 +
| style="width: 30%" align="center" |[math]\Longleftrightarrow[/math]
 +
| style="width: 35%" align="center" |<math>p|0^p-0</math>
 +
|}
 +
::Diese Aussage ist wahr für alle Primzahlen <math>p</math>, da jede ganze Zahl die <math>0</math> teilt.
 +
::'''Induktionsschritt:'''
 +
::Es gelte für ein festes, aber beliebiges <math>a</math> und alle Primzahlen <math>p</math>: <math>p|a^p-a\ </math>
 +
::Nun ist zu zeigen, dass die Aussage auch für <math>a+1</math> gilt, d.h <math>p|{(a+1)}^p-(a+1)</math>
 +
::Durch Anwenden des binomischen Lehrsatzes und anschließendes Herausziehen des ersten und letzten Summanden erhält man:
 +
::<math>({a+1)\ }^p-(a+1)=\sum_{k=0}^{p\ }{\ \binom{p}{k}\ }a^{p-k}1^k-(a+1)\ </math>
 +
::<math>=\binom{p}{0}\ a^p\ \ +\ \ \ \sum_{k=1}^{p-1}{\ \binom{p}{k}}{\ a}^{p-k}+\binom{p}{p}a^0-a-1</math>
 +
::<math>=a^p\ \ +\ \ \ \sum_{k=1}^{p-1}{\ \binom{p}{k}}\ {\ a}^{p-k}+1-a-1</math>
 +
::<math>{=a}^p-a\ \ +\ \ \ \sum_{k=1}^{p-1}{\ \binom{p}{k}\ a}^{p-k}</math>
 +
::Der erste Summand ist nach Induktionsvoraussetzung bereits durch <math>p</math> teilbar.Bleibt zu zeigen, dass auch der zweite Summand durch <math>p</math> teilbar ist.
 +
 +
<br>
 +
::''Behauptung:''  <math>p|\binom{p}{k}</math> für <math>1\le k\le p-1</math>
 +
::Nach Definition des Binomialkoeffizienten gilt:
 +
::{|
 +
|-
 +
| style="width: 35%" align="center" |<math>\binom{p}{k}\ =\frac{p!}{k!\ \left(p-k\right)!}</math>
 +
| style="width: 30%" align="center" |und damit
 +
| style="width: 35%" align="center" |<math>\binom{p}{k}k!=\ \frac{p!}{\left(p-k\right)!}</math>
 +
|}
 +
::<math>\Rightarrow\frac{p!}{\left(p-k\right)!}=\frac{\left(p-k\right)\ \left(p-k+1\right)\ldots\left(p-1\right)\ p}{\left(p-k\right)!}=\left(p-k+1\right)\ldots\left(p-1\right)\ p</math>
 +
::<math>\Rightarrow p|\frac{p!}{\left(p-k\right)!}</math> , da <math>p</math> als Faktor vorkommt.
 +
::Folglich ist [math]\ \frac{p!}{\left(p-k\right)!}[/math] durch p teilbar und somit auch [math]\binom{p}{k}k![/math].  Da <math>k \le p-1</math> und <math>p</math> eine Primzahl ist und somit insbesondere teilerfremd zu allen Zahlen kleiner gleich <math>p-1</math>, ist <math>k!</math> nicht durch <math>p</math> teilbar. Folglich muss der Primfaktor <math>p</math> also in <math>\binom{p}{k}\ </math> enthalten sein, da Primfaktoren nicht „aufgespaltet“ werden können, d.h <math>\binom{p}{k}\ </math> ist durch <math>p</math> teilbar.
 +
::Man erhält also insgesamt, dass von der Summe <math>a^p-a\ +\ \ \sum_{k=1}^{p-1}{\ \binom{p}{k}}{\ a}^{p-k}</math> sowohl der erste Summand (nach Induktionsvoraussetzung) als auch jeder einzelne Summand des zweiten Summanden durch <math>p</math> teilbar ist. Somit ist auch die ganze Summe durch <math>p</math> teilbar.
 +
2.Fall: Wir setzen <math>b:=-a  < 0</math> (a ist dabei wie oben weiterhin positiv).
 +
::<math>\Longrightarrow {(-a)}^p-(-a)={(-1)}^pa^p+a</math>
 +
::Für ungerade Primzahlen (also alle außer die <math>2</math>) gilt dann:
 +
::<math>\left(-a\right)^p-\left(-a\right)=-a^p+a=-(a^p-a)</math>
 +
::Für positive <math>a</math> weiß man aber schon aus dem ersten Fall, dass <math>p|a^p-a\ </math>. Somit gilt auch <math>{-p|-(a}^p-a)</math>.
 +
::Falls <math>p = 2</math>:
 +
::<math>\left(-a\right)^p-\left(-a\right)=a^2+a=a\ \left(a+1\right)</math>
 +
::<math>\Longrightarrow p|{(-a)}^p-(-a)\ \Longleftrightarrow\ \ 2|a\ (a+1)</math>[[Datei:Grafik- Beispiel mit p=4.png|alternativtext=|mini|330x330px]]
 +
::Da von zwei aufeinanderfolgenden ganzen Zahlen immer genau eine gerade ist, gilt die Aussage.
 +
 +
===Zweite Methode: Kombinatorik===
 +
[[Datei:Grafik-Beispiel mit p=5.png|alternativtext=|mini|331x331px]]
 +
Sei <math>p</math> eine natürliche Zahl und <math>a</math> eine beliebige ganze Zahl. Nun sollen aus Perlen mit <math>a</math> verschiedenen Farben Ketten mit <math>p</math> Perlen gebildet werden. Also gibt es insgesamt <math>a^p</math> Möglichkeiten wie eine Kette aussieht.
 +
Wenn man nun eine beliebige Kette, die an den Enden zusammengebunden ist, betrachtet, stellt man fest, dass man durch Drehen dieser, andere mögliche Ketten erhält, bis man spätestens nach <math>p</math> Drehungen wieder bei der Ursprungskette landet. Es kann aber auch sein, dass man schon vorher wieder beim Anfangsmuster landet.
 +
<br>
 +
''Beispiel'': Bei einer Kette aus <math>p=4</math> Perlen mit dem Muster rot-blau-rot-blau, wäre man nach zwei Drehungen schon wieder beim Ausgangsmuster (siehe obere Grafik).
 +
<br>
 +
<br>
 +
Wir zeigen nun, dass wenn <math>p</math> eine Primzahl ist, es aber nur zwei Möglichkeiten gibt nach welcher Anzahl an Drehungen man wieder am Anfang ist:
 +
Sei <math>p</math> prim und <math>b</math> die kleinste positive Zahl, sodass man nach <math>b</math>-maligem rotieren wieder die Anfangskette erhält.
 +
Angenommen es gilt <math>1<b<p</math>, dann sei <math>n\cdot\ b</math> das kleinste Vielfache von <math>b</math>, sodass <math>n\cdot\ b>p</math> gilt.
 +
Daraus folgt aber auch: <math>0<n\cdot\ b-p<b</math> und zudem überführt man die Kette durch <math>n\cdot\ b-p</math>-maligem rotieren ebenfalls in den Anfangszustand zurück.
 +
Das ist ein Widerspruch dazu, dass <math>b</math> die kleinste Zahl ist, für die das möglich ist.
 +
Daraus folgt, dass <math>b=1</math> oder <math>b=p</math> gelten muss.
 +
Es ergeben sich also diese beiden Möglichkeiten für die Anfangskette:
 +
*Alle Perlen besitzen dieselbe Farbe <math>\left(b=1\right)</math>
 +
*Es existiert mindestens eine andersfarbige Perle <math>\left(b=p\right)</math>
 +
<br>
 +
Im ersten Fall lässt sich durch Rotation keine neue Kette bilden. Es gibt <math>a</math> verschiedene solcher einfarbigen Ketten.
 +
Die Anzahl der gemischtfarbigen Ketten <math>\left(b=p\right)</math> ist <math>a^p-a</math>.
 +
Nach obiger Überlegung lassen sich diese aber in Gruppen zu je <math>p</math> zusammenfassen, und zwar je eine Anfangskette und die <math>p-1</math> durch-Rotation-entstehenden Ketten (beim <math>p</math>-ten Mal erhält man ja wieder die Ursprungskette). Also gilt, dass die Anzahl der gemischtfarbigen Ketten <math>(a^p-a)</math> durch <math>p</math> teilbar ist, was zu zeigen war.
 +
 +
==Fermat'scher Primzahltest==
 +
===Folgerungen aus dem kleinen Satz von Fermat===
 +
* Wenn der Satz für eine Zahl <math>p</math> nicht erfüllt ist, kann die Zahl <math>p</math> auch keine Primzahl sein (Kontraposition des Satzes).
 +
* Es folgt jedoch nicht, dass nur, weil eine Zahl <math>p</math> diese Gleichung erfüllt, diese Zahl auch zwingend eine Primzahl ist. Denn der kleine Satz von Fermat ist nur eine Implikation in eine Richtung, die Rückrichtung gilt im Allgemeinen nicht:
 +
''Beispiel'': <math>a = 4, p = 15 </math>
 +
<br>
 +
<math>4^{15}\ \ mod\ 15=4</math> , aber <math>15=5\cdot3</math> ist keine Primzahl.
 +
<br>
 +
Diese Folgerungen bilden die Grundlage für viele Primzahltests. Ein Primzahltest, der den kleinen Satz von Fermat unmittelbar anwendet, hat folgendes Algorithmus.
 +
===Algorithmus===
 +
1. Schritt: Sei [math]p[/math] eine Zahl, von der getestet werden soll, ob sie eine Primzahl ist.
 +
<br>
 +
2. Schritt: Berechne (beliebig oft) für zufällig gewählte <math>a</math> den Ausdruck <math>{\ a}^p\ \ mod\ p</math>.
 +
<br>
 +
3. Schritt: Falls man dabei einmal als Ergebnis <math>{\ a}^p\ \ mod\ p\neq a</math> erhält, so kann nach der ersten Folgerung <math>p</math> ganz sicher keine Primzahl sein.
 +
<br>
 +
4. Schritt: Falls das Ergebnis immer <math>a^p\ \ mod\ p=a</math> ist, so lässt sich keine sichere Aussage treffen. Die zu testende Zahl erfüllt eine notwendige Bedingung dafür, prim zu sein, jedoch keine hinreichende. Die Aussage ist dann „wahrscheinlich prim“. Eine genaue Wahrscheinlichkeit kann dabei im Übrigen nicht angegeben werden.
 +
<br>
 +
<br>
 +
'''Beispiele:'''
 +
<br>
 +
<math>a = 2, p = 3</math>
 +
<br>
 +
<math>{{\ a}^p\ \ mod\ p=2}^3\ mod\ 3=8\ mod\ 3=\ 2</math>
 +
<br>
 +
<math>\Longrightarrow 3</math> ist „wahrscheinlich prim“.
 +
<br>
 +
<br>
 +
<math>a = 2, p = 4</math>
 +
<br>
 +
<math>{{\ a}^p\ \ mod\ p=2}^4\ mod\ 3=16\ mod\ 3=\ 1\neq2</math>
 +
<br>
 +
<math>\Longrightarrow 4</math> ist sicher keine Primzahl.
 +
<br>
 +
'''Bemerkung:'''
 +
In der Praxis haben die zu testenden Zahlen meist mindestens mehrere hundert Stellen und für die Berechnung von <math>{\ a}^p\ \ mod\ p</math>  gibt es weitaus effizientere Möglichkeiten als zuerst die Potenz durch <math>p</math>-malige Multiplikation von <math>a</math> zu erhalten und dann modulo <math>p</math> zu rechnen.
 +
 +
==Carmichael Zahlen==
 +
Die offensichtliche Schwäche des obigen Tests ist es, dass er nicht mit absoluter Sicherheit sagen kann, ob eine Zahl prim ist. Das wäre in der Praxis nicht weiter schlimm, wenn es eine feste Irrtumswahrscheinlichkeit <math>P < 1</math> gäbe. Dann müsste man den Test nur oft genug hintereinander mit zufällig gewählten a ausführen und durch die Potenzierung der Irrtumswahrscheinlichkeit könnte die insgesamte Irrtumswahrscheinlichkeit des Tests nach mehreren Durchläufen beliebig klein gemacht werden. Doch leider gibt es für den oben vorgestellten Test keine obere Schranke < 1 für die Irrtumswahrscheinlichkeit. Grund dafür sind die sogenannten '''Carmichael-Zahlen'''.
 +
Diese haben folgende Eigenschaft: Sie erfüllen den obigen Primzahltest für alle ganzen Zahlen <math>a</math>, die teilerfremd zu der Carmichael-Zahl <math>p</math> sind, d.h. der größte gemeinsame Teiler von <math>a</math> und <math>p</math> muss 1 sein.
 +
<br>
 +
Die kleinste Carmichael-Zahl ist <math>561 = 3 \cdot11\ \cdot17</math>.
 +
D.h. für alle Basen <math>a</math>, die in ihrer Primfaktorzerlegung weder die 3 noch die 11 noch die 17 enthalten, gilt: <math>{\ a}^{561}\ \ mod\ 561  = a</math>.
 +
<br>
 +
<br>
 +
Insbesondere für Carmichael-Zahlen mit größeren Primfaktoren (die 3 bildet hier eine Ausnahme) ist dann die Wahrscheinlichkeit, dass beim Ausführen des obigen Tests mit z.B. 10 verschiedenen <math>a</math> jedes Mal „wahrscheinlich prim“ und somit auch insgesamt „wahrscheinlich prim“ herauskommt, sehr hoch, obwohl es sich nicht um eine Primzahl handelt.
 +
Die Carmichael-Zahlen werden deshalb auch ''fermatsche Pseudoprimzahlen'' genannt.
 +
Von diesen Carmichael-Zahlen gibt es zwar nur „wenige“, aber doch unendlich viele (auf den Beweis verzichten wir an dieser Stelle), d.h. in unendlich vielen Fällen liefert der obige Test höchstwahrscheinlich ein falsches Ergebnis.
 +
Um diese unschöne Eigenschaft zu vermeiden, gibt es den sogenannten Miller-Rabin-Test, der vor allem in der Kryptographie zum Einsatz kommt und im nächsten Abschnitt vorgestellt wird.
 +
 
==Der Miller-Rabin Test==
 
==Der Miller-Rabin Test==
 
Der Miller-Rabin Test ist ein probabilistischer Primzahltest, der als optimierte Version des klassischen Primzahltestes betrachtet werden kann. Ähnlich wie der Fermat’sche Test wird überprüft, ob eine Eigenschaft von Primzahlen auch für eine gegebene Zahl gilt. Dafür definiert man zuerst die starken Pseudoprimzahlen.
 
Der Miller-Rabin Test ist ein probabilistischer Primzahltest, der als optimierte Version des klassischen Primzahltestes betrachtet werden kann. Ähnlich wie der Fermat’sche Test wird überprüft, ob eine Eigenschaft von Primzahlen auch für eine gegebene Zahl gilt. Dafür definiert man zuerst die starken Pseudoprimzahlen.
 
===Starke Pseudoprimzahlen===
 
===Starke Pseudoprimzahlen===
−
Sei <math>n>2</math> eine natürliche, ungerade Zahl. <math>n</math> lässt sich schreiben als <math>2^s\cdot d+1</math>, wobei <math>s,d</math> natürliche Zahlen sind und <math>d</math> ungerade. Sei nun <math>a<n</math> eine natürliche Zahl.  
+
Sei <math>n>2</math> eine natürliche, ungerade Zahl. <math>n</math> lässt sich eindeutig schreiben als <math>2^s\cdot d+1</math>, wobei <math>s,d</math> natürliche Zahlen sind und <math>d</math> ungerade. Sei nun <math>a<n</math> eine natürliche Zahl.  
 
Man nennt <math>n</math> eine starke Pseudoprimzahl zur Basis <math>a</math>, wenn <math>n</math> eine der folgenden Bedingungen erfüllt:
 
Man nennt <math>n</math> eine starke Pseudoprimzahl zur Basis <math>a</math>, wenn <math>n</math> eine der folgenden Bedingungen erfüllt:
 
* <math>a^d\equiv1\ mod\ n</math>
 
* <math>a^d\equiv1\ mod\ n</math>
 
* <math>a^{2^rd}\equiv-1\ mod\ n</math> für eine beliebige, natürliche Zahl <math>0\le\ r<s</math>
 
* <math>a^{2^rd}\equiv-1\ mod\ n</math> für eine beliebige, natürliche Zahl <math>0\le\ r<s</math>
−
====Lemma====  
+
 
−
{|class="wikitable" style="background-color:#e6f3ff;"
+
Betrachten wir folgende zwei Beispiele zur Veranschaulichung:
−
|''Jede Primzahl ist auch eine starke Pseudoprimzahl.''
+
<br>
 +
'''1. Beispiel'''
 +
<br>
 +
<math>n=121</math> ist eine starke Pseudoprimzahl zur Basis <math>a=3</math>, denn:
 +
<br>
 +
<math>n=2^3\cdot15+1</math>, also gilt <math>s=3</math> und <math>d=15</math>.
 +
<br>
 +
Man merkt, dass die erste Bedingung erfüllt wird, da <math>3^{15}\equiv1\ mod\ 121</math> gilt.
 +
<br>
 +
'''2. Beispiel'''
 +
<br>
 +
<math>n=325</math> ist eine starke Pseudoprimzahl zur Basis <math>a=7</math>, denn:
 +
<br>
 +
<math>n=2^2\cdot81+1</math>, also gilt <math>s=2</math> und <math>d=81</math>.
 +
<br>
 +
Man stellt fest, dass die erste Bedingung nicht erfüllt wird: <math>7^{81}\ mod\ 325=307\neq1</math> (in diesem Fall ist <math>r=0</math>)
 +
<br>
 +
Wir überprüfen nun, dass die zweite Bedingung tatsächlich erfüllt wird:
 +
<br>
 +
<math>0\le r<s=2</math>, also <math>r\in\left\{0,\ 1\right\}</math>.
 +
<br>
 +
Für <math>r=0</math> gilt: <math>7^{81}\ mod\ 325=307\neq-1</math>
 +
<br>
 +
Für <math>r=1</math> gilt: <math>7^{2^1\cdot81}\ mod\ 325=7^{162}\ mod\ 325=324=-1</math>
 +
<br>
 +
Somit ist die zweite Bedingung für <math>r=1</math> erfüllt.
 +
<br>
 +
 
 +
===Lemma===  
 +
{| class="wikitable" style="font-size: 11pt; background-color:#e6f3ff;"
 +
|''Jede Primzahl ist auch eine starke Pseudoprimzahl zu jedwelcher Basis.''
 
|}
 
|}
 
''Beweis'': Eine notwendige Erkenntnis für den Beweis des Lemmas ist folgende:
 
''Beweis'': Eine notwendige Erkenntnis für den Beweis des Lemmas ist folgende:
−
{|class="wikitable" style="background-color:#e6f3ff;"
+
{| class="wikitable" style="font-size: 11pt; background-color:#e6f3ff;"
 
  |''Wenn <math>n</math> eine Primzahl ist, dann hat das Polynom  <math>X^2-1</math>  über <math>\mathbb{Z}/n\mathbb{Z}</math>  nur die beiden Wurzeln <math>x=1</math> und <math>x=-1</math>.''
 
  |''Wenn <math>n</math> eine Primzahl ist, dann hat das Polynom  <math>X^2-1</math>  über <math>\mathbb{Z}/n\mathbb{Z}</math>  nur die beiden Wurzeln <math>x=1</math> und <math>x=-1</math>.''
 
|}
 
|}
−
Diese Aussage folgt direkt aus der Tatsache, dass die Anzahl der Nullstellen eines Polynoms über einem Körper höchstens gleich mit dem Grad des Polynoms ist. Da  <math>X^2-1</math>  die beiden trivialen Wurzeln 1  und -1 über <math>\mathbb{Z}/n\mathbb{Z}</math> hat, gibt es keine weiteren Nullstellen.
+
Diese Aussage folgt direkt aus der Tatsache, dass die Anzahl der Nullstellen eines Polynoms über einem Körper höchstens gleich der Grad des Polynoms ist. Da  <math>X^2-1</math>  die beiden trivialen Wurzeln 1  und -1 über <math>\mathbb{Z}/n\mathbb{Z}</math> hat, gibt es keine weiteren Nullstellen.
 +
<br>
 +
<br>
 +
Sei nun <math>n=2^s\cdot d+1</math> eine ungerade Primzahl, <math>s,d\in\mathbb{N}</math>, <math>d</math> ungerade und <math>a\in\mathbb{N},\ a<n</math>.
 
<br>
 
<br>
 +
Da <math>a<n</math> gilt nach dem ''Kleinen Satz von Fermat'':
 
<br>
 
<br>
−
Nun gilt nach dem ''Kleinen Satz von Fermat'':<br>
+
: <math>a^{2^sd}\equiv1\ mod\ n</math>  
−
<math>a^{2^sd}\equiv1\ mod\ n</math> (oder <math>a^{2^sd}</math>ist teilbar durch <math>n</math>)<br>
 
 
Betrachtet man die Folge <math>a^{2^sd},\ \ a^{2^{s-1}d},\ \ldots,\ \ a^{2d},\ a^d</math> so merkt man, dass jedes Glied, außer dem ersten, die Wurzel des vorherigen Folgengliedes ist. Da<br>
 
Betrachtet man die Folge <math>a^{2^sd},\ \ a^{2^{s-1}d},\ \ldots,\ \ a^{2d},\ a^d</math> so merkt man, dass jedes Glied, außer dem ersten, die Wurzel des vorherigen Folgengliedes ist. Da<br>
−
{|style="font-size: 12pt" align="center"
+
{| style="font-size: 12pt" align="center"
 
|<math>a^{2^sd}-1=\left(a^{2^{s-1}d}\right)^2-1\equiv0\ \ mod\ n</math><br>
 
|<math>a^{2^sd}-1=\left(a^{2^{s-1}d}\right)^2-1\equiv0\ \ mod\ n</math><br>
 
|}
 
|}
−
gilt<br>
+
{| style="width: 100%"
−
{|style="font-size: 12pt" align="center"
+
|gilt:
−
|<math>a^{2^{s-1}d}\equiv1\ mod\ n\ \ \left(1\right)</math>  
+
| style="font-size: 12pt; width: 43%;" align="center" |<math>a^{2^{s-1}d}\equiv1\ mod\ n\ \ \left(1\right)</math>  
−
|}
+
|oder  
−
oder  
+
| style="font-size: 12pt; width: 43%;" align="center" | <math>a^{2^{s-1}d}\equiv-1\ \ mod\ n\ \ \left(2\right)</math>
−
{|style="font-size: 12pt" align="center"
 
−
|<math>a^{2^{s-1}d}\equiv-1\ \ mod\ n\ \ \left(2\right)</math>
 
 
|}
 
|}
 
Falls <math>\left(2\right)</math> richtig ist, so ist die zweite Bedingung bereits erfüllt mit  <math>r=s-1</math>. Falls <math>\left(1\right)</math> richtig ist, so wendet man wiederholt dieselben Schritte an bis entweder eins der Glieder kongruent modulo <math>n</math> mit <math>-1</math> ist oder alle Folgenglieder, insbesondere der letzte, kongruent modulo <math>n</math> mit <math>1</math> sind.
 
Falls <math>\left(2\right)</math> richtig ist, so ist die zweite Bedingung bereits erfüllt mit  <math>r=s-1</math>. Falls <math>\left(1\right)</math> richtig ist, so wendet man wiederholt dieselben Schritte an bis entweder eins der Glieder kongruent modulo <math>n</math> mit <math>-1</math> ist oder alle Folgenglieder, insbesondere der letzte, kongruent modulo <math>n</math> mit <math>1</math> sind.
 +
 
===Der Miller-Rabin Test===
 
===Der Miller-Rabin Test===
 
Mittels der vorher bewiesenen Eigenschaft der Primzahlen ergibt sich folgender Algorithmus, bekannt als der Miller-Rabin Test:<br>
 
Mittels der vorher bewiesenen Eigenschaft der Primzahlen ergibt sich folgender Algorithmus, bekannt als der Miller-Rabin Test:<br>
Zeile 46: Zeile 210:
 
# Wurde eine Zahl <math>a</math> gefunden, für die <math>n</math> die Eigenschaft nicht erfüllt, so gebe “zusammengesetzt“ aus und stoppe das Verfahren. Wenn nicht, dann wiederhole die vorherigen Schritte, insgesamt nicht mehr als k mal.  
 
# Wurde eine Zahl <math>a</math> gefunden, für die <math>n</math> die Eigenschaft nicht erfüllt, so gebe “zusammengesetzt“ aus und stoppe das Verfahren. Wenn nicht, dann wiederhole die vorherigen Schritte, insgesamt nicht mehr als k mal.  
 
Hat die gegebene Zahl beim k-maligen Durchlauf den Test bestanden, so gebe “wahrscheinlich prim“ aus.<br>
 
Hat die gegebene Zahl beim k-maligen Durchlauf den Test bestanden, so gebe “wahrscheinlich prim“ aus.<br>
−
Grundlegend für das angegebene Algorithmus ist die Tatsache, dass jede Zahl, die keine starke Pseudoprimzahl zu einer beliebigen Basis <math>a</math> ist, keine Primzahl sein kann. Der Test besteht nun darin, zu der zu prüfenden Zahl <math>n</math> eine Basis <math>a</math> zu finden, so dass <math>n</math> keine starke Pseudoprimzahl zur Basis <math>a</math> ist und somit keine Primzahl. Findet man eine solche Zahl <math>a</math>, so nennt sich diese ein Zeuge der Zerlegbarkeit von <math>n</math>.
+
Grundlegend für den angegebenen Algorithmus ist die Tatsache, dass jede Zahl, die keine starke Pseudoprimzahl zu einer beliebigen Basis <math>a</math> ist, keine Primzahl sein kann. Der Test besteht nun darin, zu der zu prüfenden Zahl <math>n</math> eine Basis <math>a</math> zu finden, so dass <math>n</math> keine starke Pseudoprimzahl zur Basis <math>a</math> ist und somit keine Primzahl. Findet man eine solche Zahl <math>a</math>, so nennt sich diese ein Zeuge der Zerlegbarkeit von <math>n</math>.
 
<br>
 
<br>
 
<br>
 
<br>
Zeile 81: Zeile 245:
 
:* <math>a^{2^3d}\ mod\ n=2^{280}\ mod\ 561=1\neq-1</math>
 
:* <math>a^{2^3d}\ mod\ n=2^{280}\ mod\ 561=1\neq-1</math>
 
Somit erfüllt <math>n=561</math> für die Basis <math>a=2</math> keine der beiden Bedingungen einer starken Pseudoprimzahl und ist daher auch keine Primzahl.
 
Somit erfüllt <math>n=561</math> für die Basis <math>a=2</math> keine der beiden Bedingungen einer starken Pseudoprimzahl und ist daher auch keine Primzahl.
 +
==Quellen==
 +
# http://www.austromath.at/medienvielfalt/materialien/krypto/lernpfad/content/k_prim_l06.htm
 +
# https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test
 +
# http://page.math.tu-berlin.de/~kant/teaching/hess/krypto-ws2007/miller-rabin.pdf
 +
# https://www.youtube.com/watch?v=YqHZQmbDw6s
 +
# https://de.wikibooks.org/wiki/Beweisarchiv:_Zahlentheorie:_Elementare_Zahlentheorie:_Kleiner_Satz_von_Fermat
 +
==Autoren==
 +
Max Jungmann
 +
<br>
 +
Robin Klotzbücher
 +
<br>
 +
Mara-Eliana Popescu

Aktuelle Version vom 12. April 2021, 18:43 Uhr

Der kleine Satz von Fermat (auch: "Der kleine Fermat") ist ein Lehrsatz der Zahlentheorie und wurde im 17. Jahrhundert vom französischen Mathematiker Pierre de Fermat formuliert. Er macht folgende Aussage über Primzahlen:

Für jede ganze Zahl [math]a \in\mathbb{Z}[/math] und jede Primzahl [math]p[/math] gilt:

[math] a^p\ mod\ p=a[/math]

Eine äquivalente Schreibweise, die auch im Folgenden vorkommen wird, ist: [math]a^p\equiv a\ mod\ p[/math].
Dabei bedeutet mod „Teilen mit Rest“ : z.B. ist [math]10\ mod\ 7=3[/math], denn [math]10/7=1\ Rest\ 3[/math].
Auf den kleinen Satz von Fermat angewendet bedeutet dies, dass der Rest bei ganzzahliger Division von [math]a^{p}/ p[/math] genau [math]a[/math] ist. Dies ist gleichbedeutend damit, dass [math](a^p-a)\ mod\ p=0[/math], d.h. dass [math]p[/math] die Zahl [math]({a\ }^p\ – a)[/math] teilt. Dies wird auch geschrieben als [math]p|a^p-a\ [/math].

Beweis

Erste Methode: Induktion

Bewiesen werden kann dieser Satz über vollständige Induktion nach [math]a[/math]: Dabei werden zwei Fälle unterschieden:
1.Fall: [math]a\geq0[/math]

Induktionsanfang: [math]a\ =\ 0[/math]
[math]p|a^p-a[/math] [math]\Longleftrightarrow[/math] [math]p|0^p-0[/math]
Diese Aussage ist wahr für alle Primzahlen [math]p[/math], da jede ganze Zahl die [math]0[/math] teilt.
Induktionsschritt:
Es gelte für ein festes, aber beliebiges [math]a[/math] und alle Primzahlen [math]p[/math]: [math]p|a^p-a\ [/math]
Nun ist zu zeigen, dass die Aussage auch für [math]a+1[/math] gilt, d.h [math]p|{(a+1)}^p-(a+1)[/math]
Durch Anwenden des binomischen Lehrsatzes und anschließendes Herausziehen des ersten und letzten Summanden erhält man:
[math]({a+1)\ }^p-(a+1)=\sum_{k=0}^{p\ }{\ \binom{p}{k}\ }a^{p-k}1^k-(a+1)\ [/math]
[math]=\binom{p}{0}\ a^p\ \ +\ \ \ \sum_{k=1}^{p-1}{\ \binom{p}{k}}{\ a}^{p-k}+\binom{p}{p}a^0-a-1[/math]
[math]=a^p\ \ +\ \ \ \sum_{k=1}^{p-1}{\ \binom{p}{k}}\ {\ a}^{p-k}+1-a-1[/math]
[math]{=a}^p-a\ \ +\ \ \ \sum_{k=1}^{p-1}{\ \binom{p}{k}\ a}^{p-k}[/math]
Der erste Summand ist nach Induktionsvoraussetzung bereits durch [math]p[/math] teilbar.Bleibt zu zeigen, dass auch der zweite Summand durch [math]p[/math] teilbar ist.


Behauptung: [math]p|\binom{p}{k}[/math] für [math]1\le k\le p-1[/math]
Nach Definition des Binomialkoeffizienten gilt:
[math]\binom{p}{k}\ =\frac{p!}{k!\ \left(p-k\right)!}[/math] und damit [math]\binom{p}{k}k!=\ \frac{p!}{\left(p-k\right)!}[/math]
[math]\Rightarrow\frac{p!}{\left(p-k\right)!}=\frac{\left(p-k\right)\ \left(p-k+1\right)\ldots\left(p-1\right)\ p}{\left(p-k\right)!}=\left(p-k+1\right)\ldots\left(p-1\right)\ p[/math]
[math]\Rightarrow p|\frac{p!}{\left(p-k\right)!}[/math] , da [math]p[/math] als Faktor vorkommt.
Folglich ist [math]\ \frac{p!}{\left(p-k\right)!}[/math] durch p teilbar und somit auch [math]\binom{p}{k}k![/math]. Da [math]k \le p-1[/math] und [math]p[/math] eine Primzahl ist und somit insbesondere teilerfremd zu allen Zahlen kleiner gleich [math]p-1[/math], ist [math]k![/math] nicht durch [math]p[/math] teilbar. Folglich muss der Primfaktor [math]p[/math] also in [math]\binom{p}{k}\ [/math] enthalten sein, da Primfaktoren nicht „aufgespaltet“ werden können, d.h [math]\binom{p}{k}\ [/math] ist durch [math]p[/math] teilbar.
Man erhält also insgesamt, dass von der Summe [math]a^p-a\ +\ \ \sum_{k=1}^{p-1}{\ \binom{p}{k}}{\ a}^{p-k}[/math] sowohl der erste Summand (nach Induktionsvoraussetzung) als auch jeder einzelne Summand des zweiten Summanden durch [math]p[/math] teilbar ist. Somit ist auch die ganze Summe durch [math]p[/math] teilbar.

2.Fall: Wir setzen [math]b:=-a \lt 0[/math] (a ist dabei wie oben weiterhin positiv).

[math]\Longrightarrow {(-a)}^p-(-a)={(-1)}^pa^p+a[/math]
Für ungerade Primzahlen (also alle außer die [math]2[/math]) gilt dann:
[math]\left(-a\right)^p-\left(-a\right)=-a^p+a=-(a^p-a)[/math]
Für positive [math]a[/math] weiß man aber schon aus dem ersten Fall, dass [math]p|a^p-a\ [/math]. Somit gilt auch [math]{-p|-(a}^p-a)[/math].
Falls [math]p = 2[/math]:
[math]\left(-a\right)^p-\left(-a\right)=a^2+a=a\ \left(a+1\right)[/math]
[math]\Longrightarrow p|{(-a)}^p-(-a)\ \Longleftrightarrow\ \ 2|a\ (a+1)[/math]
Da von zwei aufeinanderfolgenden ganzen Zahlen immer genau eine gerade ist, gilt die Aussage.

Zweite Methode: Kombinatorik

Sei [math]p[/math] eine natürliche Zahl und [math]a[/math] eine beliebige ganze Zahl. Nun sollen aus Perlen mit [math]a[/math] verschiedenen Farben Ketten mit [math]p[/math] Perlen gebildet werden. Also gibt es insgesamt [math]a^p[/math] Möglichkeiten wie eine Kette aussieht. Wenn man nun eine beliebige Kette, die an den Enden zusammengebunden ist, betrachtet, stellt man fest, dass man durch Drehen dieser, andere mögliche Ketten erhält, bis man spätestens nach [math]p[/math] Drehungen wieder bei der Ursprungskette landet. Es kann aber auch sein, dass man schon vorher wieder beim Anfangsmuster landet.
Beispiel: Bei einer Kette aus [math]p=4[/math] Perlen mit dem Muster rot-blau-rot-blau, wäre man nach zwei Drehungen schon wieder beim Ausgangsmuster (siehe obere Grafik).

Wir zeigen nun, dass wenn [math]p[/math] eine Primzahl ist, es aber nur zwei Möglichkeiten gibt nach welcher Anzahl an Drehungen man wieder am Anfang ist: Sei [math]p[/math] prim und [math]b[/math] die kleinste positive Zahl, sodass man nach [math]b[/math]-maligem rotieren wieder die Anfangskette erhält. Angenommen es gilt [math]1\lt b\lt p[/math], dann sei [math]n\cdot\ b[/math] das kleinste Vielfache von [math]b[/math], sodass [math]n\cdot\ b\gt p[/math] gilt. Daraus folgt aber auch: [math]0\lt n\cdot\ b-p\lt b[/math] und zudem überführt man die Kette durch [math]n\cdot\ b-p[/math]-maligem rotieren ebenfalls in den Anfangszustand zurück. Das ist ein Widerspruch dazu, dass [math]b[/math] die kleinste Zahl ist, für die das möglich ist. Daraus folgt, dass [math]b=1[/math] oder [math]b=p[/math] gelten muss. Es ergeben sich also diese beiden Möglichkeiten für die Anfangskette:

  • Alle Perlen besitzen dieselbe Farbe [math]\left(b=1\right)[/math]
  • Es existiert mindestens eine andersfarbige Perle [math]\left(b=p\right)[/math]


Im ersten Fall lässt sich durch Rotation keine neue Kette bilden. Es gibt [math]a[/math] verschiedene solcher einfarbigen Ketten. Die Anzahl der gemischtfarbigen Ketten [math]\left(b=p\right)[/math] ist [math]a^p-a[/math]. Nach obiger Überlegung lassen sich diese aber in Gruppen zu je [math]p[/math] zusammenfassen, und zwar je eine Anfangskette und die [math]p-1[/math] durch-Rotation-entstehenden Ketten (beim [math]p[/math]-ten Mal erhält man ja wieder die Ursprungskette). Also gilt, dass die Anzahl der gemischtfarbigen Ketten [math](a^p-a)[/math] durch [math]p[/math] teilbar ist, was zu zeigen war.

Fermat'scher Primzahltest

Folgerungen aus dem kleinen Satz von Fermat

  • Wenn der Satz für eine Zahl [math]p[/math] nicht erfüllt ist, kann die Zahl [math]p[/math] auch keine Primzahl sein (Kontraposition des Satzes).
  • Es folgt jedoch nicht, dass nur, weil eine Zahl [math]p[/math] diese Gleichung erfüllt, diese Zahl auch zwingend eine Primzahl ist. Denn der kleine Satz von Fermat ist nur eine Implikation in eine Richtung, die Rückrichtung gilt im Allgemeinen nicht:

Beispiel: [math]a = 4, p = 15 [/math]
[math]4^{15}\ \ mod\ 15=4[/math] , aber [math]15=5\cdot3[/math] ist keine Primzahl.
Diese Folgerungen bilden die Grundlage für viele Primzahltests. Ein Primzahltest, der den kleinen Satz von Fermat unmittelbar anwendet, hat folgendes Algorithmus.

Algorithmus

1. Schritt: Sei [math]p[/math] eine Zahl, von der getestet werden soll, ob sie eine Primzahl ist.
2. Schritt: Berechne (beliebig oft) für zufällig gewählte [math]a[/math] den Ausdruck [math]{\ a}^p\ \ mod\ p[/math].
3. Schritt: Falls man dabei einmal als Ergebnis [math]{\ a}^p\ \ mod\ p\neq a[/math] erhält, so kann nach der ersten Folgerung [math]p[/math] ganz sicher keine Primzahl sein.
4. Schritt: Falls das Ergebnis immer [math]a^p\ \ mod\ p=a[/math] ist, so lässt sich keine sichere Aussage treffen. Die zu testende Zahl erfüllt eine notwendige Bedingung dafür, prim zu sein, jedoch keine hinreichende. Die Aussage ist dann „wahrscheinlich prim“. Eine genaue Wahrscheinlichkeit kann dabei im Übrigen nicht angegeben werden.

Beispiele:
[math]a = 2, p = 3[/math]
[math]{{\ a}^p\ \ mod\ p=2}^3\ mod\ 3=8\ mod\ 3=\ 2[/math]
[math]\Longrightarrow 3[/math] ist „wahrscheinlich prim“.

[math]a = 2, p = 4[/math]
[math]{{\ a}^p\ \ mod\ p=2}^4\ mod\ 3=16\ mod\ 3=\ 1\neq2[/math]
[math]\Longrightarrow 4[/math] ist sicher keine Primzahl.
Bemerkung: In der Praxis haben die zu testenden Zahlen meist mindestens mehrere hundert Stellen und für die Berechnung von [math]{\ a}^p\ \ mod\ p[/math] gibt es weitaus effizientere Möglichkeiten als zuerst die Potenz durch [math]p[/math]-malige Multiplikation von [math]a[/math] zu erhalten und dann modulo [math]p[/math] zu rechnen.

Carmichael Zahlen

Die offensichtliche Schwäche des obigen Tests ist es, dass er nicht mit absoluter Sicherheit sagen kann, ob eine Zahl prim ist. Das wäre in der Praxis nicht weiter schlimm, wenn es eine feste Irrtumswahrscheinlichkeit [math]P \lt 1[/math] gäbe. Dann müsste man den Test nur oft genug hintereinander mit zufällig gewählten a ausführen und durch die Potenzierung der Irrtumswahrscheinlichkeit könnte die insgesamte Irrtumswahrscheinlichkeit des Tests nach mehreren Durchläufen beliebig klein gemacht werden. Doch leider gibt es für den oben vorgestellten Test keine obere Schranke < 1 für die Irrtumswahrscheinlichkeit. Grund dafür sind die sogenannten Carmichael-Zahlen. Diese haben folgende Eigenschaft: Sie erfüllen den obigen Primzahltest für alle ganzen Zahlen [math]a[/math], die teilerfremd zu der Carmichael-Zahl [math]p[/math] sind, d.h. der größte gemeinsame Teiler von [math]a[/math] und [math]p[/math] muss 1 sein.
Die kleinste Carmichael-Zahl ist [math]561 = 3 \cdot11\ \cdot17[/math]. D.h. für alle Basen [math]a[/math], die in ihrer Primfaktorzerlegung weder die 3 noch die 11 noch die 17 enthalten, gilt: [math]{\ a}^{561}\ \ mod\ 561 = a[/math].

Insbesondere für Carmichael-Zahlen mit größeren Primfaktoren (die 3 bildet hier eine Ausnahme) ist dann die Wahrscheinlichkeit, dass beim Ausführen des obigen Tests mit z.B. 10 verschiedenen [math]a[/math] jedes Mal „wahrscheinlich prim“ und somit auch insgesamt „wahrscheinlich prim“ herauskommt, sehr hoch, obwohl es sich nicht um eine Primzahl handelt. Die Carmichael-Zahlen werden deshalb auch fermatsche Pseudoprimzahlen genannt. Von diesen Carmichael-Zahlen gibt es zwar nur „wenige“, aber doch unendlich viele (auf den Beweis verzichten wir an dieser Stelle), d.h. in unendlich vielen Fällen liefert der obige Test höchstwahrscheinlich ein falsches Ergebnis. Um diese unschöne Eigenschaft zu vermeiden, gibt es den sogenannten Miller-Rabin-Test, der vor allem in der Kryptographie zum Einsatz kommt und im nächsten Abschnitt vorgestellt wird.

Der Miller-Rabin Test

Der Miller-Rabin Test ist ein probabilistischer Primzahltest, der als optimierte Version des klassischen Primzahltestes betrachtet werden kann. Ähnlich wie der Fermat’sche Test wird überprüft, ob eine Eigenschaft von Primzahlen auch für eine gegebene Zahl gilt. Dafür definiert man zuerst die starken Pseudoprimzahlen.

Starke Pseudoprimzahlen

Sei [math]n\gt 2[/math] eine natürliche, ungerade Zahl. [math]n[/math] lässt sich eindeutig schreiben als [math]2^s\cdot d+1[/math], wobei [math]s,d[/math] natürliche Zahlen sind und [math]d[/math] ungerade. Sei nun [math]a\lt n[/math] eine natürliche Zahl. Man nennt [math]n[/math] eine starke Pseudoprimzahl zur Basis [math]a[/math], wenn [math]n[/math] eine der folgenden Bedingungen erfüllt:

  • [math]a^d\equiv1\ mod\ n[/math]
  • [math]a^{2^rd}\equiv-1\ mod\ n[/math] für eine beliebige, natürliche Zahl [math]0\le\ r\lt s[/math]

Betrachten wir folgende zwei Beispiele zur Veranschaulichung:
1. Beispiel
[math]n=121[/math] ist eine starke Pseudoprimzahl zur Basis [math]a=3[/math], denn:
[math]n=2^3\cdot15+1[/math], also gilt [math]s=3[/math] und [math]d=15[/math].
Man merkt, dass die erste Bedingung erfüllt wird, da [math]3^{15}\equiv1\ mod\ 121[/math] gilt.
2. Beispiel
[math]n=325[/math] ist eine starke Pseudoprimzahl zur Basis [math]a=7[/math], denn:
[math]n=2^2\cdot81+1[/math], also gilt [math]s=2[/math] und [math]d=81[/math].
Man stellt fest, dass die erste Bedingung nicht erfüllt wird: [math]7^{81}\ mod\ 325=307\neq1[/math] (in diesem Fall ist [math]r=0[/math])
Wir überprüfen nun, dass die zweite Bedingung tatsächlich erfüllt wird:
[math]0\le r\lt s=2[/math], also [math]r\in\left\{0,\ 1\right\}[/math].
Für [math]r=0[/math] gilt: [math]7^{81}\ mod\ 325=307\neq-1[/math]
Für [math]r=1[/math] gilt: [math]7^{2^1\cdot81}\ mod\ 325=7^{162}\ mod\ 325=324=-1[/math]
Somit ist die zweite Bedingung für [math]r=1[/math] erfüllt.

Lemma

Jede Primzahl ist auch eine starke Pseudoprimzahl zu jedwelcher Basis.

Beweis: Eine notwendige Erkenntnis für den Beweis des Lemmas ist folgende:

Wenn [math]n[/math] eine Primzahl ist, dann hat das Polynom [math]X^2-1[/math] über [math]\mathbb{Z}/n\mathbb{Z}[/math] nur die beiden Wurzeln [math]x=1[/math] und [math]x=-1[/math].

Diese Aussage folgt direkt aus der Tatsache, dass die Anzahl der Nullstellen eines Polynoms über einem Körper höchstens gleich der Grad des Polynoms ist. Da [math]X^2-1[/math] die beiden trivialen Wurzeln 1 und -1 über [math]\mathbb{Z}/n\mathbb{Z}[/math] hat, gibt es keine weiteren Nullstellen.

Sei nun [math]n=2^s\cdot d+1[/math] eine ungerade Primzahl, [math]s,d\in\mathbb{N}[/math], [math]d[/math] ungerade und [math]a\in\mathbb{N},\ a\lt n[/math].
Da [math]a\lt n[/math] gilt nach dem Kleinen Satz von Fermat:

[math]a^{2^sd}\equiv1\ mod\ n[/math]

Betrachtet man die Folge [math]a^{2^sd},\ \ a^{2^{s-1}d},\ \ldots,\ \ a^{2d},\ a^d[/math] so merkt man, dass jedes Glied, außer dem ersten, die Wurzel des vorherigen Folgengliedes ist. Da

[math]a^{2^sd}-1=\left(a^{2^{s-1}d}\right)^2-1\equiv0\ \ mod\ n[/math]
gilt: [math]a^{2^{s-1}d}\equiv1\ mod\ n\ \ \left(1\right)[/math] oder [math]a^{2^{s-1}d}\equiv-1\ \ mod\ n\ \ \left(2\right)[/math]

Falls [math]\left(2\right)[/math] richtig ist, so ist die zweite Bedingung bereits erfüllt mit [math]r=s-1[/math]. Falls [math]\left(1\right)[/math] richtig ist, so wendet man wiederholt dieselben Schritte an bis entweder eins der Glieder kongruent modulo [math]n[/math] mit [math]-1[/math] ist oder alle Folgenglieder, insbesondere der letzte, kongruent modulo [math]n[/math] mit [math]1[/math] sind.

Der Miller-Rabin Test

Mittels der vorher bewiesenen Eigenschaft der Primzahlen ergibt sich folgender Algorithmus, bekannt als der Miller-Rabin Test:
Eingaben:

  • eine natürliche, ungerade Zahl n, die getestet wird
  • eine natürliche Zahl k, die die Anzahl der Wiederholungen des Testes angibt

Ausgabe:

  • „zusammengesetzt”, wenn n nicht prim ist
  • „wahrscheinlich prim“ sonst

Schritte:

  1. Schreibe [math]n[/math] als [math]2^s\cdot d+1[/math] mit [math]s,d\in\mathbb{N}[/math], [math]d[/math] ungerade.
  2. Wähle eine Zahl [math]a\in\left\{1,\ \ldots,\ \ n-1\right\}[/math] zufällig und gleichverteilt.
  3. Teste ob [math]n[/math] eine starke Pseudoprimzahl zur Basis [math]a[/math] ist.
  4. Wurde eine Zahl [math]a[/math] gefunden, für die [math]n[/math] die Eigenschaft nicht erfüllt, so gebe “zusammengesetzt“ aus und stoppe das Verfahren. Wenn nicht, dann wiederhole die vorherigen Schritte, insgesamt nicht mehr als k mal.

Hat die gegebene Zahl beim k-maligen Durchlauf den Test bestanden, so gebe “wahrscheinlich prim“ aus.
Grundlegend für den angegebenen Algorithmus ist die Tatsache, dass jede Zahl, die keine starke Pseudoprimzahl zu einer beliebigen Basis [math]a[/math] ist, keine Primzahl sein kann. Der Test besteht nun darin, zu der zu prüfenden Zahl [math]n[/math] eine Basis [math]a[/math] zu finden, so dass [math]n[/math] keine starke Pseudoprimzahl zur Basis [math]a[/math] ist und somit keine Primzahl. Findet man eine solche Zahl [math]a[/math], so nennt sich diese ein Zeuge der Zerlegbarkeit von [math]n[/math].

Für zusammengesetzte Zahlen [math]n[/math] lässt sich immer wenigstens ein Zeuge ihrer Zerlegbarkeit finden, aber nicht alle Zahlen [math]a[/math] eignen sich dazu (siehe das erste Beispiel). Daher muss man [math]n[/math] für mehrere Basen testen. Besteht die Zahl [math]n[/math] bei jedem Durchlauf den Test, so kann nur eine Wahrscheinlichkeitsaussage getroffen werden. Die Fehlerwahrscheinlichkeit, also die Wahrscheinlichkeit, dass die getestete Zahl keine Primzahl ist, nimmt ab je häufiger die Zahl [math]n[/math] den Test besteht. In der Praxis testet man die Zahl [math]n[/math] auf hinreichend vielen Basen [math]a[/math], so dass die Fehlerwahrscheinlichkeit vernachlässigbar klein ist.

Beispiele

I. Führen wir nun den Test [math]k=2[/math] mal für die Zahl [math]n=221[/math] durch.

1. Schritt: [math]n-1=220=2^2\cdot55\ \ \ \ [/math]
Also [math]s=2[/math] und [math]d=55[/math].


Erster Durchlauf:

2. Schritt: Wir wählen die Basis [math]a=174[/math].
3. Schritt: Wir testen, ob [math]n[/math] eine starke Pseudoprimzahl zur Basis [math]a[/math] ist:
[math]a^d\ mod\ n={174}^{55}\ mod\ 221=47\ \neq-1\ und\ \neq1[/math]
[math]a^{2d}\ mod\ n={174}^{110}\ mod\ 221=220=-1[/math]
Für [math]r=1[/math] gilt also [math]a^{2^rd}\equiv-1\ mod\ n[/math], also könnte [math]221[/math] prim sein.


Zweiter Durchlauf:

2. Schritt: Wir wählen die Basis [math]a=137[/math].
3. Schritt: Wir testen, ob [math]n[/math] eine starke Pseudoprimzahl zur Basis [math]a[/math] ist:
[math]a^d\ mod\ n={137}^{55}\ mod\ 221=188\neq-1\ und\ \neq1[/math]
[math]a^{2d}\ mod\ n={137}^{110}\ mod\ 221=205\neq-1[/math]
[math]a=137[/math] ist ein Zeuge der Zerlegbarkeit von [math]n=221[/math], also ist [math]221[/math] keine Primzahl.


II. Im Unterschied zu dem Fermat’schen Primzahltest filtert der Miller-Rabin Test auch die Carmichaelzahlen aus. Betrachten wir dafür die kleinste Carmichaelzahl [math]n=561[/math]. Wir führen den Test ein einziges Mal durch und wählen als Basis [math]a=2[/math].

1.Schritt: [math]n-1=560=2^4\cdot35[/math]
Also [math]s=4[/math] und [math]d=35[/math].
2. Schritt: [math]a=2[/math]
3. Schritt: Wir testen, ob [math]n[/math] eine starke Pseudoprimzahl zur Basis [math]a[/math] ist:
  • [math]a^d\ mod\ n=2^{35\ }\ mod\ \ 561=263\neq-1\ und\ \neq1[/math]
  • [math]a^{2d}\ mod\ n=2^{70}\ mod\ 561=166\neq-1[/math]
  • [math]a^{2^2d}\ mod\ n=2^{140}\ mod\ 561=67\neq-1[/math]
  • [math]a^{2^3d}\ mod\ n=2^{280}\ mod\ 561=1\neq-1[/math]

Somit erfüllt [math]n=561[/math] für die Basis [math]a=2[/math] keine der beiden Bedingungen einer starken Pseudoprimzahl und ist daher auch keine Primzahl.

Quellen

  1. http://www.austromath.at/medienvielfalt/materialien/krypto/lernpfad/content/k_prim_l06.htm
  2. https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test
  3. http://page.math.tu-berlin.de/~kant/teaching/hess/krypto-ws2007/miller-rabin.pdf
  4. https://www.youtube.com/watch?v=YqHZQmbDw6s
  5. https://de.wikibooks.org/wiki/Beweisarchiv:_Zahlentheorie:_Elementare_Zahlentheorie:_Kleiner_Satz_von_Fermat

Autoren

Max Jungmann
Robin Klotzbücher
Mara-Eliana Popescu

Abgerufen von „https://funfacts.mathi.uni-heidelberg.de/index.php?title=Der_kleine_Satz_von_Fermat&oldid=3612“