Computational Number Theory, Fall 09, FSF3741

Table of Contents

Recent additions

091025: Extra meeting on oct 29 scheduled

091025: Reading list for oct 27 meeting updated.

090930: The course code is now officially FSF3741

Course literature

Organization (rough sketch)

During the first period of the fall semester (week 36-44 or so) we will have weekly meetings where (mainly) the participants will take turns giving brief lectures, followed by the audience discussion of any remaining "sticky points".

Weekly meeting time: Tuesdays, 15.15-17.15 in seminar room 3721 (seventh floor in the math department.)

Course info (administrative)

ECTS credits: 7.5.

Course code: FSF3741

Misc info

Sage and gp, two packages that "know" quite a lot of number theory, are now installed on


Sep 8, 2009.

To read in Crandall-Pomerance: Chapter 6.1 (the quadratic sieve), and as much of 6.2 (the number field sieve) as you can manage. Skip 6.1.7 (Zhang's special sieve.)

Speakers: Oscar A.-F., Pär K.

Sep 15, 2009

Topic: elliptic curves. To read: a good warmup for ECM is Pollard-(p-1), it's on pages 236-239. Background on elliptic curves, and description of ECM: 319-323, 333-339.

Speaker: Dan P.

Sep 22, 2009

Topics: NFS revisited. More number field background (some keywords: number fields, ring of integers, lack of unique factorization, ideals, unique factorization for ideals, class groups, Dirichlet's unit theorem, norms.) Chapter 4 of Cohen reviews many of these thing with a computational bent. Another option is Stewart and Tall.

Background on smooth number asymptotics (see nice survey by Granville). Run time analysis of QS, ECM, NFS.

Speaker: Pär K.

Sep 29, 2009

AKS plus Bernstein's refinement. Cenny W. To read: Proving primality in essentially quartic random time and 4.5 in Crandall-Pomerance.

Probabilistic tests: from Fermat to Frobenious pseudoprimes. Edgar C. To read: 3.{4-6} in Crandall-Pomerance.

Also of interest: the original AKS article, as well as a comparison of different tests.

Oct 6, 2009

  • AKS, part 2. (Cenny W.)
  • Run time analysis of ECM, QS, MPQS, NFS via smooth integers. (Pär K.)
  • Elliptic curve pairing based crypto. (Björn T.)

To read (i.e., for Björn's lecture, see above for "old" reading suggestions):

Oct 13, 2009

The LLL algorithm. (Igor W.)

Low exponent attacks on RSA using LLL. (Anne-Maria E.-H.) The aim is to present one very simple and one not so simple attack to break RSA when the secret exponent is small.

To read: Boneh-Durfee (RSA) and the LLL-sections in Cohen's book (sections 2.5-2.6, roughly pages 78-95.)

Oct 20, 2009

Low exponent attacks on RSA using LLL, part 2. (Anne-Maria E.-H.)

ECPP, Katharina H.

Reading for ECPP: 7.5-6 in Crandall-Pomererance. Reading for RSA attack using LLL: Boneh-Durfee (see above.)

Oct 27, 2009

Fast arithmetic, part 1 ("low level details"). Torbjörn G.

Reading (for math people): Multidigit multiplication for mathematicians. Reading (for CS people): Crandall-Pomerance, ch. 9.5

Run time analysis of ECM, QS, MPQS, NFS via smooth integers. (Pär K.)

Oct 29, 2009

Fast arithmetic, part 2 ("abstract version"). Torbjörn G.

Place: room D31. Time: 15.15-17.15.


  • Factoring
    • Shank's SQUFOF
    • Quadratic sieve (Oscar A.-F.)
    • Lenstra's elliptic curve algorithm (Dan P.)
    • Number field sieve (Pär K.)
  • Elliptic curves
    • Elliptic curve intro (Dan P.)
    • Elliptic curve cryptography - avoiding factor base embeddings
    • Identity based schemes via the Weil pairing
    • Point counting on elliptic curves - the Schoof and Sato algorithms.
  • Primality proving
    • PRIMES is in P - the AKS algorithm, plus the Pomerance-Lenstra refinement. (Cenny W.)
    • Elliptic curve primality proving (Schoof, Atkin-Morain)
    • Classical and modern probabilistic primality test (Miller-Rabin, 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 (Torbjörn G.)
    • FFT
    • Fuerer
  • Z-modules and lattices
    • Ideal arithmetic
    • The LLL algorithm (Igor W.)
    • Short vectors and cryptographic applications (Anne-Maria E.-H.)

Date: 2009-10-26 22:35:39 CET