Institut: MATEMATIK OG DATALOGI

Kursustitel: ALGORITHMIC NUMBER THEORY

Semesteromfang/timetal: 0.2 semester / 2 hours lecture per week, plus 2 office hours per week.

Indgangskrav: DM02 and MM05 (though exceptions could be made).

Målsætning: The purpose of this course is to introduce the participants to algorithmic number theory. The problems considered will be from elementary number theory, i.e. primality testing, factoring, discrete logarithm, etc., and the emphasis will be on algorithms, rather than the proof of purely number-theoretic results, though some of this is, of course, necessary. Much of the material which will be covered has applications in cryptology.

Emneoversigt: The extended Euclidean algorithm, computing in the additive and multiplicative groups modulo n (including the Chinese Remainder Theorem, the Legendre symbol, and the Jacobi symbol), computing in finite fields, solving equations over finite fields, primality testing, factoring algorithms, and discrete logarithm algorithms.

Evaluering: 4 hour written exam with external examiner and grading on the 13 point scale. In addition, there will be a number of assignments which the students must have approved in order to take the exam.

Undervisningsform: Lectures by the teacher.

Lærer: Joan Boyar.

Litteratur: Algorithmic Number Theory. Volume 1: Efficient Algorithms, by Eric Bach and Jeffrey Shallit. There will also be some supplementary notes.