Miller-Rabin-primalitetstest kalkylator

Om denna kalkylator

Miller–Rabin-testet kontrollerar primalitet genom att skriva n − 1 som 2ˢ·d med d udda och sedan testa om en vittnesbas a uppfyller aᵈ ≡ 1 (mod n) eller a^(2ʳ·d) ≡ −1 (mod n) för något r < s. Ett enda vittne ger bara ett probabilistiskt resultat, men genom att testa mot en liten, bevisad uppsättning fasta vittnesbaser (till exempel 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37) blir testet deterministiskt för varje heltal under ungefär 3,18 × 10²³ — långt mer än de flesta tillämpningar någonsin behöver.

Kryptografer och mjukvaruutvecklare använder exakt den här sortens test när de genererar stora primtalskandidater för RSA- eller Diffie–Hellman-nycklar, och datavetenskapsstudenter använder det för att se, på riktiga tal, varför Miller–Rabin skalar så mycket bättre än provdivision för att kontrollera om ett stort heltal är ett primtal.