4.2 Endliche Körper
4.2.1 Rechnen mit Restklassen
Sei \(n\ge 1\) eine natürliche Zahl. Wir betrachten die Menge
mit \(n\) Elementen, die wir mit den Symbolen \(\overline{a}\) für \(a\) in den natürlichen Zahlen von \(0\) bis \(n-1\) bezeichnen. (Die Wahl der Bezeichnung – \(\left.\mathbb Z\middle /n\right.\) – wird im zweiten Semester noch klarer werden. Andere übliche Bezeichnungen sind \(\left.\mathbb Z\middle / (n)\right.\) und \(\left.\mathbb Z\middle / n\mathbb Z\right.\).)
Wir nennen die Elemente von \(\left.\mathbb Z\middle /n\right.\) auch Restklassen (modulo \(n\)).
Wir definieren die folgenden Verknüpfungen (für \(a,b\in \{ 0, \dots , n-1\} \)):
Wie üblich lassen wir den Multiplikationspunkt \(\cdot \) manchmal weg. Es ist klar, dass sowohl für \(+\) als auch für \(\cdot \) das Kommutativgesetz gilt.
Für \(n=12\) erhalten wir zum Beispiel
\[ \overline{9} + \overline{6} = \overline{3}. \](Wie beim »Rechnen« auf der Uhr: \(6\) Stunden nach \(9\) Uhr ist es \(3\) Uhr, denn ab \(12\) beginnt die Zählung wieder bei \(1\).)
Es gilt für \(n=17\):
\[ \overline{3} \cdot \overline{6} = \overline{1}\quad \text{in}\ \left.\mathbb Z\middle /17\right.. \]Für alle \(n\), und alle \(a\in \left.\mathbb Z\middle /n\right.\) gilt \(\overline{0}+ a = a\), also ist \(\overline{0}\) ein neutrales Element für \(+\). Es gilt \(\overline{0}\cdot a = \overline{0}\). Ferner gilt \(\overline{1}\cdot a=a\), also ist \(\overline{1}\) ein neutrales Element für \(\cdot \).
Sei \(n=2\). Dann ist \(\overline{1}+ \overline{1} = \overline{0}\), und wir sehen, dass die Operationen \(+\) und \(\cdot \) auf \(\left.\mathbb Z\middle /2\right.\) gerade die Addition und Multiplikation liefern, die wir auf \(\mathbb F_2\) definiert haben.
Sei \(n=3\). In diesem Fall kann man \(\left.\mathbb Z\middle /3\right.\) mit den Operationen \(+\) und \(\cdot \) mit dem Körper \((\mathbb F_3, +, \cdot )\) identifizieren.
Wir bezeichnen mit \(\pi \colon \mathbb Z\to \left.\mathbb Z\middle /n\right.\) die Abbildung, die \(x\in \mathbb Z\) abbildet auf \(\overline{r}\), wobei \(r\) der Rest von \(x\) bei Division durch \(n\) ist. Diese Abbildung nennt man manchmal die kanonische Projektion. Offenbar handelt es sich um eine surjektive Abbildung. Natürlich ist \(\pi \) nicht injektiv; es gilt genau dann \(\pi (a) = \pi (b)\), wenn \(a\) und \(b\) denselben Rest bei Division durch \(n\) haben, oder äquivalent ausgedrückt: wenn \(a-b\) durch \(n\) teilbar ist. Insbesondere gilt \(\pi (a)=0\) genau dann, wenn \(a\) ein Vielfaches von \(n\) ist.
Sehr nützlich ist, dass die Abbildung \(\pi \) mit den Additionen und Multiplikationen auf beiden Seiten verträglich ist, und zwar im folgenden Sinne:
Erstens können wir die Definition der Addition und Multiplikation auf \(\left.\mathbb Z\middle /n\right.\) auch schreiben als
Zweitens gilt:
Seien \(x, x^\prime \in \mathbb Z\). Dann gilt
Wir schreiben die Division durch \(n\) mit Rest aus als
Es gilt also \(\pi (x) = r\), \(\pi (x^\prime ) = r^\prime \).
Es ist eine offensichtliche Eigenschaft der Division mit Rest durch \(n\), dass sich der Rest nicht ändert, wenn wir den Dividenden (die Zahl, die durch \(n\) geteilt wird) um ein Vielfaches von \(n\) abändern.
Also gilt
wobei die erste Gleichheit aus (4.1) folgt, und die zweite, weil sich \(x\) und \(r\), beziehungsweise \(x^\prime \) und \(r^\prime \) nur um Vielfache von \(n\) unterscheiden.
Weil \(xx^\prime = (qq^\prime n + qr^\prime + q^\prime r)n + rr^\prime \) sich ebenfalls um ein Vielfaches von \(n\) von \(rr^\prime \) unterscheidet, können wir für \(\cdot \) ganz analog rechnen:
Dieses Lemma erlaubt es uns, ohne weiteren Aufwand zu zeigen, dass die Verknüpfungen \(+\) und \(\cdot \) auf \(\left.\mathbb Z\middle /n\right.\) assoziativ und kommutativ sind und dass das Distributivgesetz gilt. Seien nämlich \(x, y, z\in \left.\mathbb Z\middle /n\right.\), und seien \(\dot{x}, \dot{y}, \dot{z} \in \mathbb Z\) mit \(\pi (\dot{x}) = x\), \(\pi (\dot{y}) = y\), \(\pi (\dot{z}) = z\) (wir könnten \(x\), \(y\), \(z\) als Elemente von \(\mathbb Z\) auffassen und \(\dot{x} = x\) usw. wählen, aber es ist für das Weitere egal; wichtig ist nur, dass so eine Wahl überhaupt möglich ist, d.h. dass \(\pi \) surjektiv ist).
Dann gilt zum Beispiel
Diese Gleichungskette ist zwar lang, aber die einzelnen Schritte sind ganz formal. Wir benutzen mehrfach das Lemma, und in der Mitte dann das Assoziativgesetz für die Addition in \(\mathbb Z\). Wenn wir alle \(+\)-Zeichen in dieser Rechnung durch \(\cdot \) ersetzen, dann ergibt sich ein Beweis des Assoziativgesetzes der Multiplikation. Die beiden Kommutativgesetze und das Distributivgesetz können nach exakt dem gleichen Schema bewiesen werden.
Wir haben oben schon festgestellt, dass \(\overline{0}\in \left.\mathbb Z\middle /n\right.\) ein neutrales Element bezüglich \(+\) und \(\overline{1}\in \left.\mathbb Z\middle /n\right.\) ein neutrales Element bezüglich \(\cdot \) ist. Für \(a\in \mathbb Z\) ist \(\pi (-a)\) ein additives Inverses von \(\pi (a)\), denn
Das einzige Axiom, das aus der Liste der Körperaxiome noch fehlt, ist die Existenz von multiplikativen Inversen. Hier zeigt sich eine interessante Situation:
Anders als in \(\mathbb Z\) haben manchmal auch Elemente \(\ne \overline{1}\) (und \(\ne -\overline{1}\)) ein multiplikatives Inverses. Wir hatten beispielsweise oben schon festgehalten, dass in \(\left.\mathbb Z\middle /17\right.\) gilt, dass \(\overline{3}\cdot \overline{6}=\overline{1}\). Wir haben auch schon gesehen, dass \(\left.\mathbb Z\middle /2\right.\) der Körper \(\mathbb F_2\) und \(\left.\mathbb Z\middle /3\right.\) der Körper \(\mathbb F_3\) ist.
Im allgemeinen ist \(\left.\mathbb Z\middle /n\right.\) kein Körper; zum Beispiel gilt in \(\left.\mathbb Z\middle /6\right.\): \(\overline{2}\ne \overline{0}\), \(\overline{3}\ne \overline{0}\), aber \(\overline{2}\cdot \overline{3} = \overline{0}\).
Diese Beobachtung können wir leicht verallgemeinern: Wenn \(n = ab\) mit \(0 {\lt} a, b {\lt} n\) gilt, dann gilt \(\overline{a}\overline{b}=\overline{0}\) in \(\left.\mathbb Z\middle /n\right.\), obwohl \(\overline{a}\ne \overline{0}\) und \(\overline{b}\ne \overline{0}\) ist. Also ist \(\left.\mathbb Z\middle /n\right.\) kein Körper.
Der zweite Punkt zeigt uns, dass \(\left.\mathbb Z\middle /n\right.\) höchstens dann ein Körper sein kann, wenn \(n\) eine Primzahl (vergleiche Ergänzung 3.44) ist. Wir wollen nun zeigen, dass wir für eine Primzahl \(p\) tatsächlich einen Körper \(\left.\mathbb Z\middle /p\right.\) konstruiert haben.
Dafür benutzen wir die Primeigenschaft: Ist \(p\) eine Primzahl und ist \(p\) ein Teiler des Produkts \(ab\) von zwei ganzen Zahlen \(a\), \(b\), so ist \(p\) ein Teiler von \(a\) oder von \(b\) (wie immer ist auch erlaubt, dass \(p\) beide Zahlen \(a\) und \(b\) teilt). Siehe Satz 3.52 in Ergänzung 3.51 für einen Beweis. Wir wollen uns, für den Fall, dass Sie diese Ergänzung ausgelassen haben, auf die Bemerkung beschränken, dass diese Eigenschaft aus der Eindeutigkeit der Primfaktorzerlegung in \(\mathbb Z\) folgt. Denn die (eindeutige!) Primfaktorzerlegung des Produktes \(ab\) erhalten wir, indem wir die Primfaktorzerlegungen von \(a\) und von \(b\) zusammenfügen (miteinander multiplizieren), und wenn \(p\) als Faktor in dem Produkt auftritt, muss es folglich auch in einem der Faktoren dabei sein.
Sei \(p\) eine Primzahl. Dann ist \(\left.\mathbb Z\middle /p\right.\) ein Körper.
Nach dem bereits Gesagten ist nur noch zu zeigen, dass jedes Element \(a\in (\left.\mathbb Z\middle /p\right.)\setminus \{ \overline{0}\} \) ein multiplikatives Inverses besitzt. Sicher genügt es dafür, zu beweisen, dass die Abbildung
surjektiv ist, denn \(m_a(x)=\overline{1}\) besagt ja gerade \(a\cdot x=\overline{1}\); dann ist \(x\) das gesuchte Inverse.
Weil \(\left.\mathbb Z\middle /p\right.\) eine endliche Menge ist, ist es äquivalent zu zeigen, dass \(m_a\) injektiv ist (Satz 3.64).
Das bedeutet, wir müssen zeigen, dass für \(x\ne y\in \left.\mathbb Z\middle /p\right.\) stets \(ax\ne ay\), oder mit anderen Worten \(a(x-y)\ne \overline{0}\) gilt. Wir schreiben \(a=\pi (\dot{a})\), \(x=\pi (\dot{x})\), \(y=\pi (\dot{y})\) für geeignete ganze Zahlen \(\dot{a}\), \(\dot{x}\), \(\dot{y}\). Dann können wir umformulieren: Dass \(a\ne \overline{0}\) ist, ist gleichbedeutend damit, dass \(p\nmid \dot{a}\), ebenso bedeutet \(x\ne y\), dass \(p\nmid \dot{x}-\dot{y}\). Wegen der oben bemerkten Primeigenschaft erhalten wir daraus, dass \(p\) kein Teiler des Produkts \(\dot{a}(\dot{x}-\dot{y})\) ist. Folglich ist \(a(x-y) = \pi (\dot{a})(\pi (\dot{x})-\pi (\dot{y})) = \pi (\dot{a}(\dot{x}-\dot{y})) \ne \overline{0}\), wie gewünscht.
Wir geben noch einen alternativen Beweis dafür, dass \(\left.\mathbb Z\middle /p\right.\) für Primzahlen \(p\) ein Körper ist. Dieser beruht auf Lemma 3.53 aus Ergänzung 3.51. (Wir haben dieses Lemma benutzt, um die Eindeutigkeit der Primfaktorzerlegung zu beweisen; insofern hängt auch der erste Beweis für die Körpereigenschaft von \(\left.\mathbb Z\middle /p\right.\) bei unserem Aufbau der Dinge von Lemma 3.53 ab. Man kann aber die Primeigenschaft, und damit die Eindeutigkeit der Primfaktorzerlegung auch (etwas) anders beweisen.)
Sei \(n{\gt}1\) eine natürliche Zahl, und sei \(a\in \mathbb Z\). Genau dann besitzt \(\pi (a)\) ein multiplikatives Inverses in \(\left.\mathbb Z\middle /n\right.\), wenn \(\operatorname{ggT}(a,n)=1\).
Sei \(a\in \mathbb Z\) mit \(\operatorname{ggT}(a,n) = 1\). Nach Lemma 3.53 existieren dann \(x, y\in \mathbb Z\) mit
Das bedeutet aber
also ist \(\pi (x)\) das gesuchte Inverse von \(a\).
Hat andererseits \(\pi (a)\) ein multiplikatives Inverses, so können wir dieses in der Form \(\pi (b)\) für \(b\in \mathbb Z\) schreiben. Dass das Produkt \(\pi (a)\pi (b) = \overline{1}\) ist (in \(\left.\mathbb Z\middle /n\right.\)), bedeutet genau, dass \(1-ab\) von \(n\) geteilt wird. Ist also \(d\) ein gemeinsamer Teiler von \(a\) und \(n\), so muss \(d\) auch \(1\) teilen, also \(d\in \{ -1, 1\} \).
Sei \(p\) eine Primzahl. Dann ist \(\left.\mathbb Z\middle /p\right.\) ein Körper.
Sei \(a\in \left.\mathbb Z\middle /p\right.\), \(a\ne \overline{0}\). Wir schreiben \(a = \pi (\dot{a})\) für eine ganze Zahl \(\dot{a}\). Weil \(a\ne \overline{0}\), wird \(\dot{a}\) nicht von \(p\) geteilt, und weil \(p\) eine Primzahl ist, folgt \(\operatorname{ggT}(\dot{a},p)=1\). Daher können wir den vorherigen Satz anwenden.
(Wir erhalten so auch einen (etwas) anderen Beweis von Satz 3.52: Der Satz sagt, dass wenn immer die Primzahl \(p\) ein Produkt \(ab\) teilt, \(p\) einen der Faktoren teilt. In der Tat, \(p\, |\, ab\) bedeutet \(\pi (a) \pi (b) = \pi (ab)=\overline{0}\), und da \(\left.\mathbb Z\middle /p\right.\) ein Körper ist, gilt dann \(\pi (a) =\overline{0}\) oder \(\pi (b) =\overline{0}\). Das bedeutet gerade \(p\, |\, a\) oder \(p\, |\, b\).)
Für eine Primzahl \(p\) schreiben wir statt \(\left.\mathbb Z\middle /p\right.\) oft auch \(\mathbb F_p\), um zu betonen, dass es sich hierbei um einen Körper handelt.
(Wenn Sie Lust haben, ist jetzt ein guter Zeitpunkt, sich den Sternchen-Abschnitt 3.14.2 über Äquivalenzrelationen anzuschauen, und dort speziell das Beispiel über \(\left.\mathbb Z\middle /3\right.\).)
Zum Schluss noch einige gebräuchliche Schreibweisen: Oft schreibt man \(\overline{a}\) statt \(\pi (a)\) für beliebige ganze Zahlen \(a\). Für \(0\le a {\lt} n-1\) fällt das mit der oben verwendeten Schreibweise zusammen. Manchmal schreibt man auch \([a]\) statt \(\overline{a}\).
Wenn keine Missverständnisse zu befürchten sind (oder die Autor∗in entscheidet, der Leser∗in zuzumuten, das selbst (gedanklich) »aufzuräumen«), dann kann man auch einfach \(a\) statt \(\overline{a}\) schreiben.
Eine andere übliche Schreibweise ist es, statt \(\pi (x) = \pi (y)\) (für \(x,y\in \mathbb Z\) und ein fixiertes \(n\))
zu schreiben (gesprochen »\(x\) ist kongruent zu \(y\) modulo \(n\)«). Wie oben erläutert ist das äquivalent dazu zu sagen, dass \(x-y\) von \(n\) geteilt wird.
Die Schreibweise, statt \(\overline{a}\) einfach \(a\) zu schreiben, kann man im Rahmen der folgenden allgemeinen Konvention sehen: Sei \(K\) ein beliebiger Körper. Für eine natürliche Zahl \(n\) schreiben wir \(n_K\), oder einfach \(n\), wenn klar ist, dass wir \(n\) als Element von \(K\) betrachten möchten, für das Element
von \(K\). Zum Beispiel gilt (für die übliche Einbettung der Menge der natürlichen Zahlen in den Körper \(\mathbb Q\)) \(n_{\mathbb Q} = n\) für alle natürlichen Zahlen \(n\). Andererseits gilt \(2_{\mathbb F_2} = 0_{\mathbb F_2}\) und allgemeiner \(n_{\mathbb F_2} = 0_{\mathbb F_2}\) für alle geraden, und \(n_{\mathbb F_2} = 1_{\mathbb F_2}\) für alle ungeraden natürlichen Zahlen \(n\). Man sagt auch, in \(\mathbb F_2\) gelte \(2=0\), \(3=1\), etc.
Man erweitert diese Definition auf alle ganzen Zahlen, indem man \((-n)_K := - n_K\) für natürliche Zahlen \(n\) setzt. Dann ist \(n_K\) für alle ganzen Zahlen \(n\) definiert. Hier ist \(- n_K\) das Negative in \(K\) des Elements \(n_K\).
4.2.2 Die Charakteristik eines Körpers *
In diesem Abschnitt untersuchen wir das Phänomen, dass in manchen Körpern der Ausdruck \(1 + \cdots + 1\) gleich \(0\) ist, etwas genauer. Zum Beispiel gilt in \(\mathbb F_2\), dass \(1+1=0\), und in \(\mathbb F_p\), dass \(1+\cdots 1 = 0\) (mit \(p\) Summanden auf der linken Seite).
Wir verwenden weiter die am Ende des vorherigen Abschnitts eingeführte Schreibweise \(n_K\) für \(n\in \mathbb Z\). Wie gesagt, werden wir später dazu übergehen, einfach \(n\) statt \(n_K\) zu schreiben, aber für den Moment bleiben wir bei dem Index \(-_K\) zur besseren Unterscheidung.
Wir können also von der Abbildung \(\varphi \colon \mathbb Z\to K\), \(n\mapsto n_K\) sprechen. Es folgt leicht aus der Definition von \(n_K\), dass \(\varphi (m+n)=\varphi (m)+\varphi (n)\) gilt, wobei auf der linken Seite \(+\) die Addition in \(\mathbb Z\), und auf der rechten Seite \(+\) die Addition in \(K\) bezeichnet. (Überlegen Sie sich, dass das auch hinkommt, wenn \(m\) und/oder \(n\) negativ sind.) Darüberhinaus gilt auch \(\varphi (mn)=\varphi (m)\varphi (n)\), wobei wieder links in \(\mathbb Z\) und rechts in \(K\) multipliziert wird. Das zeigt man zuerst für nicht-negative \(m\) und \(n\), indem man \(m\) und \(n\) als Summen von \(m\) bzw. \(n\) Summanden \(1\) schreibt und das Distributivgesetz ausnutzt. Aus \(\varphi (-m)=-\varphi (m)\) kann man das Ergebnis dann in der allgemeinen Form herleiten.
Sei \(K\) ein Körper. Wenn es eine natürliche Zahl \(n \ge 1\) gibt, so dass \(n_K=0\), also
in \(K\) gilt (mit \(n\) Summanden auf der linken Seite), so nennen wir die kleinste solche Zahl \(n\ge 1\) die Charakteristik von \(K\).
Gibt es kein solches \(n\), so sagen wir, \(K\) habe die Charakteristik \(0\).
Da in jedem Körper per Definition die Elemente \(0\) und \(1\) verschieden sind, kann ein Körper nicht die Charakteristik \(1\) haben. Es gilt sogar die folgende viel stärkere Einschränkung:
Sei \(K\) ein Körper der Charakteristik \(p\ne 0\). Dann ist \(p\) eine Primzahl.
Sei \(K\) ein Körper mit Charakteristik \(p \ne 0\). Wir haben bereits bemerkt, dass \(p{\gt}1\) gelten muss. Angenommen, \(p\) ließe sich als Produkt zweier Zahlen \(m, n {\gt} 1\) zerlegen. Wir könnten dann \(p_K\) (oder mit der oben eingeführten Notation \(\varphi (p)\) schreiben als
was bedeutet, dass \(m_K= 0\) oder \(n_K=0\) gelten muss. Das steht im Widerspruch zur Minimalität von \(p\) in der Definition der Charakteristik.
Die Charakteristik von \(\mathbb Q\) ist \(0\), ebenso die Charakteristik von jedem Erweiterungskörper von \(\mathbb Q\), insbesondere also von \(\mathbb R\) und \(\mathbb C\).
Ist \(p\) eine Primzahl, so ist die Charakteristik von \(\mathbb F_p\) gleich \(p\). In der Tat folgt aus der Definition von \(\mathbb F_p\) als Menge von Restklassen modulo \(p\), dass \(p_{\mathbb F_p} =0\), aber \(n_{\mathbb F_p}\ne 0\) für alle \(n=1, \dots , p-1\).
Es gibt für jede Primzahl \(p\) noch weitere Körper der Charakteristik, sowohl endliche mit mehr als \(p\) Elementen, als auch unendliche. Da in einem Körper \(K\) der Charakteristik \(0\) die Elemente \(n_K\), \(n\in \mathbb Z\), alle verschieden sind, gibt es aber keine endlichen Körper der Charakteristik \(0\).
4.2.3 Der Kleine Fermatsche Satz *
Wir kommen noch einmal auf die endlichen Körper zurück und beginnen mit der folgenden simplen Beobachtung:
In allen Beispielen ist der Ausdruck \(a^n - a\) durch \(n\) teilbar. (Siehe auch Beispiel 3.36.) Das funktioniert aber nicht immer:
ist nicht durch \(9\) teilbar.
Der strukturelle Unterschied zwischen diesen Beispielen ist, dass im ersten Fall der Exponent immer eine Primzahl war. In der Tat gilt:
Wenn wir \(K =\mathbb F_p\) schreiben, dann können wir die Aussage umformulieren als
Es gilt aber \((a^p-a)_K = (a_K)^p - a_K\), also genügt es zu zeigen, dass für alle Elemente \(x\in \mathbb F_p\) gilt: \(x^p = x\).
Für \(x= 0\) ist das klar. Sei also nun \(x\ne 0\). Betrachte die Multiplikation mit \(x\) als Abbildung \(\xi \colon \mathbb F_p^\times \to \mathbb F_p^\times \): \(y\mapsto xy\). Diese Abbildung ist injektiv, weil \(x\ne 0\) und \(\mathbb F_p\) ein Körper ist. Weil \(\mathbb F_p^\times \) nur endlich viele Elemente hat, ist sie automatisch sogar bijektiv.
Das bedeutet, dass das Produkt aller Bilder \(\xi (y)\), \(y\in \mathbb F_p^\times \), unter der Abbildung \(\xi \) mit dem Produkt aller \(y\in \mathbb F_p^\times \) übereinstimmt, denn die Faktoren sind ja bis auf die Reihenfolge genau dieselben:
Die rechte Seite ist wieder in \(\mathbb F_p^\times \), also \(\ne 0\), und wir können durch sie teilen. Wir erhalten damit
also \(x^p = x\), wie gewünscht.
Eine kleine Verfeinerung (der Satz von Euler, Korollar 8.56) dieses Satzes ist ein wichtiger Bestandteil des RSA-Verfahrens, eines der wichtigsten Public-Key-Verfahren, also Verschlüsselungsverfahren, bei denen Absender und Empfänger verschlüsselt kommunizieren können, ohne vorher einen geheimen Schlüssel auszutauschen. Stattdessen kann der Empfänger den Schlüssel, den der Absender zum Verschlüsseln benutzt, öffentlich machen (public key), ohne dass Außenstehende die Möglichkeit hätten, den öffentlichen Schlüssel zum Entschlüsseln zu verwenden. Siehe Bemerkung 8.58
Ausgangsbasis für alle solchen Public-Key-Verfahren ist eine mathematische Operation, die vergleichsweise schnell berechenbar und eindeutig umkehrbar ist, für die aber die Berechnung der Umkehroperation einen wesentlich höheren Rechenaufwand erfordert. Im Falle des RSA-Verfahrens benutzt man, dass es leicht ist, große Primzahlen zu finden und das Produkt zweier solcher Primzahlen zu berechnen, dass aber kein Verfahren bekannt ist, um in annehmbarer Zeit die Zerlegung eines solchen Produkts in seine Primfaktoren zu bestimmen. Konkret würde man zum Beispiel mit zwei Primzahlen beginnen, die jeweils etwa \(1\, 000\) Stellen haben. Mittelfristig könnte die Entwicklung leistungsstarker Quantencomputer allerdings eine Möglichkeit darstellen, auch Produkte dieser Größenordnung in ihre Primfaktoren zu zerlegen, so dass das Verfahren dann als geknackt gelten müsste (siehe Shor-Algorithmus).
Der Kleine Fermatsche Satz ist eine Möglichkeit zu testen, ob eine (große) Zahl \(n\) eine Primzahl ist. Man nimmt eine Zahl \(a\) und rechnet aus, ob \(a^n-a\) durch \(n\) teilbar ist. Diese Rechnung lässt sich wesentlich schneller durchführen, als die Zahl \(n\) in ihre Primfaktoren zu zerlegen. Wenn \(a^n-a\) nicht durch \(n\) teilbar ist, dann kann \(n\) keine Primzahl sein. Wenn für mehrere Zahlen \(a\) die Zahl \(a^n-a\) durch \(n\) teilbar ist, dann ist die Wahrscheinlichkeit hoch, dass \(n\) eine Primzahl ist.
In der Praxis benutzt man etwas ausgefeiltere Tests, die aber oft letztlich auf dem Kleinen Fermatschen Satz beruhen, zum Beispiel den Miller-Rabin-Test. Diese Tests sind in der Regel probabilistischer Natur, d.h. sie liefern mit einer verschwindend geringen Wahrscheinlichkeit ein falsches Ergebnis. Das nimmt man in der Praxis dann in Kauf.
Um eine große Primzahl (sagen wir mit mehreren hundert Stellen) zu finden, wie sie zum Beispiel für manche Verschlüsselungsverfahren benötigt wird, probiert man dann einfach so lange zufällig gewählte große Zahlen durch, bis man eine findet, die den zugrunde gelegten Primzahltest besteht.