Fermat Asallık Testi Hesaplayıcı

Bu hesaplama hakkında

Fermat'nın küçük teoremi, n bir asal sayıysa, n'ye bölünmeyen herhangi bir a tam sayı tabanı için a^(n-1) ≡ 1 (mod n) olduğunu söyler. Bu hesaplayıcı bu kontrolü tersine çevirerek çalışır: verilen bir n sayısı ve seçilen bir a tabanı için a^(n-1) mod n değerini hesaplar — sonuç 1 değilse n kesinlikle bileşiktir; sonuç 1 ise n yalnızca muhtemelen asaldır, çünkü nadir bileşik sayılar (Fermat sözde asalları ve özellikle inatçı Carmichael sayıları) birçok hatta tüm tabanlar için bu testi geçebilir.

Büyük sayılar için bile hızlı hesaplanabildiğinden, Fermat testi kriptografide ve bilgisayar bilimi eğitiminde ucuz bir ön filtre olarak kullanılır — gerçek dünyadaki RSA anahtar üretiminin temelini oluşturan Miller-Rabin gibi daha yavaş ve titiz asallık testlerini çalıştırmadan önce belirgin bileşikleri hızla eler. Ayrıca sayılar teorisi derslerinde, modüler üs alma işlemini ve asallık için gerekli koşul ile yeterli koşul arasındaki farkı göstermek için standart bir alıştırmadır.