Dlaczego faktoring dużych liczb całkowitych jest uważany za trudny?

I odczytu gdzieś, że najbardziej skuteczny algorytm znaleźć można obliczyć czynniki czasu, ale to kod pisał jest O ( n ) lub prawdopodobnie O ( n log n ) w zależności od tego, jak szybki jest podział i moduł. Jestem pewien, że coś gdzieś źle zrozumiałem, ale nie jestem pewien gdzie. Oto, co napisałem w formie pseudokodu.$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

Mylisz liczbę z liczbą bitów potrzebnych do przedstawienia n . Tutaj b = liczba bitów potrzebna do przedstawienia n (więc $n$$n$$b =$$n$ ). To ogromna różnica. O ( n ) -czas algorytm jest O ( 2 b ) -czas algorytm - wykładniczy liczby bitów. Dla porównania, znaleziony „efektywny” algorytm ma czas działania podwykładniczy w b .$b \approx \lg n$$O(n)$$O(2^b)$$b$

Przykład: Rozważmy (2000000). Wtedy b = 21 bitów wystarcza do przedstawienia liczby n . Tak więc algorytm to O ( $n = 2,000,000$$b=21$$n$jest znacznie szybszy niż algorytmu, który jestO(2b). O(n)algorytm należy do tej drugiej kategorii, czyli bardzo powoli.$O(2^{b^{1/3}})$$O(2^b)$$O(n)$

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

masz tutaj z grubsza dwa pytania, ogólne i szczegółowe dotyczące twojego kodu. konkretny jest obsługiwany w drugiej odpowiedzi. ogólne pytanie w tytule dotyczące złożoności faktoringu jest bardzo głębokie. niestety nie ma mocnych dowodów naukowych, że faktoring jest poza P, poza (głównie okolicznościowymi) „wieloma ekspertami próbowali i ponieśli porażkę”, a niektórzy eksperci przypuszczają, że jest to w P; jest uważany za jeden z najważniejszych (i bardzo trudnych do rozwiązania) otwartych problemów teorii złożoności. po dziesięcioleciach „ciężkiego ataku” najlepsze algorytmy są wykładnicze. złożoność faktoringu jest jednym z „niewielu wyjątkowych problemów”, o których wiadomo, że leżą „między” P i NP zakończonymi, ale jak dotąd nie została sklasyfikowana.

jak wskazano, złożoność nie stanowiła większego problemu, dopóki nie została wykorzystana („z grubsza”) w kryptosystemach RSA w połowie lat 80. XX wieku, gdzie bezpieczeństwo kryptograficzne zależy od założenia. (dwa inne „niezupełnie zachęcające” punkty danych: algorytm Shorsa dla faktoringu kwantowego w czasie P i testowania pierwotności okazał się być w P na początku 2000 roku w słynnym / znanym algorytmie AKS .) możliwy pozytywny wynik byłby taki, że jest to czas quasipolynomialny , który jest słabszy niż NP zupełny (zakładając, że P ≠ NP i NP zupełny ma dolny czas wykładniczy ), ale technicznie „twardy”.

jak dotąd nie znalazłem świetnej ankiety dotyczącej tego kluczowego tematu. jednak patrz także

• Faktoring może być łatwiejszy niż myślisz / Cohn

• Faktoring liczb całkowitych w P / mathoverflow (wspominając, że Sarnak myśli w P, a odpowiedź Cohna również)

• „Światy Impagliazzos, osobisty pogląd na średnią złożoność przypadków / Impagliazzo. Mówi o złożoności teoretycznych założeń / przypuszczeń ogólnie związanych z kryptografią (np. Faktoring). Wiele / większość kluczowych (np. P vs. NP itp.) Jest nadal otwartych po dziesięcioleciach.