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ą?

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

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)$