Hvis man læser på nettet om kryptering opdager man, at der er mange der anbefaler at man ikke skriver sit eget computer-program til RSA kryptering.
Man bør, ifølge anbefalingerne, bruge færdige ‘biblioteker’, hvor færdige program-dele importeres og anvendes. Det er sikkert rigtig nok.
En meget stor fordel ved selv at skrive koden til RSA, er dog, at man har 99% styr på hvad der foregår. Det har men ikke ved brug af færdige biblioteker.
Det er dog lidt mere vanskeligt at lave et sikkert RSA kryptosystem, der er en del man skal tage hensyn til. Jeg er ikke krypteringsekspert, men herunder er nogle råd.
Et RSA-system kræver, som nævnt, to meget store primtal p og q.
De to primtal ganges så sammen til \(n = p \cdot q\).
Så skal man finde e og d. Og det er sådan set det!
For at systemet skal være rimelig sikkert, så skal man, for det første, bruge store primtal p og q, samt værdier for e og d med mange cifre.
Ifølge artiklen herunder, så er det ikke nok bare at finde to meget store primtal. De to primtal bør desuden være stærke primtal; se artiklen. Et problem er, som artiklen beskriver, at der ikke er ret mange stærke primtal. Som jeg har læst mig til, så vælger man derfor ikke stærke primtal, men primtal som opfylder krav der gør at de næsten er ‘stærke primtal’.
Jeg kommer måske til at skrive mere om det med sikkerhed. Jeg tror ikke det er helt så vanskeligt som nogen gør det til, og jeg vil gerne afslutte med mit eget RSA kryptosystem som opfører sig præcis som jeg vil have det til.
Det anbefales også at man bruger ‘padding’ og ‘salting’.
Padding betyder nok(?) ikke andet end at man skal særge for at de filer man krypterer har fuld information. Er de for korte skal de udfyldes med anden date.
Salting betyder nok(?) at man, inden kryptering med RSA, skal tilføje tilfældig data, således at strukturen i de oprindelige date fjernes.
Det skal jeg nok læse lidt lidt op på, men det er nærppe ret vanskeligt.
Pointen er, at man, for at alt lave RSA rimelig sikker, skal sørge for at det grundlæggende er i orden. Da princippet i RSA matematisk set er i orden, så er udfordringen at det grundlæggende er i orden, således at an angriber ikke kan angribe pga. svagheder i den grundliggende.
Jeg vender frygtelig tilbage med et RSA krypto-system som prøver at fjerne kendte svagheder, som kan tweekes efter behov, som bliver ubrydeligt for alle ‘fjender’. Jeg skal undgå kendte fælder, jeg skal lade nøglelængden være bestemt af brugeren, og jeg skal fjerne al information om selve kryptosystemet – hvorfor hjælpe en modstander med information om metoden, det er direkte åndsvagt.
Nu skal vi se på hvordan man kan undersøge om et stort tal m er et primtal.
Den hårde og langsomme metode
Hvis tallet m ikke er et primtal, så findes der et helt tal, større end 1 og mindre end m, som går op i m. Det med at finde de tal som går op i et andet tal kaldes for faktorisering. Det kan være meget svært at faktorisere store tal. Det er i bund og grund den kendsgerning der giver sikkerheden i RSA kryptering.
Som eksempel kan vi tage tallet 987654321. Er det et primtal? Ikke let at svare på. Vi kan prøve at undersøge om 2 går op i tallet. Nej, det gør det ikke, for tallet er ikke et lige tal. Går 3 op i tallet? Vi kan jo dividere tallet 987654321 med 3. Det giver 329218107. Dermed er tallet 987654321 ikke et primtal, for 3 går jo op i det
Faktisk er tallet et primtal. Så havde vi prøvet at dividere det store tal 9876543211 med de første mange hele tal; 2, 3, 4, 5, 6, 7, 8, .., så ville ingen af divisionerne gå op.
Skal man derfor undersøge om et stort tal er et primtal, så er det ikke fornuftigt at begynde fra bunden af, og så se om 2 går op i tallet, om 3 går op i tallet, ….
Vi skal se på Fermats primtalstest, og senere Miller-Rabins primtalstest.
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
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.
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.
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
I afsnittet om Fermats primtalstest diskuterer jeg hvordan man kan teste om et stort tal m er et primtal.
Mere præcist; vi så på hvor mange af tallene a = 1,2,3, …, m – 1 som opfylder at
\(a^{m-1} \equiv 1 \textrm{ mod } m \)
Hvis m er et primtal, så skal \(a^{m-1} \equiv 1 \textrm{ mod } m \) for alle værdier af a, fra a = 1, til a = m – 1.
Hvis vi bare har en værdi af a, så \(a^{m-1}\) ikke er lig 1, modulo m, så kan m ikke være et primtal.
Vi så også, at for langt de fleste tal m, som ikke er primtal, så vil de a‘er, hvor \(a^{m-1} \equiv 1 \textrm{ mod } m \), typisk kun udgøre få procent af samtlige a‘er fra a = 1 til a = m -1.
I dette afsnit vil vi ikke se på alle værdier af a, fra a = 1 til a = m – 1. Vi vil kun se på de værdier af a som er primiske med m.
Python-program
Ved at ændre minimalt i python-programmet fra forrige afsnit, så kan jeg, for hver værdi af m, optælle hvor mange af a‘erne der både er primiske med m, og som giver 1, når a opløftes i potensen m – 1. Vi regner naturligvis modulo m.
import math
mmax=1000
for m in range(1,mmax+1):
antal=0
antal_primiske=0
for a in range(1,m):
if math.gcd(a,m)==1:
antal_primiske+=1
if pow(a,m-1,m)==1:
antal+=1
print(m,antal_primiske,antal)
I pakken math, som vi importerer, ligger funktionen gcd, som beregner den største fælles divisor for to tal.
Jeg har brugt antal_primiske til at tælle de a‘er som er primiske med m.
Jeg har brugt antal til at tælle de a‘er som opfylder at \(a^{m-1} \equiv 1 \textrm{ mod } m \). Bemærk at antal kun forøges hvis a både er primiske med m og \(a^{m-1} \equiv 1 \textrm{ mod } m \).
Andet tal er antallet af a‘er, fra a = 1, til a = m -1, der er primiske med m.
Tredie tal er antallet af de tal, der er primiske med m, som også opfylder at \(a^{m-1} \equiv 1 \textrm{ mod } m \).
Række 2: Når m = 2, så er der ét tal der er primisk med m; det er tallet 1. Og tallet 1 opfylder, at \(1^{2-1} \equiv 1 \textrm{ mod } 2 \). Derfor står der i række 2; “2 1 1”
Så det er kun tallet a = 1 der både er primisk med 4 og som opfylder at \(a^{m-1} \equiv 1 \textrm{ mod } m \).
Figur
Jeg har, for alle værdier af m fra m = 1 til m = 105, optalt antal a‘er der er primiske med m, og antal a‘er som både er primiske med m og som opfylder at \(a^{m-1} \equiv 1 \textrm{ mod } m \).
Jag har så divideret antal med antal_primiske, og omregnet til procent.
Figuren viser resultaterne:
De værdier af m hvor procenten er 100 er primtallene. Når m er et primtal, så vil alle værdier af a, fra a = 1 til a = m – 1, både være primiske med m og opfylde at \(a^{m-1} \equiv 1 \textrm{ mod } m \).
Man kan så omvendt spørge; findes der værdier af m, som ikke er primtal, hvor der for alle a‘er, som er primiske med m, også gælder at \(a^{m-1} \equiv 1 \textrm{ mod } m \) ?
Svaret er ‘ja’, der findes sammensatte tal m som opfylder, at der for alle a‘er primiske med m, gælder at \(a^{m-1} \equiv 1 \textrm{ mod } m \).
Disse tal kaldes Carmichael-tal. Det mindste af disse tal er 561. Der er 320 tal fra a = 1 til a = 560 som er primiske med 561. For alle disse 320 værdier af a gælder der at \(a^{560} \equiv 1 \textrm{ mod } 561 \).
Tallet 561 er ikke et primtal; \(561 = 3 \cdot 11 \cdot 17\).
Hvis vi derfor vil teste om et tal m er et primtal, og kun kontrollerer for a‘er der er primiske med m, så kan vi komme ud for værdier af m hvor alle a‘er opfylder ligningen \(a^{m-1} \equiv 1 \textrm{ mod } m \).
For at forstå matematikken bag RSA kryptering, for at forstå matematikken bag Bitcoins, så er det nødvendigt med lidt tal-teori.
I folkeskolen har du mødt de hele tal, de lige tal, de ulige tal, primtallene.
Du ved måske, at lægger man to lige tal sammen, så får man igen et lige tal. Lægger man to ulige tal sammen, så får man et ulige tal.
Måske har du også hørt at ethvert helt positivt helt tal kan skrives som nogle primtal ganget sammen.
Det er alt sammen talteori.
Om talteorien og hjemmesiden
Jeg har været meget i tvivl om hvordan jeg skal forklare om den tal-teori der bruges på denne hjemmeside.
Der er ikke noget lettere end at opskrive en masse definitioner, opskrive nogle sætninger, og mere eller mindre skrive nogle beviser af. Og så snakke lidt om anvendelse. Problemet med den fremgangsmåde er, at læseren ingen fornemmelse har og ingen fornemmelse får for emnet.
Jeg har forsøgt at fortælle om tal-teori på en sådan måde, at læseren får et billede af teorien, hvad det er det handler om, sammenhænge, resultater.
Jeg vil arbejde med de hele tal; læseren er nemlig fortrolig med de hele tal, læseren kan let forstå beregningerne, læseren kan se mønstre i resultaterne.
I begyndelsen ville jeg, for ikke at skræmme læsere væk, helt undgå begreber som ‘grupper’ og ‘restklasser’. Men jo mere jeg får skrevet, jo sværere bliver det at undgå de præcise faglige begrever. Uden de faglige begreber er det svært at forklare kort og præcist.
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
\(a^{11-1}\) modulo 11.
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
\(a^{15-1}\) modulo 15.
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
\(a^{128}\) modulo 129.
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
Antal 1-taller blandt \(a^{m-1}\) modulo m, for a = 1, a = 2, a = 3, …, a = m -1.
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
Antal 1-taller blandt \(a^{m-1}\) modulo m, for a = 1, a = 2, a = 3, …, a = m -1.
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.
Antal a’er så \(a^{m-1} \equiv 1\) modulo m, for m = 1, 2, 3, … , 100
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
Antal a’er så \(a^{m-1} \equiv 1\) modulo m, for m = 1, 2, 3, … , 1000
Til sidst en figur for m = 1, 2, 3, … , 10000:
Antal a’er så \(a^{m-1} \equiv 1\) modulo m, 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 hver værdi af m i intervallet 2 til 100000. procentdel af a’er som opfylder at \(a^{m-1} \equiv 1\) modulo m
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.
En gruppe er en mængde af elementer, og en regneoperation, som opfylder at
1 – Mængden af elementer skal være lukket mht. regneoperationen. 2 – Der skal gælde en parentesregel; a + (b + c) = (a + b) + c 3 – Der skal være et neutralt element. 4 – Alle elementer skal have et inverst element.
Vi har her brugt ‘+’ som symbol for regneoperationen. Når man bruger ‘+’ som regneoperation, så bruger man ofte ‘0’ som symbol for det neutrale element.
Lad os se på \(\mathbb{Z}_n\) når \(n=10\).
Vi vil altså her se på \(\mathbb{Z}_{10}\).
Denne mængde består af de 10 elementer
\(0, 1, 2, 3, 4, 5, 6, 7, 8, 9\)
Den tilhørende regneopeartion er ‘+’. Man adderer altså to elementer, ved at lægge dem sammen som man plejer. Får man en sum som er større end 9, så ‘reguleres ned’ modulo 10:
Jeg har farvet tallet 2 i første kolonne og tallet 3 i første række røde. Disse to tal, lagt sammen, giver 5. Derfor er 5-tallet inde i tabellen også farvet rødt.
Jeg har farvet tallet 6 i første kolonne og tallet 7 i første række blå. Disse to tal, lagt sammen, giver 13. 13 er kongruent med 3 modulo 10. Derfor er 3 tallet inde i tabellen farvet blåt.
Mængde \(\mathbb{Z}_{10}\) med regneoperationen ‘+’ udgør en gruppe. Tallet ‘0’ er det neutrale element.
Betingelsen ‘1 – Mængden af elementer skal være lukket mht. regneoperationen’ er opfyldt, for når vi adderer to tal, og reducerer modulo 10, så får vi igen et element i \(\mathbb{Z}_{10}\).
Betingelsen ‘2 – Der skal gælde en parentesregel; a + (b + c) = (a + b) + c‘ er opfyldt, for parentesreglen gælder for de almindelige tal, så ventres side bliver altis lig højre side, og når vi reducerer modulo n så får vi altså samme resultat.
Betingelsen ‘3 – Der skal være et neutralt element’ er opfyldt; tallet ‘0’ er nelig et neutralt element, for lægges det til ethvert element i \(\mathbb{Z}_{10}\) får vi uændret samme element. Det ses også af tabellen, hvor række 2, med 0 til ventre, bare består af tallene 0, 1, 2, …, 9. Vi ser også at 2. søjle, søjlen med et 0 for oven, også består af tallene 0, 1, 2, …, 9.
Betingelsen ‘4 – Alle elementer skal have et inverst element’ er opfyldt. F.eks. har 7 et inverst element. Lægger man nemlig 3 til 7, så får man 10, der er kongruent med 0 modul 10. Elementet 3 er altså det inverse element til elementer 7. Hvis man ser ned gennem tabellen, så ser man at der er 0’er i alle rækker. Alle elementer i \(\mathbb{Z}_{10}\) har dermed et inverst element.
Nu tænker du nok; Gad vide hvad en gruppe er. Og hvad kan det med grupper bruges til?
Måske tænker du? Skal jeg ikke bare springe det med grupper over, det virker list mystisk, det er nok for svært for mig. Men brug nu 15 minutter på at læse testen, tænk over hvad der står, og så har du styr på hvad en gruppe er.
Det med grupper er egentlig ikke så svært. Det er måske lidt abstrakt, men det er ikke svært. Hvis man arbejder med matematik, så lægger man måske mærke til, at man, i en masse forskellige tilfælde, står over for de samme problemer/udfordringer. Måske lægger man mærke til, at de ting man arbejder med, opfører sig på sammen måde, og at de opgaver man skal løse, kan løses på samme måde, selv om der er tale om helt forskellige ting. Her skal læseren se en masse konkrete eksempler/opgaver for sig, som måske, i første omgang, ikke har noget med hinanden at gøre, men som faktisk kan løses på præcis samme måde. At de kan løses på præcis sammen måde skyldes måske, at det er samme slags problemer, bare i forskellige forklædninger. Matematikeren ser måske dette, og laver så en generel teori der beskriver de forskellige konkrete eksempler, og forklarer hvordan opgaver kan løses. Gruppeteori er noget abstrakt matematik, som kan bruges i en masse konkrete tilfælde.
Måske har jeg hægtet læseren af her, for hvad mener jeg? Hvis du går i gymnasier, så kender du til lineær vækst. Det er noget med y = ax + b. Lineær vækst kan bruges til at beskrive en masse konkrete eksempler. Selve teorien om lineær vækst er en abstrakt teori, der ikke er bundet til eksemplerne. Teorien for lineær vækst kommer fra, at en matematiker, en gang for længe siden, har set en masse fællestræk ved en masse konkrete opgaver. Matematikeren har så lavet en abstraktv teori om ‘ineær vækst’. Den generelle teori om lineær vækst kan så bruges i en masse konkrete eksempler; taletidskort, taxakørsel, …
Eller et mere jordnært eksempel: Når man tager kørekort, så lærer man at køre bil. Man lærer ikke at køre Volvo. Man lærer ikke at køre Opel. Man lærer at køre i den abstrakte størrelse der kaldes for’ bil’. Grunden til at det giver mening, altså det at lære at køre bil, er, at alle biler, mere eller mindre, opfører sig på samme måde. Der er et rat, der er et gear, der er nogle pedaler m.v. Når man har lært at køre ‘bil’, så kan man køre Volvo, så kan man køre Opel, …
Når man har taget kørekort til ‘grupper’, så ved man hvordan man arbejder med grupper, og man ved hvilke regler der gælder for grupper. Når man så møder en konkret gruppe, så kan den generelle teori, som man har lært, bruges til det konkrete tilfælde.
Nok snak. Tilbage til det med grupper.
Vi ved alle hvad der menes med en gruppe mennesker. Men hvad menes der med en gruppe, i matematik?
I matematik er en gruppe ikke anden end en mængde af elementer, og en regneoperation, som opfylder de fire krav:
1 – Mængden af elementer skal være lukket mht. regneoperationen. 2 – Der skal gælde en parentesregel; a + (b + c) = (a + b) + c 3 – Der skal være et neutralt element. 4 – Alle elementer skal have et inverst element.
Lad og sige at vores regneoperation er ‘+’. Kalder vi elementerne for a, b, c, … så kan de fire krav, til det at være en grupper, skrives
1 –Summen a + b af to elementera og b skal også være et element i mængden af elementer. 2 – Der skal gælde at a + (b + c) = (a + b) + c. 3 – Der skal være et nul-element 0 (nul). 4 – For hvert element a skal der findes et andet element b, således at a + b = 0 (og b + a = 0).
I nogle grupper er a + b ikke lig b + a, så derfor står der i punkt 4 at der både skal gælde at a + b = 0 og b + a = 0.
Som huskeregel for de krav, der er til det at være en gruppe, kan man bruge ‘CAN I’.
Bogstavet ‘C’ står for ‘Closed’, dvs. lukket. Bogstavet ‘A’ så for ‘Associativ’, som er navnet på parentesreglen. Bogstavet ‘N’ så for ‘Neutralt element’. Bogstavet ‘I’ står for ‘Inverst element’.
Det lyder måske lidt mystisk, og for folk der er vant til at bruge ‘grupper’ er det nok trivielt, men for os andre er det med grupper en noget mystisk ting, som ikke siger de fleste ret meget. Men prøv at huske på ‘CAN I’, og se se på eksemplerne herunder.
C = Closed = Lukket
A = Associativ regel: a + (b + c) = (a + b) + c
N = Neutral element N
I = Alle elementer har et inverst element, summen af de to lig N.
Eksempel 1
Lad og se på mængden af de hele tal. Som regneoperation tager vi ‘plus’, dvs. ‘+’.
Påstanden er nu, at mængden af hele tal, med regneoperationen ‘plus’, er en gruppe.
1 – Lægger vi to hele tal sammen, så får vi et nyt helt tal. Mængden af hele tal, sammen med ‘plus’, er altså lukket. 2 – For hele tal gælder at a + (b + c) = (a + b) + c. F.eks. er 6 + (4 + 3) = (6 + 4) + 3. Det er derfor man ikke skriver parenteser når man skriver 6 + 4 + 3, for det er lige meget i hvilken rækkefølge man lægger tallene sammen. Hvis rækkefølgen betød noget, så skulle man nemlig indsætte parenteser. 3 – Det neutrale element er 0. Når man lægger tallet 0 til et helt tal a, så gælder jo at a + 0 = a og 0 + a = a . 4 – Alle elementer skal have et inverst element. Elementet 7 har f.eks. det inverse element -7. Det skyldes at 7 + (-7) = 7 – 7 = 0.
Eksempel 2
Lad os nu prøve selv at lave en gruppe. Vi siger at der skal være fire elementer i grupper. Lad os kalde de fire elementer for a, b, c og d.
