Schnellste primality test

Konnte Sie deuten auf eine schnelle, deterministische Methode, die verwendbar ist, in der Praxis zu testen, ob eine große Zahl eine Primzahl ist oder nicht?

Außerdem würde ich gerne wissen, wie der Umgang mit nicht-deterministischen primality tests korrekt. Zum Beispiel, wenn ich mit einer solchen Methode kann ich mir sicher sein, dass eine Zahl keine Primzahl, wenn der Ausgang auf "Nein", aber was ist mit dem anderen Fall, wenn der Ausgang "wahrscheinlich"? Muss ich testen, primality manuell in diesem Fall?

Vielen Dank im Voraus.

InformationsquelleAutor | 2010-12-20
  1. 7

    Nur die deterministischen, polynomial-time algorithm for primality Tests, die ich kenne, ist die AKS primality test (http://en.wikipedia.org/wiki/AKS_primality_test). Allerdings gibt es eine Menge sehr guter randomisierte primality tests, die sind schnell und haben sehr gute Erfolgsaussichten. Sie arbeiten in der Regel durch Feststellung, ob die Zahl zusammengesetzt ist, mit exponentiell gute Wahrscheinlichkeit, so werden Sie entweder Bericht, dass die Zahl zusammengesetzt ist oder wird von Ihnen verlangen, zu sagen, "vielleicht" mit sehr gut Vertrauen.

    • Wenn wir sagen "mit sehr gutem Vertrauen", bedeutet es, dass die Wahrscheinlichkeit, eine falsche Ausgabe, da einer Fehlfunktion des Systems ist höher als die Wahrscheinlichkeit, dass der Algorithmus produziert die falsche Antwort? 🙂
    • es kommt auf den Algorithmus, die Sie verwenden. Einige werden sogar erlauben Ihnen zu spezifizieren, Ihre Chancen. Test ~50%, 75%, 90%, etc. Die AKS, dass er die angegebene Antwort richtig 100% der Zeit, vorausgesetzt, es ist richtig codiert.
    • Störung"? Wahrscheinlichkeiten sind betroffen, denn ein "richtiger" Algorithmus würde langsam sein, so können Sie prüfen, eine viel kleinere Menge von Werten, die Ihnen würde sagen zu 99,9% Wahrscheinlichkeit die richtige Antwort. Was denken Sie nicht-deterministisch, ein Begriff, den Sie verwendet haben, bedeutet?
    • Grigorij ist im wesentlichen korrekt, Sie können die "zuversicht" auf der Ebene der probabilistic primality test, so dass die Wahrscheinlichkeit eines falschen positiven-Deklaration eine Zahl prim ist, wenn es in der Tat composite-ist so gering, dass Sie eher zu einem false positive aus einer Fehlfunktion des Systems (z.B. eine fehlgeschlagene memory-bit-oder bit-register) als aus der primality test.
    InformationsquelleAutor templatetypedef
  2. 7

    "Wahrscheinlich" bedeutet eigentlich 1-ε, und ε wird so klein, wie Sie benötigen.

    Meisten Anwendungen haben einige kleine, aber von null verschiedenen Wahrscheinlichkeit zu scheitern, dass nicht mit primality testing, zum Beispiel

    • in kryptographischen Anwendungen, die ein Angreifer zum Glück erraten, das Geheimnis, zum Beispiel,
      eine Wahrscheinlichkeit von 2^(-100)

    • einen hardware-Fehler (strahlenbedingte) zufällig spiegeln sich einige etwas von Ihrem computer-Speicher (vielleicht einer, der hält den Ausgang des "deterministischen" primality test

    • bugs (ja, wahrscheinlicher als die andere Art der Fehler)

    So drücken die ε zu, dass die Größenordnung genügt in der Praxis.

    Beispielsweise OpenSSL, GnuPG, der die Verwendung von nicht-deterministischen primality test nur. `Wahrscheinlich", die Sie nicht wirklich wollen, keine deterministische Tests. Aber prüfen Sie, was Ihnen zur Verfügung steht: Wenn Sie irgendwelche Bibliotheken zur hand, und führen Sie genug - gehen Sie auf und verwenden Sie Sie.

    InformationsquelleAutor Mitro
  3. 3

    Wenn Sie schauen, um eine zufällige prime für den Einsatz im RSA-Schlüssel, die Sie verwenden sollten ein probabilistischer test zunächst. Wenn die Wahrscheinlichkeit hoch genug für Ihre Bedürfnisse, dann stoppen Sie es. Wenn Sie müssen sicher sein, dann, wenn Sie finden eine große zufällige wahrscheinlich-prime, überprüfen Sie es mit AKS oder anderen nicht-probabilistische test. Dadurch können Sie prüfen, eine Menge von nicht-Primzahlen schnell, während Sie sicher, wenn Sie denken, Sie haben eine gefunden.

    Werden, wenn Sie versuchen, um zu überprüfen, einer bestimmten, vorhandenen Zahl eine Primzahl ist, dann sollten Sie mit einer der tests, die Antworten mit Sicherheit. Es gibt noch andere nicht-polynomial-Zeit-tests zu erhalten, verwenden Sie eine, die ist am schnellsten in der Praxis.

    InformationsquelleAutor phkahler
Schreibe einen Kommentar