Vi har set på Fermats primtalstest. Den er anvendelig, men en bedre test er Miller-Rabins primtalstest. Miller-Rabins primtalstest skulle være meget anvendt, så lad os se på den her.
Vi har et stort tal n. Vi skal undersøge om tallet n er et primtal.
Inden vi udfører testen, så skal tallet n, der antages at være ulige, skrives på formen
\(n = 2^s \cdot d + 1\)
Det med at tallet n antages at være ulige er helt ok, det eneste primtal der er et lige tal er jo tallet 2.
Lad os se på tallet n = 201. Vi trækker 1 fra, og får tallet 200.
\(201 = 200 + 1\)
Nu dividerer vi tallet 200 med 2, og se hvad der sker:
\(200/2 = 100\)
Divisionen gik op. Vi ved nu at 2 går op i n – 1, og vi har
\(201 = 2 \cdot 100 + 1\)
Vi dividerer så de 100 med 2, og ser hvad der sker:
\(100/2 = 50\)
Divisionen gik op. Vi har nu at
\(201 = 2^2 \cdot 50 + 1\)
Vi dividerer så de 50 med 2, og ser hvad der sker:
\(50/2 = 25\)
Divisionen gik igen op. Vi har nu at
\(201 = 2^3 \cdot 25 + 1\)
Da 25 er et ulige tal, kan 25 ikke divideres med 2.
Sammenligner vi de to udtryk
\(n = 2^s \cdot d + 1\) \(201 = 2^3 \cdot 25 + 1\)
så ser vi at s = 3 og d = 25.
Vi har nu fået skrevet tallet n på formen \(2^s \cdot d + 1\)
Python-program
Jeg har lavet et lille Python-program der udfører beregningerne for os.
Vi har tallet n, og skal undersøge om det er et primtal.
Vi trækker 1 fra tallet n. Resultatet kalder vi for d:
\(d = n-1 \)
Vi sætter s til 0. Variablen s tæller hvor mange gange 2 gå op i tallet d.
I hvert trin, så undersøges om 2 gå op i d. Hvis 2 går op i d, så forøges s med 1, og d divideres med 2. Præcis samme fremgangsmåde som i eksemplet herover.
Programmet er her:
n=201
d=n-1
s=0
while True:
if d % 2 == 0: # Går 2 op i d ?
d = d // 2 # Hvis 'ja', så divideres d med 2
s=s+1 # og s forøges med 1
else:
break # Hvis 2 ikke gik op i d, så er vi færdige
print('n =',n)
print('2^s*d+1 = 2^',s,'',d,'+1 = ',pow(2,s)*d+1,sep='')
Output når n = 201
n = 201 2^s*d+1 = 2^3*25+1 = 201
Output når n = 987654321
n = 987654321 2^s*d+1 = 2^4*61728395+1 = 987654321