199 pages
Danish
Obtenez un accès à la bibliothèque pour le consulter en ligne
En savoir plus

Tal og Palynomier

-

Obtenez un accès à la bibliothèque pour le consulter en ligne
En savoir plus
199 pages
Danish

Description

Som erkendelse har talteori og algebra en interesse i sig selv, og resultaterne er helt fundamentale for moderne kryptografi og datasikkerhed. I Tal og polynomier introduceres centrale talteoretiske og algebraiske begreber, resultater og metoder. De perspektiveres og placeres i savel historisk som aktuel sammenhAeng. Bogen rummer blandt andet en matematisk velfunderet behandling af moderne krypterings- og kodningsmetoder, principperne bag digital signatur og deling af hemmeligheder. Ved studiet af teorien og arbejdet med bogens mange opgaver gores lAeseren fortrolig ikke bare med talteori og grundlAeggende algebra specifikt, men ogsa med abstrakt matematisk tankegang i det hele taget og med fagets stringente argumentation. Bogen er malrettet undervisningen pa forste semester i matematik ved universitetet.

Sujets

Informations

Publié par
Date de parution 01 août 2018
Nombre de lectures 0
EAN13 9788771847147
Langue Danish
Poids de l'ouvrage 15 Mo

Informations légales : prix de location à la page 0,0065€. Cette information est donnée uniquement à titre indicatif conformément à la législation en vigueur.

Exrait

TAL OG POLYNOMIER
Som erkendelse har talteori og algebra en inte­ JO H AN P. H AN S E N
resse i sig selv, og resultaterne er helt fundamen­
tale for moderne kryptograf og datasikkerhed.
  TAL OG
I Tal og polynomier introduceres centrale talte­
oretiske og algebraiske begreber, resultater og POLYNOMIER metoder. De perspektiveres og placeres i såvel
historisk som aktuel sammenhæng. Bogen rum­ begreber, metoder, resultater,
mer blandt andet en matematisk velfunderet
kodning og kryptografbehandling af moderne krypterings­ og kodnings­
metoder, principperne bag digital signatur og
deling af hemmeligheder.
 
Ved studiet af teorien og arbejdet med bogens
mange opgaver gøres læseren fortrolig ikke bare
med talteori og grundlæggende algebra specifkt,
men også med abstrakt matematisk tankegang i
det hele taget og med fagets stringente argumen­
tation.
 
Bogen er målrettet undervisningen på første
semester i matematik ved universitetet.
aAarhus Universitetsforlagtalogpolynomiertalogpolynomier
Begreber, metoder, resultater, kodning
og kryptografi
johanp.hansen
Aarhus UniversitetsforlagTal og polynomier – Begreber, metoder, resultater, kodning og kryptografi
© Johan P. Hansen og Aarhus Universitetsforlag 2018
Tilrettelægning og sats: Lars Madsen
Omslag: Jørgen Sparre
Forlagsredaktion: Henrik Jensen
Sat med Kp-Fonts
eISBN 978 87 7184 714 7
Aarhus Universitetsforlag
Finlandsgade 29
8200 Aarhus N
www.unipress.dk
Kopiering fra denne bog må kun finde sted på institutioner, der har indgået aftale med
Copydan, og kun inden for de i aftalen nævnte rammer.indhold
Forord v
I Tal og modulo-regning
1 Indledning 3
Opgaver til Kapitel 1 . . . . . . . . . . . . . . . . . . . . . . . . . 5
2 De naturlige tal – Induktion 7
2.1 Dedekind–Peanos aksiomer og induktion . . . . . . . . . . . . . . 7
Opgaver til Kapitel 2 . . . . . . . . . . . . . . . . . . . . . . . . . 15
3 Divisibilitet og største fælles divisor 19
3.1 Største fælles divisor – Euklids algoritme . . . . . . . . . . . . . . 19
3.2 Mindste fælles multiplum . . . . . . . . . . . . . . . . . . . . . . 23
Opgaver til Kapitel 3 . . . . . . . . . . . . . . . . . . . . . . . . . 24
4 Primtal og heltalsdeling 29
4.1 Primtalsfaktorisering . . . . . . . . . . . . . . . . . . . . . . . . . 30
Opgaver til Kapitel 4 . . . . . . . . . . . . . . . . . . . . . . . . . 33
5 Uendelig mange primtal – tre beviser 37
5.1 Euklids bevis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
5.2 Bevis baseret på Fermat-tal . . . . . . . . . . . . . . . . . . . . . . 37
5.3 Eulers bevis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
6 Optælling af primtal – primtalssætningen 41
6.1 Chebyshevs sætning . . . . . . . . . . . . . . . . . . . . . . . . . . 42
6.2 En nedre grænse for antallet af primtal op til en vis størrelse . . 43
7 Landaus primtalsproblemer 45
7.1 Goldbachs formodning . . . . . . . . . . . . . . . . . . . . . . . . 45
7.2 Formodningen om primtalstvillinger . . . . . . . . . . . . . . . . 46
7.3 Hardy-Littlewood-formodningen . . . . . . . . . . . . . . . . . . 46
27.4 (N + 1)-formodningen . . . . . . . . . . . . . . . . . . . . . . . . 47
7.5 Legendres f . . . . . . . . . . . . . . . . . . . . . . . . 47
8 Mersenne-primtal – de største kendte primtal 49
8.1tal og perfekte tal . . . . . . . . . . . . . . . . . . 49
iIndhold
9 Kongruenser og potenser 51
9.1 Kongruensklasser og modulær regning . . . . . . . . . . . . . . . 51
9.2 Fermats lille sætning . . . . . . . . . . . . . . . . . . . . . . . . . 58
9.3 Eulers sætning og roduddragning modulom . . . . . . . . . . . . 59
Opgaver til Kapitel 9 . . . . . . . . . . . . . . . . . . . . . . . . . 64
10 Primtalstest 67
10.1 Rabin–Millers probabilistiske primtalstest . . . . . . . . . . . . . 67
10.2 Konstruktion af store (sandsynlige) primtal . . . . . . . . . . . . 69
Opgaver til Kapitel 10 . . . . . . . . . . . . . . . . . . . . . . . . . 70
11 Relationer 71
11.1 Ækvivalensrelationer . . . . . . . . . . . . . . . . . . . . . . . . . 71
Opgaver til Kapitel 11 . . . . . . . . . . . . . . . . . . . . . . . . . 75
II Ringe – Polynomiumsringe – Kvotientringe
12 Ringe – faktorisering 79
12.1 Faktorisering af primtal iZ[i] og Diofantiske ligninger . . . . . . 81
Opgaver til Kapitel 12 . . . . . . . . . . . . . . . . . . . . . . . . . 82
13 Polynomier 87
13.1 Polynomiumsringe . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
13.2 Faktorisering af et polynomium iK[X] –K et legeme . . . . . . . 88
13.3 Polynomiers division . . . . . . . . . . . . . . . . . . . . . . . . . 89
13.4 Rødder i et polynomium med koefficienter i et legemeK . . . . . 91
13.5 Interpolation med polynomier . . . . . . . . . . . . . . . . . . . . 92
13.6 Euklids algoritme for polynomier . . . . . . . . . . . . . . . . . . 93
13.7 Bezouts identitet for pol . . . . . . . . . . . . . . . . . . . 94
13.8 Entydig faktorisering iK[X] –K et legeme . . . . . . . . . . . . . 96
13.9 Polynomier med koefficienter iZ og iQ . . . . . . . . . . . . . . 97
13.10 Pol med koefficienter iR og iC . . . . . . . . . . . . . . . 101
Opgaver til Kapitel 13 . . . . . . . . . . . . . . . . . . . . . . . . . 107
14 Kongruensringe og legemer 111
14.1 Kongruensklasser og modulær regning iK[X] . . . . . . . . . . . 111
Opgaver til Kapitel 14 . . . . . . . . . . . . . . . . . . . . . . . . . 117
15 Primitivt element iZ – diskret logaritme 119p
15.1t . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
15.2 Det diskrete logaritmeproblem . . . . . . . . . . . . . . . . . . . . 121
15.3 Diskret logaritme med Pollards-metode . . . . . . . . . . . . . 121
Opgaver til Kapitel 15 . . . . . . . . . . . . . . . . . . . . . . . . . 125
iiIndhold
III Kryptografi og Kodning: RSA, ElGamal, Shamir
Secret Sharing, Reed–Solomon-fejlkorrektion
16 Hemmelig kommunikation og digital underskrift 129
16.1 Offentlig-nøgle-kryptosystemet RSA . . . . . . . . . . . . . . . . 130
16.2 ElGamal-offentlig-nøgle-kryptosystem . . . . . . . . . . . . . . . 131
Opgaver til Kapitel 16 . . . . . . . . . . . . . . . . . . . . . . . . . 132
17 Shamir Secret Sharing 133
Opgaver til Kapitel 17 . . . . . . . . . . . . . . . . . . . . . . . . . 136
18 Reed–Solomon-koder 137
18.1 Introduktion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137
18.2 Lineære koder, Hamming-afstand . . . . . . . . . . . . . . . . . . 138
18.3 Konstruktion af Reed–Solomon-koder . . . . . . . . . . . . . . . . 139
18.4 Afkodning af . . . . . . . . . . . . . . . . . 140
Opgaver til Kapitel 18 . . . . . . . . . . . . . . . . . . . . . . . . . 145
Appendikser
A COCALC–SAGE 149
A.1 Vedr. Divisibilitet og største fælles divisor, jf. Kapitel 3 . . . . . . 149
A.2 Vedr. Primtal, faktorisering og optælling af primtal, jf. Kapitel 4
og Kapitel 6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150
A.3 Vedr. Kongruenser og potenser, jf. Kapitel 9 . . . . . . . . . . . . 151
A.4 Primtalstest, jf. Kapitel 10 . . . . . . . . . . . . . . . . . . . . . . 152
A.5 Vedr. Polynomier, jf. Kapitel 13 . . . . . . . . . . . . . . . . . . . 153
A.6 Vedr. Kongruensringe og legemer, jf. Kapitel 14 . . . . . . . . . . 154
A.7 Vedr. Primitivt element iZ – diskret logaritme, jf. Kapitel 15 . . 156p
A.8 Vedr. Reed–Solomon-koder, jf. Kapitel 18 . . . . . . . . . . . . . . 156
B Gentagen kvadrering 159
C Ligningssystemer 161
Opgaver til Appendiks C . . . . . . . . . . . . . . . . . . . . . . . 173
Navne 177
Litteratur 181
Indeks 185
iiiforord
Denne bog sigter mod
– at give læseren kendskab til og forståelse af vigtige egenskaber og
konstruktioner ved tal og polynomier,
– derigennem at gøre læseren fortrolig med abstrakt matematisk tankegang og
stringente argumenter,
– præsentere autentiske anvendelser inden for kodning og kryptering af den
etablerede teori og de opnåede resultater:
• RSA-kryptosystemet, der beror på primtalsfaktorisering
• ElGamal, der beror på det diskrete logaritmeproblem i endelige legemer
• Shamir Secret Sharing, der bygger på rod-antal i polynomier
• Reed–Solomon-fejlkorrigerende koder, der også bygger på rod-antal i
polynomier
– igennem eksempler at præsentere de abstrakte konstruktioner og beregninger
ig det symbolske matematikprogram COCALC–SAGE.
Ideen om det matematiske bevis og matematiks logiske og strukturerede
opbygning kan føres tilbage til det antikke Grækenland. Stringent omgang med og
dannelse af grundlæggende matematiske begreber og elementer samt håndtering
og produktion af holdbare ræsonnementer i abstrakte sammenhænge er stadig
uomgængelige kompetencer, som den matematikstuderende skal tilegne sig senest
ved universitetsstudiets start.
Nærværende bog omfatter en sammen- og omskrivning af en del af det i årene
2003–2017 anvendte undervisningsmateriale i kurset Perspektiver i matematikken,
der siden 2017 er et semesterkursus på 10 ECTS.
Lidt om notation: I denne bog anvendes som afslutning af beviser, mens
markerer afslutningen på bemærkninger samt eksempler.
E-mail og hjemmeside
Enhver bog kan forbedres, og jeg modtager meget gerne forslag hertil og
kommentarer i øvrigt på e-mailadressen
matjph@math.au.dk
vForord
Taksigelser
Lars Madsen takkes for det store arbejde med layoutet samt meget konstruktive
kommentarer til det matematiske indhold og præsentationen.
August 2018
Johan P. Hansen
viDel I
Tal og modulo-regning�










indledning1
Tælletallene, som vi skriver 1;2;3;::: og kalder de naturlige tal, menes at være
(op)fundet af sumererne i den sydlige del af Mesopotamien, landet mellem floderne
Eufrat og Tigris i det nuværende Irak, og kort før 2000 f.Kr. kom de med historiens
første kendte positions-talsystem.
De ældste skriftlige kilder med tal er lertavler, der er indprægede med
kileformede skrifttegn – såkaldt kileskrift. O. Neugebauer og hans medarbejdere
afslørede i 1935/37 igennem tydning af et stort antal lertavler, fundet ved byen
Babylon, repræsentationen af tælletallene (Neugebauer, 1973).
De fandt, at tallene fremstilledes ved hjælp af skrifttegnet for tallet 1 og
skrifttegnet for 10 i et seksagesimalt positionssystem, hvor cifrene dannedes ud
fra tegnene og , således at 2599801 skrives:
3 2 1 0(10 + 1 + 1) 60 + (1 + 1) 60 + 10 60 + 1 60 :
YBC 7289 fra Yales babylonske samling er en af de bedst kendte lertavler.
Tavlen menes at være fra den første tredjedel af det andet årtusinde f.Kr. og
viser et kvadrat med dets diagonaler og nogle kileskriftstegn, se Figur 1.1. På
Figur 1.2 læses skrifttegnene i den øverste række til 1 24 51 10 i det seksagesimale
Figur 1.1: Babylonsk lertavle YBC
7289 (Yale) fra den første tredjedel
af det andet årtusinde f.Kr. med
repræsentation af diagonalen i et
kvadrat. Skriften og figuren giver rigtigp
tolket en god værdi for 2.
3�














1. Indledning
1 1 1talsystem, som tolkes til 1+24 +51 +10 = 1;4142129::: – en temmelig2 360 60 60p
nøjagtig værdi for 2, den rigtige værdi er 1;4142135::: I Fowler og Robson (1998)
uddybes, hvordan babylonierne faktisk bestemte kvadratrødder.
Figur 1.2: Optegning og
kommen1 24 51 10
tering af YBC 7289 fra Figur 1.1. Se.
Aaboe (1964) for mere information.
42 25 35
Talbegrebet ligger før sproget, og samtlige store verdenskulturer har haft
talbegrebet under en eller anden form. I Renæssancen (14. til 17. århundrede)
opsamledes og konsolideredes verdens viden til den nu herskende viden; men det
var først mod slutningen af 1800-tallet, at man fuldt ud forstod talbegrebet og
udmøntede det i Peanos aksiomer, som behandles i Kapitel 2.
Hvor den mesopotamiske kultur fokuserede sin matematik på at udvirke
løsninger til problemer, mere end på argumenter eller beviser, var den græske
matematiks særkende det matematiske bevis’ centrale rolle. Det matematiske
bevis – og her især det indirekte bevis (modstridsbeviset) – gjorde det muligt
at udtale og begribe, at en bestemt opgave ikke lod sig løse, hvilket er et andet
abstraktionsniveau end at eftersøge en løsning, jf. Sørensen (2011).
Primtallene tilhører den eksklusive verden af intellektuelle begreber, der på
den ene side har en simpel og elegant beskrivelse og på den anden side fører til
ekstrem kompleksitet i detaljen. Et barn kan forstå definitionen af et primtal;
men intet menneske har et komplet billede af deres teori og de sammenhænge, de
indgår i.
Vi vil ved hjælp af matematisk bevisførelse forstå dele af de naturlige tals
multiplikative struktur og primtallenes centrale rolle. Deling eller faktorisering af
tal er her det overordnede tema, eksempelvis kan tallet 60 deles eller faktoriseres
i 60 = 4 15, som videre deles til:
60 = 2 2 3 5;
hvorefter yderligere faktorisering er umulig. Dette simple eksempel giver
anledning til en række klassiske og forskningsaktuelle spørgsmål, hvis besvarelse også
har stor praktisk betydning:
• Kan ethvert tal i lighed med 60 faktoriseres i et produkt af primtal – tal, der
ikke kan deles yderligere? Kan en faktorisering kun foretages på én måde?
4
30Opgaver
JA – Aritmetikkens fundamentalsætning, der behandles i afsnit 4.1, præciserer
og besvarer begge spørgsmål positivt.
• Er det hurtigt at faktorisere et tal i sine primfaktorer?
NÆPPE – men der er ikke et definitivt svar. Temaet, der behandles i afsnit 4.1,
er helt centralt i moderne kryptografi, jf. afsnit 16.1.
• Er der uendelig mange primtal, tal, der i lighed med 2, 3 og 5 er udelelige?
JA – bevises i Kapitel 5 på tre forskellige måder.
• Kan man anslå, hvad chancen er for, at et tilfældigt valgt tal er et primtal?
JA – primtalssætningen, der behandles i Kapitel 6, giver estimater. I nærheden
afn = 1000 er cirka hvert syvende tal et primtal, og i nærheden af 10000000000
er omkring 1 ud af 23 tal et primtal.
• Kan man hurtigt afgøre, om et konkret tal er et primtal eller i det mindste med
meget stor sandsynlighed afgøre at det er et primtal?
JA – i afsnit 10.1 beskrives en hurtig gennemførlig test, der fejler mindre end 1
ud af 1000000000000000000 gange, hvis den erklærer et givet tal for at være et
primtal.
• Ved man alt om primtal?
NEJ – i Kapitel 7 behandles fire klassiske og stadig uløste problemer.
• Kan primtalsfaktorisering anvendes i praksis?
JA – det er kernen bag sikkerheden i offentlig-nøgle-kryptosystemet RSA, jf.
afsnit 16.1.
Hensigten er at uddybe disse spørgsmål og give præcise svar, så vidt det er muligt,
belyst såvel igennem den klassiske viden som ved aktuel matematisk forskning.
Et yderligere sigte er anvendelsen i moderne kryptografi.
Opgaver
1.1. Forsøg at tolke de øvrige kileskriftsrækker på YBC 7289, jf. Figur 1.2, og sæt
dem ind i en sammenhæng med den geometriske figur på lertavlen.
5denaturligetal–induktion2
I indledningen blev det nævnt, at det først var hen mod slutningen af 1800-tallet,
at man helt forstod talbegrebet. I 1888–1889 formulerede Giuseppe Peano de
naturlige tal i bogen “Arithmetices principia, nova methodo exposita” (Peano, 2010),
og Richard Dedekind i artiklen “Was sind und was sollen die Zahlen?” (Dedekind,
1888).
Denne karakteristik af de naturlige talN kendes under navnet Dedekind–
Peano-aksiomerne. Dedekinds fundamentale bidrag til matematik i øvrigt er for
eksempel udredt i Reck (2017).
2.1 Dedekind–Peanos aksiomer og induktion
De naturlige tal
N =f1;2;3;:::g
synes velkendte; men deres eksistens og grundlæggende egenskab – princippet
om matematisk induktion – beror på Dedekind–Peanos aksiomer.
Aksiom 2.1 (Dedekind–Peano).
En mængdeN med et særligt element 12N (et initialt element) og udstyret med en
+efterfølger-afbildningN!N, hvorn afbildes in , således at:
(i) Det initiale element 12N ikke er efterfølgeren af nogetn2N.
+ +(ii) Efterfølger-afbildningen er 1-1 (det vil sige:m,n)m ,n ).
(iii) Hvis en delmængdeSN indeholder det initiale element 1 og er lukket under
+efterfølger-afbildningen (det vil sige:n2S)n 2S), så erS =N.
Alle de velkendte egenskaber ved de naturlige tal kan udledes af dette aksiom.
+Addition er defineret ud fra, atn + 1 :=n , jf. Korollar 2.9. Ordningen< påN er
defineret vedn<n +a fora2N, jf. afsnit 2.1.
Dedekind–Peanos aksiom giver et kriterium for, hvornår en delmængde af de
naturlige tal udgør alle naturlige tal, hvilket også kan udtrykkes i princippet om
matematisk induktion. Et induktionsbevis er et bevis for en sætning, der indeholder
en række nummererede udsagn
U ; n = 1;2;:::,n
som vi ønsker at vise, er sande for allen.
72. De naturlige tal – Induktion
Sætning 2.2 (Første princip om matematisk induktion).
LadU være nummererede udsagn, som for ethvertn2N er enten sandt eller falskt,n
og lad
S =fnj udsagnetU er sandtgN:n
Hvis
Induktionsstart: 12S,
+Induktionsskridt: n2S)n 2S.
Så erS =N, og udsagnetU er sandt for allen2N.n
Sætning 2.3 (Sum af differensrække).
Lada2R være et vilkårligt reelt tal. Udsagnet
(n + 1)n
U : a + 2a + 3a + +na = an
2
er sandt for ethvertn2N.
Bevis. Det er nok at viseU i tilfældeta = 1, idet det generelle tilfælde opnås vedn
skalering meda. Vi skal altså vise, at udsagnet
(n + 1)n
U : 1 + 2 + 3 + +n =n 2
er sandt for allen2N.
Vi bruger induktion eftern.
(1+1)1
InduktionsstartenU : 1 = er trivielt og dermed sand.1 2
(n+1)n
Antag, at udsagnetU : 1 + 2 + 3 + +n = er sandt, og betragt udsagnetn 2
U , som vi skal verificere er sandt. Per induktionsantagelse får vi, atn+1
(n+1)n
2
(n + 1)n (n + 2)(n + 1)
(1 + 2 + 3 + +n) + (n + 1) = + (n + 1) = ;
2 2
hvilket netop er udsagnetU . Ifølge princippet om matematisk induktion erUn+1 n
sandt for ethvertn2N.
Der er en anekdote om skoleeleven Carl Friedrich Gauss – en af historiens
største matematikere. Læreren gav klassen til opgave at beregne summen 1 + 2 +
3 + + 100 for derved at beskæftige for en tid. Gauss svarede angiveligt
næsten øjeblikkeligt med det korrekte svar!
Sætning 2.4 (Sum af kvotientrække).
Lada;q2R være reelle tal medq, 1. Udsagnet
n+11 q2 3 nU : a +aq +aq +aq + +aq =an
1 q
er sandt for ethvertn2N.
8