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 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 seven.math.kth.se.
Schedule
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):
- Menezes, Okamoto, Vanstone: Reducing elliptic curve logarithms to logarithms in finite fields
- Boneh, Franklin: Identity-based 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. (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.
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 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