Menambahkan bilangan bulat yang diwakili oleh faktorisasi mereka sama sulitnya dengan anjak piutang? Permintaan referensi

Saya mencari referensi untuk hasil berikut:

Menambahkan dua bilangan bulat dalam representasi factored sama sulitnya dengan memfaktorkan dua bilangan bulat dalam representasi biner biasa.

(Saya cukup yakin itu ada di luar sana karena ini adalah sesuatu yang saya tanyakan pada suatu saat, dan kemudian bersemangat ketika akhirnya saya melihatnya di media cetak.)

"Menambahkan dua bilangan bulat dalam representasi yang difaktorkan" adalah masalahnya: mengingat faktorisasi utama dari dua angka dan , hasilkan faktorisasi utama . Perhatikan bahwa algoritma naif untuk masalah ini menggunakan faktorisasi dalam representasi biner standar sebagai subrutin.y x + $x$$y$$x+y$

Pembaruan : Terima kasih Kaveh dan Sadeq untuk buktinya. Jelas semakin banyak bukti yang lebih meriah, tetapi saya juga ingin mendorong lebih banyak bantuan dalam menemukan referensi , yang seperti yang saya katakan saya cukup yakin ada. Saya ingat pernah membacanya di sebuah makalah dengan ide-ide lain yang menarik dan tidak sering dibahas di dalamnya, tetapi saya tidak ingat apa ide-ide lain itu atau apa makalah itu secara umum.

Asumsikan bahwa kita dapat menyelesaikan masalah (sebut saja FactSum) dalam kompleksitas kelas dan ditutup di bawah -iteration (alias recursi-terikat) (misalnya jika kita dapat menghitung mana adalah fungsi biner, kita dapat menghitung ) dan berisi (kondisi terakhir ini dapat dibuat lebih lemah). Kami menunjukkan bahwa anjak dalam juga dalam .C log log x * y * x 1 * ... * x log n P$C$$C$$\log$$\log$$x*y$$*$$x_1*\ldots*x_{\log{n}}$$\mathsf{P}$$C$

Perhatikan bahwa setiap angka dapat ditulis sebagai jumlah dari kekuatan 2 . Masing-masing dari mereka mudah diperhitungkan.$\log n$$2$

Sekarang diberi nomor, tulis sebagai jumlah kekuatannya, lalu tulis masing-masing ringkasan dalam representasi anjak, dan kemudian gunakan algoritma untuk menjumlahkannya dalam representasi anjak. Hasilnya akan menjadi anjak dari nomor input.

Ini menunjukkan bahwa anjak piutang dapat direduksi menjadi -masalah pada FactSum Anda. Oleh karena itu, anjak piutang adalah dalam P FactSum (dan saya pikir P dapat diganti dengan N C 1 di sini).$\log$$\mathsf{P}^{\text{FactSum}}$$\mathsf{P}$$\mathsf{NC^1}$

Saya tidak mengetahui referensi, tapi saya pikir saya datang dengan bukti:

Asumsikan Anda memiliki oracle yang, pada input dua angka faktor$\mathcal{O}$

$x = \prod_{i=1}^n p_i^{\alpha_i}$

dan

$y = \prod_{i=1}^m q_i^{\beta_i} \enspace$,

menghasilkan faktorisasi .$x+y$

Dengan memiliki akses ke , kami dapat memperhitungkan faktor N dalam waktu polinomial menggunakan prosedur rekursif berikut.$\mathcal{O}$$N$

Faktor PROSEDUR ( )$N$

1. Temukan bilangan prima sehingga N / 2 ≤ x ≤ N - 1 , dan biarkan y = N - x .$x$$N/2 \le x \le N-1$$y = N - x$
2. Jika tidak prima, mendapatkan faktorisasi dari y oleh faktor rekursif panggilan ( y ) dan output O ( x , f a c t o r ( y ) ) .$y$$y$$y$$\mathcal{O}(x, factor(y))$
3. Keluaran lain .$\mathcal{O}(x,y)$

Analisis:

Dengan teorema bilangan prima untuk cukup besar , ada banyak bilangan prima di antara N / 2 dan N - 1 . Jika N sangat kecil sehingga tidak ada prima yang jatuh dalam interval ini, Anda dapat memfaktorkan N dengan mudah. Karena itu, langkah 1 berlalu.$N$$N/2$$N-1$$N$$N$

Pada langkah 2, Anda dapat menggunakan AKS atau tes primality waktu polinomial lainnya.

Jumlah rekursi hanyalah , karena pada setiap langkah N dipotong menjadi setengah (setidaknya)$O(\lg(N)) = O(|N|)$$N$

PS-1: Dengan asumsi dugaan Goldbach dapat membantu mempercepat prosedur untuk bilangan bulat genap (dan mungkin ganjil).

PS-2: Pengurangan yang digunakan adalah pengurangan Cook. Orang mungkin tertarik untuk melakukan bukti menggunakan pengurangan Karp.

Tanggapan ini tidak tergantung pada jawaban saya sebelumnya . Tujuannya adalah untuk mengatasi kekhawatiran @ Kaveh dalam komentar:

Hal ini mudah dilakukan jika kita ingin angka, tapi saya tidak melihat bagaimana melakukannya bahkan dengan log log n nomor.$\log n$$\log \log n$

Saya memiliki keprihatinan serupa:

Pengurangan yang digunakan adalah pengurangan Cook. Seseorang mungkin tertarik untuk melakukan bukti menggunakan pengurangan Karp.

(Pengurangan karp adalah untuk masalah keputusan. Di sini, dengan pengurangan Karp, maksud saya pengurangan Cook dengan permintaan tunggal. Maaf untuk terminologi non-standar!)

Jawaban di bawah ini didasarkan pada diskusi di sini: /math/54580/factoring-some-integer-in-the-given-interval .

Dalam jawaban ini, saya akan memberikan pengurangan Karp waktu polinimial deterministik dari anjak piutang menjadi anjak jumlah dua bilangan bulat yang diwakili oleh faktorisasi mereka . Namun, ada satu tangkapan: Dalam proses pembuktiannya, saya akan menggunakan asumsi angka-teoretis berikut:

$p_n$$p_{n+1}$$p_{n+1} - p_n = O(\log^2p_n)$

$N$$n=|N|=O(\log N)$$N$$[N - \log^3N, N]$$\log^3N = O(n^3)$

$x$$[N - \log^3N, N]$$y=N-x$

$0 \le y \le \log^3N$$|y| = O(\log \log N) = O(\log n)$$y$

$(x,y)$$N = x+y$