Pemeriksa Primalitas

Pemeriksa primalitas memberi tahu Anda apakah suatu bilangan bulat adalah bilangan prima, dan — tidak seperti kebanyakan kalkulator online — menunjukkan kepada Anda algoritme sebenarnya yang membuktikannya, bukan tabel pencarian yang disimpan dalam cache. Ketikkan bilangan bulat apa pun, positif atau negatif, kecil atau besar, dan alat akan memutuskan algoritma mana yang akan dijalankan berdasarkan ukurannya.

Untuk bilangan di bawah 10¹² (satu triliun), ia menjalankan pembagian percobaan asli: mulai dari 2, ia mencoba setiap kandidat bilangan bulat hingga √n sebagai pembagi yang mungkin, menghentikan saat seseorang membagi secara merata (komposit) atau mengonfirmasi tidak ada yang dilakukan setelah setiap kandidat hingga √n telah diperiksa (prima). Untuk jumlah kandidat yang besar, jejak yang ditampilkan dibatasi hingga ~18 percobaan pertama ditambah yang terakhir, dengan catatan jujur ​​tentang berapa banyak yang dilewati dalam tampilan — namun setiap kandidat sebenarnya masih diperiksa oleh kode, tidak ada yang dilewati dalam perhitungan.

Untuk angka-angka pada atau di atas ambang batas tersebut — rentang ukuran yang digunakan dalam kriptografi — pembagian percobaan akan memakan waktu terlalu lama, sehingga alat tersebut beralih ke uji primalitas Miller–Rabin dengan kumpulan 13 saksi utama yang tetap dan deterministik (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41). Kumpulan saksi yang tepat ini adalah hasil yang sudah diketahui: tidak ada positif palsu untuk n di bawah 3.317.044.064.679.887.385.961.981 (sekitar 3,3×10²⁴), batas yang ditentukan oleh verifikasi komputasi (lihat Sorenson & Webster, 2015, dan tabel saksi deterministik yang direproduksi secara luas). Di atas batas tersebut, pengujian yang sama masih berjalan, namun alat tersebut memberi tahu Anda dengan jujur ​​bahwa jaminan tersebut menjadi jaminan probabilistik yang sangat kuat, bukan kepastian matematis.

Jejak Miller–Rabin menulis n − 1 = 2ˢ × d dengan d ganjil, lalu berjalan melalui eksponensial modular BigInt nyata — kuadrat dan kalikan, mengurangi modulo n di setiap langkah sehingga angkanya tidak pernah meledak — sedikit demi sedikit untuk saksi pertama, dan melaporkan setiap keputusan saksi, termasuk saksi mana yang membuktikan komposititas jika bilangan tersebut ternyata bukan bilangan prima. Semuanya berjalan secara lokal di browser Anda: tidak ada server, tidak ada API eksternal, tidak ada data yang keluar dari perangkat Anda.