Apa kompleksitas kasus terburuk dari saringan bidang angka?

Mengingat komposit jumlah jenderal lapangan saringan terkenal algoritma faktorisasi untuk integer faktorisasi . Ini adalah algoritma acak dan kami mendapatkan kompleksitas yang diharapkan dari faktor . $N\in\Bbb N$ $N$ $O\Big(e^{\sqrt{\frac{64}{9}}(\log N)^{\frac 13}(\log\log N)^{\frac 23}}\Big)$ $N$

Saya mencari informasi tentang kompleksitas kasus terburuk pada algoritma acak ini. Namun saya tidak dapat menemukan informasi.

(1) Apa kompleksitas kasus terburuk dari saringan bidang Angka?

(2) Juga dapatkah keacakan dihapus di sini untuk memberikan algoritma subeksponensial deterministik?

reference-request derandomization factoring average-case-complexity worst-case
sumber

Jawaban:

Saringan bidang angka tidak pernah dianalisis secara ketat. Kompleksitas yang Anda kutip hanyalah heuristik. Satu-satunya algoritma subeksponensial yang telah dianalisis secara ketat adalah algoritma faktorisasi Dixon , yang sangat mirip dengan saringan kuadratik. Menurut Wikipedia, algoritma Dixon berjalan dalam waktu . Algoritma Dixon adalah acak. $e^{O(2\sqrt{2}\sqrt{\log n\log\log n})}$

Semua algoritma subeksponensial (heuristik) yang dikenal membutuhkan pengacakan. Algoritma Dixon perlu menemukan bilangan bulat sehingga halus (dapat difaktorkan ke dalam produk bilangan prima kecil) dan "acak", dan saringan bidang angka memiliki persyaratan yang sama tetapi lebih rumit. Metode kurva eliptik kebutuhan untuk menemukan kurva modulo eliptik yang rangka modulo beberapa faktor adalah halus. Dalam kedua kasus itu tampaknya sulit untuk derandomisasi algoritma. $x$ $x^2 \pmod{n}$ $n$ $n$

Kompleksitas nominal terburuk dari semua algoritma ini adalah tak terhingga: dalam kasus saringan kuadrat dan saringan angka-bidang Anda mungkin selalu menghasilkan sama , sedangkan dalam metode kurva eliptik Anda selalu dapat menghasilkan kurva eliptik yang sama . Ada banyak cara untuk mengatasi hal ini, misalnya menjalankan algoritma waktu eksponensial secara paralel. $x$

Yuval Filmus
sumber

Karena Anda menyentuh ECM juga: kami tahu algoritma acak sub-eksploitasi untuk menghitung di waktu menggunakan ECM di mana tidak diketahui dan acak. Apakah Anda memiliki perkiraan tentang berapa banyak percobaan dari algoritma ini yang cukup untuk mendapatkan dan mana ?

n! r

$n!r$

O (e x p (\sqrt{\log n}))

$O(exp(\sqrt{\log n}))$

r

$r$

n! r

$n!r$

n! s

$n!s$

(r, s) = 1

$(r,s)=1$

Saya tidak tahu apa itu , tetapi secara umum, ketika memilih parameter dalam ECM, kami menyeimbangkan antara probabilitas bahwa kurva cukup halus, dan waktu berjalan diperlukan untuk menguji setiap kurva. Biasanya titik keseimbangan adalah ketika . Jadi jumlah percobaan yang diharapkan adalah .

n! r

$n!r$

p

$p$

T

$T$

1 / p \approx T

$1/p \approx T$

O (\exp \sqrt{\log n})

$O(\exp\sqrt{\log n})$

Yuval Filmus

n!

$n!$ adalah faktorial dari . Ini adalah masalah terbuka untuk mendapatkan kompleksitas garis lurus faktorial. Kita tahu cara menghitung mana tidak diketahui dalam waktu subexp. Jika kita mengetahui dua dan , kita dapat memperolehdalam waktu subexp jika .

n

$n$

n! r

$n!r$

r

$r$

n! r

$n!r$

n! s

$n!s$

(n! r, n! s) = n!

$(n!r,n!s)=n!$

(r, s) = 1

$(r,s)=1$

Saya ingat menghitung beberapa waktu lalu. Saya tidak berpikir saya bisa mendapatkan peningkatan karena ada tangkapan dan saya tidak ingat detailnya.

paragraf terakhir sepertinya aneh & bisa diklarifikasi lebih lanjut. Apakah Anda berbicara tentang sebuah skenario di mana RNG "rusak" dalam arti tidak sampel ruang distribusi keseluruhan? tetapi kemudian apakah paralelisme tidak akan membantu di sana? karena itu akan menjadi RNG "rusak" yang sama secara paralel? atau apakah ide itu akan menjalankan RNG yang berbeda secara paralel? sebenarnya kompleksitas paralel dari algoritma anjak adalah benar-benar seluruh topik kompleks lainnya misalnya beberapa dapat diparalelkan lebih baik daripada yang lain, big-O mungkin tidak dapat diterapkan, dll

vzn

Dalam beberapa bulan terakhir, versi ayakan bidang angka telah dianalisis dengan ketat: http://www.fields.utoronto.ca/talks/rigorous-analysis-randomized-number-field-sieve-factoring

Pada dasarnya waktu menjalankan kasus terburuk adalah tanpa syarat dan bawah GRH. Ini bukan untuk saringan bidang angka "klasik", tetapi versi yang sedikit dimodifikasi yang mengacak lebih banyak langkah untuk membuat analisis kompleksitas lebih mudah. $L_n(1/3, 2.77)$ $L_n(1/3, (64/9)^{1/3})$

Saya percaya makalah yang sesuai masih dalam peninjauan.

Pembaruan: Makalah sudah keluar sekarang. Jonathan D. Lee dan Ramarathnam Venkatesan, "Analisis ketat ayakan bidang angka acak," Journal of Number Theory 187 (2018), hlm. 92-159, doi: 10.1016 / j.jnt.2017.10.019

djao
sumber

Bisakah Anda memberikan referensi yang lebih lengkap di mana kita bisa belajar lebih banyak, dengan judul, penulis, dan di mana diterbitkan, sehingga jawabannya tetap berguna bahkan jika tautannya berhenti berfungsi?

Karena hasilnya baru saja diumumkan, saya percaya ini sedang ditinjau sebagaimana ditunjukkan dalam jawaban saya, dan karena itu belum dipublikasikan. Saya akan memperbarui jawaban saya di masa mendatang ketika informasi publikasi tersedia.

djao

FWIW sepertinya tidak ada di arxiv.org. Namun, penulisnya adalah Ramarathnam Venkatesan, yang dapat membantu pencarian di masa depan jika diperlukan.

Peter Taylor

Ini sebenarnya adalah karya dua penulis (JD Lee dan R. Venkatesan): cmi.ac.in/activities/…

Sary