Batas bawah pada periode dalam faktorisasi bilangan bulat?

11

Nrf(x)=axmodNf(x+r)=f(x)a<Nrr

Pertanyaan saya sekarang adalah: Apakah ada batas bawah yang diketahui pada untuk acak ? Apakah ada batasan pada diberikan dipilih seperti di RSA? Jelas, harus karena jika tidak, orang hanya bisa mengevaluasi pada poin berturut-turut untuk mencari klasik. Apakah cukup untuk memecah RSA jika ada algoritma anjak piutang klasik yang hanya bekerja berdasarkan asumsi pada distribusi , misalnya atau ?rNrN=pqrΩ(log(N))f(x)O(log(N))rrrΘ(N/log(N))rΘ(N)

Presentasi dari Carl Pomerance di " The perkalian agar mod rata-ratan " mengutip bukti bahwa adalah rata-rata selama semua , namun saya tidak yakin apakah algoritma klasik yang dapat faktor di bawah hipotesis akan memutuskan RSA secara meyakinkan. Dapatkah dipilih secara berlawanan untuk memiliki atau ?rO(N/log(N))NNrO(N/log(N))NrO(N))rO(N)

(Catatan: Ada pertanyaan terkait pada anjak piutang generik vs anjak piutang RSA)

Martin Schwarz
sumber

Jawaban:

17

Jika , periode akan selalu menjadi pembagi . Jika Anda memilih dan untuk prime, maka kecuali Anda sangat beruntung, kami akan memiliki . Saya juga percaya bahwa kita dapat secara efisien menemukan bilangan prima dengan dengan memilih kandidat secara acak dan mengujinya (ini benar jika peristiwa yang danN=pqrϕ(N)=lcm(p1,q1)p1=2pq1=2qp,qrpqN/4pp=2p+1ppprima kira-kira independen; Saya tidak tahu apakah ini sudah terbukti). Dengan demikian, dengan hati-hati memilih bilangan prima Anda, RSA akan tetap aman terhadap serangan bahkan dengan hipotesis tambahan tentang anjak piutang mudah.

Saya menduga angka acak atau acak sangat tidak mungkin memiliki , tetapi saya tidak memiliki bukti begitu saja. Hipotesis sangat kuat, dan saya tidak akan terkejut jika algoritma anjak piutang yang efisien sudah diketahui untuk kasus ini.NN=pqrO(N)rO(N)

Peter Shor
sumber