Miller-Rabin Asallık Testi Hesaplama

Bu hesaplama hakkında

Miller-Rabin testi, n − 1 sayısını d tek sayı olacak şekilde 2ˢ·d biçiminde yazıp, bir tanık taban a'nın aᵈ ≡ 1 (mod n) ya da bir r < s için a^(2ʳ·d) ≡ −1 (mod n) koşulunu sağlayıp sağlamadığını kontrol eder. Tek bir tanıkla sonuç yalnızca olasılıksaldır; ancak küçük, kanıtlanmış sabit bir tanık taban kümesiyle (örneğin 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37) test yapıldığında, yaklaşık 3,3 × 10²⁴'ün altındaki her tam sayı için deterministik bir sonuç elde edilir — bu da çoğu uygulamanın ihtiyaç duyacağının çok ötesindedir.

Kriptograflar ve yazılım geliştiriciler, RSA veya Diffie-Hellman anahtarları için büyük asal aday sayılar üretirken tam olarak bu tür bir testi kullanır; bilgisayar mühendisliği öğrencileri ise Miller-Rabin'in büyük bir tam sayının asallığını kontrol etmede neden deneme bölmesinden çok daha hızlı ölçeklendiğini gerçek sayılar üzerinde görmek için bu aracı kullanır.