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

17

I odczytu gdzieś, że najbardziej skuteczny algorytm znaleźć można obliczyć czynniki czasu, ale to kod pisał jest lub prawdopodobnie 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

— EnderShadow
źródło

3

Google „pseudo wielomian”.

— Raphael

Algorytm ten jest w rzeczywistości bardzo wolny - jeśli liczba jest liczbą pierwszą, pętla podczas iteracji (liczby) razy. Istnieje bardzo prosty argument, który pozwala uniknąć iteracji sqrt (liczby).

— gnasher729,

26

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

Przykład: Rozważmy (2000000). Wtedy bitów wystarcza do przedstawienia liczby . Tak więc algorytm to $n = 2,000,000$ $b=21$ $n$ jest znacznie szybszy niż algorytmu, który jest. 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

— DW
źródło

1

Wiedziałem, że to takie proste.

— EnderShadow,

3

@EnderShadow: Również liczby, których faktoring uważa się za trudne przy użyciu obecnie dostępnego sprzętu i używane np. W szyfrowaniu RSA, mają

(tj.

b > 1,000

$b > 1{,}000$

n > 2^{1,000}

$n > 2^{1{,}000}$ ) lub więcej. W ramach ćwiczenia, zakładając, że komputer może uruchamiać algorytm

z, powiedzmy, miliardem iteracji na sekundę, obliczyć, ile lat zajęłoby współczynnik

O (n)

$O(n)$

. (Jeśli twoja początkowa reakcja brzmi „to nie może być poprawne!”, Prawdopodobnie poprawnie to obliczyłeś.)

n \approx 2^{1,000}

$n \approx 2^{1{,}000}$

— Ilmari Karonen,

1

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.

— vzn
źródło

innym możliwym, z pozoru „scenariuszem skrajnym”, jest fakt, że faktoring może być w P, ale wciąż nie ma wykonalnego algorytmu. alias algorytmy galaktyczne

— od

Należy wspomnieć, że RSA dotyczy faktoryzacji iloczynu dwóch dużych liczb pierwszych (gdzie ktoś zna liczby pierwsze i po prostu je pomnożył, a ktoś inny otrzymuje ten produkt i powinien znaleźć liczby pierwsze). Można sobie wyobrazić algorytm, który może uwzględniać produkty dwóch dużych liczb pierwszych, ale nie iloczyn więcej niż dwóch dużych liczb pierwszych. Podobnie jak liczby faktoringowe, które są dużymi liczbami pierwszymi (ale nie są wcześniej znane jako duże liczby pierwsze), można wykonać w czasie wielomianowym.

— gnasher729