Referensi untuk algoritma factoring optimal Levin?

Dalam " Saran untuk Mahasiswa Pascasarjana " Manuel Blum :

LEONID LEVIN percaya ketika saya melakukan itu, apa pun jawaban untuk P = NP? masalah, itu tidak akan seperti apa pun yang Anda pikir seharusnya. Dan dia telah memberikan beberapa contoh yang indah. Untuk satu, ia telah memberikan ALGORITMA PABRIK yang terbukti optimal, hingga konstanta multiplikasi. Dia membuktikan bahwa jika algoritmanya eksponensial, maka setiap algoritme untuk FAKTOR adalah eksponensial. Setara, jika ada algoritma untuk anjak adalah poli-waktu, maka algoritme-nya adalah poli-waktu. Tetapi kami belum dapat mengetahui waktu berjalan dari algoritmanya karena, dalam arti yang kuat, waktu berjalannya tidak dapat dianalisis.

Halaman publikasi Levin menghasilkan 404, DBLP menunjukkan tidak ada yang terkait dengan anjak piutang, dan pencarian untuk "leonid levin anjak" di Google Cendekia tidak menghasilkan apa pun yang menarik yang dapat saya temukan. AFAIK saringan umum adalah algoritma tercepat yang dikenal untuk anjak piutang. Apa yang sedang dibicarakan Manuel Blum? Adakah yang bisa menautkan saya ke kertas?

ds.algorithms reference-request factoring Christopher Monsanto
sumber

Jawaban:

Manuel Blum berbicara tentang penerapan algoritma pencarian universal Levin untuk masalah Faktorisasi Integer. Ide algoritma pencarian Universal Levin sama berlaku untuk setiap masalah dalam . $NP$

Berikut adalah kutipan dari catatan kuliah yang diberikan oleh Blum tentang KEAMANAN dan CRYPTOGRAFI:

Leonid LEVIN's OPTIMAL NUMBER-SPLITTING (FACTORING) ALGORITMA. Biarkan SPLIT menunjukkan algoritma apa pun yang menghitung INPUT: integer komposit positif (yaitu bukan prime) n. OUTPUT: faktor nontrivial dari n.

THEOREM: Terdapat algoritme pemecahan angka "optimal", yang kami sebut OPTIMAL-SPLIT. Algoritma ini adalah OPTIMAL dalam arti bahwa: untuk setiap Algoritma SPLIT pemisah-angka terdapat konstanta (cukup besar tetapi tetap) sehingga untuk setiap input integer komposit positif n, "waktu berjalan" OPTIMAL-SPLIT pada input n adalah paling banyak C kali waktu berjalan SPLIT pada input n.

Berikut adalah algoritma pemfakturan yang optimal dari Levin :

ALGORITMA OPTIMAL-SPLIT: BEGIN Hitung semua algoritme sesuai ukuran, secara leksikografis dalam setiap ukuran. Jalankan semua algoritma sehingga setiap saat dalam waktu, t, algoritma ith mendapat [1 / (2 ^ i)] fraksi waktu untuk dieksekusi. Setiap kali suatu algoritma berhenti dengan beberapa bilangan bulat m dalam kisaran 1 <m <n, periksa apakah m membaginya n (yaitu jika n mod m = 0). Jika demikian, kembalikan m. AKHIR

Mohammad Al-Turkistany
sumber

Adakah yang bisa menjelaskan mengapa pecahannya harus 1 / (2 ^ i) tetapi bukan sesuatu yang lebih sederhana seperti 1 / i?

netvope

@netvope: Jumlah tak terbatas dari 1 / i diverges. Anda mungkin dapat melakukannya dengan 1 / i ^ 2 tetapi 1/2 ^ saya jauh lebih sederhana.

Antimony

$NP \cap coNP$

Diberi nomor yang ingin kita beri faktor N.

Apakah N prime? Jika demikian, output 'PRIME' yang lain:

$i = 1...\infty$

$P = 1...i$

Jalankan program P untuk langkah saya dengan input N

$L \neq 1$ $M \neq 1$ $N = L*M$ $(L,M)$

Artem Kaznatcheev
sumber

Anda tidak dapat menggunakan tes primality yang dikenal karena tidak diketahui lebih cepat daripada anjak piutang optimal. Selain itu, saya tidak mengerti satu hal. Untuk membuktikan bahwa ini optimal untuk memfaktorkan faktor konstan, saya pikir kita harus membuktikan bahwa perkalian pada langkah terakhir bukanlah istilah dominan dalam kompleksitas waktu. Jika saya ingat dengan benar, algoritma multiplikasi yang paling cepat diketahui dalam pengaturan asimptotik didasarkan pada FFT dan membutuhkan waktu O (n log n log log n) untuk bilangan bulat n-bit. Apakah mungkin membuktikan bahwa anjak piutang optimal membutuhkan setidaknya selama ini?

Tsuyoshi Ito

@ Tsuyoshi: Saya pikir Anda benar karena algoritma ini gagal menjadi optimal jika tes multiplikasi / primality yang diketahui lebih sulit daripada anjak piutang. Namun, jika Anda membaca kutipan Blum di atas, ia hanya mengatakan bahwa algoritma Levin adalah polinomial jika dan hanya jika yang optimal adalah, yang mengatasi masalah ini. Dua hal lain: (1) bagaimana Anda bisa menghindari menggunakan tes primality yang dikenal dalam algoritma ini? (2) Saya pikir algoritma ini tidak dirumuskan dengan benar karena waktu berjalan tidak dipartisi dengan benar di antara berbagai program; lihat jawaban Al-Turkistany untuk formulasi yang tepat.

Peter Shor

@ Peter: Yah, kutipan Blum mengatakan "dia [Levin] telah memberikan ALGORITMA FAKTOR yang terbukti optimal, hingga konstanta multiplikatif." Tetapi mengingat bahwa kita bahkan tidak tahu apakah anjak piutang membutuhkan lebih dari waktu linier atau tidak, pernyataan itu sulit dipercaya.

Tsuyoshi Ito

@ Tsuyoshi: Begitu, saya membaca kutipan Blum yang salah.

Peter Shor