Fermats primtalstest

Selv om det kan være meget vanskeligt at faktorisere et stort tal m, så kan man alligevel godt afgøre om et givet tal m er et primtal.

Det lyser måske mærkeligt. Men vi kan jo også let afgøre om en dør er låst, uden at låse den op. Vi behøver ikke engang have en nøgle til låsen, det er bare at tage i håndtaget, så kan vi se om den er låst.

Der er forskellige primtalstests. Vi er allerede stødt på en metode; vi kan nemlig bruge Fermats lille sætning: Er p et primtal, og er a er helt tal som p ikke går op i, så vil

 \( a^{p-1} \equiv_p 1 \)

Her har jeg skrevet \(\equiv_p\) fordi vi regner modulo p.

Er a derfor et helt tal, mindre end primtallet p, så skal \(a^{p-1}\) være kongruent med 1, når vi regner modulo p. Det er her primtalstesten kommer ind i billedet. Hvis \(a^{p-1}\) nemlig ikke er kongruent med 1, modulo p, så er p ikke et primtal!

Vi ved at tallet p = 11 er et primtal. Vi kan let beregne \(1^{p-1}\), \(2^{p-1}\), \(3^{p-1}\), …, \(10^{p-1}\) modulo p:

a	1	2	3	4	5	6	7	8	9	10
\(a^{10}\)	1	1	1	1	1	1	1	1	1	1

Da tallet 11 er et primtal, så får vi lutter 1-taller.

Vi ved også at tallet 15 ikke er et primtal. Vi kan tage hvert af de hele tal 1, 2, 3, …, 14, og opløfte dem i 14. potens. Hvis tallet 15 var et primtal, så skulle alle 14. potenser af tallene 1, 2, 3, …, 14 give 1, modulo 15:

a	1	2	3	4	5	6	7	8	9	10	11	12	13	14
\(a^{10}\)	1	4	9	1	10	6	4	4	6	10	1	9	4	1

Vi ser, at vi kun sjældent for et 1’tal, når vi opløfter hvert af tallene 1, 2, 3, …, 14 i 14. potens, og regner modulo 15. Der er dog enkelte 1-taller.

Når vi skal undersøge om et stort tal m er et primtal, så kan vi altså opløfte forskellige hele tal a, der er mindre end m, i m-1’te potens. Hvis bare en af disse beregninger givet et tal som ikke er er kongruent med 1, modulo m, så er m ikke et primtal.

Lad og se på tallet 129. Jeg ved ikke om det er et primtal. Lad og vælge forskellige hele tal a, der er mindre end 129, og opløfte dem i den 128. potens. Lad os begynde med de små hele tal:

a	1	2	3	4	5	6
\(a^{128}\)	1	4	9	16	25	36

Vi ser ret hurtigt at vi ikke kun får 1-taller, når vi regner modulo 129. Dermed er tallet 129 ikke et primtal. Faktisk er \(129 = 3 \cdot 43\), så 129 er altså et sammensat tal.

Vi kan lave lidt statistik over, hvor mange 1-taller der kommer, når vi opløfter alle tallene 1, 2, 3, …, m-1 til den m-1’te potens. Lad os se på de første ulige tal, større end 100:

m	101	103	105	107	109	111	113	115	117
Antal 1-taller	100	102	16	106	108	4	112	4	8

Vi ser, at enten får vi kun få 1-taller, ellers også får vi ikke andet end 1-taller (når m er et primtal).

Vi kan prøve med nogle lidt større værdier for m:

m	1001	1003	1005	1007	1009	1011	1013	1015	1017
Antal 1-taller	80	4	16	4	1008	4	1012	24	16

For m = 1001 finder vi altså 80 et-taller blandt tallene \(a^{1000}\) modulo 1001. Hvis vi derfor, for tallet m = 1001, prøver med 10 tilfældige tal, så kan vi godt ramme ind i nogle af dem der, når de opløftes i potensen 1000, giver 1 modiulo 1001. Men 80 ud af 1001 er trods alt kun 8%. Det er nogenlunde samme sandsynlighed som det at få f.eks. en 12’er med en 12-sidet terning. Det kan man godt få en gang, måske to gange i træk, men næppe 10 gange i træk.

Konklusionen er, at man kan bruge Fermats lille sætning til at undersøge om et givet tal m er et primtal. Det er ikke en vandtæt metode, man kan komme ud for at de første mange tal man prøver med alle giver et et-tal, men det er trods alt meget lidt sandsynligt.

Der findes bedre metoder, der med større sikkerhed kan afgøre om et helt tal er et primtal.

Der findes også en metode som med 100% sikkerhed kan afgøre om et helt tal er et primtal.

Python-program og grafer

Hvis m er et stort tal, så er det naturligvis ret tidskrævende, hvis man manuelt vil undersøge, hvor mange af potenserne \(a^{m-1}\) der giver 1.

Jeg har derfor lavet et lille Python-program som løser det for os.

mmax=100
 for m in range(1,mmax+1):
     antal=0
     for a in range(1,m):
         if pow(a,m-1,m)==1:
             antal+=1
     print(m,antal)

I første linie sættes mmax til 100. Derefter er der en løkke; m sættes først til 1, så til 2, så til 3, så til 4, … og til sidst til mmax.

For hver værdie af m gennemløber a en løkke, med a = 1, a = 2, a = 3, … a = m-1.

For hver værdi af m optælles så antallet af gange \(a^{m-1} \equiv 1\) modulo m. Løkken med a sætter først a til 1. Så undersøges om \(a^{m-1} \equiv 1\) modulo m. Hvis \(a^{m-1} \equiv 1\) så forøges antal med 1, eller lades antal være uændret. Herefter sættes a til 2. Så undersøges om \(a^{m-1} \equiv 1\) modulo m. Hvis \(a^{m-1} \equiv 1\) så forøges antal med 1, eller lades antal være uændret. Sådan fortsættes indtil a = m-1.

Begyndelsen af outputtet ses her:

1 0
2 1
3 2
4 1
5 4
6 1
7 6
8 1
9 2

For m = 1 er der ingen tal, som opløftet til 0’te potens, giver 1.

For m = 2 er der ét tal, som omløftet til 1’te potens, giver 1, når vi regner modulo 2.
\(0^1 \equiv 0\) og \(1^1 \equiv 1\).

For m = 3 er der to tal, som omløftet til 2’te potens, giver 1, når vi regner modulo 3.
\(0^2 \equiv 0\) , \(1^2 \equiv 1\), \(2^2 = 4 \equiv 1\).

For m = 4 er der ét tal, som omløftet til 3’te potens, giver 1, når vi regner modulo 4.
\(0^3 \equiv 0\) , \(1^3 \equiv 1\), \(2^3 = 8 \equiv 0\).

For m = 5 er der fire tal, som omløftet til 4’te potens, giver 1, når vi regner modulo 5.
\(0^4 \equiv 0\) , \(1^4 \equiv 1\), \(2^4 = 16 \equiv 1\) , \(3^4 = 81 \equiv 1\).

Jeg har så taget værdierne (outputtet), indsæt det i et regneark, og tegnet en graf:

Nedenstående figur viser sammenhængen mellem værdier af m, for m = 1, 2, 3, …, 100, og antal gange \(a^{m-1} \equiv 1\) modulo m.

Alle prikkerne på den skrå linie kommer fra primtallene. Er m = 19, der er et primtal, så vil de 18 tal; 1, 2, 3, 4, …, 18 alle give 1, når der opløftes i potensen 19, og man regner modulo 19.

Når m således er et primtal, så vil der for alle tal a, der er mindre end m, og større end 0, gælde at \(a^{m-1} \equiv 1\) modulo m.

For m = 91, der ikke er et primtal, er der ikke mindre end 36 værdier for a, som giver 1, når de opløftes i potensen 90, når vi regner modulo 91. Det er 40% af de mulige a-værdier.

Hvis vi laver en tilsvarende figur for m = 1, 2, 3, … , 1000 får vi

Til sidst en figur for m = 1, 2, 3, … , 10000:

For m = 6601 er der 5280 værdier for a, som, når de opløftes i potensen 6600, giver 1, når vi regner modulo 6601. Det svarer til 80%.

For m = 8911 er der ikke mindre end 7128 værdier for a, som, når de opløftes i potensen 8910, giver 1, når vi regner modulo 8911. Det svarer også til 80%.

Antag at vi vil undersøge om tallet m er et primtal.

Vi vælger så f.eks. 10 tilfgældige tal a blandt tallene 1, 2, 3, …, m-1.

Vi undersøger, for hvert af disse, om \(a^{m-1} \equiv 1\) modulo m.

Hvis m er et primtal, så vil der for alle de 10 værdier af a gælde at \(a^{m-1} \equiv 1\) modulo m.

Hvis m ikke er et primtal, så vil der for hver af de 10 tal gælde, at sandsynligheden for, at \(a^{m-1} \equiv 1\) modulo m, normal er langt mindre end \(\frac{1}{3}\).

Sandsynligheden for, at der for alle de 10 tal gælder, at \(a^{m-1} \equiv 1\) modulo m , er dermed langt mindre end \(\left( \frac{1}{3} \right) ^{10} = 0.000017 = 0.0017\)%.

Hvis m ikke er et primtal, så er det altså ret usandsynligt at \(a^{m-1} \equiv 1\) modulo m for alle 10 forskellige værdier af a.

Lad os til sidst se på, hvor mange procent af tallene mellem 1 og m-1, for m = 1, 2, 3, …, 100000, som opfylder at \(a^{m-1} \equiv 1\) modulo m.

Jeg har optalt resultaterne, og omreget til procent. Da 0 opløftet i en potens aldrig kan give 1, så ser jeg bort fra a = 0.

Vi ved, at når m er et primtal, så vil alle a‘er, når de opløftes i potensen m-1, give 1, regnet modulo m. Så procentdelen, for alle primtal, er 100%.

Men omvendt; hvis nu procentdelen for et helt tal m er 100%, kan vi så være sikker på at m er et primtal? Dét kan der med garanti siges noget klogt om, men pointen er her, at Fermats primtalstest reelt kun kan bruges til at afvise at et tal er et primtal; får man nemlig ikke resultatet 1 når man beregner \(a^{m-1}\) mod m, for bare en værdi af a, så er m ikke et primtal

Figuren viser resultaterne:

For m = 46657 vil 88.9% af a‘erne, når de opløftes i potensen 56656, give 1, når vi regner modulo 46657.