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
 Prime numbers : a computational perspective by Richard Crandall and Carl Pomerance.
 Additional reading: A course in computational algebraic number theory by Henri Cohen.
Organization (rough sketch)
During the first period of the fall semester (week 3644 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.1517.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 seven.math.kth.se.
Schedule
Sep 8, 2009.
To read in CrandallPomerance: 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(p1), it's on pages 236239. Background on elliptic curves, and description of ECM: 319323, 333339.
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 CrandallPomerance.
Probabilistic tests: from Fermat to Frobenious pseudoprimes. Edgar C. To read: 3.{46} in CrandallPomerance.
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):
 Menezes, Okamoto, Vanstone: Reducing elliptic curve logarithms to logarithms in finite fields
 Boneh, Franklin: Identitybased encryption from the Weil pairing.
 Boneh, Lynn, Shacham: Short signatures from the Weil pairing.
Oct 13, 2009
The LLL algorithm. (Igor W.)
Low exponent attacks on RSA using LLL. (AnneMaria 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: BonehDurfee (RSA) and the LLLsections in Cohen's book (sections 2.52.6, roughly pages 7895.)
Oct 20, 2009
Low exponent attacks on RSA using LLL, part 2. (AnneMaria E.H.)
ECPP, Katharina H.
Reading for ECPP: 7.56 in CrandallPomererance. Reading for RSA attack using LLL: BonehDurfee (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): CrandallPomerance, 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.1517.15.
Topics

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 PomeranceLenstra refinement. (Cenny W.)
 Elliptic curve primality proving (Schoof, AtkinMorain)
 Classical and modern probabilistic primality test (MillerRabin, 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

Zmodules and lattices
 Ideal arithmetic
 The LLL algorithm (Igor W.)
 Short vectors and cryptographic applications (AnneMaria E.H.)
Date: 20091026 22:35:39 CET