Schnellster Primzahltest

Question

Können Sie eine schnelle, deterministische Methode vorschlagen, die in der Praxis verwendet werden kann, um zu testen, ob eine große Zahl prim ist oder nicht?

Auch würde ich gerne wissen, wie nicht-deterministische Primzahltests richtig zu verwenden. Wenn ich zum Beispiel eine solche Methode verwende, kann ich sicher sein, dass eine Zahl nicht prim ist, wenn die Ausgabe "nein" ist, aber was ist mit dem anderen Fall, wenn die Ausgabe "wahrscheinlich" ist? Muss ich in diesem Fall manuell auf Primalität prüfen?

Vielen Dank im Voraus.

Answer 1

Der einzige deterministische, polynomiale Zeitalgorithmus für Primzahltests, den ich kenne, ist der AKS-Primalitätstest (http://en.wikipedia.org/wiki/AKS_primality_test). Es gibt jedoch viele sehr gute randomisierte Primzahltests, die schnell sind und eine extrem gute Erfolgswahrscheinlichkeit haben. Sie arbeiten normalerweise, indem sie herausfinden, ob die Zahl zusammengesetzt ist, mit exponentiell guter Wahrscheinlichkeit, also berichten sie entweder, dass die Zahl zusammengesetzte ist, oder erfordern Sie, "vielleicht" mit sehr guter Zuversicht zu sagen.

Answer 2

"Wahrscheinlich" bedeutet eigentlich 1-ε, und ε wird so klein wie Sie brauchen.

Die meisten Anwendungen haben einige kleine, aber von Null verschiedene Wahrscheinlichkeit, dass der Fehler ist nicht an Primtests, zum Beispiel

• in kryptographischer Anwendungen, kann ein Angreifer zum Glück das Geheimnis mit, zum Beispiel zu raten, eine Wahrscheinlichkeit von 2^(- 100)

• ein Hardwarefehler (strahlungsinduzierte) zufällig einige Bit des Computers Speicher Spiegeln (vielleicht eine, die mit dem Ausgang des „deterministisch“ Primzahltest hält

• Fehler (in der Tat wahrscheinlicher als die andere Art des Ausfalls)

drücken also die ε zu dieser Größenordnung in der Praxis genügt.

Zum Beispiel, OpenSSL, GnuPG der Verwendung nur nicht-deterministischen Primzahltest. "Wahrscheinlich" willst du nicht wirklich einen deterministischen Test. Aber überprüfen Sie, was Ihnen zur Verfügung steht: Wenn Sie Bibliotheken zur Hand haben und sie genug leisten, machen Sie weiter und nutzen Sie sie.

Answer 3

Wenn Sie eine zufällige Primzahl für die Verwendung in RSA-Schlüsseln suchen, sollten Sie zunächst einen probabilistischen Test verwenden. Wenn die Wahrscheinlichkeit für Ihre Bedürfnisse hoch genug ist, dann hören Sie auf. Wenn Sie sich sicher sein müssen, dann sollten Sie, sobald Sie eine große zufällige Wahrscheinlichkeit gefunden haben, diese mit AKS oder einem anderen nicht probabilistischen Test überprüfen. Auf diese Weise können Sie viele Nicht-Primzahlen schnell überprüfen, während Sie sicher sind, dass Sie glauben, einen gefunden zu haben.

Wenn Sie versuchen, eine bestimmte vorhandene Nummer zu überprüfen, dann sollten Sie einen der Tests verwenden, der mit Sicherheit antwortet. Es gibt auch andere nicht-polynomiale Zeittests, verwenden Sie den, der in der Praxis am schnellsten ist.