Kryptologie/Fermat-Test (Primzahltest 2)

Einleitung

Der Fermat-(Primzahl-)Test beruht auf dem kleinen Satz von Fermat. Dieser Satz liefert uns eine Eigenschaft, die alle Primzahlen erfüllen.

Satz (Kleiner Satz von Fermat)

Primzahl, Teilerfremdheit, Kongruenz und Teilbarkeit
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.
Teilerfremdheit
Zwei ganze Zahlen $a$ und $b$, wobei mindestens einer der beiden Zahlen ungleich Null ist, heißen teilerfremd, wenn $ggT(a,b)=1$. Betrachten wir mehr als zwei Zahlen, dann nennen wir diese paarweise teilerfremd, wenn je zwei beliebige von diesen Zahlen zueinander teilerfremd sind.
Kongruenz
Seien $a,b\in \mathbb {Z}$ und $m\in \mathbb {N}$, dann gilt $a\equiv b{\bmod {m}}\Leftrightarrow m\mid (a-b)$.
Teilbarkeit
Eine ganze Zahl $a$ teilt eine ganze Zahl $b$ genau dann, wenn es eine ganze Zahl $n$ gibt, für die $a\cdot k=b$ ist. Wir schreiben $a\mid b$.

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}}$.

Bemerkung: Durch Multiplikation im Restklassenring mit $a$ gilt auch die folgende Äquivalenz: $a^{p-1}\equiv 1{\bmod {p}}\Leftrightarrow a^{p}\equiv a{\bmod {p}}$.

Beweis Satz (Kleiner Satz von Fermat)

Voraussetzung

$p$ prim und $a\in \mathbb {N}$ mit $ggT(p,a)=1$.

Zu zeigen

$a^{p}\equiv a{\bmod {p}}$

Beweis (Vollständige Induktion)

Bemerkung: Bei der vollständigen Induktion wird eine Aussage in der Regel für alle natürlichen Zahlen bewiesen. Dabei beginnt man bei einem Startwert (meist $0$ oder $1$) und zeigt, dass die Aussage für diesen Startwert gilt. Man nennt dies den Induktionsanfang. Im Induktionsschritt wird anschließend gezeigt, dass wenn die Aussage für eine Zahl gilt, dann gilt sie auch für die nächstgrößere Zahl.

Induktionsanfang

Wir zeigen zunächst, dass die Aussage für $a=0$.

$0^{p}\equiv 0{\bmod {p}}$

$\Leftrightarrow p\mid 0^{p}-0$

$\Leftrightarrow p\mid 0$.

Induktionsschritt

Wir haben nun ein solches $a\in \mathbb {N}$ gefunden, für das $a^{p}\equiv a\mod p$ gilt, also ist

$p\mid a^{p}-a$ (Induktionsvoraussetzung)

Nun zeigen wir, dass die Behauptung auch für den Nachfolger eines solchen $a$ gilt, nämlich

$p\mid (a+1)^{p}-(a+1)$

Wir verwenden hierzu den binomischen Lehrsatz:

$(a+1)^{p}-(a+1)=a^{p}+{p \choose 1}a^{p-1}+\ldots +{p \choose p-1}a+1-(a+1)$

Betrachten wir nun den Binomialkoeffizienten genauer:

${p \choose k}={\frac {p\cdot (p-1)\cdots (p-k+1)}{1\cdot 2\cdots k}}$

$p$ taucht für $1\leq k\leq p-1$ nur im Zähler auf.

Da $p$ prim ist, treten im Nenner keine Teiler von $p$ auf.

Die Binomialkoeffizienten sind daher alle durch $p$ teilbar.

Damit folgt

$(a+1)^{p}-(a+1)\equiv a^{p}+1-(a+1)=a^{p}-a$

und nach Induktionsvoraussetzung gilt

$p\mid a^{p}-a$.

Somit haben wir gezeigt, dass

$p\mid (a+1)^{p}-(a+1)$ für einen beliebigen Nachfolger von $a$ gilt.

Fermat-Test

Die Idee des Fermat-Tests ist es, durch die Umkehrung des kleinen fermatschen Satzes, Zahlen daraufhin zu prüfen, ob sie zusammengesetzt sind.

Algorithmus des Fermat-Tests

Sei $n\in \mathbb {N}$ ungerade. Ziel ist es zu ermitteln, ob $n$ zusammengesetzt ist.

1. Wähle eine zu $n$ teilerfremde Basis $a$
2. Berechne $a^{n-1}{\bmod {n}}$
   • Gilt $a^{n-1}\equiv 1{\bmod {n}}$, dann ist $n$ mit hoher Wahrscheinlichkeit prim und sonst zusammengesetzt
   • Gilt $a^{n-1}\not \equiv 1{\bmod {n}}$ (Fall 2), dann ist $n$ zusammengesetzt

Im ersten Fall erfüllt $n$ die vom kleinen fermatschen Satz formulierte Bedingung an Primzahlen und im zweiten Fall nicht.

Nur, weil $n$ die Voraussetzung für Primzahlen des kleinen fermatschen Satzes erfüllt, ist damit noch nicht gezeigt, dass $n$ eindeutig eine Primzahl ist. $n$ kann stattdessen eine zusammengesetzte Zahl sein, die auch die untersuchte Eigenschaft von Primzahlen erfüllt. Tritt jedoch Fall 2 ein, so kann man also sicher sagen, dass $n$ zusammengesetzt und somit nicht prim ist.

Beispiele des Fermat-Tests

Beispiel 1

Primzahl und Teilerfremdheit
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.
Teilerfremdheit
Zwei ganze Zahlen $a$ und $b$, wobei mindestens einer der beiden Zahlen ungleich Null ist, heißen teilerfremd, wenn $ggT(a,b)=1$. Betrachten wir mehr als zwei Zahlen, dann nennen wir diese paarweise teilerfremd, wenn je zwei beliebige von diesen Zahlen zueinander teilerfremd sind.

Seien $n=7$ und $a=3$. Die beiden Zahlen sind teilerfremd, da $ggT(3,7)=1$.

$a^{n-1}{\bmod {n}}$

$\Rightarrow 3^{7-1}{\bmod {7}}$

$\Leftrightarrow 3^{6}{\bmod {7}}$

$\Rightarrow 3^{6}\equiv 1{\bmod {7}},$ da $3^{6}=729=104\cdot 7+1$

Somit ist $n=7$ prim oder zusammengesetzt.

Beispiel 2

Seien $n=9$ und $a=2$. Die beiden Zahlen sind teilerfremd, da $ggT(2,9)=1$.

$a^{n-1}{\bmod {n}}$

$\Rightarrow 2^{9-1}{\bmod {9}}$

$\Rightarrow 2^{8}\equiv 4{\bmod {9}},$ da $2^{8}=256=28\cdot 9+4$

$\Rightarrow 2^{8}\not \equiv 1{\bmod {9}}$

Somit ist $n=9$ zusammengesetzt.

Bemerkung: Wir können anhand von Beispiel 2 erkennen, dass eine Basis $a$, für die $a^{n-1}\not \equiv 1{\bmod {n}}$, nicht zwangsläufig ein Teiler von $n$ ist, denn es gilt $2\not \mid 9$.

Fermat-Test als Primzahltest

Der Fermat-Test eignet sich in der Praxis nicht als Primzahltest. Aus $a^{n-1}\equiv 1{\bmod {n}}$ folgt nämlich nicht direkt, dass $n$ prim ist. Es gibt also natürliche Zahlen $n$, die keine Primzahlen sind und die Eigenschaft $a^{n-1}\equiv 1{\bmod {n}}$ dennoch erfüllen. Es gibt zwei Arten von solchen Zahlen: Fermatsche Pseudoprimzahlen zur Basis $a$ und Carmichael-Zahlen.

Fermatsche Pseudoprimzahl

Definition Fermatsche Pseudoprimzahl

Primzahl, Teilerfremdheit, Kongruenz und Probedivision
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.
Teilerfremdheit
Zwei ganze Zahlen $a$ und $b$, wobei mindestens einer der beiden Zahlen ungleich Null ist, heißen teilerfremd, wenn $ggT(a,b)=1$. Betrachten wir mehr als zwei Zahlen, dann nennen wir diese paarweise teilerfremd, wenn je zwei beliebige von diesen Zahlen zueinander teilerfremd sind.
Kongruenz
Seien $a,b\in \mathbb {Z}$ und $m\in \mathbb {N}$, dann gilt $a\equiv b{\bmod {m}}\Leftrightarrow m\mid (a-b)$.
Probedivision
Sei $n\in \mathbb {N}$ ungerade (für $n<2$ gerade ist $2$ Primteiler). Ziel ist es zu ermitteln, ob $n$ prim oder zusammengesetzt ist. Berechne ${\sqrt {n}}$ Ist bekannt, dass ${\sqrt {n}}$ prim, dann ist $n$ zusammengesetzt und die Probedivision abgeschlossen Andernfalls muss der Algorithmus fortgeführt werden Wähle eine Primzahl $p\leq {\sqrt {n}}$ Wurde die Probedivision noch nicht auf $n$ angewandt, wähle $p=2$ Ist dies mindestens der zweite Durchlauf von Schritt 2 auf $n$, dann wähle die nächstgrößere Primzahl zu diesem Durchlauf Ermittle, ob die Primzahl $p$ ein Teiler von $n$ ist Gilt $p\mid n$, dann ist $n$ zusammengesetzt und die Probedivision abgeschlossen Gilt $p\not \mid n$, dann und es gibt ein $p\leq {\sqrt {n}}$, welches noch nicht getestet wurde, dann wiederhole ab Schritt 2 Wurden alle $p\leq {\sqrt {n}}$ durchlaufen und für all diese gilt $p\not \mid n$, so ist $n$ prim und die Probedivision abgeschlossen

Eine natürliche Zahl n wird fermatsche Pseudoprimzahl zur Basis $a$ genannt, wenn sie eine zusammengesetzte Zahl ist, die sich in Bezug auf eine zu $n$ teilerfremde Basis $a$ wie eine Primzahl verhält. Dies ist der Fall, wenn nämlich die Kongruenz

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

für die zu $n$ teilerfremde Zahl $a$ erfüllt ist.

Beispiel Pseudoprimzahl

Sei $n=4$, somit $n$ ist keine Primzahl, da wir mit der Probedivision feststellen können, dass $2\mid 4$ gilt. Somit hat $4$ einen Primteiler $p\leq {\sqrt {n}}$.

Nun wenden wir den Fermat-Test an und wählen $a=5$.

$n$ und $a$ sind also teilerfremd, d.h. $ggT(4,5)=1$.

$a^{n-1}{\bmod {n}}$

$\Rightarrow 5^{4-1}{\bmod {4}}$

$\Rightarrow 5^{3}{\bmod {4}}$, da $5^{3}=125=31\cdot 4+1$

$\Rightarrow 5^{3}\equiv 1{\bmod {4}}$

Also ist $n=4$ nach einmaligen anwenden des Fermat-Test mit hoher Wahrscheinlichkeit eine Primzahl.

Bedeutung von Pseudoprimzahlen für den Fermat-Test

Es gibt unendlich viele Pseudoprimzahlen. Diese sind jedoch wesentlich seltener als Primzahlen. So kommt beispielsweise bezüglich Basis $a=2$ im Zahlenraum bis $10^{10}$ auf jeweils $30.577$ Primzahlen nur eine Pseudoprimzahl. Den zugehörigen Beweis ersparen wir uns an dieser Stelle, da dieser zu weit von unserem eigentlichen Thema wegführt.

Wir könnten annehmen, dass man, durch das wiederholte Anwenden des Fermat-Tests auf die selbe Zahl $n$ mit wechselnder Basis $a$, mit hoher Wahrscheinlichkeit davon ausgehen kann, dass $n$ prim ist, wenn die Kongruenz $a^{n-1}\not \equiv 1{\bmod {n}}$ (Fall 2) nicht eintritt. Dies erscheint logisch, da es sich bei den einzelnen Durchführungen um unabhängige Ereignisse handelt, deren Wahrscheinlichkeit nach dem Multiplikationssatz multipliziert werden.

Wir werden mithilfe des dritten Primzahltests jedoch zeigen, dass Pseudoprimzahlen existieren, die für fast alle Basen die Kongruenz $a^{n-1}\equiv 1{\bmod {n}}$ erfüllen. Dies sind die bereits erwähnten Carmichael-Zahlen. Ein mehrfaches Ausführen des Fermat-Tests mit festem $n$ und wechselnder Basis ist daher nicht zielführend.

Lernaufgabe

Aufgabe

Fermat-Test
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

Prüfen Sie mit dem Fermat-Test für eine oder mehrere der drei Basen $2,31$ und $223$, ob die Zahl $561$ zusammengesetzt ist.

Lösung
Sei $a=2$. $2^{560}\equiv 1{\bmod {5}}61$ Sei $a=31$. $31^{560}\equiv 1{\bmod {5}}61$ Sei $a=223$. $2^{223}\equiv 1{\bmod {5}}61$ Keiner der drei Testdurchläufe lässt darauf schließen, dass $561$ zusammengesetzt ist und wir gehen mit hoher Wahrscheinlichkeit davon aus, dass $561$ prim ist.

Lernempfehlung

Kursübersicht

Übergeordnete Lerneinheit
7.1: Schlüsselerzeugung des RSA-Verschlüsselungsverfahrens
Vorherige Lerneinheit	Aktuelle Lerneinheit	Empfohlene Lerneinheit
7.1.2: Probedivision (Primzahltest 1)	7.1.3: Fermat-Test (Primzahltest 2)	7.1.4: Miller-Rabin-Test (Primzahltest 3)