Odniesienie do optymalnego algorytmu faktoringu Levina?

W „ Poradzie dla początkującego studenta ” Manuela Bluma :

LEONID LEVIN wierzy, jak to robię, niezależnie od odpowiedzi na P = NP? problem, to nie będzie tak, jak myślisz, że powinno być. Podał też wspaniałe przykłady. Po pierwsze, podał FACTORING ALGORITHM, który jest optymalnie optymalny, aż do stałej multiplikatywnej. Udowadnia, że jeśli jego algorytm ma charakter wykładniczy, to każdy algorytm FAKTOROWANIA jest wykładniczy. Odpowiednio, jeśli dowolny algorytm faktoringu jest wielogodzinny, to jego algorytm jest wielogodzinny. Ale nie byliśmy w stanie określić czasu działania jego algorytmu, ponieważ w silnym sensie czas ten jest niemożliwy do przeanalizowania.

Strona publikacji Levina zwraca 404, DBLP nie pokazuje nic związanego z faktoringiem, a poszukiwanie „leonid levin factoring” w Google Scholar nie zwraca niczego, co mogłoby znaleźć. AFAIK uogólnione sito jest najszybszym algorytmem znanym z faktoringu. O czym mówi Manuel Blum? Czy ktoś może powiązać mnie z gazetą?

ds.algorithms reference-request factoring

— Christopher Monsanto
źródło

Odpowiedzi:

Manuel Blum mówi o zastosowaniu uniwersalnego algorytmu wyszukiwania Levina do problemu faktoryzacji liczb całkowitych. Idea uniwersalnego algorytmu wyszukiwania Levina ma również zastosowanie do każdego problemu w . $NP$

Oto cytat z notatek z wykładów wydanych przez Blum na temat BEZPIECZEŃSTWA i KRYPTOGRAFII:

Leonid LEVIN OPTYMALNY ALGORYTM LICZBY ROZDZIELANIA (FAKTOROWANIA). Niech SPLIT oznacza dowolny algorytm obliczający WEJŚCIE: dodatnią liczbę całkowitą złożoną (tj. Nie pierwszą) n. WYDAJNOŚĆ: nietrywialny czynnik n.

TEOREM: Istnieje „optymalny” algorytm dzielenia liczb, który nazywamy OPTIMAL-SPLIT. Algorytm ten jest OPTYMALNY w tym sensie, że: dla każdego algorytmu rozdzielającego liczby SPLIT istnieje (dość duża, ale stała) stała C, tak że dla każdego pozytywnego złożonego wejścia liczby całkowitej n „czas działania” OPTIMAL-SPLIT na wejściu n wynosi najwyżej C razy czas działania SPLIT na wejściu n.

Oto optymalny algorytm faktoringu Levina :

Algorytm OPTIMAL-SPLIT: POCZĄTEK Wylicz wszystkie algorytmy według wielkości, leksykograficznie dla każdego rozmiaru. Uruchom wszystkie algorytmy, aby w dowolnym momencie t, i-ty algorytm otrzymał [1 / (2 ^ i)] ułamek czasu na wykonanie. Gdy algorytm zatrzymuje się z pewną liczbą całkowitą wyjściową m w zakresie 1 <m <n, sprawdź, czy m dzieli n (tj. Czy n mod m = 0). Jeśli tak, zwróć m. KONIEC

— Mohammad Al-Turkistany
źródło

Czy ktoś może wyjaśnić, dlaczego ułamek musi wynosić 1 / (2 ^ i), ale nie coś prostszego jak 1 / i?

— netvope

@netvope: Nieskończona suma 1 / i jest rozbieżna. Możesz to zrobić za pomocą 1 / i ^ 2, ale 1/2 ^ i jest o wiele prostsze.

— Antymon

Nie jestem pewien, czy właśnie o tym mówił Blum, ale łatwo jest stworzyć optymalny algorytm aż do stałego współczynnika dla prawie każdego . Oto w szczególności szkic faktoringu. $NP \cap coNP$

Biorąc pod uwagę liczbę, chcemy czynnik N.

Czy N jest liczbą pierwszą? Jeśli tak, wpisz „PRIME” w innym przypadku:

Dla $i = 1...\infty$

Dla $P = 1...i$

Uruchom program P dla i kroków z wejściem N

Jeśli P wyprowadza dwie liczby całkowite (L, M) i i i wówczas wyprowadza $L \neq 1$ $M \neq 1$ $N = L*M$ $(L,M)$

— Artem Kaznatcheev
źródło

Nie można użyć znanego testu pierwszeństwa, ponieważ nie jest on znany jako szybszy niż faktoring optymalny. Poza tym nie rozumiem jednego punktu. Aby udowodnić, że jest to optymalne do faktorowania do stałego czynnika, uważam, że musimy udowodnić, że mnożenie w ostatnim kroku nie jest dominującym terminem w złożoności czasowej. Jeśli dobrze pamiętam, najszybszy znany algorytm mnożenia w ustawieniu asymptotycznym jest oparty na FFT i zajmuje O (n log n log log n) czas na n-bitowe liczby całkowite. Czy można udowodnić, że optymalny faktoring zajmuje co najmniej tyle czasu?

— Tsuyoshi Ito

@Tsuyoshi: Myślę, że masz rację, ponieważ ten algorytm nie jest optymalny, jeśli znane testy mnożenia / pierwotności są trudniejsze niż faktoring. Jeśli jednak przeczytasz powyższy cytat Bluma, mówi on tylko, że algorytm Levina jest wielomianowy wtedy i tylko wtedy, gdy jest optymalny, co rozwiązuje ten problem. Dwie inne rzeczy: (1) jak można uniknąć stosowania znanego testu pierwszeństwa w tym algorytmie? (2) Myślę, że ten algorytm nie jest sformułowany całkiem dobrze, ponieważ czas działania nie jest właściwie podzielony między różne programy; patrz odpowiedź Al-Turkistany na właściwe sformułowanie.

— Peter Shor,

@Peter: Cóż, cytat Bluma mówi: „on [Levin] podał FACTORING ALGORITHM, który jest możliwy do udowodnienia optymalnie, aż do stałej multiplikatywnej”. Biorąc jednak pod uwagę, że nie wiemy nawet, czy faktoring zajmuje więcej niż czas liniowy, czy nie, trudno jest w to uwierzyć.

— Tsuyoshi Ito

@Tsuyoshi: Rozumiem, czytałem zły cytat Bluma.

— Peter Shor,