WikiDer > Primzahltest

EIN Primzahltest ist ein Algorithmus das bestimmt, ob eine gegebene Zahl ist oder nicht Ahle ist. Ein solcher Test wird unter anderem in der Kryptographie. Der Unterschied zwischen einem Primzahltest und Zerlegung in Primfaktoren ist, dass ein Primzahltest nicht unbedingt Primfaktoren liefert, sondern nur sagt, ob die gegebene Zahl eine Primzahl ist oder nicht. Die Zerlegung in Primfaktoren liefert natürlich diese Faktoren. Es ist einfacher zu bestimmen, ob eine Zahl eine Primzahl ist oder nicht (mit einem Primzahltest) als die Primfaktoren. Einige Primzahltests beweisen dass eine Zahl eine Primzahl ist, während andere beweisen, dass eine Zahl zusammengesetzt ist. Wir sollten diese Tests daher besser machen Compounding-Tests benennen kann.

Naive Methoden

Der einfachste Primzahltest ist wie folgt: Gegeben ein positives gerade Zahlnein, überprüfe, ob es eine Zahl 2 gibt ≤ ich ≤ nein−1 ist so, dass neinteilbar ist durch ich. Wenn dies der Fall ist, dann neinzusammengesetzt; ist anders nein Ahle. Beachten Sie, dass wenn nein zusammengesetzt ist, finden wir mit diesem Test auch Primfaktoren. Damit ist es auch ein Faktorisierungsmethode.

Es stellt sich jedoch heraus, dass es nicht notwendig ist, ich bis einschließlich nein−1, aber nur bis ${displaystyle scriptstyle {sqrt {n}}}$. Der Grund dafür ist: wenn nein zusammengesetzt ist, dann nein das Produkt zweier Faktoren, von denen einer mindestens ≤ . ist${displaystyle scriptstyle {sqrt {n}}}$ ist.

Es könnten noch mehr Zahlen sein ich werden übersprungen. wenn nein da nicht durch 2 teilbar ist, dann ist nein auch nicht durch 4, 6, 8 usw. teilbar. nein ist nicht durch alle teilbar Ein bisschen Zahlen. wenn nein dann ist nicht durch 3 teilbar, dann nein auch nicht durch alle teilbar Vielfaches von drei. Wenn Sie dies fortsetzen, erhalten Sie die Sieb von Eratosthenes, woraus folgt, dass wir nur alle haben ich zwischen 2 und ${displaystyle scriptstyle {sqrt {n}}}$ muss nachfragen mit ich Ahle.

Diese Verfahren können beschleunigt werden, indem man vorab eine Liste von Primzahlen erstellt (z. B. mit dem Sieb des Eratosthenes) und prüft, ob die Zahl zu prüfen ist nein ist durch eine dieser Zahlen teilbar. Wenn dies der Fall ist, wurde die Nummer erstellt und es sind keine weiteren Tests erforderlich.

Wahrscheinlichkeitstests

Die am häufigsten verwendeten Primzahlentests sind Wahrscheinlichkeitsrechnung testet. Bei diesen Tests wird zusätzlich zur zu testenden Zahl nein ebenfalls zufällig Zahlen ein verwendet, um zu Beginn des Tests zu bestimmen, wie viele verschiedene ein sind auserwählt. Im Allgemeinen wird in probabilistischen Tests eine Zahl, die tatsächlich eine Primzahl ist, auch als Primzahl gemeldet; eine zusammengesetzte Zahl kann jedoch auch als Primzahl angegeben werden. Die Wahrscheinlichkeit dieses Fehlers kann verringert werden, indem der Test mit verschiedenen Werten von . wiederholt wird ein. Für eine Reihe von Tests gilt dies für jede Verbindung nein mindestens die Hälfte von allen ein das wird's geben give nein ist in der Tat zusammengesetzt. Für diese Primzahlprüfung gilt also: falls für eine ganze Zahl k, k Tests werden durchgeführt (mit auch k verschiedene ein 's), dann stehen die Chancen nein dennoch wird als Primzahl höchstens 2 . angegeben^−k. Wir können diese Chance reduzieren durch k beliebig groß.

Ein probabilistischer Test hat im Allgemeinen den folgenden Aufbau:

1. Wähle eine beliebige Zahl ein.
2. Prüfen Sie eine gewisse Gleichheit (je nach gewähltem Test) bezüglich der Zahl ein und die zu testende Nummer nein. Wenn die Gleichheit nicht gilt, dann ist nein komponiert und heiß ein ein Zeuge aus der Tatsache, dass nein zusammengesetzt ist. Es sind keine weiteren Tests erforderlich.
3. Ab Schritt 1 wiederholen, bis eine gewisse Gewissheit der Zusammensetzung besteht.

Wenn nach einer vorgegebenen Zahl Iterationen (nämlich k) wurde immer noch nicht gefunden nein zusammengesetzt ist, kann es wahrscheinlich prim deklariert werden.

Wann nein eine zusammengesetzte Zahl ist, dann gibt es die folgenden zwei Möglichkeiten:

• der Test gibt eine Ausgabe zusammengesetzt für eine gewisse ein; in diesem Fall wird ein ein Zeuge erwähnt aus der Tatsache, dass nein besteht;
• der test liefert ergebnis wahrscheinlich prim für eine gewisse ein; in diesem Fall wird ein ein Lügner benannt nach nein.

Beispiele

Der einfachste Wahrscheinlichkeitstest ist der Fermat-Prime-Test (Dies ist einer dieser Tests, die besser als Compositeness-Tests bezeichnet werden könnten). Dieser funktioniert wie folgt:

Gegeben eine ganze Zahl nein, wähle eine beliebige ganze Zahl ein so dass gcd(ein,nein) = 1. Berechnen ein^nein−1modularnein. Wenn das Ergebnis davon ungleich 1 ist, dann ist neinzusammengesetzt. Wenn das Ergebnis 1 ist, dann ist neinmöglicherweise Ahle.

Der Primzahltest von Fermat ist ein heuristischer Test: einige zusammengesetzte Zahlen (Carmichael-Zahlen) wird unabhängig vom gewählten Zeugen für "möglicherweise prim" erklärt. Trotzdem wird dieser Test manchmal verwendet, wenn eine Zahl schnell auf Primzahl überprüft werden muss, zum Beispiel im RSA-Verschlüsselungsalgorithmus, beim Generieren des Schlüssels.

Das Miller-Rabin-Primzahltest und Solovay-Straßen-Primzahltest, auch Beispiele für Compounding-Tests, sind etwas anspruchsvoller und finden alle zusammengesetzten Zahlen: für jede zusammengesetzte Zahl nein Für den Miller-Rabin- bzw. Solovay-Strassen-Test gilt, dass mindestens 3/4 bzw. 1/2 der Zahlen ein bezeugen, dass nein zusammengesetzt ist.

Der Miller-Rabin-Test funktioniert wie folgt: Gegeben eine ganze Zahl nein, wähle eine ganze Zahl ein < nein. Wenn:

${displaystyle a^{d}nicht gleich 1{pmod {n}}}$

und

${displaystyle a^{2^{r}d}ot equiv -1{pmod {n}}}$ für alle ${displaystyle 0leq rleq s-1}$,

dann ist nein zusammengesetzt und ist ein ein Zeuge. anders ist nein möglicherweise prim.

Der Solovay-Strassen-Test funktioniert ähnlich: Gegeben eine ganze Zahl nein, wähle eine beliebige Zahl ein < nein. Wenn:

${displaystyle left({frac {a}{n}}ight){pmod {n}}nicht gleich ^{frac {n-1}{2}} }$,

mit

${displaystyle left({frac {a}{n}}ight) }$ es Jacobi-Symbol,

dann ist nein zusammengesetzt und ist ein ein Zeuge. anders ist nein möglicherweise prim.

Ein weiteres Beispiel ist die Lucas-Lehmer-Test. Dieser Test erfordert die Faktorisierung von nein-1; das bedeutet, dass es für die allgemeinen Zwecke eines Primzahltests nicht geeignet ist, aber nützlich sein kann, wenn die zu testende Zahl nein hat zum Beispiel eine besondere Form Mersenne-Zahlen (sehen Lucas-Lehmer-Test für Mersenne-Zahlen).

Der Lucas-Lehmer-Test verwendet das, wenn nein ist prim, dass dann die multiplikative Ordnung einer Zahl ein (mod nein) gleich nein−1 wenn ein ein primitive Wurzel modulo nein ist. Also wenn wir das zeigen können ein eine primitive Wurzel ist für nein, dann ist nein Ahle.

Deterministische Methoden

Der Miller-Rabin-Primzahltest ist nicht nur eine probabilistische Methode, er hat auch eine deterministisch Ausführung.^[1] Millers ursprüngliche Version war sogar deterministisch, aber weil es von der noch nicht bewiesenen abhängt Riemann-Hypothese, hat Rabin den Test an eine probabilistische Methode angepasst.

Im August 2002 veröffentlicht Manindra Agrawal, Neeraj Kayal und Nitin Saxena der Artikel Primzahlen ist in P im Internet raus.^[1] Darin beschrieben sie eine neue Methode, um Primalität zu testen. Diese Methode ist nach ihnen benannt und heißt die AKS-Test. Mit dieser Methode ist es möglich in Polynomzeit bestimmen, ob eine Zahl eine Primzahl ist.

Verweise

• Dieser Artikel oder eine frühere Version ist eine (Teil-)Übersetzung des Artikels Primzahltest auf der englischsprachigen Wikipedia, die unter der Creative Commons Namensnennung/Weitergabe unter gleichen Bedingungen Stürze. Siehe die Verlauf bearbeiten Dort.
• (und) Cai, Jin-Yi und Zhu, Hong, Fortschritte in der Computational Complexity Theory, Journal of Computational Science and Technology Vol. 2, No. 20 (2005), Nr. 6, pp. 735-750.
• (und) Agrawal, M. und Biswas, S., Primalitäts- und Identitätsprüfung durch chinesischen Rest, Zeitschrift der ACM-Vol. 50 (2003), Nr. 4, S. 429-443.