Generasi Perdana

Sebagai kelanjutan dari topik yang dimulai dalam seri artikel ini, hari ini kita akan berbicara tentang generasi bilangan prima. Generasi adalah probabilistik dan dijamin. Jadi, kasus kami adalah dengan jaminan yang memungkinkan Anda menggunakan angka yang diperoleh dalam aplikasi yang terkait dengan kriptografi, yang memastikan, misalnya, keamanan mengelola uang Anda melalui aplikasi perbankan. Selanjutnya Anda akan melihat bagaimana dijamin untuk menerima bilangan prima ukuran yang cukup untuk kriptografi, serta masalah apa yang bisa terjadi jika Anda mengabaikan jaminan.


Skema keamanan umum untuk pertukaran data didasarkan pada kompleksitas faktorisasi sejumlah komposit besar. Selain itu, jika ada banyak faktor, maka mereka akan menjadi kecil, dan ini sangat menyederhanakan peretasan sistem keamanan. Oleh karena itu, angka komposit besar diperoleh dengan mengalikan dua bilangan prima dari ukuran tertentu. Tapi di sini satu masalah sudah jelas - bagaimana memilih bilangan prima yang cukup besar?

Pertama, tentukan ukurannya. Dalam kriptografi modern, urutan bilangan komposit ditentukan oleh rumus $$$2 ^ {2048}$ , yaitu, urutan sebenarnya adalah 2048 dalam notasi biner. Dan pembagi bilangan komposit ini adalah urutan 1024, yaitu di suatu tempat di sekitar nilai-nilai $$$2 ^ {1024}$ . Kenapa 1024? Karena sepuluh tahun yang lalu faktor urutan 768 difaktorkan, dan hari ini sangat mungkin bahwa jumlah majemuk urutan 1024 didekomposisi. Jadi diputuskan untuk keandalan untuk menggandakan pesanan sekaligus, yaitu, hingga 2048. Nah, mulai dari pesanan ini mudah untuk ditentukan urutan faktor yang diperlukan.

Tetapi apa yang terjadi jika urutan faktor-faktornya kurang dari 1024? Kemudian, dalam waktu yang dapat diterima, Anda dapat menguraikan angka komposit, bahkan jika itu adalah urutan 2048. Ini berarti bahwa perlu untuk memastikan bahwa faktor-faktor yang dipilih oleh kami memiliki pesanan mendekati 1024 dan sederhana, yaitu, mereka tidak dapat difaktorkan. Tapi di sini pilihan itu sendiri dilakukan sesuai dengan skema probabilistik, dan ini hanya mengarah pada masalah potensial.

Probabilitas kesederhanaan angka diperiksa atas dasar asumsi bahwa angka itu "paling mungkin" prima jika periode (yang dijelaskan di sini ) adalah pembagi angka itu sendiri, minus satu ( $$$N-1$ ) Dalam bentuk rumus, tampilannya seperti ini:

$$

$$a ^ p \ pmod N = 1$$

$$

$$N-1 \ pmod p = 0$$

Di sini $$$N$ - nomor yang diselidiki, $$$a$ - nilai dari $$$2$ sebelumnya $$$N-2$ (Ini menentukan dasar sistem bilangan di mana periode dihitung), $$$p$ - periode nomor yang diselidiki. Operasi $$$mod$ di sini berarti mengambil sisa dari membagi operan pertama dengan operan kedua.

Pemeriksaan yang ada hanya mengandalkan pendekatan semacam itu, karena untuk sejumlah besar penentuan kesederhanaan tanpa syarat oleh tes yang diketahui membutuhkan waktu yang sangat lama. Tetapi minus dari pemeriksaan seperti itu jelas - kadang-kadang Anda bisa mendapatkan nomor komposit, bukan yang sederhana. Selain itu, tidak ada yang tahu pembagi apa yang akan menjadi bagian dari nomor tersebut. Lebih tepatnya, seorang penyerang akan dapat mengetahuinya dengan menerapkan metode-metode faktorisasi yang terkenal, yang mulai bekerja dalam waktu yang dapat diterima jika faktor-faktornya ada dalam urutan kurang dari beberapa ratus bit.

Seberapa sering kesalahan kesederhanaan probabilistik? Cukup jarang. Ada satu kesalahan untuk beberapa puluh ribu yang sederhana, dan kadang-kadang dua, tapi tidak ada yang menjamin kita dari tiga. Selain itu, banyak tergantung pada tes yang digunakan. Jadi, misalnya, di perpustakaan bahasa Jawa standar di kelas BigInteger, pemeriksaan diterapkan yang memungkinkan kehilangan 2-3 kali per seribu yang sederhana. Artinya, Anda tidak boleh berpikir bahwa jika secara teoritis ada sedikit kesalahan, maka dalam praktiknya semuanya akan menjadi cokelat.

Bagaimana ini berbahaya? Tampaknya tidak seseram yang mungkin dikatakan beberapa orang, karena, jika sebuah situs yang menutup penjelajahan halamannya dengan protokol https menerima kunci yang mudah dihitung, lalu apa masalahnya? Nah, peretas akan mencari tahu berita apa yang Anda baca di situs ini, dan apa gunanya? Namun pada kenyataannya, enkripsi tidak hanya dilakukan saat menjelajah web. Situasi yang lebih tidak menyenangkan akan terjadi jika peretas mengetahui kunci layanan perbankan favorit Anda untuk mengelola uang Anda dari jarak jauh. Meskipun, sekali lagi, tampaknya untuk membuka pertukaran dengan bank (dan jika bank menggunakan cek kesederhanaan yang lemah), peretas harus menunggu sekitar 500 tahun hingga kemungkinan mengeluarkan kunci yang mudah dihitung akhirnya terwujud, karena kunci biasanya memiliki masa berlaku 1 tahun dan karena itu, untuk menjamin peretasan, Anda harus menunggu hingga 500 masalah kunci baru dilakukan. Tampaknya semuanya logis, tetapi ada "tetapi" yang lain - ada lebih banyak bank daripada 500 di dunia. Karena itu, saat ini, mungkin di bank favorit Anda, peretas dapat memperoleh akses ke uang Anda sendiri.

Apakah kamu takut? Tentunya tidak, karena kita semua sangat berani, sampai ayam panggang mematuk. Tetapi masih ada sesuatu yang harus ditakuti. Meskipun kemungkinan serangan yang berhasil oleh peretas tepat di bank Anda tidak begitu tinggi, namun demikian, jika disadari, maka uang Anda mungkin tidak akan ditemukan. Mengapa Ini sangat sederhana - asumsi standar pertama dari layanan keamanan bank adalah bahwa seseorang dengan hak akses yang tepat harus disalahkan. Bukan seorang hacker, kemungkinan gangguan yang mereka anggap minimal, yaitu seseorang dari mereka sendiri. Oleh karena itu, seorang hacker mungkin tidak dihukum.

Bagaimana cara mengatasi masalah ini? Anda perlu mempelajari cara mendapatkan nomor perdana yang dijamin. Tetapi bagaimana menjamin kesederhanaan mereka? Ada empat metode untuk ini.

Metode pertama adalah penghilang dengan batasan minimal. Ini biasanya merupakan varian dari saringan Eratosthenes yang lebih baik. Metode ini dapat diandalkan dan dijamin, tetapi terbatas pada pesanan yang sangat sederhana (kurang dari seratus). Oleh karena itu, metode ini tidak berlaku dalam kriptografi.

Metode kedua adalah penghitungan dengan batasan yang lebih kuat. Jadi, jika periode angka sama dengan angka itu sendiri, minus satu, maka angka tersebut dijamin prima. Rumusnya di sini adalah - $$$N-1 = p$ . Tetapi untuk menentukan persamaan periode perbedaan antara angka dan satuan, metode yang sangat berat digunakan yang tidak bekerja untuk semua kelas angka. Oleh karena itu, penggunaannya dalam kriptografi bertumpu pada jumlah terbatas dari kelas-kelas tertentu, atau selama verifikasi, jika kita menambah ukuran angka. Dan di samping itu, bahkan jumlah kelas tertentu saja tidak menjamin apa pun, yang berarti perlunya memilah banyak nomor kandidat. Di sini, misalnya, angka-angka Mersenne, yang di dalamnya terdapat uji kesederhanaan tanpa syarat, telah dipilah-pilah dan menemukan bahwa angka-angka tersebut praktis tidak ada dalam kisaran yang digunakan dalam kriptografi. Berikut daftar lengkap mereka dengan pesanan dekat - 1279, 2203, 2281, 3217. Seperti yang Anda lihat, dari 1024 hingga 2048 hanya ada satu nomor yang sesuai. Tetapi bahkan jika kita mengambil sisanya, jumlah mereka mengisyaratkan kepada kita dengan sangat jelas - itu tidak layak! Jadi sekali lagi kami kurang beruntung dengan metode verifikasi.

Metode ketiga adalah probabilistik. Itu yang digunakan hari ini, termasuk di bank favorit Anda. Bagaimana cara kerjanya? Sangat sederhana - sisa pembagian angka sewenang-wenang dalam kekuasaan diperiksa $$$N-1$ pada $$$N$ jika sisanya adalah satu, kemungkinan jumlahnya prima. Dan di sini kata "mungkin" adalah yang paling tidak menyenangkan di sini. Meskipun metode probabilistik untuk memeriksa kesederhanaan juga mengandung peningkatan tambahan, namun, seperti yang ditunjukkan di atas, perpustakaan Java standar cukup sering keliru.

Dan akhirnya, metode keempat. Ini tidak bekerja secepat tes probabilistik (meskipun sesuatu dapat dioptimalkan di sini juga), tetapi memberikan bilangan prima yang dijamin, dan bahkan dengan periode yang mudah didefinisikan. Untuk apa periode prima, Anda bertanya? Misalnya, untuk menghasilkan urutan pseudo-acak atau enkripsi. Lebih tepatnya, mengetahui periode, kita tahu persis berapa banyak angka dalam urutan, yang membuatnya mudah untuk merencanakan berapa lama kita dapat menggunakan generator urutan berdasarkan nomor ini. Benar, ini sudah berlaku untuk enkripsi simetris, tetapi juga bisa berguna dalam sejumlah kasus. Selanjutnya, kami akan mempertimbangkan teori yang menjamin kesederhanaan memeriksa nomor kandidat.

Latar belakang teoritis

Untuk memahami cara menghasilkan bilangan prima yang dijamin, Anda perlu menyelami sedikit matematika. Tapi jangan khawatir, matematika ada di sini di tingkat kelas lima.

Untuk kelengkapan, disarankan untuk mencari di sini untuk rincian tentang apa periode dan serangkaian residu. Baiklah, katakan secara singkat bahwa sejumlah residu terbentuk dengan membagi "sudut" (sebuah metode yang diketahui oleh setiap siswa) dari unit dengan jumlah yang dipilih untuk penelitian. Pada saat yang sama, pada setiap langkah, perbedaan muncul antara angka yang lebih tinggi, dengan nol yang ditambahkan padanya, dan produk dari angka yang sedang diselidiki dengan nilai dari 0 hingga 9 (untuk sistem angka desimal) - ini adalah sisanya. Tetapi ada banyak langkah dalam membagi dengan "sudut", oleh karena itu ada juga banyak residu, dan bersama-sama mereka membentuk serangkaian residu di mana himpunan angka yang sama secara berkala diulang beberapa kali tanpa batas. Tanda awal dari siklus baru adalah sisa sama dengan satu. Jumlah residu antar unit adalah panjang periode (atau siklus). Faktanya, itu saja, tetapi perlu juga dipahami bahwa metode membangun serangkaian saldo dapat diterapkan menggunakan sistem angka apa pun, dan khususnya, sistem dengan basis 2 (dan bukan 10, seperti kebiasaan di sekolah) akan paling sering digunakan. Saat menggunakan sistem angka lainnya, semua aturan dipertahankan, tetapi jumlah varian produk pada setiap langkah akan berbeda, sama dengan b (dari pangkalan), yaitu pangkalan sistem angka.

Jadi, dari yang ditunjukkan sebelumnya, kita tahu bahwa bilangan komposit selalu memberikan periode yang relatif singkat yang tidak termasuk sejumlah nilai "terlarang". Mengetahui faktorisasi bilangan majemuk, mudah untuk menghitung berapa banyak nilai yang harus tidak ada dalam sejumlah residu yang membentuk periode bilangan tertentu. Serangkaian residu tidak akan mengandung faktor dan semua angka yang merupakan kelipatan dari faktor-faktor ini jika seri itu sendiri dibangun berdasarkan sistem angka yang bukan kelipatan dari pembagi mana pun (yaitu, basis tidak dibagi dengan pembagi nomor tersebut). Misalnya, jika hanya ada dua faktor, maka jumlah beberapa residu ditentukan oleh rumus $$$m = a + b-2$ dimana $$$m$ - jumlah beberapa residu, $$$a$ dan $$$b$ Apakah faktor-faktor yang membentuk angka komposit kami. Mengetahui jumlah residu "terlarang", mudah untuk menghitung bahwa serangkaian residu lebih lama dari setengah nilai $$$N-1$ akan memiliki panjang sama dengan $$$L = N-1- (a + b-2) = N-a-b + 1$ . Artinya, seri seperti itu akan diputar $$$a + b-2$ lebih pendek dari seri yang akan muncul jika nomor yang diberikan adalah prima. Ini menjelaskan mengapa semua angka dengan periode sama dengan periode penuh (mis. $$$N-1$ ), berubah menjadi sederhana - jika setidaknya satu elemen (yang "dilarang") dikeluarkan dari urutan residu, maka periode akan menjadi kurang $$$N-1$ . Sebagai hasil dari adanya keteraturan seperti itu, kami mengamati operabilitas dari semua tes probabilitas, yang hari ini memverifikasi kesederhanaan angka. Tes ini menghitung nilai dalam serangkaian saldo per posisi. $$$N-1$ atau $$$(N-1) / 2$ , dan jika nilainya sama $$$1$ atau $$$N-1$ , maka sangat mungkin bahwa jumlahnya prima. Kenapa hanya dengan probabilitas tinggi, dan tidak dijamin? Karena periode uji probabilistik tidak dihitung, tetapi antara posisi $$$N-1$ dan $$$(N-1) / 2$ mungkin ada lebih banyak unit, yang berarti ketimpangan periode dengan nilai $$$N-1$ tetapi jika periodenya tidak sama $$$N-1$ , maka jumlahnya mungkin gabungan. Selain itu, kurangnya kesetaraan itu sendiri tidak kritis, hal lain adalah penting - angka semu-sederhana dapat memberikan pengaturan unit seperti itu. Di antara angka-angka yang diverifikasi oleh tes semacam itu, Anda dapat menemukan nomor semu-sederhana yang bersifat gabungan dan yang membantu peretas yang mencuri uang Anda. Lagi pula, apa pembagi angka komposit seperti itu? Mereka mungkin cukup kecil bagi penyerang untuk dengan mudah membuka pertukaran data terenkripsi.

Sekarang ingat mengapa bilangan prima semu mungkin muncul sama sekali. Angka tersebut memiliki periode pendek yang berulang kali dalam periode penuh. $$$N-1$ oleh karena itu, mereka kadang-kadang dapat "cocok" dan cocok dalam jumlah penuh kali dalam periode penuh. Jadi, misalnya, angka 25 memiliki periode 4 untuk sistem angka dengan basis 7. $$$N-1$ untuk 25 adalah 24, cobalah untuk membagi: 24/4 = 6. Artinya, periode ini ditata bilangan bulat beberapa kali dalam periode penuh. Fakta ini dapat diverifikasi dengan rumus di atas untuk mempersingkat periode, tetapi dengan mempertimbangkan fakta bahwa a dan b adalah sama dalam kasus ini. Periode maksimum yang mungkin adalah 24-4 = 20, di sini 24 adalah jumlah total residu, 4 adalah jumlah residu yang merupakan kelipatan dari 5. Tetapi periode tidak selalu maksimum, dan semua opsi lain dapat diperoleh dengan membagi periode maksimum sepenuhnya. 20 dibagi dengan 2,4,5,10, dan hanya dengan membagi 20 dengan angka dari daftar di atas kita mendapatkan periode 4 panjangnya, yang memberi kita pada akhir periode penuh $$$N-1$ unit. Dan ketika memeriksa kesederhanaan, hanya nilai-nilai di posisi yang diperiksa $$$N-1$ , yaitu nilai terakhir dalam periode penuh. Dan untuk 25 itu sama dengan 1, yang merupakan tanda kesederhanaan angka. Meskipun sebenarnya merupakan tanda kesederhanaan yang jelas, saat ini untuk semua basis sistem bilangan, lebih sedikit $$$N$ , nilai terakhir dalam periode penuh sama dengan satu. Tetapi tidak ada cara untuk memeriksa semua sistem angka untuk jumlah besar, sehingga angka semu-sederhana muncul yang kadang-kadang digunakan bahkan dalam kriptografi, yang meningkatkan kerentanan keuangan kita.

Bagaimana cara menghilangkan pengaruh bilangan prima semu? Pada prinsipnya, ini sederhana - Anda dapat memeriksa periode untuk semua sistem angka, tetapi kemudian untuk operasi ini untuk jumlah besar tidak akan ada cukup waktu. Karena itu, kita akan pergi ke arah lain. Dan jalannya juga sederhana (dalam arti literal - ia menggunakan bilangan prima lainnya). Kita telah melihat bahwa periode pendek dapat menyesuaikan periode penuh dengan bilangan bulat beberapa kali, dan ini memberi kita angka semu-sederhana. Tetapi apa yang mencegah kita mengambil dan membatalkan hari Senin ini? Ya, secara umum, tidak ada yang mencegah.

Untuk periode singkat, periode penuh ( $$$N-1$ ) harus dibagi menjadi banyak pembagi. Jadi untuk angka 25, periode penuh 24 dibagi menjadi 2, 3, 4, 6, 8, 12. Ada begitu banyak kemungkinan untuk menembus ke dalam wilayah terlindungi dari angka semu sederhana. Jadi kita hanya perlu mengambil prima sebagai periode penuh, karena itu tidak terbagi menjadi apa pun dan karena itu secara otomatis menyelamatkan kita dari elemen musuh. Benar, ada satu "tetapi" - kita perlu bilangan prima, dan mereka dikenal ganjil (kecuali satu pengecualian - 2), yang berarti jika $$$N-1$ sederhana maka itu sendiri $$$N$ itu tidak bisa sederhana lagi. Karena itu, kita harus mengakui kemungkinan munculnya periode yang tidak lengkap. Kenapa ini buruk? Seperti yang kita lihat di atas, periode penuh menjamin kesederhanaan angka, tetapi kami belum membuktikan periode yang tidak lengkap. Jadi kita perlu membuktikan momen ini.

Buktinya cukup sederhana - untuk senyawa $$$N$ panjangnya periode $$$N-1$ dua kali, diperoleh dalam sistem bilangan yang bukan kelipatan dari pembagi N, hanya memiliki dua baris residu, dan tidak satupun dari mereka harus mengandung angka yang merupakan kelipatan dari pembagi dari $$$N$ (Nomor "Terlarang"). Jika setidaknya satu elemen dikecualikan dari satu baris residu, maka yang kedua secara otomatis berkurang dengan jumlah yang sama (setelah semua, satu baris sama dengan yang lain dikalikan dengan angka apa pun yang tidak ada dalam yang pertama). Jadi jika ada pembagi di nomor tersebut $$$N$ , kami memperoleh panjang total lebih pendek dari dua periode dengan semua saldo "diizinkan" dari nilai periode penuh dan dengan demikian memindahkan unit dari tempatnya pada akhir periode penuh, dengan demikian memastikan tidak adanya kesederhanaan semu. Tapi bisakah jumlah sisa pembagi ganda seperti memberikan tepat setengah atau sepertiga dari periode penuh? Memang, kemudian kita akan menerima, misalnya, dua pertiga dari saldo yang "diperbolehkan" (dua baris) dan sepertiga dari yang "terlarang", dan secara total - periode penuh. Tetapi untuk mendapatkan sepertiga kita perlu memastikan pembagian periode penuh ( $$$N-1$ ) dengan 3, yang dapat dengan mudah kita kecualikan - ambil bilangan prima, kalikan dengan dua dan tambahkan satu ke hasilnya - voila, kami dijamin untuk mengecualikan kesederhanaan semu. Dengan dia, jumlah pembagi yang dapat dibagi oleh pembagi tidak dapat sama dengan sepertiga dari periode penuh, karena ia tidak dapat membagi dengan tiga periode penuh. Masih ada opsi dengan separuh sisanya yang merupakan kelipatan dari pembagi $$$N$ . Opsi ini dihilangkan sedikit lebih sulit, sehingga akan ada sedikit penyimpangan di bawah ini.

Perhitungan periode, atau semua angka - anak-anak Mersenne

Periode angka apa pun dapat dihitung. Dalam kasus yang paling sederhana, perhitungan dilakukan dengan hanya membagi sudut $$$1 / N$ sampai kita bertemu dengan sisa yang sama dengan satu (dalam sistem angka, bukan kelipatan dari pembagi $$$N$ ) Tetapi untuk sejumlah besar, ini adalah panjang yang tidak realistis. Oleh karena itu, ada kebutuhan untuk memperoleh formula untuk menghitung periode. Dan formula seperti itu ada, meskipun tidak dalam bentuk yang ideal, ketika kita memiliki angka pada input dan periode pada output. Rumusnya adalah:

$$

$$N = \ frac {b ^ {m + n + 1} -1} {b ^ n + k}$$

Di sini $$$N$ - nomor yang diselidiki, $$$b$ - dasar sistem angka yang digunakan (basis), $$$m$ - tingkat maksimum $$$b$ di mana hasil eksponensial kurang $$$N$ (Dengan kata lain, indeks tingkat senior di $$$N$ dalam sistem angka $$$b$ ), $$$n$ - jarak dari kiri ke kanan dalam serangkaian residu dari indeks $$$m + 1$ (sama dengan jumlah bit dalam $$$N$ ) ke satu, $$$k$ Apakah beberapa koefisien integer.

Output formula

Dengan definisi rumus, jelas bahwa (1) $$$b ^ {m + 1} -N = x$ , yaitu tingkat pertama $$$b$ yang lebih besar $$$N$ , memungkinkan Anda untuk mengurangi $$$N$ dan dapatkan beberapa perbedaan dalam formulir $$$x$ . Ini juga mengikuti dari definisi bahwa (2) $$$x * b ^ n-k * N = 1$ disini $$k adalah koefisien integer. Jika Anda kalikan(1)dengan$k$$$b n dan ganti$b^n$$$x ∗ b n untuk nilainya dari(2), yang sama dengan$x*b^n$$$k N + 1 , kita memperoleh$kN+1$$$$b^{m+n+1}=N*b^n+kN+1=N*(b^n+k)+1 => N=\frac{b^{m+n+1}-1}{b^n+k}$ .

Properti yang berguna

Seperti yang bisa kita lihat, menggunakan rumus ini Anda bisa mendapatkan angka dengan periode yang diketahui. Benar, ada satu kesulitan - Anda harus memilih koefisien$$k , yang dalam jumlah besar sekali lagi berubah menjadi sesuatu yang tidak dapat dicapai. Tetapi formula memberi kita sesuatu yang lain - kita dengan jelas melihat bagaimana semua angka terbentuk. Ya, benar-benar semua bilangan bulat positif dapat diperoleh dengan rumus ini, karena semua angka memiliki periode tertentu. Dan yang menarik, semua angka diperoleh dengan membagi angka Mersenne dengan salah satu pembagi nya. Ingat bahwa nomor Mersenne adalah angka yang sama dengan$k$$$$2^n-1$ .Dalam rumus dalam pembilang, kita melihat generalisasi untuk angka Mersenne dengan basis apa pun (termasuk 2, tentu saja). Dan jika kita tertarik pada bilangan prima, maka kita tidak akan membutuhkan pangkalan lain selain 2.

Mengetahui bahwa kita membagi angka Mersenne, akan berguna bagi kita untuk dapat menghitung periode angka dengan tepat untuk kasus pembagian angka Mersenne (ingat konsep periode yang diperluas di sini ). Tetapi yang sangat luar biasa adalah bahwa rumus untuk menghitung periode Mersen bertepatan dengan rumus untuk menghitung periode dari jenis tersebut.$$$1/N$ . Nah, untuk mendapatkan rumus untuk membagi angka Mersenne, prinsip yang sama digunakan seperti ketika menurunkan rumus untuk membagi $$1 / N , dengan pengecualian rumus untuk menghitung nilai dalam serangkaian residu dengan indeks$1/N$$$n yang terlihat seperti ini -$n$$$b n + 1 - 1b - 1 , dan untuk bilangan biner kita dapatkan$\frac{b^{n+1}-1}{b-1}$$$$2^{n+1}1$ .

Sekarang kita memiliki semua kartu dan kita dapat memulai permainan dengan membuka pemanah semu-sederhana di jajaran bilangan prima.

Seperti yang kita ketahui dari seri sebelumnya, bila dapat dibagi, seluruh periode Mersen dari suatu angka harus sesuai dengan jumlah digit dari angka Mersenne dan bilangan bulat beberapa kali. Oleh karena itu, dalam rumus di atas, solusi dalam bilangan bulat hanya mungkin jika penyebut memiliki periode yang sama dengan pembilang atau beberapa kali lebih kecil. Tetapi periode yang jauh lebih singkat akan memberi kita, termasuk pembagi nomor itu sendiri$$N , karena jika$N$$$N membagi nomor Mersenne, kemudian pembagi juga membagi nomor Mersenne. Dan ini adalah poin yang sangat penting, karena dari sini maka panjang periode pembagi N membagi panjang periode$N$$$N sepenuhnya. Itu kalau kita ambil$N$$$N adalah sedemikian sehingga periodenya sama dengan periode pembilang, lalu semua pembagi$N$$$N akan menjadi pembagi waktu yang sama dari nomor Mersenne, dan karena itu harus sesuai dengan periode dan$N$$$N , dan Mersenne memberi angka bilangan bulat beberapa kali.$N$

Sekali lagi sekitar setengah periode

Sekarang ingat bahwa kita berhenti mencari cara untuk membuktikan bahwa kita dapat mengecualikan kasus ketika setengah panjang dari serangkaian angka residu adalah kelipatan dari pembagi nya. Kami ingin membuktikan ini untuk menghilangkan bilangan prima palsu ketika memilih satu bilangan prima sebagai dasar untuk membangun periode bilangan prima berikutnya. Jadi sekarang kita tahu bahwa jika angka yang dibangun memiliki pembagi, maka periode mereka selalu membagi periode dari angka yang dibangun sepenuhnya. Maka tetap bagi kita untuk memeriksa pembagi mana yang dapat masuk ke dalam pembatasan yang diberikan sebelumnya pada nomor yang dibangun. Dan pembatasan seperti itu - periode nya hanya dibagi menjadi$$2 dan seterusnya$2$$$$(N-1)/2$ . Oleh karena itu, hanya angka dengan titik yang dapat menjadi pembagi $$$2$ dan $$$(N-1)/2$ . Periode $$2 memiliki nomor$2$$$2 , tidak ada nomor lain dari periode seperti itu memiliki lebih banyak. Periode$2$$$2 tidak cocok dengan bilangan bulat berapa kali dalam$2$$$( N - 1 ) / 2 , karena$(N-1)/2$$$( N - 1 ) / 2 adalah prima, oleh karena itu pembagian menjadi tiga dikecualikan untuk periode tersebut. Jadi hanya ada satu kemungkinan yang tersisa - pembagi memiliki titik$(N-1)/2$$$$(N-1)/2$ . Tetapi jumlahnya tidak boleh kurang dari atau sama dengan periode, sehingga nilai minimum untuk pembagi adalah $$$(N-1)/2+1$ . Jika kita mengalikan dua pembagi minimal, kita mendapatkan - $$( N - 1 ) 2 / 4 + ( N - 1 ) + 1 = ( N 2 - 2 N + 1 + 4 N ) / 4 = ( N 2 + 2 N + 1 ) / 4 , nilai ini harus tidak lebih$(N-1)^2/4+(N-1)+1=(N^2-2N+1+4N)/4=(N^2+2N+1)/4$$$N , karena kita berbicara tentang pembagi$N$$$$N$ . Lalu kami mendapatkan ketimpangan $$$(N^2+2N+1)/4\leq N => N^2-2N+1\leq 0$ . Ketidaksetaraan ini bisa negatif atau sama dengan nol hanya untuk $$N = 1 , oleh karena itu, untuk semua angka yang dibangun dengan cara ini, kesederhanaan semu dikecualikan jika jumlah yang dihasilkan lebih besar dari$N=1$$$$1$ . Nah, untuk jumlah yang lebih kecil, kita dapat menguji kesederhanaan bahkan dalam pikiran.

Sekarang ada dua opsi - angka baru adalah bilangan prima, yang kami butuhkan, atau ini adalah bilangan komposit dan kemudian periodenya tidak cocok dengan bilangan bulat bilangan dalam periode penuh, dan oleh karena itu angka ini dapat dengan mudah diperiksa kesederhanaannya dengan menghitung nilai terakhir dalam serangkaian residual penuh. Artinya, angka yang dibangun dapat dengan mudah diperiksa dengan tes kesederhanaan probabilistik standar, dan yang penting, hasil tes tidak akan probabilistik, tetapi dijamin. Jadi, pada akhirnya, kami menyingkirkan kutukan kesederhanaan semu, yang memberi tekanan pada semua tes probabilitas.

Tapi tentu saja, hidup akan menjadi madu jika semua masalah diselesaikan dengan sederhana. Menghilangkan kesederhanaan semu, kami tidak mengecualikan angka yang tidak disembunyikan dari siapa pun dan tidak ditutupi di bawah apa pun. Dan dengan mereka ada satu masalah lagi - untuk saat ini, kita dapat memeriksa istilah arbitrer dalam urutan residu hanya dengan menaikkan ke kekuatan dan kemudian mengambil sisanya. Tetapi metode ini sangat lambat. Lebih tepatnya, ini cukup cepat untuk angka yang digunakan dalam kriptografi, tetapi tidak cocok untuk menemukan bilangan prima besar di rumah, karena memerlukan bertahun-tahun menghitung komputer rumah biasa, yang tidak memungkinkan kita untuk mendapatkan $ 400k (seperti yang ditunjukkan di sini ).

Namun demikian, hampir semuanya siap untuk menghitung bilangan kriptografi. Meskipun teman lama kita tetap - maksimalisme. Dia bertanya - apakah Anda dapat menggunakan titik $$$(N-1) / 2$ , apa yang mencegah penggunaan periode $$$(N-1) / 4, (N-1) / 6, (N-1) / 8$ dll? Dan ternyata dengan hati-hati - tidak ada yang mencegah!

Dengan cara yang sama seperti dengan periode $$$(N-1) / 2$ untuk periode tersebut $$$(N-1) / 4$ kita dapat mengatur batas bawah dengan mengalikan sebuah prima dengan 4 dan menambahkan 1. Kemudian kita menjamin diri kita dari pseudo-sederhana dengan periode kurang dari $$$(N-1) / 4$ . Oleh karena itu, tetap mempertimbangkan kemungkinan kejadian pseudo-sederhana dengan kelipatan periode 4, 3, 2 (1 dikecualikan untuk komponen, seperti yang ditunjukkan di atas). Dari rumus untuk menghitung angka dengan periode terlihat bahwa periode dividen harus sama dengan kelipatan pembagi yang paling tidak umum, yang menyiratkan bahwa periode yang mungkin dari angka tersebut $$$N$ seharusnya tidak hanya sesuai dengan bilangan bulat beberapa kali dalam $$$N-1$ (Jika tidak akan ada kesederhanaan semu), tetapi juga mengandung jumlah periode pembagi integer. Dengan demikian, jumlah pembagi yang mungkin dari bilangan prima semu sangat terbatas. Karena periode nomor berapa pun tidak boleh lebih lama $$$N-1$ , kemudian untuk kemungkinan pembagi $$$N$ memberi sebagai hasil dari divisi 3, periode tidak bisa lebih lama $$$N / 3-1$ , di samping itu, kami memperhitungkan bahwa periode 3 adalah 2. $$$N / 3$ Pasti aneh karena aneh $$$N$ . Dari penjelasan di atas dapat disimpulkan bahwa periode genap N / 3-1 adalah kelipatan umum terkecil dengan periode 2 dari angka 3, yang berarti bahwa periode yang mungkin dari N semu yang berpotensi pseudo-sederhana harus sama dengan periode angka $$$N / 3$ . Total ada satu nilai periode $$$N$ untuk yang kesederhanaan semu mungkin, ini $$$(N-1) / 4$ . Untuk nilai lain, baik $$$N / 3$ terlalu sedikit atau periode (dan dengan itu periode $$$N$ ) akan pergi ke area terlarang di bawah ini $$$(N-1) / 4$ . Kisah yang sama dengan angka ganjil, lebih sedikit $$$N / 3$ tetapi periode mereka tidak bisa lebih lama $$$(N-1) / 4$ , dan karena itu semuanya dikeluarkan dari pertimbangan. Sekarang tunjukkan itu $$$N / 3$ tidak dapat memiliki menstruasi $$$(N-1) / 4$ , yang berarti tidak dapat membagi seluruh periode seluruhnya. Pertama, ingat rumusnya $$$m = a + b-2$ , yang memberi kami jumlah beberapa residu pembagi untuk nomor yang hanya dapat dibagi oleh $$$a$ dan $$$b$ . Dalam kasus kami $$$N$ seharusnya dibagi menjadi $$$N / 3$ dan pada 3, semua pembagi lainnya dikecualikan, jadi kami mendapatkan - $$$m = N / 3 + 3-2 = N / 3 + 1$ . Sekarang dari periode penuh Anda perlu mengurangi nilai "terlarang", yang akan menjadi $$$N / 3 + 1$ , dan kemudian bagi dengan 4. Kami mendapatkan periode kerja yang memungkinkan $$$3 * N / 3$ : $$$p = (N-1-N / 3-1) / 4 = N / 6-1 / 2$ itu kurang $$$(N-1) / 4$ , yaitu, periode panjang $$$(N-1) / 4$ tidak mungkin karena perlunya memperhitungkan residu "terlarang", yang membawa semua periode pseudo-sederhana yang mungkin ke wilayah terlarang (kurang $$$(N-1) / 4$ ) Ini berarti bahwa situasi ini menjamin kita bahwa angka yang dikonstruksikan tidak pseudo-sederhana, dan oleh karena itu kita dapat lagi yakin akan hasil dari uji kesederhanaan probabilitas berikutnya.

Demikian pula, dan dengan mempertimbangkan pembagian periode penuh, seseorang dapat memperoleh hasil yang sama untuk nilai-nilai lain. Tetapi jika kita ingin mendapatkan bilangan kriptografi dengan cara ini, maka mengalikannya dengan 2,4,6, kita akan menambah ukuran bilangan untuk waktu yang sangat lama, jadi masuk akal untuk melihat ke arah pilihan lain - penggandaan dua bilangan prima. Jika kita mengalikan satu perdana dengan yang lain, kita mendapatkan angka ganjil, jadi pastikan untuk mengalikannya dengan 2 untuk mendapatkan periode genap genap dan angka kandidat ganjil di perdana. Periode penuh dalam hal ini akan dibagi menjadi $$$2, a, b, 2a, 2b, ab$ dimana $$$a$ dan $$$b$ Apakah bilangan prima. Sekarang kita perlu membuktikan bahwa periode yang ditunjukkan tidak akan memberikan kesederhanaan semu, atau untuk menemukan tanda-tanda yang memperingatkan kita tentang keberadaan kesederhanaan semu. Perhatikan bahwa jika periode sama dengan $$$2 * a * b$ , maka angkanya akan prima (seperti yang ditunjukkan di atas). Juga ditunjukkan di atas bahwa angka setengah periode tidak dapat pseudo-sederhana, oleh karena itu periode panjang $$$ab$ dapat dikecualikan. Meskipun untuk kelengkapan, Anda dapat memeriksa periode $$$ab$ cara alternatif. Jadi jika periodenya $$$ab$ , lalu diberikan itu $$$a$ dan $$$b$ sederhana, menjadi jelas bahwa kelipatan periode pembagi paling umum $$$N$ hanya bisa sama $$$ab$ , sedangkan periode pembagi dapat sama dengan $$$ab$ keduanya, atau satu $$$a$ dan lainnya $$$b$ . Karena periode selalu kurang dari angka itu sendiri, maka $$$(ab + x) * (ab + y)$ jelas akan ada lebih banyak $$$2b + 1$ . Oleh karena itu, kesederhanaan semu tidak dimungkinkan dengan periode seperti itu. Karena itu, masih harus memeriksa periode $$$2, a, b, 2a, 2b$ . 2 kurang dari periode periode minimum yang mungkin untuk semua angka, lebih dari 3, oleh karena itu kami mengecualikan periode tersebut. Sekarang anggaplah angka yang dibangun dibagi dengan $$$m$ dan $$$n$ , kemudian dengan persamaan periode $$$N$ artinya $$$a$ , periode mereka juga akan sama $$$a$ , karena ini adalah satu-satunya kelipatan paling umum untuk dua angka, karena $$$a$ tidak dibagi menjadi apa pun. Karena itu $$$(a + x) * (a + y) = N = ab * 2 + 1$ dimana $$$a + x = m$ - faktor pertama yang mungkin dengan suatu periode $$$a$ , dan $$$a + y = n$ - kedua. Selanjutnya: $$$a ^ 2 + kapak + ay + xy = 2ab + 1$$$$=>$$$$a ^ 2 + kapak + ay + (ka + r) = 2ab + 1$$$$=>$$$$a + x + y + k = (2ab + 1-r) / a$ . Di sini $$$r$ bisa sama dengan hanya satu, jika bilangan bulat tidak akan berfungsi di sebelah kiri. Lalu: $$$x + y + k = 2b-a$ , dari mana diikuti jika $$$a \ geq 2b$ , lalu pseudo-sederhana dengan titik $$$a$ tidak mungkin. Tetap memverifikasi kesederhanaan semu di $$$a <2b$ , yang dapat dilakukan dengan memeriksa nilai-nilai dalam rangkaian residu pada posisi $$$a$ jika ada 1, maka angka tersebut dapat menjadi semu-sederhana dan harus dikeluarkan dari operasi lebih lanjut. Alasan untuk $$$b$ sepenuhnya analog, yang berarti kebutuhan untuk memverifikasi kesetaraan unit dan sisanya, disediakan $$$b <2a$ .

Untuk periode $$$2a$ kami memiliki: $$$4a ^ 2 + 2ax + 2ay + xy = 2ab + 1$$$$=>$$$$4a ^ 2 + 2ax + 2ay + (ka + r) = 2ab + 1$$$$=>$$$$4a + 2x + 2y + k = (2ab + 1-r) / a$$$$=>$$$$2x + 2thn + k = 2b-4a$ . Kami mendapatkannya untuk $$$4a \ geq 2b$ (atau yang setara - $$$2a \ geq b$ ) lagi, tidak ada kesederhanaan, tetapi jika $$$2a <b$ , maka Anda perlu memeriksa saldo pada posisi $$$2a$ . Demikian pula untuk $$$b$ - periksa apakah $$$2b <a$ . Secara total, kami memperoleh untuk $$$a$ dan untuk $$$b$ kebutuhan untuk memeriksa hanya untuk item baris $$$2a$ dan $$$2b$ karena titik $$$a$ dan $$$b$ akan mengulangi tepat pada posisi $$$2a$ dan $$$2b$ . Verifikasi dilakukan hanya dalam kondisi di atas, yang hampir akan menggandakan proses ketika memeriksa nilai-nilai besar $$$a$ atau $$$b$ , karena bagi mereka mereka harus $$$a \ geq 2b$ dengan skema pembangkitan sederhana di bawah ini, dan nilai yang lebih rendah akan diperiksa dengan sangat cepat karena ukurannya yang kecil.

Dengan demikian, fondasi teoritis telah ditunjukkan di atas untuk dapat menghasilkan bilangan prima yang dijamin untuk bidang-bidang kritis seperti kriptografi.

Selain itu, cara dibuka untuk memeriksa kesederhanaan nomor yang berubah-ubah, asalkan pembagi periode penuhnya ditemukan ( $$$N-1$ ) Jadi, untuk bilangan prima <126.000.000, jumlah "bilangan prima yang dikalikan" milik kelas adalah 676625, dengan jumlah total bilangan prima 7163812, yang memberi kita sedikit kurang dari 9,5%. Untuk bilangan prima hingga satu miliar, kita memiliki 3,49% milik kelas 2p + 1, 1,8116% dari kelas 4p + 1, 2,4709% dari kelas 6p + 1, dan hanya 7,7746%, di mana p adalah bilangan prima. Benar, harus dicatat bahwa dekomposisi periode penuh jumlah besar sangat sulit. Dalam hal ini, Anda dapat menawarkan cek rekursif, yang akan sedikit meningkatkan ukuran angka yang tersedia untuk diperiksa, tetapi pada saat yang sama sangat mengurangi proporsi angka yang melewati cek tersebut, karena jika koefisien menentukan keanggotaan kelas-kelas bilangan prima rekursif diambil sama dengan 0,2, maka sudah pada cek kedua kita akan hanya memiliki 0,04, atau 4% dari total jumlah bilangan prima. Namun demikian, dalam beberapa kasus, pendekatan ini dapat bermanfaat.

Hasil yang praktis

Generator itu sendiri, tentu saja, ditulis dan diuji, karena kompleksitasnya minimal. Selama pemeriksaan, ternyata algoritma berikut ini akan berfungsi penuh:

Kami mendapatkan, misalnya, 1000 bilangan prima awal, yang dapat dihasilkan menggunakan ayakan Eratosthenes atau cukup diunduh dari sini . Lalu kita kalikan setiap nilai dengan masing-masing yang tersisa dan jangan lupa untuk mengalikannya dengan dua, lalu tambahkan satu. Kandidat yang dihasilkan sering dibagi dengan 3, karena bilangan prima memiliki fitur spesifik mirip dengan adanya muatan pada partikel dalam fisika. Orang sederhana dengan "tuduhan" yang sama diusir, dan dengan orang yang berbeda mereka tertarik. Dalam hal ini, "muatan" adalah sisa dari pembagian dengan 3. Artinya, jika sisa pembagian dengan 3 adalah sama untuk kedua bilangan prima, perdana baru tidak akan berfungsi, karena akan dibagi dengan 3. Dan jika sisanya berbeda, maka kita bisa mendapatkan yang benar kandidat untuk sederhana. Selain itu, semua yang sederhana yang diperoleh dengan perkalian adalah “disinkronkan”, yaitu, mereka menerima sisa yang sama dengan 2. Oleh karena itu, tidak ada gunanya untuk mengalikan mereka sendiri lagi. Jadi, untuk mendapatkan bilangan prima baru, kita perlu menyaring bagian dari 1000 awal, di mana modulus dari triple (sisa dari pembagian dengan 3) adalah 1. Jadi, setelah perkalian pertama dari semua dengan semua orang, kita tumbuh dalam jumlah angka yang sudah tidak ada gunanya untuk saling mengalikan satu sama lain, oleh karena itu, untuk lebih meningkatkan ukuran (ke yang digunakan dalam kriptografi), kita harus berkali-kali mengalikan bilangan prima yang diperoleh dengan angka-angka "yang ditagih berlawanan" yang sebelumnya dipilih. Setelah mengalikan dan menambahkan unit, kami melakukan pemeriksaan sesuai dengan kriteria untuk kemungkinan kesederhanaan semu dan jika kriteria terpenuhi, maka kami memeriksa sisanya di posisi 2a untuk setiap kandidat. Jika ada 1, maka kandidat ditolak. Selanjutnya, setiap kandidat diperiksa dengan uji probabilistik biasa, yaitu nilainya dihitung dalam rangkaian residu pada posisi $$$(N-1) / 2$ jika 1 atau $$$N-1$ , maka di depan kita ada nomor perdana yang dijamin.

Ketika melakukan pembangkitan, harus diingat bahwa pada setiap iterasi, diperoleh peningkatan jumlah bilangan prima yang dihasilkan, yaitu, koefisien multiplikasi untuk 1000 bilangan awal lebih dari sekadar persatuan. Oleh karena itu, untuk mendapatkan bilangan prima kriptografis, perlu untuk membatasi generasi, jika tidak akan memakan waktu yang sangat lama, dan mungkin tidak ada cukup memori. Pada saat yang sama, seseorang seharusnya tidak mengurangi set awal dari yang sederhana, karena generasi harus acak, sehingga, mengetahui algoritmanya, penyerang tidak akan memprediksi nilai yang dihasilkan. Untuk ini, perlu untuk menerapkan mekanisme untuk memotong cabang-cabang pohon generasi, yang memungkinkan setiap kali untuk mendapatkan yang sederhana yang unik yang terletak cukup jauh dari yang dihasilkan sebelumnya. Dan tentu saja, memotong kelebihan secara signifikan mempercepat proses.

Waktu pelaksanaan tes tergantung pada jumlah kandidat yang dihasilkan. Masing-masing kandidat lulus tes probabilitas, yang memperlambat generasi ke tingkat terbesar. Dalam uji coba untuk mendapatkan beberapa ratus kisaran sederhana $$$2 ^ {900}$ - $$$2 ^ {1200}$ 5 hingga 20 menit dihabiskan. Perbedaan waktu ini dijelaskan oleh berbagai cara yang dilalui algoritma dalam pohon pembangkitan. Jadi pada awalnya, pembangkitan terbatas pada sekitar 10 angka, tetapi ketika ukuran kriptografi mendekati, pembangkitan memudar karena pengurangan yang signifikan dalam koefisien perkalian dengan peningkatan jumlah. Oleh karena itu, perlu untuk meningkatkan jumlah bilangan prima menengah, tetapi sulit untuk mengatakan seberapa spesifiknya, dan oleh karena itu peningkatan sederhana dalam kuantitas yang diizinkan oleh faktor dua digunakan untuk membatasi dengan peningkatan ukuran jumlah dan melebihi ambang kasar. Akibatnya, dalam batas keterbatasan, jumlah yang sederhana baru dapat mengambang dan dengan demikian membuat perbedaan yang signifikan dalam total waktu pembuatan.

Berikut ini adalah teks dari prosedur Java yang menghasilkan bilangan prima. Secara alami, itu tidak memenuhi persyaratan kriptografi yang jauh melampaui kode program dan terutama terkait dengan masalah organisasi. Pada bagian perangkat lunak murni, prosedur tidak menerapkan mekanisme pemangkasan cabang-cabang pohon generasi, dengan pengecualian pembatasan paling sederhana. Namun demikian, sebagai contoh implementasi algoritma pembangkitan, program dapat membantu dengan sesuatu.

Parameter input adalah daftar awal yang sederhana dan PrintWriter untuk menyimpan hasil ke file. Setelah penyelesaian algoritma, file akan berisi semua produk dari bilangan prima yang dihasilkan dengan angka awal yang memiliki modul tiga sama dengan satu. Hasilnya dapat diperiksa dengan bantuan layanan online yang menerapkan faktorisasi angka, tetapi harus dipahami bahwa mereka dapat menggunakan uji probabilistik untuk kesederhanaan sebelum melakukan faktorisasi, dan karena itu, untuk memeriksa pendekatan yang diusulkan, mereka menjadi tidak berguna (karena semua angka sudah diperiksa dengan uji probabilistik). Tetapi beberapa dari mereka segera mulai memasukkan faktor jumlah yang diusulkan menjadi faktor-faktor, situs-situs tersebut dapat menanamkan kepercayaan tambahan pada kebenaran metode yang diusulkan.

public static void generatePrimes(List<Integer> primes, PrintWriter pw) { List<BigInteger> mod3_1 = new ArrayList<BigInteger>(); List<BigInteger> l = new ArrayList<BigInteger>(); BigInteger three=BigInteger.valueOf(3), two=BigInteger.valueOf(2); for (int k=0;k<primes.size()-1;k++) { BigInteger seed=BigInteger.valueOf(primes.get(k)); BigInteger s2=seed.shiftLeft(1); BigInteger r0=seed.remainder(three); if (r0.intValue()==1) mod3_1.add(seed); for (int i=k+1;i<primes.size();i++) { BigInteger p=BigInteger.valueOf(primes.get(i)); BigInteger r=p.remainder(three); if (r.intValue()==r0.intValue()) continue; // divisible by 3 else addIfPrime(p,seed,s2,two,l); } } List<BigInteger> ps=l; do { System.out.println("found "+l.size()+", bits="+l.get(0).bitLength()); l=new ArrayList<BigInteger>(); for (int k=0;k<ps.size();k++) { BigInteger seed=ps.get(k); BigInteger s2=seed.shiftLeft(1); for (int i=0;i<mod3_1.size();i++) addIfPrime(mod3_1.get(i),seed,s2,two,l); int n=100000; // change following to adjust for required bit count if (l.size()>0) if (l.get(0).bitLength()<700) n=10; else if (l.get(0).bitLength()<800) n=20; else if (l.get(0).bitLength()<900) n=40; if (l.size()>n) break; } ps=l; for (int i=0;i<l.size();i++) pw.println(l.get(i)); pw.flush(); } while (l.size()>0); System.out.println("Done"); } private static void addIfPrime(BigInteger a, BigInteger b, BigInteger b2, BigInteger two, List<BigInteger> l) { BigInteger a2=a.shiftLeft(1), fp=b.multiply(a2), n=fp.add(BigInteger.ONE); BigInteger r=null; if (a2.compareTo(b)<0) r=two.modPow(a2,n); // 2a<b else if (a.compareTo(b2)<0) r=two.modPow(a,n); // a<2b if (r!=null && r.compareTo(BigInteger.ONE)==0) return; r=null; if (b2.compareTo(a)<0) r=two.modPow(b2,n); // 2b<a else if (b.compareTo(a2)<0) r=two.modPow(b,n); // b<2a if (r!=null && r.compareTo(BigInteger.ONE)==0) return; r=two.modPow(fp.shiftRight(1),n); if (r.compareTo(BigInteger.ONE)!=0) return; l.add(n); } 

Nah, sekarang setelah Anda (yah, hampir) tahu segalanya tentang menghasilkan bilangan prima, mungkin minat Anda akan melampaui kriptografi saja dan akan menjadi menarik bagi Anda untuk mempelajari teori bilangan, karena, sebagaimana disebutkan di atas, tersedia untuk siswa kelas lima, tetapi pada saat yang sama itu juga memungkinkan Anda untuk secara mandiri menemukan berlian sejati tanpa menunggu bantuan dari ahli matematika yang serius.