Pemeriksa Keprimalan
Uji sama ada suatu nombor adalah perdana dan lihat sebabnya: pembahagian cubaan sebenar hingga √n untuk nombor kecil dan sederhana, dan penelusuran Miller–Rabin tulen untuk nombor bersaiz kriptografi.
🔒 Diproses sepenuhnya dalam penyemak imbas anda — tiada apa yang anda masukkan di sini pernah dimuat naik.
Keputusan
Pemeriksa keprimalan ini memberitahu anda sama ada suatu integer adalah perdana, dan — tidak seperti kebanyakan kalkulator dalam talian — menunjukkan algoritma sebenar yang membuktikannya, bukan jadual carian dalam cache. Taip sebarang integer, positif atau negatif, kecil atau besar, dan alat ini memutuskan algoritma sebenar mana yang akan dijalankan berdasarkan saiznya.
Untuk nombor di bawah 10¹² (satu trilion), ia menjalankan pembahagian cubaan sebenar: bermula dari 2, ia mencuba setiap integer calon hingga lantai √n sebagai pembahagi yang mungkin, berhenti sebaik sahaja satu membahagi tepat (komposit) atau mengesahkan tiada yang membahagi tepat setelah semua calon hingga √n disemak (perdana). Untuk kiraan calon yang besar, jejak yang dipaparkan dihadkan kepada kira-kira 18 percubaan pertama serta yang terakhir, dengan nota jujur tentang berapa banyak yang dilangkau dalam paparan — tetapi setiap calon tetap disemak oleh kod, tiada yang dilangkau dalam pengiraan.
Untuk nombor pada atau melebihi ambang itu — julat saiz yang digunakan dalam kriptografi — pembahagian cubaan akan mengambil masa terlalu lama, jadi alat ini beralih kepada ujian keprimalan Miller–Rabin dengan set saksi perdana deterministik tetap sebanyak 13 (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41). Set saksi ini adalah hasil yang terkenal: ia tiada positif palsu untuk sebarang n di bawah 3,317,044,064,679,887,385,961,981 (kira-kira 3.3×10²⁴), suatu batasan yang dibuktikan melalui pengesahan pengiraan (lihat Sorenson & Webster, 2015, dan jadual saksi deterministik yang diterbitkan secara meluas yang mengandunginya). Di atas batasan itu, ujian yang sama tetap dijalankan, tetapi alat ini memberitahu anda secara jujur bahawa jaminan tersebut menjadi satu kebarangkalian yang amat kuat dan bukannya kepastian matematik.
Penelusuran Miller–Rabin menulis n − 1 = 2ˢ × d dengan d ganjil, kemudian menelusuri eksponensiasi modular BigInt sebenar — kuasa dua-dan-darab, dikurangkan modulo n pada setiap langkah supaya nombor tidak pernah meletup — bit demi bit untuk saksi pertama, dan melaporkan keputusan setiap saksi, termasuk saksi mana yang membuktikan kekompositan jika nombor tersebut bukan perdana. Semuanya dijalankan secara setempat dalam pelayar anda: tiada pelayan, tiada API luaran, tiada data yang meninggalkan peranti anda.