Mathematik Informatik Philosophie Diverses Kontatkt FAQ
Benutzername:
Passwort:
 Home > News
Montag, 26. Juni 2017 14:03 
Probabilistische Primzahltests
 
Geschrieben von Alexander am Freitag, 12. Januar 2007

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 Zn 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 T2-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.

Probabilistische Primzahltest

Präsentation Primzahltest

Probabilistische Primzahltests

Für den Inhalt der Kommentare sind die Verfasser verantwortlich.



die letzten 5 Artikel

Artikel-Archiv

Einstellungen



Artikel Bewertung
Ergebnis: 5
Stimmen: 9


Bitte nehmen Sie sich die Zeit und bewerten diesen Artikel:
Excellent
Sehr gut
Gut
Okay
Schlecht


Verwandte Links

Der meistgelesene Artikel zu dem Thema Kryptographie:


Alle Logos und Warenzeichen auf dieser Seite sind Eigentum der jeweiligen Besitzer und Lizenzhalter.
Im übrigen gilt Haftungsausschluss. Weitere Details finden Sie im Impressum.
Die Inhalte dieser Seite sind als RSS/RDF-Quelle verfügbar.
Die Artikel sind geistiges Eigentum des/der jeweiligen Autoren,
alles andere © 2004 - 2017 by mathematik-netz.de

Seitenerstellung in 0.0824 Sekunden, mit 55 Datenbank-Abfragen