Ganzzahlfaktorisierung

"Prime Decomposition" leitet hier weiter. Für den Prime Decomposition-Theorem für 3-Manifolds siehe Prime-Zersetzung (3-Maniflold).
Ungelöstes Problem in der Informatik:

Kann die Integer -Faktorisierung in der Polynomzeit auf einem klassischen Computer gelöst werden?

(mehr ungelöste Probleme in der Informatik)

Im Zahlentheorie, Ganzzahlfaktorisierung ist die Zersetzung von a zusammengesetzte Zahl in ein Produkt von kleineren Ganzzahlen. Wenn diese Faktoren sind weiter beschränkt auf Primzahlen, der Prozess heißt Primfaktorisierung.

Wenn die Zahlen ausreichend groß sind, nicht effizient Nicht-Quantum ganze Zahl Faktorisierung Algorithmus ist bekannt. Es wurde jedoch nicht nachgewiesen, dass ein solcher Algorithmus nicht existiert. Das vermutete Schwierigkeit Von diesem Problem ist für die verwendeten Algorithmen wichtig Kryptographie wie zum Beispiel RSA Public-Key-Verschlüsselung und die RSA Digitale Signatur.[1] Viele Bereiche von Mathematik und Informatik wurden zu dem Problem gebracht, einschließlich Elliptische Kurven, Algebraische Zahlentheorie, und Quanten-Computing.

Im Jahr 2019 faszinierte Fabrice Boudot, Pierrick Gaudry, Aurore Guillevic, Nadia Henerer, Emmanuel Thomé und Paul Zimmermann eine 240-stellige (795-Bit) NummerRSA-240) Verwendung von ca. 900 Kernjahre der Rechenleistung.[2] Die Forscher schätzten, dass ein 1024-Bit-RSA-Modul etwa das 500-mal so lange dauern würde.[3]

Nicht alle Zahlen einer bestimmten Länge sind gleichermaßen schwer zu faktorieren. Die schwierigsten Fälle dieser Probleme (für derzeit bekannte Techniken) sind Semiprimesdas Produkt von zwei Primzahlen. Wenn sie beide groß sind, zum Beispiel mehr als zweitausend Bits lang, zufällig ausgewählt und ungefähr gleich groß (aber beispielsweise nicht zu nah, um eine effiziente Faktorisierung durch zu vermeiden Fermat -Faktorisierungsmethode) sogar die schnellsten Primfaktorisierungsalgorithmen auf den schnellsten Computern können genügend Zeit in Anspruch nehmen, um die Suche unpraktisch zu machen. Das heißt, wie die Anzahl der Ziffern der berücksichtigten Primzahlen zunimmt, nimmt die Anzahl der für die Durchführung der Faktorisierung auf einem Computer erforderlichen Vorgängen drastisch zu.

Viele kryptografische Protokolle basieren auf der Schwierigkeit, große Verbundbezahlen oder ein damit verbundenes Problem zu berücksichtigen - zum Beispiel die RSA -Problem. Ein Algorithmus, der eine willkürliche Ganzzahl effizient fördert RSA-basierend Öffentlicher Schlüssel Kryptographie unsicher.

Prime -Zersetzung

Prime -Zersetzung von n = 864 as 25 × 33

Bis zum Grundsatz der Arithmetik, jede positive Ganzzahl hat eine einzigartige Primfaktorisierung. (Durch Konvention ist 1 das leeres Produkt.)) Testen Ob die Ganzzahl Prime ist Polynomzeitzum Beispiel von der ASS -Primalitätstest. Wenn komposit jedoch die Polynomzeittests geben, geben keinen Einblick in die Erlangung der Faktoren.

Bei einem allgemeinen Algorithmus für die Ganzzahlfaktorisierung kann jede Ganzzahl in seinen Bestandteil berücksichtigt werden Hauptfaktoren durch wiederholte Anwendung dieses Algorithmus. Die Situation ist mit Spezialfaktorisierungsalgorithmen komplizierter, deren Vorteile möglicherweise nicht auch mit den während der Zersetzung erzeugten Faktoren realisiert werden. Zum Beispiel wenn n = 171 × p × q wo p < q sind sehr große Primzahlen, Versuchsabteilung wird schnell die Faktoren 3 und 19 produzieren, aber ertragen p Abteilungen, um den nächsten Faktor zu finden. Als kontrastierendes Beispiel, wenn n ist das Produkt der Primzahlen 13729, 1372933 und 18848997161, wo 13729 × 1372933 = 18848997157, Fermats Faktorisierungsmethode beginnt mit was sofort ergibt und daher die Faktoren a − b = 18848997157 und a + b = 18848997161. Diese sind zwar leicht als zusammengesetzter bzw. Prime zu erkennen, aber die Methode von Fermat dauert viel länger, um die zusammengesetzte Zahl zu berücksichtigen, da der Startwert von zum a ist bei weitem nicht 1372933.

Aktueller Stand der Kunst

Siehe auch: Ganzzahlfaktorisierungsaufzeichnungen

Unter den b-Bitzahlen, die am schwierigsten zu berücksichtigendsten in der Praxis mit vorhandenen Algorithmen sind Produkte von zwei Primzahlen ähnlicher Größe. Aus diesem Grund sind dies die ganzen Zahlen, die in kryptografischen Anwendungen verwendet werden. Das größte solcher Semiprime, das noch berücksichtigt wurde, war RSA-250, eine 829-Bit Intel Xeon Gold 6130 bei 2,1 GHz. Wie bei allen aktuellen Faktorisierungsaufzeichnungen wurde diese Faktorisierung mit einer hoch optimierten Implementierung des Allgemeines Zahlenfeld Sieb Laufen Sie auf Hunderten von Maschinen.

Schwierigkeit und Komplexität

Nein Algorithmus wurde veröffentlicht, die alle Ganzzahlen berücksichtigen können Polynomzeitdas heißt, das kann a faktor a b-bitnummer n rechtzeitig O(bk) für eine Konstante k. Es wurde weder die Existenz noch die Nichteinheit solcher Algorithmen bewiesen, aber es wird im Allgemeinen vermutet, dass sie nicht existieren, und daher ist das Problem nicht in Klasse P.[4][5] Das Problem ist eindeutig in der Klasse NP, aber es wird im Allgemeinen vermutet, dass dies nicht der Fall ist NP-Complete, obwohl dies nicht bewiesen wurde.[6]

Es gibt veröffentlichte Algorithmen, die schneller sind als O ((1+)ε)b) für alle positiv ε, das ist, Subexponential. Ab 2021-03-12 ist der Algorithmus mit der besten theoretischen asymptotischen Laufzeit die Allgemeines Zahlenfeld Sieb (GNFS), erstmals 1993 veröffentlicht,[7] auf A laufen b-bitnummer n rechtzeitig:

Für aktuelle Computer ist GNFS der beste veröffentlichte Algorithmus für große n (mehr als etwa 400 Bit). Für ein Quantencomputer, jedoch, Peter Shor entdeckte 1994 einen Algorithmus, der ihn in Polynomzeit löst. Dies wird erhebliche Auswirkungen auf die Kryptographie haben, wenn die Quantenberechnung skalierbar wird. Shors Algorithmus nimmt nur o (b3) Zeit und o (b) Raum auf b-bitnummer Eingänge. Im Jahr 2001 wurde der Shor -Algorithmus zum ersten Mal durch Verwendung implementiert NMR Techniken auf Molekülen, die 7 Qubits liefern.[8]

Es ist nicht genau bekannt Komplexitätsklassen enthalten Entscheidungsversion des Ganzzahlfaktorisierungsproblems (dh: tut n haben einen Faktor, der kleiner ist als k?). Es ist bekannt, dass es in beiden ist Np und Co-NP, was bedeutet, dass sowohl "Ja" als auch "Nein" Antworten in Polynomzeit verifiziert werden können. Eine Antwort auf "Ja" kann durch eine Faktorisierung zertifiziert werden n = d(n/d) mit d ≤ k. Eine Antwort von "Nein" kann durch die Ausstellung der Faktorisierung von zertifiziert werden n in unterschiedliche Primzahlen, alle größer als k; Man kann ihre Primalität mit dem überprüfen ASS -Primalitätstestund dann multiplizieren Sie sie, um zu erhalten n. Das Grundsatz der Arithmetik garantiert, dass es nur eine mögliche Reihe von zunehmenden Primzahlen gibt, die akzeptiert werden, was zeigt, dass das Problem in beiden liegt HOCH und Co-up.[9] Es ist bekannt, dass es in ist BQP Wegen des Shor -Algorithmus.

Das Problem wird vermut CO-NP-Complete. Es ist daher ein Kandidat für die NP-Intermediate Komplexitätsklasse. Wenn sich erwiesen werden könnte, dass es sich entweder um NP-Complete oder Co-NP-Vervollständigung handelt, würde dies NP = CO-NP implizieren, ein sehr überraschendes Ergebnis, und daher wird weithin vermutet, dass die ganzzahlige Faktorisierung außerhalb beiden Klassen liegt.

Im Gegensatz dazu ist das Entscheidungsproblem " n eine zusammengesetzte Zahl? "(oder gleichwertig:" ist n Eine Primzahl? ") scheint viel einfacher zu sein als das Problem der Angabe von Faktoren von n. Das zusammengesetzte/Prime -Problem kann in der Polynomzeit gelöst werden (in der Zahl b von Ziffern von n) mit dem ASS -Primalitätstest. Außerdem gibt es mehrere Probabilistische Algorithmen Das kann in der Praxis sehr schnell die Primalität testen, wenn man bereit ist, eine verschwindend kleine Fehlermöglichkeit zu akzeptieren. Die Leichtigkeit von Primalitätstest ist ein entscheidender Teil der RSA Algorithmus, da es notwendig ist, große Primzahlen zu finden.

Factoring -Algorithmen

Spezialzweck

Die Laufzeit eines speziellen Fabrik-Algorithmus hängt von den Eigenschaften der Anzahl ab, die berücksichtigt werden sollen, oder von einem seiner unbekannten Faktoren: Größe, spezielle Form usw. Die Parameter, die die Laufzeit bestimmen, variieren zwischen Algorithmen.

Eine wichtige Unterklasse von Spezial-Fabricing-Algorithmen ist die Kategorie 1 oder Erste Kategorie Algorithmen, deren Laufzeit von der Größe des kleinsten Primfaktors abhängt. Bei einer Ganzzahl unbekannter Form werden diese Methoden normalerweise vor allgemeinen Methoden angewendet, um kleine Faktoren zu entfernen.[10] Zum Beispiel naiv Versuchsabteilung ist ein Algorithmus der Kategorie 1.

Allgemeiner Zweck

Ein allgemeiner Fabrikalgorithmus, auch bekannt als a Kategorie 2, Zweite Kategorie, oder Kraitchik Familie Algorithmus,[10] hat eine Laufzeit, die ausschließlich von der Größe der Ganzzahl abhängt, um berücksichtigt zu werden. Dies ist die Art von Algorithmus, die zum Faktor verwendet werden RSA -Zahlen. Die meisten allgemeinen Fabrikalgorithmen basieren auf dem Kongruenz der Quadrate Methode.

Andere bemerkenswerte Algorithmen

Heuristische Laufzeit

In der Zahltheorie gibt es viele ganzzahlige Faktorierungsalgorithmen, die heuristisch erwartet haben Laufzeit

in Little-o und L-Notation. Einige Beispiele für diese Algorithmen sind die Elliptische Kurvenmethode und die quadratisches Sieb. Ein weiterer solcher Algorithmus ist der Klassengruppenbeziehungsmethode vorgeschlagen von Schnorr,[11] Seysen,[12] und Lenstra,[13] was sie nur unter Annahme der Unprobierten bewiesen haben Generalisierte Riemann -Hypothese (GRH).

Strenge Laufzeit

Der probabilistische Schnorr -Seysen -Genstra -Algorithmus wurde durch Lensstra und Pomeranz streng bewiesen[14] Erwartung der Laufzeit erwartet haben Durch Ersetzen der GRH -Annahme durch Multiplikatoren. Der Algorithmus verwendet die Klassengruppe von positivem Binär quadratische Formen von Diskriminanz Δ gekennzeichnet durch GΔ.GΔ ist der Satz von Dreifachzahlen (a, b, c), in denen diese Ganzzahlen relative Prime sind.

Schnorr -Seysen -Genstra -Algorithmus

Eine Ganzzahl gegeben n das wird berücksichtigt, wo n ist eine seltsame positive Ganzzahl größer als eine bestimmte Konstante. In diesem Factoring -Algorithmus wird die Diskriminanz δ als ein Vielfaches von ausgewählt n, Δ = -dn, wo d ist ein positiver Multiplikator. Der Algorithmus erwartet das für einen d Es gibt genug glatt Formen in GΔ. Lenstra und Pomeranz zeigen, dass die Wahl von d kann auf ein kleines Set beschränkt werden, um das Smoothness -Ergebnis zu gewährleisten.

Bezeichnet durch PΔ der Satz aller Primzahlen q mit Kronecker -Symbol . Durch Konstruktion eines Satzes von Generatoren von GΔ und erstklassige Formen fq von GΔ mit q in PΔ eine Folge von Beziehungen zwischen den Generatorenmengen und fq werden produziert. Die Größe von q kann von begrenzt werden von für einige Konstante .

Die verwendete Beziehung ist eine Beziehung zwischen dem Produkt von Kräften, die gleich dem sind Neutrales Element von GΔ. Diese Beziehungen werden verwendet, um eine sogenannte mehrdeutige Form von zu konstruieren GΔ, was ein Element von ist GΔ der Reihenfolge Dividierung 2. Durch Berechnung der entsprechenden Faktorisierung von δ und durch Annahme von a GCDDiese mehrdeutige Form liefert die vollständige Primfaktorisierung von n. Dieser Algorithmus hat diese Hauptschritte:

Lassen n Sei die Anzahl, die berücksichtigt werden soll.

  1. Sei δ eine negative Ganzzahl mit Δ = -dn, wo d ist ein Multiplikator und δ ist die negative Diskriminanz einer quadratischen Form.
  2. Nehmen Sie die t Erste Primzahlen , für einige .
  3. Lassen eine zufällige Hauptform von sein GΔ mit .
  4. Finden Sie eine Erzeugungsmenge X von GΔ
  5. Sammeln Sie eine Folge von Beziehungen zwischen Set X und {fq: q ∈ PΔ} befriedigend:
  6. Eine mehrdeutige Form konstruieren Das ist ein Element f ∈ GΔ von Ordnung, die 2 geteilt werden, um eine Coprime -Faktorisierung des größten ungeraden Divisors von δ zu erhalten, in dem
  7. Wenn die mehrdeutige Form eine Faktorisierung von liefert n Dann stoppen, sonst eine andere mehrdeutige Form finden, bis die Faktorisierung von n gefunden. Um zu verhindern, dass nutzlose zweideutige Formen erzeugt werden, bauen Sie die auf 2-sylow Gruppe Sll2(Δ) von G(Δ).

Um einen Algorithmus zur Faktorierung einer positiven Ganzzahl zu erhalten Jacobi -Summentest.

Erwartete Laufzeit

Der Algorithmus wie angegeben ist a Probabilistischer Algorithmus wie es zufällige Entscheidungen treffen. Die erwartete Laufzeit ist höchstens .[14]

Siehe auch

Anmerkungen

  1. ^ Lenstra, Arjen K. (2011), Van Tilborg, Henk C. A.; Jajodia, Sushil (Hrsg.), "Ganzzahl Factoring", Enzyklopädie der Kryptographie und Sicherheit, Boston, MA: Springer US, S. 611–618, doi:10.1007/978-1-4419-5906-5_455, ISBN 978-1-4419-5905-8, abgerufen 2022-06-22
  2. ^ "[CADO-NFS-Discuss] 795-Bit Factoring und diskrete Logarithmen". Archiviert von das Original Am 2019-12-02.
  3. ^ Kleinjung; et al. (2010-02-18). "Faktorisierung eines 768-Bit-RSA-Moduls" (PDF). Internationale Vereinigung für kryptologische Forschung. Abgerufen 2010-08-09. {{}}: Journal zitieren erfordert |journal= (Hilfe)
  4. ^ Krantz, Steven G. (2011), Der Beweis liegt im Pudding: die sich ändernde Natur des mathematischen Beweises, New York: Springer, p. 203, doi:10.1007/978-0-387-48744-1, ISBN 978-0-387-48908-7, HERR 2789493
  5. ^ Arora, Sanjeev; Barak, Boaz (2009), Rechenkomplexität, Cambridge: Cambridge University Press, p. 230, doi:10.1017/CBO9780511804090, ISBN 978-0-521-42426-4, HERR 2500087
  6. ^ Goldreich, Oded; Wigderson, Avi (2008), "IV.20 Computational Complexity", in Gowers, Timothy; Barrow-Green, Juni; Anführer, Imre (Hrsg.), Der Princeton -Begleiter der Mathematik, Princeton, New Jersey: Princeton University Press, S. 575–604, ISBN 978-0-691-11880-2, HERR 2467561. Siehe insbesondere p. 583.
  7. ^ Buhler, J. P.; Lenstra, H. W. Jr.; Pomerance, Carl (1993). Berücksichtigung von Ganzzahlen mit dem Feld Feld Sieb (Vorlesungen in Mathematics, Band 1554 ed.). Springer. S. 50–94. doi:10.1007/bfb0091539. ISBN 978-3-540-57013-4. Abgerufen 12. März 2021.
  8. ^ Vanderypen, Lieven M. K.; et al. (2001). "Experimentelle Realisierung des Quanten -Faktorierungsalgorithmus von Shor unter Verwendung einer nuklearen Magnetresonanz". Natur. 414 (6866): 883–887. Arxiv:Quant-Ph/0112176. Bibcode:2001Natur.414..883v. doi:10.1038/414883a. PMID 11780055. S2CID 4400832.
  9. ^ Lance Fortnow (2002-09-13). "Computerkomplexität Blog: Komplexitätsklasse der Woche: Factoring".
  10. ^ a b David Bressoud und Stan Wagon (2000). Ein Kurs in der Rechenzahltheorie. Key College Publishing/Springer. pp.168–69. ISBN 978-1-930190-10-8.
  11. ^ Schnorr, Claus P. (1982). "Raffinierte Analyse und Verbesserungen bei einigen Factoring -Algorithmen". Journal of Algorithmen. 3 (2): 101–127. doi:10.1016/0196-6774 (82) 90012-8. HERR 0657269. Archiviert von das Original am 24. September 2017.
  12. ^ Seysen, Martin (1987). "Ein probabilistischer Faktorisierungsalgorithmus mit quadratischen Formen negativer Diskriminanzes". Mathematik der Berechnung. 48 (178): 757–780. doi:10.1090/s0025-5718-1987-0878705-x. HERR 0878705.
  13. ^ Lenstra, Arjen K (1988). "Schnelle und strenge Faktorisierung unter der verallgemeinerten Riemann -Hypothese". Indagationes Mathematicae. 50 (4): 443–454. doi:10.1016/s1385-7258 (88) 80022-2.
  14. ^ a b Lenstra, H. W.; Pomerance, Carl (Juli 1992). "Eine strenge Zeit für Factoring Ganzzahlen" (PDF). Zeitschrift der American Mathematical Society. 5 (3): 483–516. doi:10.1090/s0894-0347-1992-1137100-0. HERR 1137100.

Verweise

Externe Links