Subexponential Algorithms for Factoring and Discrete Logarithm (CSE 290), Winter 2014

Organizers: Sorina Ionica, Shachar Lovett, Hovav Shacham

Class Times: Wednesdays 2-4pm, Computer Science building (EBU3B), room 4217

The seminar will cover both classic and recent results regarding algorithms for factoring integers and discrete logarithms over finite fields. Topics include: mathematical background; generic algorithms and the Elliptic Curve Method; the Quadratic Sieve; the Number-Field Sieve; the Function-Field Sieve; recent developments in the FFS for the small- and medium-characteristic case; applications to cryptography.

Students are expected to read papers and present them in class. If you know which lecture interests you, please email slovett@ucsd.edu to reserve it. First come first serve.

Lectures:

Generic factoring methods; mathematical background (April 2) [Shachar]
Elliptic curves and ECM (April 9) [Sorina]
L(1/2) algorithms: CFRAC, Linear Sieve, Quadratic Sieve (April 16) [Michael]
- Morrison and Brillhart: A Method of Factoring and the Factorization of F_7, 1975.
- Hellman: Public Key Cryptography [section 5], 1995.
- Pomerance: The Quadratic Sieve Factoring Algorithm, 1985.
The (Special and General) Number Field Sieve - Factoring(April 23) [Kaave]
- Lenstra, Lenstra, Manasse and Pollard: The number field sieve, 1990.
- Buhler, Lenstra and Pomerance: Factoring integers with the number field sieve, 1993.
- Pomerance: The number field sieve, 1994.
- Stevenhagen: The number field sieve, 2008.
Discrete logarithm in GF(p) using the Number Field Sieve(April 30) [Semih]
- Gordon: Discrete logarithm in GF(p) using the number field sieve, 1992.
- Weber: Computing discrete logarithms using the number field sieve, 1996.
Linear algebra with sparse matrices (May 7) [Leo]
the Function Field Sieve (May 14) [Shachar]
- Adleman: The Function Field Sieve, 1994.
- Adleman and Huang: Function Field Sieve Method for Discrete Logarithms over Finite Fields, 1999.
- Joux and Lercier: The Function Field Sieve is quite special, 2002.
- Joux and Lercier: The Function Field Sieve in the Medium Prime Case, 2006.
Actual implementations and hardware considerations (May 21) [Keaton]
- Thorsten et al.: Factorization of a 768-bit RSA modulus, 2010.
- Thorsten, Nussbaum and Thomë: Using a grid platform for solving large sparse linear systems over GF(2), 2010.
- Bai, Thomë and Zimmermann: Factorization of RSA-704 with CADO-NFS, 2012.
Recent breakthrough: L(1/4) and quasi-polynomial for small-char (May 28) [Sorina]
- Göloglu, Granger, McGuire, and Zumbrägel: On the Function Field Sieve and the Impact of Higher Splitting Probabilities: Application to Discrete Logarithms in $\F_{2^{1971}}$.
- Joux: A new index calculus algorithm with complexity L(1/4 + o(1)) in very small characteristic (Draft).
- Göloglu, Granger, McGuire, and Zumbrägel: Solving a $6120$-bit DLP on a Desktop Computer.
- Adj, Menezes, Oliveira, and Rodríguez-Henríquez: Computing Discrete Logarithms in F_{3^{6*137}} and F_{3^{6*163}} using Magma.
- Barbulescu, Gaudry, Joux, and Thomé: A quasi-polynomial algorithm for discrete logarithm in finite fields of small characteristic.
- Cheng, Wan, and Zhuang: Traps to the BGJT-Algorithm for Discrete Logarithms.
Applications to cryptography: Pairing-based crypto (June 4) [Hovav]
- Adj, Menezes, Oliveira, and Rodríguez-Henríquez: Weakness of F_{3^{6*1429}} and F_{2^{4*3041}} for Discrete Logarithm Cryptography.
- Granger, Kleinjung, and Zumbrägel: Breaking "128-bit Secure" Supersingular Binary Curves (or how to solve discrete logarithms in $\F_{2^{4 \cdot 1223}}$ and $\F_{2^{12 \cdot 367}}$).

References:

Crandall and Pomerance. Prime numbers: a computational perspective. (UC campuses only)
Lenstra and Lenstra. The development of the Number Field Sieve (LNCS). (UC campuses only)
Hellman. A survey on factoring algorithms.
Cohen and Frey. Handbook of elliptic and hyperelliptic curve cryptography.
Charlap and Robbins: An Elementary Introduction to Elliptic Curves.
Charlap and Coley: An Elementary Introduction to Elliptic Curves, II.