Warum wird es als schwierig angesehen, große ganze Zahlen zu faktorisieren?

Ich habe irgendwo gelesen , dass der effizienteste Algorithmus gefunden können die Faktoren berechnen Zeit, aber der Code , den ich geschrieben habe , ist O ( n ) oder Möglicherweise O ( n log n ), je nachdem, wie schnell Division und Modul sind. Ich bin mir ziemlich sicher, dass ich irgendwo etwas falsch verstanden habe, aber ich bin mir nicht sicher, wo. Hier ist, was ich in Pseudocode-Form geschrieben habe.$O(\exp((64/9 \cdot b)^{1/3} \cdot (\log b)^{2/3})$$O(n)$$O(n \log n)$

function factor(number) -> list
    factors = new list
    if number < 0
        factors.append(-1)
        number = -number
    i = 2
    while i <= number
        while number % i == 0
            factors.append(i)
            number /= i
        i++
    return factors

Sie verwechseln die Zahl mit der Anzahl der Bits, die zur Darstellung von n benötigt werden . Hier ist b = die Anzahl der zur Darstellung von n benötigten Bits (also b ≤ lg n ). Das macht einen großen Unterschied. A O ( n ) -Zeit - Algorithmus ist ein O ( 2 b ) -Zeit - Algorithmus - exponential in der Anzahl der Bits. Im Vergleich dazu hat der von Ihnen gefundene "effiziente" Algorithmus eine Laufzeit, die in b subexponentiell ist .$n$$n$$b =$$n$$b \approx \lg n$$O(n)$$O(2^b)$$b$

Beispiel: Betrachten Sie (2 Millionen). Dann genügen b = 21 Bits, um die Zahl n darzustellen . Also, ein Algorithmus, ist O ( 2 b 1 / 3 ) wird viel schneller als ein Algorithmus, ist O ( 2 b ) . Ein O ( n ) -Algorithmus fällt in die letztere Kategorie, dh sehr langsam.$n = 2,000,000$$b=21$$n$$O(2^{b^{1/3}})$$O(2^b)$$O(n)$

Siehe https://en.wikipedia.org/wiki/Integer_factorization

Sie haben hier ungefähr zwei Fragen, eine allgemeine und eine spezifische zu Ihrem Code. das spezifische wird in der anderen Antwort behandelt. Die allgemeine Frage im Titel über die Komplexität des Factorings ist sehr tief. Leider gibt es keine soliden wissenschaftlichen Beweise dafür, dass Factoring außerhalb von P liegt, mit Ausnahme der (meist umständlichen) Vermutung, dass viele Experten es innerhalb von P versucht haben und gescheitert sind. Es gilt als eines der wichtigsten (und schwer zu lösenden) offenen Probleme der Komplexitätstheorie. nach jahrzehntelangen "heftigen angriffen" sind die besten algorithmen exponentiell. Die Faktorisierungskomplexität ist eines der "wenigen außergewöhnlichen Probleme", von denen bekannt ist, dass sie zwischen " P " und "NP " liegen, die jedoch bisher nicht als vollständig eingestuft wurden.

Wie bereits erwähnt, war die Komplexität kein großes Problem, bis sie Mitte der achtziger Jahre ("grob") in den RSA-Kryptosystemen zum Einsatz kam, in denen die kryptografische Sicherheit von der Annahme abhängt . (Zwei weitere "nicht genau ermutigende" Datenpunkte: Shors-Algorithmus für P-Zeit-Quantenfaktor- und Primalitätstests wurde in den frühen 2000er-Jahren im berühmten / gefeierten AKS-Algorithmus als P-Wert nachgewiesen .) Ein mögliches positives Ergebnis wäre der folgende Die quasipolynomiale Zeit ist schwächer als NP complete (vorausgesetzt, dass P P NP und NP complete eine Exponentialzeituntergrenze haben ), aber technisch immer noch "hart".

Ich habe noch keine großartige Umfrage zu diesem Schlüssel-Thema gefunden. siehe aber auch

• Factoring kann einfacher sein als Sie denken / Cohn

• Evidence Integer Factoring in P / Mathoverflow (Erwähnung der Sarnak-Gedanken in P und Antwort auch von Cohn)

• "Impagliazzos-Welten, eine persönliche Sicht auf die durchschnittliche Fallkomplexität / Impagliazzo. Sie sprechen über komplexitätstheoretische Annahmen / Vermutungen im Allgemeinen im Zusammenhang mit der Kryptographie (z. B. Factoring). Viele / die meisten Schlüsselwelten (z. B. P vs NP usw.) sind nach Jahrzehnten noch offen.