Primzahltests sind wichtige Beispiele so genannter probabilistischer Algorithmen. Der Solovay-Strassen-Test war sogar einer der ersten seiner Art und wird am Ende dieses Dokuments behandelt.

Die in diesem Dokument behandelten Primzahltests, der Fermat-Test bzw. Miller-Rabin-Test, sind eng miteinander verknüpft. Der Miller-Rabin-Test kann als Fort- bzw. Weiterentwicklung des Fermat-Tests angsehen werden. Beide Algorithmen basieren auf dem wichtigen und einfach zu beweisenden (kleinen) Satz von Fermat. Allerdings treten beim Fermat-Test Anomalien in Form von Carmichael-Zahlen auf, welche der Miller-Rabin-Test erfolgreich versucht zu umgehen.

Auch der Solovay-Strassen-Test ist eng mit den beiden anderen untersuchten Primzahltests verwandt. Dies äußert sich auch im Zusammenhang zwischen den einzelnen Pseudoprimzahlarten.

Im Einzelnen werden behandelt:

• Grundsätzliches Vorgehen bei einem probabilistischen Primzahltest, Vorgehen bei einem negativen Testausgang um eine große Primzahl zu finden.
• Brute-Force-Mathode um eine Zahl zu testen, Zusammenhang mit der Komplexitätstheorie, AKS-Test, deterministischer polynomieller Primzahltest.
• Definition Zusammengesetzte Zahl, Primzahl, Primfaktorzerlegung, Primfaktoren, Hauptsatz der Zahlentheorie, es existieren unendlich viele Primzahlen, Primzahlsatz und Primzahlverteilung.
• Anforderungen an ein Kryptosystem; Komplexität; deterministisch; stochastisch unabhängige Wahl der Basis, Zeugen (witness), nicht Zeugen (liar), randomisierten bzw. probabilistischer Algorithmus.
• Der Fermat-Test, Lemma von Bézout, modulare Inverse, "kleiner" Satz von Fermat, Satz von Euler; a Einheit im Ring Z_n genau dann, wenn ggT(n,a)=1; Pseudoprimzahl, Beispiele, Einheitengruppe, Restklassenring, erzeugende Elemente, Eulersche phi-Funktion, Menge aller Basen bilden eine Untergruppe von (Z/nZ)^*, zusammengesetzte Zahl, Pseudoprimzahl für mind. die Hälfte aller Basen oder aber für alle Basen.
• Carmichael-Zahl, Satz von Korselt, Verteilung der Carmichael-Zahlen, "wahrscheinlich prim", Charakterisierung von Carmichael-Zahlen, mindestens Produkt drei verschiedener Primzahlen.
• Rabin-Miller-Test, Polynom T²-1 hat in einem endlichen Körper der Ordnung p die einzigen Nullstellen +1 und -1, Beweis bzw. Herleitung, triviale Wurzeln bzw. nicht triviale Wurzeln, Beispiele, starke Pseudoprimzahl, höchstens für die Hälfte aller Basen b kann eine zusammengesetzte Zahl eine starke Pseudoprimzahl sein, Laufzeituntersuchungen, O-Notation.
• Quadratische Reste, quadratische Nichtreste, Anzahl der Quadratwurzeln, Legendre-Symbol, Jacobi-Symbol und quadratische Reste, Zusammenhang beider Symbole, Satz von Euler, Rechenrelgen des Jacobi- bzw. Legendre-Symbols, Eulersche Pseudoprimzahl, der Algorithmus.