Størrelse: 7.5 ECTS

Placering: 2. eller 3. år, blok 2C

Udbydes: Hvert andet år

Kompetencebeskrivelse: Opnå viden om strukturen af moderne Public Key systemer, inklusive

forståelse for de abstrakte krav, der stilles til sådanne. Dybtgående viden - inklusive

beherskelse af beviser - om talteoretiske strukturer, resultater og algoritmer af

betydning for moderne Public Key systemer.

Emner: Kryptosystemer: Niveauer af sikkerhed, Public Key, Key Exchange, algoritmer.

Kompleksitet af grundlæggende aritmetiske operationer, inklusive kongruensaritmetik,

hurtig eksponentiering, elementære anvendelser på faktorisering.

Egenskaber af endelige legemer, kvadratisk reciprocitet, beregning af Jacobi-symbolet.

Public Key systemer: ElGamal, Key exchange, RSA, systemer baserede på det diskrete

logaritmeproblem, Pohlig-Hellman algoritmen, index calculus.

Primtalstests: Pseudoprimtal og Carmichael-tal, stærke pseudoprimtal, Miller-Rabin testen,

Agrawal-Kayal-Saxena testen.

Faktorisering: Pollard's rho, Fermat faktorisering, psi-funktionen (asymptotik, nedre

grænser), Dixon's algoritme (factor base algorithm).

Videregående emner (kursorisk): Faktorisering via kædebrøker, kvadratisk si, tallegemesi,

elliptiske kurver og kryptosystemer baserede herpå. Tilfældighedsgeneratorer.

Lærebøger og andet undervisningsmateriale:

N. Koblitz: A course in number theory and cryptography. Second edition.

Graduate Texts in Mathematics 114, Springer 1994.

Desuden evt. diverse komplementerende noter.

Forudsætninger: Alg2

Undervisningsform: Forelæsninger og øvelser

Evalueringsform: Løbende. Med karakter, men uden ekstern censur

En mulighed er følgende:

3 skriftlige 1-times tests i en forelæsningstime.

2 større skriflige opgaver med en uges afleveringsfrist.

De 3 tests og de 2 opgaver tæller hver med 50 % i det endelige resultat.

Undervisningsbelastning: 1 lærer til forelæsninger.

1 instruktor til øvelser.

Bemærkninger: I tvivl om, hvorvidt kurset burde udbydes hvert eller hvert andet år. Kan

ikke rigtigt bedømme, om der ville være grundlag for udbydelse hvert år, men det ville

måske være en god ide (i stedet for som foreslået hvert andet år).