Mencari Bilangan Prima: Pendekatan Neural AlphaZero untuk Permainan Pemfaktoran

Permainan menggeser token pada papan N\timesN ditunjukkan setara dengan pemfaktoran bilangan bulat, dan pencarian bergaya AlphaZero digunakan untuk menyelidiki batas look-ahead neural pada lingkungan yang setara pemfaktoran ini.

Marcel Crasmaru· 2026· DOI 10.48550/arXiv.2609.22968

Masalah inti

Pemfaktoran bilangan bulat adalah masalah komputasi sentral yang menopang keamanan sistem kriptografi yang banyak digunakan. Karya ini memperkenalkan permainan token satu pemain yang dimainkan pada papan N \times N, di mana token bergeser sepanjang diagonal atau menggandakan diri ke sel tetangga untuk membentuk persegi panjang kombinatorial R \times S . Permainan diatur oleh bobot bilangan bulat W^{'} yang kekal dan monovarian ketat, yang bersama-sama menjamin bahwa solusi memiliki panjang O (N^{2}), menempatkan permainan ini dalam kelas kompleksitas NP . Klaim utamanya adalah bahwa mencapai posisi akhir permainan ini memfaktorkan bilangan bulat 2 N -bit W^{'} menjadi dua faktor N -bit V, M < 2^{N} yang mengodekan baris dan kolom persegi panjang tersebut. Akibatnya, menyelesaikan permainan untuk target semiprima seimbang setara dengan pemfaktoran bilangan bulat. Makalah ini kemudian memanfaatkan ruang pencarian terbatas—yang diperoleh dengan memberikan popcount dari faktor-faktor sebagai janji—menggunakan jaringan policy/value yang dipelajari dan Monte-Carlo tree search bergaya AlphaZero, secara empiris menyelidiki batas look-ahead neural pada lingkungan yang setara pemf

Inovasi

Makalah ini menetapkan beberapa hasil teoretis dan melaporkan temuan empiris dari pencarian bergaya AlphaZero. **Hasil teoretis.** - Permainan berada di NP : solusi memiliki panjang O (N^{2}) karena monovarian ketat. - Mencapai posisi akhir memfaktorkan W^{'} 2 N -bit menjadi dua faktor N -bit V, M < 2^{N} . - Untuk target semiprima seimbang, menyelesaikan permainan setara dengan pemfaktoran bilangan bulat. - Jika persegi panjang target diketahui, solusinya tereduksi menjadi dua langkah waktu polinomial: aliran chip ke bawah yang dipaksakan dan faktorisasi polinomial 0/1 yang memanfaatkan teorema Cohn. - Memberikan popcount dari faktor-faktor sebagai janji mempertahankan kekerasan asimptotik tetapi membatasi ruang pencarian target. **Hasil empiris.** Penulis memanfaatkan ruang terbatas menggunakan jaringan policy/value yang dipelajari dan Monte-Carlo tree search bergaya AlphaZero. Mereka secara empiris menyelidiki batas look-ahead neural pada lingkungan yang setara pemfaktoran. Hasilnya mencirikan bagaimana janji pada popcount membatasi pencarian dan bagaimana panduan neural berperforma dalam ruang terbatas tersebut. Tidak ada metrik performa numerik spesifik yang diber

Pemfaktoran bilangan bulat adalah masalah komputasi sentral yang menopang keamanan sistem kriptografi yang banyak digunakan. Karya ini memperkenalkan permainan token satu pemain yang dimainkan pada papan N \times N, di mana token bergeser sepanjang diagonal atau menggandakan diri ke sel tetangga untuk membentuk persegi panjang kombinatorial R \times S . Permainan diatur oleh bobot bilangan bulat W^{'} yang kekal dan monovarian ketat, yang bersama-sama menjamin bahwa solusi memiliki panjang O (N^{2}), menempatkan permainan ini dalam kelas kompleksitas NP . Klaim utamanya adalah bahwa mencapai posisi akhir permainan ini memfaktorkan bilangan bulat 2 N -bit W^{'} menjadi dua faktor N -bit V, M < 2^{N} yang mengodekan baris dan kolom persegi panjang tersebut. Akibatnya, menyelesaikan permainan untuk target semiprima seimbang setara dengan pemfaktoran bilangan bulat. Makalah ini kemudian memanfaatkan ruang pencarian terbatas—yang diperoleh dengan memberikan popcount dari faktor-faktor sebagai janji—menggunakan jaringan policy/value yang dipelajari dan Monte-Carlo tree search bergaya AlphaZero, secara empiris menyelidiki batas look-ahead neural pada lingkungan yang setara pemfaktoran.

Metodologi berlangsung dalam dua bagian: reduksi teoretis dan algoritma pencarian empiris.

Mengapa penting

Karya ini mengisolasi kesulitan komputasi permainan pada pemisahan teori bilangan awal. Setelah persegi panjang target diketahui, langkah-langkah selanjutnya adalah waktu polinomial: aliran chip ke bawah yang dipaksakan dan faktorisasi polinomial 0/1 yang memanfaatkan teorema Cohn. Pemisahan ini signifikan karena menunjukkan bahwa kekerasan permainan bukan pada dinamika token melainkan pada inti teori bilangan. Janji pada popcount dari faktor-faktor mempertahankan kekerasan asimptotik sekaligus membatasi ruang pencarian target. Hal ini membuat masalah dapat ditangani dengan pencarian heuristik dan berbasis pembelajaran, seperti MCTS bergaya AlphaZero yang digunakan di sini. Penyelidikan empiris look-ahead neural pada lingkungan yang setara pemfaktoran memberikan wawasan tentang batas metode tersebut. Pendekatan ini menghubungkan teori permainan kombinatorial, pemfaktoran bilangan bulat, dan pencarian neural, menyarankan testbed baru untuk mengevaluasi algoritma look-ahead pada masalah teori bilangan yang sulit. **Implikasi.** Reduksi ini menyiratkan bahwa kemajuan apa pun dalam menyelesaikan permainan secara efisien akan menghasilkan algoritma pemfaktoran yang efisien, dengan konsekuensi bagi kriptografi. Sebaliknya, versi yang dibatasi janji menawarkan pengaturan terkendali untuk mempelajari pencarian neural. Penggunaan teorema Cohn untuk faktorisasi polinomial 0/1 adalah bahan teknis kunci yang menjembatani struktur kombinatorial permainan ke pemfaktoran aljabar. **Batasan dan pekerjaan selanjutnya.** Abstrak tidak melaporkan metrik performa empiris spesifik, sehingga skalabilitas praktis pendekatan neural masih perlu dikuantifikasi. Pekerjaan selanjutnya dapat mengeksplorasi N yang lebih besar, jenis janji yang berbeda, dan perbandingan dengan algoritma pemfaktoran klasik.

Siapa yang sebaiknya membaca

Praktisi dan peneliti ilmu komputer

Membuka konten member…