MAT-1300 Tallteori - 10 stp

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.

• 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).

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

Eksamensdato er foreløpig og vil kunne bli endret. Endelig eksamensdato kunngjøres ved oppslag på det enkelte fakultet primo mai for vårsemesteret og primo november for høstsemesteret.

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