Pemeriksa Keprimaan
Uji apakah sebuah bilangan prima dan lihat alasannya secara persis: trial division sungguhan hingga √n untuk bilangan kecil dan menengah, serta penelusuran Miller–Rabin sesungguhnya untuk bilangan seukuran kriptografi.
🔒 Diproses sepenuhnya di browser Anda — apa pun yang Anda masukkan di sini tidak akan pernah diunggah.
Hasil
Pemeriksa keprimaan ini memberi tahu Anda apakah sebuah bilangan bulat prima, dan — tidak seperti kebanyakan kalkulator daring — menunjukkan algoritma yang benar-benar membuktikannya, bukan tabel pencarian yang di-cache. Ketik bilangan bulat apa pun, positif atau negatif, kecil atau sangat besar, dan alat ini akan memutuskan algoritma sungguhan mana yang akan dijalankan berdasarkan ukurannya.
Untuk bilangan di bawah 10¹² (satu triliun), alat ini menjalankan trial division sungguhan: dimulai dari 2, ia mencoba setiap kandidat bilangan bulat hingga nilai floor dari √n sebagai pembagi yang mungkin, berhenti saat salah satunya membagi habis (komposit) atau mengonfirmasi tidak ada yang membagi setelah setiap kandidat hingga √n selesai diperiksa (prima). Untuk jumlah kandidat yang sangat besar, jejak yang ditampilkan dibatasi pada ~18 percobaan pertama ditambah yang terakhir, dengan catatan jujur tentang berapa banyak yang dilewati dalam tampilan — tetapi setiap kandidat masih benar-benar diperiksa oleh kode, tidak ada yang dilewati dalam komputasi.
Untuk bilangan pada atau di atas ambang tersebut — rentang ukuran yang digunakan dalam kriptografi — trial division akan memakan waktu terlalu lama, sehingga alat ini beralih ke uji keprimaan Miller–Rabin dengan himpunan 13 saksi prima yang tetap dan deterministik (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41). Himpunan saksi yang tepat ini adalah hasil yang terkenal: ia tidak memiliki positif palsu untuk n apa pun di bawah 3.317.044.064.679.887.385.961.981 (sekitar 3,3×10²⁴), sebuah batas yang ditetapkan melalui verifikasi komputasi (lihat Sorenson & Webster, 2015, dan tabel saksi deterministik yang banyak direproduksi yang memuatnya). Di atas batas itu, pengujian yang sama tetap berjalan, tetapi alat ini dengan jujur memberi tahu Anda bahwa jaminannya menjadi probabilistik yang sangat kuat, bukan kepastian matematis.
Jejak Miller–Rabin menulis n − 1 = 2ˢ × d dengan d ganjil, lalu menelusuri eksponensial modular BigInt sungguhan — square-and-multiply, mereduksi modulo n di setiap langkah sehingga bilangan tidak pernah meledak — bit demi bit untuk saksi pertama, dan melaporkan vonis setiap saksi, termasuk saksi mana yang membuktikan komposit jika bilangan tersebut ternyata tidak prima. Semuanya berjalan secara lokal di browser Anda: tidak ada server, tidak ada API eksternal, tidak ada data yang meninggalkan perangkat Anda.