Skip to main content
Till KTH:s startsida

FSF3741 Computational Number Theory 7.5 credits

Administer About course

Information per course offering

Course offerings are missing for current or upcoming semesters.

Course syllabus as PDF

Please note: all information from the Course syllabus is available on this page in an accessible format.

Course syllabus FSF3741 (Spring 2019–)
Headings with content from the Course syllabus FSF3741 (Spring 2019–) are denoted with an asterisk ( )

Content and learning outcomes

Course contents

  • Factoring

  • Shank's SQUFOF

  • Quadratic sieve

  • Lenstra's elliptic curve algorithm

  • Number field sieve

  • Elliptic curves

  • Elliptic curve cryptography - avoiding factor base embeddings

  • Identity based schemes via the Weil pairing

  • Point counting on elliptic curves (Shoof, Sato)

  • Primality proving

  • PRIMES is in P - the AKS algorithm, plus the Pomerance-Lenstra refinement.

  • Elliptic curve primality proving (Schoof, Atkin-Morain)

  • Some modern probabilistic primality test (Frobenius pseudo primes etc) and analogues of Carmichael numbers.

  • Class groups

  • Determining the size/generators with and without assuming GRH.

  • Fast verification via trace formulae

  • Fundamental units/regulators

  • Fast arithmetic

  • FFT

  • Fuerer

  • Z-modules and lattices

  • Ideal arithmetic

  • The LLL algorithm

  • Short vectors and cryptographic applications

Intended learning outcomes

Broad overview of modern computational number theory. In depth knowledge of specialized

Literature and preparations

Specific prerequisites

Masters degree in mathematics, or in computational mathematics or in computer science/engineering with at least 30 cr in mathematics.

Literature

Prime numbers: a computational perspective by Richard Crandall,  Carl Pomerance

F- A course in computational algebraic number theory by Henri Cohen

Examination and completion

Grading scale

P, F

Examination

  • SEM1 - Seminars, 7.5 credits, grading scale: P, F

Based on recommendation from KTH’s coordinator for disabilities, the examiner will decide how to adapt an examination for students with documented disability.

The examiner may apply another examination format when re-examining individual students.

If the course is discontinued, students may request to be examined during the following two academic years.

Oral presentation of selected topic. At least 90% seminar attendence

Other requirements for final grade

Approved oral presentation of selected topic. At least 90% seminar attendence.

Examiner

Profile picture Pär Kurlberg

Ethical approach

  • All members of a group are responsible for the group's work.
  • In any assessment, every student shall honestly disclose any help received and sources used.
  • In an oral assessment, every student shall be able to present and answer questions about the entire assignment and solution.

Further information

Course room in Canvas

Registered students find further information about the implementation of the course in the course room in Canvas. A link to the course room can be found under the tab Studies in the Personal menu at the start of the course.

Offered by

SCI/Mathematics

Education cycle

Third cycle

Postgraduate course

Postgraduate courses at SCI/Mathematics