Bilangan prima

O salah satu aplikasi utama bilangan prima ada dalam beberapa algoritme yang terkait dengan kriptografi (mis. RSA) dan oleh karena itu, ini terkait dengan teknik yang dikembangkan untuk menjaga privasi, pembelajaran mesin. Pada posting sebelumnya kita telah mendefinisikan grup dan field menggunakan bilangan prima dan tujuan utama kita dalam posting ini adalah untuk menunjukkan bagaimana cara menghitung bilangan prima dan memeriksa apakah bilangan tertentu adalah bilangan prima atau tidak. Karena pentingnya matematika bilangan prima saya anggap bermanfaat untuk menulis posting lengkap tentang mereka.

Bilangan prima adalah bilangan asli yang hanya habis dibagi oleh dirinya sendiri dan 1 Misalnya 7 adalah bilangan prima karena tidak ada bilangan asli yang lebih kecil dari 7 yang dibagi 7 menghasilkan bilangan bulat. Beberapa bilangan prima yang diurutkan adalah {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41,…}.

Bilangan prima dianggap sebagai bahan dasar aritmatika karena tidak peduli bilangan asli apa pun yang Anda pikirkan, Anda dapat menyatakannya sebagai hasil kali bilangan prima. Misalnya, ambil 30, itu dapat diuraikan menjadi 2 · 3 · 5. Atau 123456 dalam 2 ^ 6 · 3 · 643. Proses penguraian bilangan menjadi faktor bilangan prima disebut dengan faktorisasi.

Teorema fundamental dari aritmatika (alias teorema faktorisasi unik) menyatakan bahwa setiap bilangan bulat yang lebih besar dari 1 adalah bilangan prima itu sendiri atau dapat direpresentasikan sebagai hasil perkalian bilangan prima dan selanjutnya representasi ini unik . Jadi diberi bilangan bulat arbitrer a kita dapat menuliskannya sebagai

Image for post

Image for post

faktorisasi unik dari bilangan komposit

dengan p adalah bilangan prima dan e adalah eksponen dari bilangan tersebut.

Tapi mari kita kembali ke topik, kami tertarik pada kriptografi, apa hubungannya semua ini dengan itu ?. Nah, dalam kriptografi modern seseorang mencoba untuk menemukan masalah matematika yang sulit untuk dipecahkan yang mudah diperiksa. Faktorisasi bilangan prima adalah tugas yang sangat sulit untuk diselesaikan. Ada algoritma seperti Faktorisasi Pollard atau Faktorisasi kurva elips Lenstra yang efisien tetapi jika Anda punya sebuah komputer kuantum di tangan yang terbaik sejauh ini adalah algoritma Shor (polinomial dalam log (N)). Dalam RSA algoritme satu memilih dua besar bilangan prima p dan q dan menghitung N = p · q , tugas musuh untuk memecahkan kode adalah menemukan faktor-faktor dari N . Untuk bilangan prima yang cukup besar, kemungkinan menyelesaikan tugas ini secara kebetulan dapat diabaikan dan metode pemfaktoran klasik memakan waktu terlalu lama sehingga dalam praktiknya tidak mungkin untuk memecahkan kekuatan komputasi saat ini berdasarkan operasi biner. Sebaliknya memiliki p dan N sangat mudah untuk memeriksa apakah p adalah faktor N dengan satu operasi. Ini juga merupakan persyaratan untuk protokol crypto modern.

Itu dibuktikan oleh Euclid pada 300 SM bahwa ada banyak bilangan prima yang tak terhingga. Yang terbesar yang ditemukan pada Agustus 2020 adalah 2 ^ 82589933-1 dan memiliki 24.862.048 digit jika ditulis dalam basis 10.

Alangkah baiknya memiliki rumus yang ketika Anda memasukkan “beri saya bilangan prima 532” itu akan menghasilkan 3833 (bilangan prima 532), semua itu mengambil O (1) menghitung waktu. Sayangnya rumus ini tidak ada dan menemukan bilangan prima baru membutuhkan banyak usaha komputasi. Itu berarti bahwa mereka tidak dapat diprediksi dan ini adalah salah satu misteri tentang bilangan prima… begitu Anda melihat bilangan prima, Anda tidak tahu kapan akan menemukan bilangan prima berikutnya. Apakah ada semacam random / chaos dalam struktur bilangan prima? Belum ada yang tahu.

Meskipun kami bisa ‘ t memprediksi bilangan prima dengan rumus kita dapat menghitung probabilitas menemukan bilangan prima di antara berbagai bilangan. Kami mendefinisikan Pi (x) sebagai bilangan prima yang lebih kecil dari x. Misalnya, Pi (20)=8, karena bilangan prima lebih kecil dari 20 adalah {2, 3, 5, 7, 11, 13, 17, 19}. Oleh karena itu, untuk menghitung jumlah bilangan prima antara x2 dan x1 (x2> x1) kita hanya perlu mengurangi Pi (x2) -Pi (x1). Di sini Pi (x) adalah perhitungan eksak dan kita harus melakukannya secara numerik. Teorema bilangan prima menetapkan distribusi bilangan prima asimtotik dengan mendekati hitungan ke x / ln (x)

Image for post

Image for post

Representasi grafis dari hasil ini ditunjukkan di bawah ini:

Image for post

Image for post

Rasio fungsi penghitungan bilangan prima dengan dua perkiraan. Dari Wikipedia

Dalam grafik Anda dapat melihat bagaimana hitungan bilangan prima (the tepat satu) dibagi dengan pendekatan cenderung 1 untuk x besar untuk dua pendekatan, hasil bagi dan integral. Sebenarnya perkiraan terbaik adalah yang tidak terpisahkan. Hasil ini sangat menarik dan membutuhkan waktu bertahun-tahun untuk menemukannya, memberikan beberapa struktur pada kegilaan bilangan prima ini. Tapi tetap saja, kami tidak bisa memprediksi mereka dan ini bagus untuk crypto!.

Pada bagian ini kita menyelidiki bagaimana menemukan bilangan prima dan menguji apakah bilangan acak adalah bilangan prima.

Cara naif untuk menghasilkan bilangan prima

Cara alami untuk menghasilkan bilangan prima adalah memulai dari yang terkecil {2} dan menguji apakah yang berikutnya satu (3) habis dibagi 2, karena bukan, kita tambahkan ke daftar, lalu kita punya {2, 3}. Kami pergi ke tes 4 sekarang, karena habis dibagi oleh salah satu bilangan prima yang sudah kami miliki (2) kami tidak menambahkannya ke daftar dan kami mencoba yang berikutnya, 5. 5 tidak dapat dibagi baik oleh 2 maupun oleh 3 jadi kami menambahkannya ke daftar, {2, 3, 5} dan seterusnya… Ini adalah algoritme yang sangat intensif secara komputasi karena setiap saat Anda harus memeriksa daftar lengkap yang, omong-omong, meningkat setiap kali Anda menemukan bilangan prima baru.

Saringan Eratosthenes

SEBUAH cara yang lebih cepat untuk menghasilkan bilangan prima adalah menggunakan saringan Eratosthenes di mana pada dasarnya Anda membuat daftar semua bilangan asli dari 1 hingga n ( n adalah natural bilangan di bawah ini yang Anda inginkan semua bilangan prima) dan hapus semua kelipatan dari bilangan prima yang baru ditemukan. Katakanlah kita ingin bilangan prima lebih kecil dari n =120. Algoritme dimulai dengan 2, lalu Anda membuang kelipatannya (2, 4, 8,…, 120), Anda memilih 3 dan Anda tahu itu adalah bilangan prima karena belum dibuang, jadi Anda menghilangkan kelipatan 3 tempat berlindung itu ‘ t telah dibuang (3, 9, 12, 15…). Angka berikutnya adalah 4 dan telah dibuang sehingga Anda pergi ke 5 dan menambahkannya sebagai bilangan prima, lalu menghilangkan kelipatannya… Anda dapat menemukan implementasi yang bagus di python sini.

Pengujian primality dan algoritma Miller-Rabin

Semua pendekatan sejauh ini tampaknya sangat panjang… dalam kriptografi Anda sering menggunakan bilangan prima 256 bit (2²⁵⁵ hingga 2²⁵⁶). Sekarang, Anda tidak dapat membuat semua bilangan prima hingga 2²⁵⁶ lalu memilih satu secara acak, untuk ini Anda perlu menggunakan uji primalitas. Pada dasarnya yang Anda lakukan adalah menggambar bilangan asli acak dan kemudian memeriksa apakah bilangan ini prima atau bukan.

Jadi diberi bilangan asli n , bagaimana cara mengetahui apakah n adalah bilangan prima atau tidak? Ingat teorema kecil Fermat pertama: Misalkan p menjadi bilangan prima dan misalkan a menjadi sembarang bilangan bulat lalu

Image for post

Image for post

Kami dapat menggunakan itu untuk memeriksa apakah n adalah bilangan prima. Jika kita pasang n dan bukan p ke persamaan di atas (mengambil misalnya. a =2) dan menemukan bahwa ^ {n-1} (mod n) adalah 1 maka dapatkah kita katakan bahwa n adalah bilangan prima ?. Jawabannya tidak, karena teorema kecil Fermat hanya mengarah ke satu arah (kita perlu tahu pasti bahwa p adalah bilangan prima). Namun hal itu memberikan indikasi yang baik bahwa mungkin n adalah bilangan prima. Jadi bagaimana jika kita menguji banyak a ? Jika kita menemukan bahwa pangkatnya 1 untuk semuanya, dapatkah kita mengatakan bahwa n adalah bilangan prima? Sayangnya jawabannya sekali lagi tidak. Sebenarnya ada bilangan yang dikenal sebagai bilangan Carmichael yang merupakan gabungan dan kekuatannya a ^ (n-1) selalu 1. Bilangan Carmichael yang terkenal adalah 561=3 · 11 · 17 dan yang pangkatnya

menyalakan nomor Carmichael 561

untuk semua a lebih kecil dari 561.

Sepertinya kita berada dalam situasi cul-de-sac… Tapi semoga kita memiliki algoritma Miller-Rabin untuk membantu kita. Tes ini dikembangkan oleh Miller pada tahun 1976 sebagai tes deterministik penuh tetapi kemudian dimodifikasi oleh Rabin pada tahun 1980 untuk menjadikannya algoritma probabilistik. Untuk menghindari bilangan Carmichael, izinkan saya membuat proposisi berikut: Misalkan p menjadi bilangan prima (berbeda dari 2) kemudian kita dapat menulis p dalam bentuk

Image for post

di mana q adalah bilangan ganjil dan k bilangan bulat . Sekarang biarkan a menjadi nomor apa pun yang tidak dapat dibagi oleh p . Maka salah satu dari dua ketentuan berikut adalah benar

Image for post

Image for post

Image for postatau

Image for post

Image for post

untuk c di {1, 2, 4,…, 2 ^ k}. Anda dapat menemukan bukti dari proposisi ini adalah buku dari Hoffstein, Pipher dan Silverman. Ini terjadi secara ketat ketika p adalah bilangan prima tapi mari kita gantikan ini p untuk sembarang nomor n . Kita bisa menulis n – 1=2 ^ k q dan temukan a sedemikian rupa sehingga kedua kondisi di atas adalah

tidak terpenuhi, lalu kita sebut a seorang saksi Miller-Rabin untuk keterpaduan n . Yaitu. jika kita menemukan a kita tahu pasti bahwa n adalah komposit.

Ok, tapi berapa banyak acak a yang harus diuji untuk memberikan kepastian katakanlah 99% bahwa bilangan p mungkin bilangan prima ?. Ada proposisi lain yang menilai itu. Misalkan n adalah bilangan komposit ganjil, lalu setidaknya 75% bilangan antara 1 dan n – 1 adalah saksi Miller-Rabin untuk n . Ini berarti bahwa jika kita secara acak mengambil sampel 10 nilai berbeda dari a dalam rentang 1 hingga n – 1, kemungkinan memukul sedikitnya 1 saksi adalah 1- P_Bernoulli (k=1, n=10 )=0,99997. Oleh karena itu kami cukup yakin bahwa jika dalam 10 persidangan kami belum menemukan saksi bilangan prima tetapi kami tidak akan pernah yakin 100%.

Implementasi saya dalam kode algoritma Miller-Rabin dapat ditemukan sini. Juga kode untuk menghasilkan bilangan prima acak. Memeriksa waktu kalkulasi dengan laptop biasa (2.6GHz 6 core 16 GB RAM) Saya mendapatkan antara 25ms hingga 60ms untuk menghasilkan 256 bit random prime, di antara 80 dan 120ms untuk 512 bit prime dan antara 500ms hingga 2.15s untuk 1024 bit utama. Semua ini memeriksa 40 nilai maksimum saksi potensial a .

Bilangan prima adalah blok bangunan aritmatika dan sangat berguna dalam kriptografi. Kita telah melihat bagaimana bilangan prima didistribusikan dalam kepadatan, cara menemukannya secara efisien, dan cara menguji apakah suatu bilangan prima atau komposit menggunakan pengujian primalitas Miller-Rabin. Terima kasih telah membaca!. Jika Anda menyukai artikel itu, harap beri bintang github saya repo dan beri saya beberapa tepuk di artikel.

Read More

RELATED ARTICLES

LEAVE A REPLY

Please enter your comment!
Please enter your name here

Most Popular

Recent Comments