Cari algoritma bilangan prima

“ ^Bilangan prima terbesar adalah 2 ^32582657 -1 . Dan saya dengan bangga menegaskan bahwa saya mengingat semua nomornya ... dalam bentuk biner. "
Karl Pomerance

Bilangan alami disebut prima jika hanya memiliki dua pembagi yang berbeda: satu dan itu sendiri. Tugas menemukan bilangan prima telah menghantui matematikawan sejak lama. Untuk waktu yang lama masalah ini tidak memiliki aplikasi praktis langsung, tetapi semuanya berubah dengan munculnya kriptografi kunci publik. Artikel ini membahas beberapa cara untuk mencari bilangan prima, keduanya murni kepentingan akademis dan digunakan saat ini dalam kriptografi.

Saringan Eratosthenes

Saringan Eratosthenes - sebuah algoritma yang diusulkan oleh ahli matematika Yunani kuno Eratosthenes. Metode ini memungkinkan Anda untuk menemukan semua bilangan prima kurang dari angka yang diberikan n . Inti dari metode ini adalah sebagai berikut. Ambil satu set angka dari 2 hingga n . Coret semua angka yang dapat habis dibagi 2, kecuali 2. Dari set (kita hilangkan), kita beralih ke nomor "tidak dihilangkan" berikutnya - 3, lagi mencoret semua yang habis dibagi 3. Kita meneruskan ke sisa angka berikutnya - 5, dan seterusnya sampai kita kita sampai ke n . Setelah melakukan langkah-langkah di atas, hanya bilangan prima yang akan tetap dalam daftar asli.

Algoritma dapat sedikit dioptimalkan. Karena salah satu pembagi dari bilangan komposit n adalah wajib $$$\ leqslant \ sqrt {n}$, algoritme dapat dihentikan setelah menghapus angka yang habis dibagi $$$\ sqrt {n}$.

Ilustrasi pengoperasian algoritma dari Wikipedia:


Kompleksitas dari algoritma ini adalah $$$O (n \ log \ log n)$pada saat yang sama, untuk menyimpan informasi tentang nomor yang dicoret, diperlukan $$$O (n)$memori.

Ada sejumlah optimasi untuk mengurangi indikator-indikator ini. Trik yang disebut faktorisasi roda adalah memasukkan dalam daftar awal hanya angka-angka yang coprime dengan beberapa bilangan prima pertama (misalnya, kurang dari 30). Secara teori, diusulkan untuk mengambil yang sederhana pertama sampai sekitar $$$\ sqrt {\ log n}$. Ini mengurangi kompleksitas algoritma dalam $$$\ log \ log n$kali. Selain mengurangi konsumsi memori yang digunakan apa yang disebut segmentasi. Set angka awal dibagi menjadi beberapa segmen ukuran $$$\ leqslant \ sqrt {n}$dan untuk setiap segmen, ayakan Eratosthenes diterapkan secara terpisah. Konsumsi memori berkurang menjadi $$$O (\ sqrt {n})$.

Atkin ayakan

Algoritma yang lebih baik untuk menyaring angka komposit diusulkan oleh Atkin dan Bershtein dan disebut Saringan Atkin . Metode ini didasarkan pada tiga properti bilangan prima berikut.

Properti 1

Jika n adalah bilangan positif maka bukan kelipatan kuadrat dari bilangan prima dan sedemikian rupa sehingga $$$n \ equiv 1 (\ mod 4)$. Maka n adalah prima jika dan hanya jika jumlah akar dari persamaan $$$4x ^ 2 + y ^ 2 = n$aneh

Properti 2

Jika n adalah bilangan positif maka bukan kelipatan kuadrat dari bilangan prima dan sedemikian rupa sehingga $$$n \ equiv 1 (\ mod 6)$. Maka n adalah prima jika dan hanya jika jumlah akar dari persamaan $$$3x ^ 2 + y ^ 2 = n$aneh

Properti 3

Jika n adalah bilangan positif maka bukan kelipatan kuadrat dari bilangan prima dan sedemikian rupa sehingga $$$n \ equiv 11 (\ mod 12)$. Maka n adalah prima jika dan hanya jika jumlah akar dari persamaan $$$3x ^ 2-y ^ 2 = n$aneh

Bukti dari sifat ini diberikan dalam artikel ini .

Pada tahap awal algoritma, saringan Atkin adalah array A dengan ukuran n yang diisi dengan nol. Untuk menentukan bilangan prima, semua $$$x, y <\ sqrt n$. Untuk setiap pasangan demikian dihitung $$$4x ^ 2 + y ^ 2$. $$$3x ^ 2 + y ^ 2$, $$$3x ^ 2-y ^ 2$dan nilai elemen array $$$A [4x ^ 2 + y ^ 2]$. $$$A [3x ^ 2 + y ^ 2]$, $$$A [3x ^ 2-y ^ 2]$meningkat satu. Pada akhir algoritma, indeks semua elemen array yang memiliki nilai ganjil adalah bilangan prima atau kuadrat dari bilangan prima. Pada langkah terakhir dari algoritma, kuadrat dari angka yang tersisa di set akan dicoret.

Ini mengikuti dari deskripsi algoritma bahwa kompleksitas komputasi dari saringan Atkin dan konsumsi memori $$$O (n)$. Saat menggunakan faktorisasi roda dan segmentasi, perkiraan kompleksitas algoritma dikurangi menjadi $$$O (n / \ log \ log n)$, dan konsumsi memori hingga $$$O (\ sqrt {n})$.

Angka Mersenne dan tes Luke-Lemer

Tentu saja, dengan indikator kompleksitas seperti itu, bahkan saringan Atkin yang dioptimalkan tidak dapat digunakan untuk mencari bilangan prima yang benar-benar besar. Untungnya, ada tes cepat untuk memeriksa apakah angka yang diberikan prima. Tidak seperti algoritma saringan, tes semacam itu tidak dirancang untuk mencari semua bilangan prima, mereka hanya dapat mengetahui dengan beberapa probabilitas apakah angka tertentu prima.

Salah satu metode pengujian tersebut adalah tes Luc-Lemer . Ini adalah ujian kesederhanaan yang deterministik dan tanpa syarat. Ini berarti bahwa lulus tes menjamin kesederhanaan angka. Sayangnya, tes ini hanya ditujukan untuk nomor jenis khusus $$$2 ^ p-1$di mana p adalah bilangan alami. Nomor-nomor tersebut disebut nomor Mersenne.

Tes Luke-Lemer mengklaim bahwa nomor Mersenne $$$M_p = 2 ^ p-1$jika dan hanya jika p adalah prima dan $$$M_p$membagi $$$(p-1)$anggota urutan $$$S_k$atur secara rekursif: $$$S_1 = 4, S_k = S_ {k-1} ^ 2-2$untuk $$$K> 1$.

Untuk nomornya $$$M_p$p bit length, kompleksitas komputasi dari algoritma ini $$${\ Displaystyle O (p ^ {3})}$.

Karena kesederhanaan dan determinisme tes, bilangan prima terbesar yang diketahui adalah angka Mersenne. Bilangan prima terbesar yang diketahui saat ini adalah $$$2 ^ {82.589.933} -1$, notasi desimalnya terdiri dari 24.862.048 digit. Anda bisa mengagumi keindahan ini di sini .

Teorema Fermat dan Miller-Rabin

Tidak banyak bilangan prima Mersenne yang dikenal, sehingga kriptografi kunci publik memerlukan cara berbeda untuk mencari bilangan prima. Salah satu metode tersebut adalah tes kesederhanaan Fermat . Ini didasarkan pada teorema kecil Fermat, yang menyatakan bahwa jika n adalah bilangan prima, maka untuk setiap a yang tidak dapat dibagi oleh n , kesetaraan $$$a ^ {n-1} \ equiv 1 {\ pmod {n}}$. Bukti teorema dapat ditemukan di Wikipedia .

Uji kesederhanaan Farm - tes probabilistik yang iterasi beberapa nilai, jika setidaknya salah satu dari mereka ketidaksamaan $$$a ^ {n-1} \ not \ equiv 1 \ pmod n$, maka angka n adalah komposit. Kalau tidak, n mungkin prima. Semakin banyak nilai yang digunakan dalam tes, semakin tinggi probabilitas bahwa n adalah prima.

Sayangnya, ada bilangan komposit n untuk perbandingan mana $$$a ^ {n-1} \ equiv 1 {\ pmod {n}}$berlaku untuk semua yang sama - sama prima dengan n . Angka seperti itu disebut angka Carmichael . Bilangan majemuk yang berhasil lulus tes Fermat disebut pseudo-simple Fermat. Jumlah Fermat pseudo-sederhana tidak terbatas, sehingga tes Fermat bukan cara yang paling dapat diandalkan untuk menentukan bilangan prima.

Tes Miller-Rabin

Hasil yang lebih dapat diandalkan dapat dicapai dengan menggabungkan teorema kecil Fermat dan fakta bahwa untuk prime p tidak ada akar persamaan lain $$$x ^ 2 \ equiv 1 \ pmod p$kecuali 1 dan -1. Tes Miller-Rabin menyebutkan beberapa nilai a dan memeriksa apakah kondisi berikut ini benar.

Biarkan p menjadi prima dan $$$p-1 = 2 ^ sd$, Kemudian untuk setiap benar setidaknya satu dari kondisi berikut:

1. $$$a ^ {d} \ equiv \ pm1 {\ pmod {p}}$
2. Ada bilangan bulat r <s sehingga $$$a ^ {2 ^ {r} d} \ equiv -1 {\ pmod {p}}$

Dengan teorema Fermat $$$a ^ {p-1} \ equiv1 \ pmod p$Serta $$$p-1 = 2 ^ sd$dari properti akar persamaan $$$x ^ 2 \ equiv 1 \ pmod p$karena itu jika kita menemukan sedemikian rupa sehingga salah satu syaratnya tidak terpenuhi, maka p adalah bilangan komposit. Jika salah satu syarat terpenuhi, angka a disebut saksi kesederhanaan angka n menurut Miller, dan angka n itu sendiri mungkin prima.

Semakin banyak saksi kesederhanaan ditemukan, semakin tinggi kemungkinan bahwa n adalah prima. Menurut teorema Rabin, probabilitas bahwa bilangan a yang dipilih secara acak akan menyaksikan kesederhanaan bilangan komposit adalah sekitar $$$1/4$.

Oleh karena itu, jika kita memeriksa k bilangan acak a , maka probabilitas mengambil bilangan komposit sebagai bilangan prima $$$\ approx (1/4) ^ k$.

Kompleksitas algoritma $$$O (k \ log ^ 3p)$di mana k adalah jumlah cek.

Karena kecepatan dan akurasi tinggi, uji Miller-Rabin banyak digunakan dalam mencari bilangan prima. Banyak perpustakaan kriptografi modern hanya menggunakan tes ini ketika memeriksa kesederhanaan dalam jumlah besar, dan, seperti yang ditunjukkan Martin Albrecht dalam karyanya , ini tidak selalu cukup.

Dia mampu menghasilkan angka-angka komposit yang berhasil lulus tes kesederhanaan di perpustakaan OpenSSL, CryptLib, JavaScript Big Number dan banyak lainnya.

Luke Test dan Baillie - PSW Test

Untuk menghindari kerentanan terkait dengan situasi di mana seorang penyerang yang dihasilkan sejumlah komposit dikeluarkan untuk sederhana, Martin Albrecht menyarankan menggunakan uji Baillie-PSW . Terlepas dari kenyataan bahwa tes Baillie - PSW adalah probabilistik, sampai saat ini, tidak ada bilangan majemuk telah ditemukan yang berhasil lulus tes ini. Untuk menemukan nomor seperti itu pada tahun 1980, penulis algoritma menjanjikan hadiah sebesar $ 30. Hadiah belum diklaim.

Sejumlah peneliti memeriksa semua angka hingga $$$2 ^ {64}$dan tidak ada satu nomor majemuk yang lulus uji Baillie - PSW. Karena itu, untuk angka lebih sedikit $$$2 ^ {64}$tes ini dianggap deterministik.

Inti dari tes ini adalah untuk secara konsisten memeriksa nomor pada waktu henti dengan dua metode berbeda. Salah satu metode ini adalah uji Miller-Rabin yang sudah dijelaskan di atas. Yang kedua adalah ujian Luke untuk kesederhanaan semu yang kuat .

Luke Strong Pseudo-Simplicity Test

Urutan Luke adalah pasangan urutan perulangan $$$\ {U_ {n} (P, Q) \}, \ {V_ {n} (P, Q) \}$ dijelaskan oleh ungkapan:

$$

$${\ displaystyle U_ {0} (P, Q) = 0, \ quad U_ {1} (P, Q) = 1, \ quad U_ {n + 2} (P, Q) = P \ cdot U_ {n +1} (P, Q) -Q \ cdot U_ {n} (P, Q), \, n \ geq 0}$$

$$

$${\ displaystyle V_ {0} (P, Q) = 2, \ quad V_ {1} (P, Q) = P, \ quad V_ {n + 2} (P, Q) = P \ cdot V_ {n +1} (P, Q) -Q \ cdot V_ {n} (P, Q), \, n \ geq 0}$$

Biarkan $$$U_n (P, Q)$dan $$$V_n (P, Q)$Adalah urutan Lucas, di mana bilangan bulat P dan Q memenuhi kondisi tersebut $$${\ displaystyle D = P ^ {2} -4Q \ neq 0}$

Kami menghitung simbol Jacobi : $$$\ kiri ({\ frac {D} {p}} \ kanan) = \ varepsilon$.

Temukan r, s untuk mana kesetaraan $$$n-ε = 2 ^ rs$

Untuk prime n , salah satu dari kondisi berikut berlaku:

1. n membagi $$$U_s$
2. n membagi $$$V_ {2 ^ js}$untuk beberapa j <r

Kalau tidak, n adalah gabungan.

Probabilitas bahwa angka komposit n akan berhasil lulus uji Luc untuk pasangan parameter P, Q tidak melebihi 4/15. Oleh karena itu, setelah menerapkan tes k kali, probabilitas ini adalah $$$(4/15) ^ k$.

Tes Miller-Rabin dan Luke menghasilkan set angka pseudo-sederhana yang terpisah, masing-masing, jika angka p melewati kedua tes, itu sederhana. Di properti inilah tes Baillie - PSW didasarkan.

Kesimpulan

Bergantung pada tugas, berbagai metode untuk menemukan bilangan prima dapat digunakan. Misalnya, ketika mencari bilangan prima Mersenne besar, pertama, menggunakan ayakan Eratosthenes atau Atkin, daftar bilangan prima ditentukan hingga batas tertentu, misalkan $$$10 ^ 8$. Kemudian, untuk setiap nomor p dari daftar, menggunakan tes Luc-Lemer, diperiksa kesederhanaannya $$$M_p = 2 ^ p-1$.

Untuk menghasilkan bilangan prima yang besar untuk keperluan kriptografi, bilangan acak a dipilih dan diverifikasi oleh uji Miller-Rabin atau Baillie - PSW yang lebih andal. Menurut teorema distribusi bilangan prima , untuk bilangan yang dipilih secara acak dari 1 ke n, peluang menjadi prima kira-kira sama $$${\ frac {1} {\ ln n}}$. Oleh karena itu, untuk menemukan bilangan prima 1024 bit, cukup memilah sekitar seribu opsi.

Sumber PS

Implementasi semua algoritma yang dijelaskan di Go dapat dilihat di GitHub .