Cara Membuat Bilangan Prima Besar | Majalah Quanta

Bilangan prima adalah hal yang rumit. Kita belajar di sekolah bahwa mereka adalah bilangan tanpa faktor selain 1 dan diri mereka sendiri, dan bahwa ahli matematika telah mengetahui selama ribuan tahun bahwa jumlahnya tidak terbatas. Memproduksi satu sesuai perintah sepertinya tidak sulit.

Tapi itu. Membangun bilangan prima besar yang sewenang-wenang sangat rumit. Anda pada dasarnya memiliki dua opsi komputasi, keduanya dengan kekurangan. Anda dapat menggunakan keacakan dan menemukannya dengan menebak, tetapi metode ini tidak konsisten — Anda berisiko menghasilkan bilangan prima yang berbeda setiap saat. Atau Anda dapat menggunakan algoritme deterministik yang lebih andal, tetapi dengan biaya komputasi yang mahal.

Pada bulan Mei, tim ilmuwan komputer menunjukkan bahwa semacam pendekatan hibrida juga bisa berhasil. Mereka menerbitkan sebuah algoritme yang secara efektif menggabungkan pendekatan acak dan deterministik untuk menghasilkan bilangan prima dengan panjang tertentu, dengan probabilitas tinggi untuk menghasilkan bilangan yang sama bahkan jika algoritme dijalankan berkali-kali. Algoritme menghubungkan keacakan dan kompleksitas dengan cara yang menarik, dan mungkin juga berguna untuk kriptografi, di mana beberapa skema pengkodean bergantung pada konstruksi bilangan prima besar.

“Mereka menyusun urutan percobaan, masing-masing mencoba menyusun bilangan prima dengan panjang yang berbeda, dan menunjukkan bahwa salah satu percobaan berhasil,” kata Roei Beritahu, seorang ilmuwan komputer teoretis di Institute for Advanced Study yang tidak terlibat dalam pekerjaan tersebut. "Ini adalah konstruksi yang menghasilkan bilangan prima yang dipilih secara deterministik, tetapi memungkinkan Anda untuk melempar koin dan membuat pilihan acak dalam prosesnya."

Tantangan untuk membuat resep bilangan prima yang efisien memiliki akar yang dalam. "Kami benar-benar tidak tahu banyak tentang bagaimana bilangan prima didistribusikan, atau tentang kesenjangan dalam bilangan prima," kata Ofer Grossman, yang mempelajari algoritma pseudorandom. Dan jika kita tidak tahu di mana menemukannya, tidak ada cara mudah untuk menghasilkan bilangan prima dari nol.

Seiring waktu, para peneliti mengembangkan pendekatan yang disebutkan di atas. Cara paling sederhana adalah dengan menebak. Jika Anda menginginkan bilangan prima dengan 1,000 digit, misalnya, Anda dapat memilih bilangan 1,000 digit secara acak lalu memeriksanya. “Kalau tidak prima, coba saja yang lain, dan yang lain, dan seterusnya sampai ketemu,” kata Rahul Santanam, seorang ilmuwan komputer di Universitas Oxford dan salah satu penulis makalah baru. “Karena ada banyak bilangan prima, algoritme ini akan memberi Anda sejumlah bilangan prima dengan probabilitas tinggi, setelah jumlah iterasi yang relatif kecil.” Tetapi menggunakan keacakan berarti Anda kemungkinan besar akan mendapatkan nomor yang berbeda setiap saat, katanya. Itu bisa menjadi masalah jika Anda membutuhkan konsistensi — jika, katakanlah, Anda menggunakan metode keamanan kriptografi yang bergantung pada ketersediaan bilangan prima besar.

Pendekatan lainnya adalah menggunakan algoritma deterministik. Anda dapat memilih titik awal dan mulai menguji angka, secara berurutan, untuk primalitas. Akhirnya Anda ditakdirkan untuk menemukannya, dan algoritme Anda akan secara konsisten menampilkan yang pertama Anda temukan. Tapi ini bisa memakan waktu cukup lama: Jika Anda mencari bilangan prima dengan 1,000 digit, bahkan perhitungan dengan 2⁵⁰⁰ langkah - yang akan memakan waktu lebih lama dari usia alam semesta - tidak cukup untuk menjamin kesuksesan.

Pada tahun 2009, ahli matematika dan peraih medali Fields Terence Tao ingin berbuat lebih baik. Dia menantang ahli matematika untuk menghasilkan algoritma deterministik untuk menemukan bilangan prima dari ukuran tertentu dalam batas waktu komputasi.

Batas waktu itu dikenal sebagai waktu polinomial. Algoritma memecahkan masalah dalam waktu polinomial jika jumlah langkah yang diperlukan tidak lebih dari fungsi polinomial dari n, ukuran masukan. (Fungsi polinomial mencakup suku-suku yang memiliki variabel yang dipangkatkan bilangan bulat positif, seperti n² atau 4n³.) Dalam konteks konstruksi bilangan prima, n mengacu pada jumlah digit pada bilangan prima yang Anda inginkan. Berbicara secara komputasi, ini tidak memerlukan biaya banyak: Ilmuwan komputer menjelaskan masalah yang dapat diselesaikan dengan algoritme dalam waktu polinomial dengan mudah. Masalah yang sulit, sebaliknya, membutuhkan waktu eksponensial, yang berarti membutuhkan sejumlah langkah yang didekati oleh fungsi eksponensial (yang mencakup istilah seperti 2ⁿ).

Selama beberapa dekade, para peneliti telah menyelidiki hubungan antara keacakan dan kekerasan. Masalah konstruksi bilangan prima dianggap mudah jika Anda mengizinkan keacakan - dan puas dengan menerima nomor yang berbeda setiap kali - dan sulit jika Anda bersikeras pada determinisme.

Belum ada yang berhasil memenuhi tantangan Tao, tetapi pekerjaan baru sudah dekat. Ini sangat mengacu pada pendekatan yang diperkenalkan pada tahun 2011 oleh Shafi Goldwasser dan Eran Gat, ilmuwan komputer di Massachusetts Institute of Technology. Mereka mendeskripsikan algoritme "pseudoterministik" — resep matematis untuk masalah pencarian, seperti menemukan bilangan prima besar, yang dapat memanfaatkan manfaat keacakan dan, dengan probabilitas tinggi, tetap menghasilkan jawaban yang sama setiap saat. Mereka akan menggunakan efisiensi bit acak dalam resep, yang akan dide-acak pada hasilnya, tampak deterministik.

Para peneliti telah mengeksplorasi algoritma pseudodeterministic sejak saat itu. Pada 2017, Santhanam dan Igor Oliveira dari University of Warwick (yang juga berkontribusi pada karya baru ini) dijelaskan pendekatan pseudodeterministik untuk membangun bilangan prima yang menggunakan keacakan dan tampak deterministik meyakinkan, tetapi bekerja dalam waktu "subeksponensial" - lebih cepat dari eksponensial, tetapi lebih lambat dari waktu polinomial. Kemudian pada tahun 2021, Tell dan Lijie Chen, seorang ilmuwan komputer di University of California, Berkeley, dieksplorasi bagaimana menggunakan masalah sulit untuk membuat generator nomor pseudorandom (algoritme yang menghasilkan serangkaian angka yang tidak dapat dibedakan dari keluaran acak). “[Kami] menemukan hubungan baru antara kekerasan dan keacakan semu,” kata Chen.

Potongan-potongan itu akhirnya bersatu pada musim semi 2023, selama bootcamp tentang kompleksitas komputasi di Simons Institute for the Theory of Computing di Berkeley, ketika para peneliti mulai bekerja sama dalam masalah ini, menenun bersama hasil-hasil sebelumnya. Untuk karya baru, kata Chen, Hanlin Ren — seorang ilmuwan komputer di Oxford dan rekan penulis — memiliki ide awal untuk menggabungkan hasil Chen-Tell dengan pendekatan Santhanam-Oliveira dengan cara baru. Kemudian seluruh tim mengembangkan ide lebih lengkap untuk menghasilkan kertas baru.

Algoritma pseudodeterministik yang dihasilkan, kata Santhanam, menggunakan cara baru untuk melihat pekerjaan sebelumnya untuk menghasilkan bilangan prima dalam waktu polinomial. Ini terbukti menggunakan keacakan untuk menghasilkan bilangan prima dengan panjang tertentu, dan alat ini lebih akurat daripada tebakan acak dan lebih efisien secara komputasi daripada penguraian deterministik.

Algoritme baru ini juga sangat sederhana, kata Santhanam, dan dapat diterapkan pada berbagai masalah pencarian — sungguh, pada subkumpulan angka yang padat, seperti bilangan prima, yang keanggotaannya dapat ditentukan dalam waktu polinomial. Tapi itu tidak sempurna. Algoritme bekerja untuk panjang input yang tak terbatas, tetapi tidak mencakup semua panjang digit. Mungkin masih ada beberapa nilai dari n di luar sana yang algoritmanya tidak menghasilkan bilangan prima secara deterministik.

“Akan keren untuk menghilangkan peringatan kecil itu,” kata Grossman.

Tujuan utamanya, kata Santhanam, adalah menemukan algoritme yang tidak memerlukan keacakan sama sekali. Tapi pencarian itu tetap terbuka. "Determinisme adalah apa yang ingin kami gunakan," katanya.

Tetapi dia juga menunjukkan bahwa proses pseudorandom adalah alat yang ampuh, dan proyek seperti membangun bilangan prima hanyalah salah satu cara menggunakannya untuk menghubungkan ide dari matematika, ilmu komputer, teori informasi, dan bidang lainnya.

“Menarik untuk mencoba dan berpikir ke mana lagi pengamatan brilian ini akan mengarah,” kata Tell.