vår 2018: MAT-1300 Tallteori - 10 stp
Opptakskrav
Generell studiekompetanse eller realkompetanse + Matematikk R1 eller (S1+S2) og enten Matematikk (R1+R2) eller Fysikk (1+2) eller Kjemi (1+2) eller Biologi (1+2) eller Informasjonsteknologi( 1+2) eller Geologi (1+2) eller Teknologi og forskningslære (1+2).
Søknadskode 9336 - enkeltemner i realfag.
Hva lærer du
Emnet gir en innføring i elementær tallteori og det fokuseres på kryptografiske anvendelser. Etter fullført kurs skal studentene kunne- Løse lineære kongruensligninger.
- Beherske Euklids utvidede algoritme til å finne inverser modulo heltall.
- Kunne anvende kinesisk restteorem.
- Beskrive Pollard faktoriseringsalgoritmer og gjøre rede for hvilke konsekvenser disse algoritmene har for valg av primtall til offentlig nøkkel kryptosystemet RSA.
- Kunne anvende Hensels lemma til å finne løsninger til polynomligninger modulo potenser av primtall.
- Beherske Fermats og Eulers teorem og kunne beskrive hvordan Eulers teorem anvendes innen RSA kryptering.
- Ha kjennskap til begreper som pseudoprimtall, Carmichael tall, sterke pseudoprimtall og Euler pseudoprimtall.
- Kjenne til multiplikative aritmetiske funksjoner som "sum av divisorer", "antall divisorer", "Eulers Phi-funksjon", og kunne regne dem ut når faktoriseringen er gitt.
- Kunne utføre Möbius Inversjon av aritmetiske funksjoner.
- Kjenne til historiske kryptosystemer som Vigenère- og blokkshiffrering.
- Ha inngående kjennskap til RSA offentlig nøkkel kryptering og hvordan dette også kan brukes til signering.
- Gjøre rede for Diffie - Hellman nøkkelutveksling og forklare hvorfor nøkkelen ikke røpes under utvekslingen.
- Gjøre rede for hvilke heltall som har primitiv rot, finne primitiv rot for små heltall og kunne bruke primitive røtter til å løse enkle ligninger
- Forklare hva en primitiv rest og ikkerest er og kunne bruke kvadratisk resiprositet til å regne ut Legendresymbol
- Kunne anvende Eulersymbolet og resiprositetteoremet til å regne ut Legendresymbol
- Beregne kvadratrøtter av a modulo n når n er et produkt av to primtall.
- Forstå hvordan teorien om kvadratrøtter modulo heltall kan brukes til minimale kunnskapsprotokoller (Zero Knowledge Proofs).
Eksamen
En skriftlig eksamen av 4 timers varighet som teller 100%.
Karakterskala: Bokstavkarakterer A-F.
Kontinuasjonseksamen: Studenter som ikke har bestått siste ordinære eksamen tilbys kontinuasjonseksamen tidlig i påfølgende semester, dersom emnet inngår som obligatorisk i studieprogrammet.
Utsatt eksamen: Studenter med gyldig forfall tilbys utsatt eksamen tidlig i påfølgende semester.
Arbeidskrav
Obligatoriske øvelser kreves godkjent for adgang til å avlegge eksamen.
For mer informasjon, se forøvrig:
- Utfyllende bestemmelser for eksamener ved Fakultet for naturvitenskap og teknologi
Pensum
Pensumliste for MAT-1300 Tallteori, våren 2018
UiT Norges arktiske universistet, Institutt for matematikk og statistikk
Lærebok:Kenneth H. Rosen, "Elementary Number Theory", Pearson New International Edition, 6th Edition, ISBN-13: 9781292039541
Kap 3. Primes and Greatest Common Divisor (7 sider):
3.7 Linear Diophantine Equations
Kap 4. Congruences (33 sider):
4.1 Introduction to Congruences
4.2 Linear Congruences
4.3 The Chinese Remainder Theorem
4.4 Solving Polynomial Congruences
Kap 5. Applications of Congruences (12 sider):
5.4 Hashing Functions
5.5 Check Digits
Kap 6. Some Special Congruences (22 sider):
6.1 Wilson's Theorem and Fermat's Little Theorem
6.2 Pseudoprimes
6.3 Euler's Theorem
Kap 7. Multiplicative Functions (38 sider):
7.1 The Euler Phi-function
7.2 The Sum and Number of Divisors
7.3 Perfect Numbers and Mersenne Primes
7.4 Möbius Inversion
Kap 8. Cryptology (55 sider):
8.1 Character Ciphers
8.2 Block and Stream Ciphers
8.3 Exponentiation Ciphers
8.4 Public-Key Cryptography
8.5 Knapsack Ciphers
8.6 Cryptographic Protocols and Applications
Kap 9. Primitive Roots (29 sider)
9.1 The Order of an Integer and Primitive Roots
9.2 Primitive Roots for Primes
9.3 The Existence of Primitive Roots
9.5 Primality Tests Using Orders of Integers and Primitive Roots
Kap 11. Quadratic Residues (54 sider):
11.1 Quadratic Residues and Nonresidues
11.2 The Law of Quadratic Residues
11.3 The Jacobi Symbol
11.4 Euler Pseudoprimes
11.5 Zero-Knowledge Proofs
Til sammen: 250 sider
Tillatte hjelpemidler til eksamen:
Rottmanns tabeller
Godkjente statistiske tabeller
To A4-ark (4 sider) med egne notater
Godkjent kalkulator
Error rendering component
- Om emnet
- Studiested: Tromsø |
- Studiepoeng: 10
- Emnekode: MAT-1300
- Ansvarlig enhet
- Institutt for matematikk og statistikk