Mengapa Odlyzko meningkatkan Algoritma Shor mengurangi jumlah uji coba menjadi

Dalam makalahnya tahun 1995, Algoritma Polinomial-Waktu untuk Faktorisasi Utama dan Logaritma Terpisah pada Komputer Quantum , Peter W. Shor membahas peningkatan pada bagian pencarian-urutan dari algoritma faktorisasi-nya. Output algoritma standar $r'$ , pembagi dari urutan $r$ dari $x$ modulo $N$ . Alih-alih memeriksa jika $r'=r$ dengan memeriksa jika , peningkatannya adalah sebagai berikut: $x^{r'}\equiv 1 \mod N$

[F] atau kandidat $r$ harus dipertimbangkan tidak hanya $r ′$ tetapi juga kelipatan kecilnya $2r ′ , 3r ′ , \dots$ , untuk melihat apakah ini adalah urutan aktual $x$ . [... Ini] teknik akan mengurangi jumlah percobaan yang diharapkan untuk paling sulit $n$ dari $O(\log \log n)$ menjadi $O(1)$ jika yang pertama ( $\log n)^{1+\epsilon}$ kelipatan $r ′$ Dianggap [Odylzko 1995].

Referensi ke [Odylzko 1995] adalah "komunikasi pribadi", tetapi saya tidak hadir ketika Peter Shor dan Andrew Odlyzko membahas ini ... Saya sangat mengerti mengapa ini merupakan peningkatan, tetapi saya tidak tahu bagaimana menunjukkan nomornya. uji coba dikurangi menjadi . Apakah Anda tahu bukti tentang ini? $O(1)$

quantum-computing nt.number-theory factoring Frédéric Grosshans
sumber

Apa yang dilakukan algoritma? Pada dasarnya, dibutuhkan dan acak dan keluaran . jadi jika Anda memeriksa semua kelipatan kecil dari , maka sangat mungkin bahwa adalah salah satunya. Mengapa memberi ? Itu teori bilangan. Andrew Odlyzko adalah ahli teori angka, dan saya berkonsultasi dengannya tentang masalah ini, tetapi saya benar-benar lupa pembenarannya untuk ini.

r

$r$

ℓ \leq r

$\ell \leq r$

r^{'} = r / g c d (ℓ, r)

$r' = r/gcd(\ell,r)$

r^{'}

$r'$

r

$r$

(\log n)^{1 + ϵ}

$(\log n)^{1+\epsilon}$

O (1)

$O(1)$

Peter Shor

Terima kasih! Sepertinya saya perlu mencari sejumlah ahli teori sendiri!

Frédéric Grosshans

Anda mungkin ingin mencoba MathOverflow .

Kaveh

Saya sedang memikirkannya. Saya mungkin akan merumuskannya kembali dengan cara yang lebih "teori nomor" untuk itu, jika saya tidak mendapatkan jawabannya segera. Saya pikir itu dapat diulang sebagai jumlah fungsi totient.

Frédéric Grosshans

@ Kaveh: Pertanyaan terkait pada MathOverflow , menanyakan pertanyaan teori bilangan terkait yang, saya pikir, setara.

Frédéric Grosshans

Mengapa Odlyzko meningkatkan Algoritma Shor mengurangi jumlah uji coba menjadi

Jawaban: