dlaczego współczynnik faktoryzacji całkowitej jest czasem nie-wielomianowym?

Question

Jestem dopiero początkującym informatykiem. Nauczyłem się czegoś o czasie pracy, ale nie mogę być pewien, co rozumiem. Więc proszę, pomóż mi.

Faktoryzacja liczb całkowitych nie jest obecnie problemem z czasem wielomianowym, ale testem pierwotności jest. Załóżmy, że liczba do sprawdzenia to n. Jeśli uruchomimy program, aby zdecydować, czy każda liczba od 1 do sqrt (n) może dzielić n, a jeśli odpowiedź brzmi tak, to zapisz numer. Myślę, że ten program to czas wielomianowy, prawda?

Jednym z możliwych sposobów, w jaki się mylę, byłby program faktoryzacji powinien znaleźć wszystkie liczby pierwsze, zamiast pierwszego odkrytego. Więc może to jest powód.

Jednak w kryptografii z kluczem publicznym znalezienie współczynnika głównego dużej liczby jest niezbędne do zaatakowania kryptografii. Ponieważ zazwyczaj duża liczba (klucz publiczny) jest tylko iloczynem dwóch liczb pierwszych, znalezienie jednej wartości początkowej oznacza znalezienie drugiej. To powinien być czas wielomianowy. Dlaczego atakowanie jest trudne lub niemożliwe?

Answer 1

Dorywcze opisy złożoności, takie jak "wielomianowy faktoring" Algorytm "ogólnie odnosi się do złożoności w odniesieniu do rozmiaru wejściowego rozmiaru sygnału wejściowego. Kiedy więc ludzie mówią "brak znanego wielomianowego algorytmu faktoringu", oznacza to, że nie ma znanego algorytmu do faktycznego obliczania liczby naturalnej, która działa w czasie wielomianowym względem N. Nie wielomian w odniesieniu do samej liczby, która może wynosić maksymalnie 2^N.

Answer 2

Jeśli uruchomimy program tylko po to, aby zdecydować, czy każda liczba od 1 do sqrt (n) może dzielić n, a jeśli odpowiedź brzmi tak, to zapisać numer.

Nawet pomijając, że test podzielność potrwa dłużej przy większych ilościach, to podejście trwa prawie dwa razy dłużej, jeśli po prostu dodać jeden (binarnie) cyfrę n. (Właściwie to zajmie dwa razy więcej, jeśli dodasz dwie cyfry)

Myślę, że jest to definicja wykładniczego runtime: Make n o jeden raz dłużej, algorytm zajmuje dwa razy dłużej.

Należy jednak zauważyć, że ta uwaga dotyczy tylko zaproponowanego algorytmu. Wciąż nie wiadomo, czy faktoryzacja całek jest wielomianem czy nie. Kryptografowie mają nadzieję, że tak nie jest, ale są też alternatywne algorytmy, które nie zależą od twardej faktoryzacji prime (takiej jak kryptografia krzywej eliptycznej), na wszelki wypadek ...

Answer 3

Trudność faktoryzacji to jeden z tych pięknych problemów matematycznych, które są proste do zrozumienia i od razu prowadzą do krawędzi ludzkiej wiedzy. Podsumowując (dzisiejszą) wiedzę na ten temat: nie wiemy, dlaczego jest to trudne, nie z żadnym stopniem dowodu, i najlepsze metody, które prowadziliśmy w czasie dłuższym niż wielomian (ale także znacznie mniej niż czas wykładniczy). Wynik, że primality testing jest nawet w P jest całkiem nowy; zobacz powiązaną stronę Wikipedii.

Najlepszym wyjaśnieniem heurystycznym, które znam, jest to, że liczby pierwsze są losowo rozdzielane. Jednym z łatwiejszych do zrozumienia wyników jest Dirichlet's theorem. To twierdzenie mówi, że każda arytmetyczna progresja zawiera nieskończenie wiele liczb pierwszych, innymi słowy, można myśleć o liczbach pierwszych jako gęstych w odniesieniu do progresji, co oznacza, że ​​nie można uniknąć w nich ucieczki.Jest to najprostsza z dość dużej kolekcji takich wyników; we wszystkich przypadkach liczby pierwsze pojawiają się w sposób bardzo podobny do liczb losowych.

Trudny faktoring jest zatem analogiczny do niemożliwości cofnięcia jednorazowej podkładki. W jednorazowym padzie jest trochę nie znamy XOR z innym, którego nie znamy. Dostajemy zerową informację o pojedynczym kawałku znającym wynik XOR. Zastąp "bit" słowem "prime" i mnożenie przez XOR, i masz problem z faktoringiem. To tak, jakbyś pomnożył dwie liczby losowe, a otrzymasz bardzo mało informacji z produktu (zamiast zera informacji).