Kesulitan Menghasilkan Bilangan Prima 1024-bit

• Pendahuluan
  • Bilangan prima memang mudah dijelaskan, tetapi menyimpan kompleksitas yang luar biasa
  • Digunakan dalam beragam bidang seperti konsep matematika, visualisasi yang menarik, kriptografi, dan lain-lain
  • Memutuskan tantangan untuk menghasilkan bilangan prima dengan pemrograman
• Tantangan
  • Menghasilkan bilangan prima yang bisa dipakai untuk algoritma RSA
  • Karena panjang yang cocok untuk kunci RSA saat ini adalah 2048 bit, dibutuhkan dua bilangan prima berukuran 1024 bit
  • Batasan:
    • Menulis kode dari awal (tanpa dependensi eksternal)
    • Hanya menggunakan CPU AMD Ryzen 7 dan RAM 16GB pada laptop
    • Menghasilkan bilangan prima dalam waktu yang "wajar"
  • Memilih bahasa Rust
• Pembuatan bilangan prima 16-bit
  • Menghasilkan bilangan acak memakai /dev/urandom sebagai PRNG
  • Menggunakan metode uji pembagian coba (Trial Division), metode uji prima paling sederhana
  • Dapat menghasilkan bilangan prima 16-bit dalam rata-rata 40ms
• Pembuatan bilangan prima 64-bit
  • Mengimplementasikan algoritma Trial Division yang dioptimalkan
    • Hanya memeriksa angka berbentuk 6k±1
    • Membangkitkan daftar bilangan prima kecil lebih dulu untuk menyaring angka yang mudah dibagi
  • Setelah dioptimalkan, memakan waktu sekitar 6 detik
  • Ada batasan untuk angka yang lebih besar jika memakai algoritma deterministik
• Uji prima probabilistik
  • Menggunakan Teorema Kecil Fermat (Fermat's Little Theorem)
    • Ada masalah di mana bilangan komposit pun bisa memenuhi syarat (Pseudoprimes)
  • Uji Keprimaan Miller-Rabin (Miller-Rabin Primality Test)
    • Versi probabilistik yang menyempurnakan uji Fermat
    • Tidak ada bilangan komposit yang selalu menjadi pseudoprime untuk satu basis (base) tertentu
    • Probabilitas kesalahan sangat rendah sehingga dapat dipakai secara praktis
• Pembuatan bilangan prima 128-bit
  • Dapat dihasilkan dengan cepat menggunakan uji Miller-Rabin (rata-rata 0.03 detik)
  • Sulit untuk memperluas hingga 1024 bit karena keterbatasan tipe data u128
• Implementasi BigInt untuk 1024 bit
  • Meningkatkan secara bertahap melalui beberapa percobaan
    • Percobaan 1: Menyimpan setiap digit angka dalam array
    • Percobaan 2: Menyimpan angka dalam bentuk biner
    • Percobaan 3: Menyimpan angka sebagai potongan per byte
    • Percobaan 4: Menyimpan angka sebagai potongan u64
    • Percobaan 5: Mengoptimalkan algoritma empat operasi aritmatika
  • Mengoptimalkan uji Miller-Rabin dan alur logika secara menyeluruh
  • Pemrosesan paralel dengan memanfaatkan multithreading
• Hasil akhir
  • Dapat menghasilkan bilangan prima 1024-bit dalam sekitar 40ms (8ms ~ 800ms)
  • Dengan pemrosesan paralel, rata-rata memakan waktu 0.04 detik

Opini GN⁺

• Proses penyempurnaan bertahap melalui siklus mencoba-gagal sangat mengesankan
  • Mulai dari implementasi sederhana, lalu pada setiap tahap menerapkan ide baru dan melakukan optimasi
  • Meski mengalami kegagalan, tidak menyerah dan terus mengidentifikasi akar masalah serta mencari solusi
• Menarik karena meskipun penulis memiliki keterbatasan dasar matematika, ia tetap mencari referensi terkait dan berusaha memahaminya
  • Mempelajari konsep-konsep matematika yang dibutuhkan seperti Teorema Kecil Fermat dan uji Miller-Rabin
  • Materi yang sulit dipahami hingga level yang bisa diimplementasikan
• Menarik bahwa penulis membangun BigInt sendiri untuk mengatasi batasan tipe integer ukuran tetap
  • Bukan sekadar menggunakan pustaka yang sudah ada, tetapi juga memahami cara kerjanya secara internal dan melakukan optimasi
  • Menonjolnya upaya mencoba berbagai ide dan memperbaiki secara bertahap sangat terlihat
• Menarik bagaimana pemrosesan paralel menggunakan multithreading meningkatkan performa secara signifikan
  • Menangkap dan memanfaatkan karakteristik masalah yang dapat dihitung secara independen
  • Bukan sekadar mengejar kecepatan, tetapi pendekatan efektif yang mempertimbangkan karakteristik masalah
• Meskipun belum mencapai tingkat keamanan kriptografi, ini terlihat sebagai proyek yang sangat berarti sebagai proses belajar dan eksplorasi
  • Lebih menonjolkan rasa ingin tahu dan semangat tantangan penulis daripada pemanfaatan praktis
  • Diharapkan wawasan dan pengalaman yang didapatkan akan sangat membantu pertumbuhan penulis ke depan

[GN⁺]

Komentar Hacker News

• Terkait hal tersebut, beberapa cryptocurrency menggunakan hal-hal yang berhubungan dengan pencarian bilangan prima besar sebagai bagian dari fungsi bukti kerja. Sekitar delapan tahun lalu, banyak orang bisa menghasilkan uang banyak berkat implementasi uji bilangan prima yang sangat cepat. Penulis sempat menjadi pembuat sekaligus administrator perangkat lunak penambangan untuk Riecoin untuk sementara waktu.

• Di artikel ini, penulis mengabaikan Montgomery multiplication, optimasi terbaik untuk uji bilangan prima yang cepat. Ini menjadi dasar implementasi operasi perpangkatan modular praktis yang cepat.

• CGBN karya Niall Emmart adalah pustaka bigint GPU yang sangat cepat. Ini masih implementasi batch modexp tercepat yang saya ketahui.

• Python menyediakan modexp bawaan yang cukup baik untuk menghitung pow(x, y, m) → x^y % m, sehingga uji primalitas Fermat atau Miller-Rabin bisa dengan mudah diimplementasikan.

• Awalnya saya merasa konsep uji primalitas probabilistik aneh dan mencoba mencari algoritma deterministik yang bisa menangani angka raksasa, tetapi APR-CL dan ECPP terlalu rumit secara matematika untuk saya pahami. Saya sadar bahwa hampir semua sistem, termasuk RSA, menggunakan algoritma probabilistik.

• Membuat Miller-Rabin menjadi deterministik untuk batas maksimum tertentu adalah hal yang jelas. Cukup pilih basis yang terbukti mengeliminasi semua pseudoprime dalam rentang itu.

• Satu baris inline assembly bisa membuat perkalian angka besar jadi sederhana. Akan lebih baik jika bahasa C menambahkan konsep perkalian ekstended. Dukungan perangkat kerasnya ada di mana-mana.

• Tes Fermat sudah cukup, karena algoritma tidak akan berjalan jika bilangan tersebut ternyata bukan prima sebenarnya. Tapi saya tidak tahu apakah bisa dibuktikan bahwa tidak ada nilai P/Q komposit yang tetap bisa mengenkripsi dan mendekripsi pesan dengan sukses.

• Saya penasaran berapa lama proyek ini dikerjakan. Penulis sudah mengimplementasikan Karatsuba, Toom-Cook, FFT kompleks, NTT, dan Schönhage–Strassen. Ia merekomendasikan buku Silverman berjudul 'A Friendly Introduction to Number Theory'.

• Saat menulis sendiri kode untuk perkalian angka besar, saya merasakan betapa sulitnya menerjemahkan penjelasan tingkat tinggi di makalah matematika menjadi operasi nyata. Ada sedikit masalah pada bagian penjelasan basis.

• Optimisasi terakhir yang menambahkan +2 alih-alih membangkitkan angka baru sedikit mengurangi keamanan. Karena bilangan prima tidak terdistribusi merata, sehingga memihak bilangan prima yang langsung mengikuti celah prima besar.

• Terdapat sedikit kekeliruan pada penjelasan Teorema Kecil Fermat. Ia mengatakan a^(p-1) habis dibagi p, padahal a^(p-1) - 1 lah yang seharusnya habis dibagi p. Dalam istilah aritmetika modular, ini dijelaskan dengan benar.