Primtests
DIESER TEIL BEFINDET SICH NOCH IM AUFBAU!
Beschreibung
Im wesentlichen gibt es zwei Arten von Primtests, wobei man präziser doch eher von Zusammengestztheitstests sprechen sollte: probabilistische und deterministische Tests. Bei beiden handelt es sich um Funktionen in einem Argument (d.h. einer natürlichen Zahl), die einen Wahrheitswert zurückgeben.
Ein probabilistischer Primtest klassifiziert eine Primzahl stets als prim. Ist das Argument zusammengesetzt, so wird in einem guten Prozentsatz dies von dem Test erkannt, gelegentlich gibt der Test jedoch die Antwort, dass die Zahl prim sei. Die Antwort eines probabilistischen Primtests kann also nicht als Beweis für die Primalität angesehen werden, wohl aber als Beweis für die Zusammengestztheit einer Zahl, sofern der Test ein einziges mal die Zahl als zusammengesetzt klassifiziert hat.
Deterministische Primtests hingegen beweisen in der Tat die Primalität bzw. Zusammengesetztheit des Arguments. Nun stellt sich sofort die Frage, warum man denn nicht gleich einen solchen deterministischen Test nutzt. Die Antwort ist einfach: Deterministische Tests sind um vieles langsamer als die probabilistischen Tests. Genaugenommen war es lange Zeit nicht klar, ob Primalität in deterministischer Polynomialzeit überhaupt entschieden werden kann. Es stellte sich dank eines genialen Resultats von Agrawal, Kayal und Saxena heraus, dass dies in der Tat möglich ist.
Im folgenden werden wir eine beachtliche Anzahl verschiedener Tests kennenlernen. Neben Funktionsweise, mathematischem Hintergrund und Laufzeitanalyse sollen auch einige historische Bemerkungen zu den jeweiligen Tests gemacht werden.
VIEL SPASS!!!
Probabilistisch vs. Deteministisch
Probabilistische Tests
- Fermat Test
- Solovay-Strassen Test
- Miller-Rabin Test
- Lucas Test
- Frobenius Test
Deterministische Tests
- Sieb des Erathostenes
- Pratt'sche Primzahlzertifikate
- Elliptic Curves Primality Test
- AKS-Test
