Pemeriksa Keutamaan

Pemeriksa keutamaan memberitahu anda sama ada integer adalah prima, dan — tidak seperti kebanyakan kalkulator dalam talian — menunjukkan kepada anda algoritma sebenar yang membuktikannya, bukan jadual carian cache. Taipkan mana-mana integer, positif atau negatif, kecil atau besar, dan alat menentukan algoritma sebenar untuk dijalankan berdasarkan saiznya.

Untuk nombor di bawah 10¹² (satu trilion), ia menjalankan bahagian percubaan tulen: bermula pada 2, ia mencuba setiap calon integer sehingga ke tingkat √n sebagai pembahagi yang mungkin, menghentikan saat satu membahagi sama rata (komposit) atau mengesahkan tiada yang melakukan sebaik sahaja setiap calon sehingga √n telah disemak (utama). Untuk kiraan calon yang besar, jejak yang ditunjukkan dihadkan kepada ~18 percubaan pertama ditambah yang terakhir, dengan nota yang jujur ​​tentang bilangan yang dilangkau dalam paparan — tetapi setiap calon masih sebenarnya disemak oleh kod, tiada yang dilangkau dalam pengiraan.

Untuk nombor pada atau di atas ambang itu — julat saiz yang digunakan dalam kriptografi — pembahagian percubaan akan mengambil masa terlalu lama, jadi alat itu beralih kepada ujian keutamaan Miller–Rabin dengan set tetap, deterministik 13 saksi utama (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 1). Set saksi tepat ini merupakan hasil yang terkenal: ia tidak mempunyai positif palsu untuk mana-mana n di bawah 3,317,044,064,679,887,385,961,981 (kira-kira 3.3×10²⁴), terikat yang diwujudkan melalui pengesahan pengiraan (lihat Sorenson & Webster, 2015, dan jadual kepunyaannya secara meluas). Di atas batas itu ujian yang sama masih berjalan, tetapi alat itu memberitahu anda dengan jujur ​​bahawa jaminan itu menjadi satu kebarangkalian yang sangat kuat dan bukannya kepastian matematik.

Jejak Miller–Rabin menulis n − 1 = 2ˢ × d dengan d ganjil, kemudian berjalan melalui eksponensial modular BigInt sebenar — segi empat sama dan darab, mengurangkan modulo n pada setiap langkah supaya nombor tidak pernah meletup — sedikit demi sedikit untuk saksi pertama, dan melaporkan keputusan setiap saksi, termasuk saksi yang membuktikan keterpaduan nombor jika tidak menjadi ketepatan nombor. Semuanya berjalan secara setempat dalam penyemak imbas anda: tiada pelayan, tiada API luaran, tiada data yang pernah meninggalkan peranti anda.