Vi vil nu se på selve Miller-Rabin testen.
Vi har tallet n. Vi skal undersøge om dette tal n er et primtal.
Vi skriver tallet n på formen \(2^s \cdot d + 1\).
Vi tager så et tilfældigt test-tal a, positivt, og mindre end n. Dvs. \(0<a<n\).
Vi tester så tallet n ved brug af tallet a. Hvis n passerer testen, dvs. hvis n godkendes for denne værdi af a, så prøver vi med en ny tilfældig værdi for a. Sådan fortsættes f.eks. 10 gange.
Hvis n godkendes for alle de 10 værdier af a, så kan vi med stor sandsynlighed antage, at n er et primtal.
Hvis der bare er en værdi af a hvor n ikke godkendes, så ved vi at n er et sammensat tal.
Nu til testen, der består af to dele:
Hvis \(a^d \equiv_n 1\) så godkendes n for denne værdi af a, og vi tester for en ny værdi af a.
Hvis der ikke gælder at \(a^d \equiv_n 1\) , så skal vi undersøge om \(a^{2 ^ r \cdot d} \equiv_n n-1\) for en eller anden værdi af r, mindre end s.
Det gør vi helt konkret ved at prøve med r = 0, så med r = 1, så med r = 2, o.s.v. helt frem til r = s – 1. Hvis der bare for en værdi af r‘erne gælder at \(a^{2 ^ r \cdot d} \equiv_n n-1\), så passerer n testen. Hvis der ikke er nogle værdier af r, så \(a^{2 ^ r \cdot d} \equiv_n n-1\), så ved vi at n er et sammensat tal.
Python-programmet
Jeg har lavet et Python-program som tester om et helt tal n er et sammensat tal, eller, med stor sandsynlighed er et primtal.
Jeg genbruger Python-programmet som skriver n som \(2^s \cdot d + 1\). Dette er den første del i Python-programmet.
Herefter kører jeg testen som forklaret herover:
import random
n = 1001 # Tallet der skal testes
# Skriv tallet n på den specielle form, dvs. bestem s og d
s = 0
d = n-1
while True:
if d % 2 == 0:
d = d // 2
s=s+1
else:
break
i_max = 10 # Antal a'værdier der testes med
sammensat = False
for i in range(1,i_max):
a=random.randint(1,n-1) # Tilfældig værdi af a
if pow(a,d,n)==1:
continue # Næste i og nyt a
r=0 # Undersøger for r=0 til r=s-1
while(True):
if pow(a,pow(2,r)*d,n)==n-1:
break # Afbryd while-løkken
else:
r = r+1
if r == s+1: # Ingen værdi af r kan bruges
sammensat=True # Tallet er sammensat?
break # Hvis 'ja', afbryd while-løkken
if sammensat==True: # Er tallet sammensat?
break # Hvis 'ja', afbryd i-løkken
if sammensat==True:
print('Tallet',n,'er sammensat')
else:
print('Tallet',n,'er et primtal')
Eksempler på output:
Kontrol med Maple:
En pointe er, at selv om det lyder avanceret med en Miller-Rabin test, så er selve testen ret simpel at gå igennem, Python-programmet er ikke ret langt, det er ikke så kompliceret, dog skal der udføres en række tests undervejs, og resultaterne af disse tests skal der tages hånd om.
Miller-Rabin test som funktion i Python
Det kan være smart at have Miller-Rabins primtalstest som en funktion i Python. Så kan programmet let kaldes, igen og igen. Her er det uden kommentarer:
import random
def ErSammensat(n):
s = 0
d = n-1
while True:
if d % 2 == 0:
d = d // 2
s=s+1
else:
break
i_max = 10
sammensat = False
for i in range(1,i_max):
a=random.randint(1,n-1)
if pow(a,d,n)==1:
continue
r=0
while(True):
if pow(a,pow(2,r)*d,n)==n-1:
break
else:
r = r+1
if r == s+1:
sammensat=True
break
if sammensat==True:
break
return sammensat
for k in range(2,100):
if ErSammensat(k)==True:
print(k,'er et sammensat tal')
else:
print(k,'er et primtal')
De sidste fem linier undersøger om tallene 2, 3, 4, …, 100 er primtal. En del af outputtet er:
Miller-Rabins test afslører, som nævnt, om et tal er et sammesat tal, eller om et tal, med stor sandsynlighed, er et primtal.
Man kunne så, for faste værdier af n, teste n for alle værdier af a fra a = 1 til a = n – 1. Resultatet ville sige noget om hvor sikker Miller-Rabin’s test er.
Man kunne også, for faste værdier af n, finde de værdier af a hvor testen giver et forkert resultat; der må være nogle værdier af a hvor testen siger ‘primtal’ selv om tallet n er et sammesat tal.
For at teste om et givet tal n er et primtal, så tester vi med forskellige værdier for a. Værdierne for a skal vælges tilfældigt blandt tallene 1, 2, …, n -1. Det med at vælge tilfældige tal er en kunst i sig selv. Mange indbyggede tilfældige-tals-generatorer, vælger ikke tilfældigt nok, så man bør bruge lidt tid på at find og anvende gode tilfældige-tals-generatorer. Der er sikkert en i et Python bibliotek der kan anvendes.