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:

Background and introduction (April 2) [Shachar]

Generic algorithms; ECM (April 9) [Sorina]

L(1/2) algorithms: CFRAC, Linear Sieve, Quadratic Sieve (April 16)

L(1/3) algorithms: The (Special and General) Number Field Sieve (April 23)

...the Function Field Sieve (April 30)

...the Special FFS: small-char (May 7)

...the medium-prime case (May 14)

Recent breakthrough: L(1/4) for small-char (May 21)

Recent breakthrough: Quasi-polynomial for small-char (May 28)

Applications to cryptography: Pairing-based crypto (June 4) [Hovav]

References:

Crandall and Pomerance. Prime numbers: a computational perspective. E-book (UC campuses only).

Lenstra and Lenstra. The development of the Number Field Sieve (LNCS). E-book (UC campuses only).

Hellman. A survey on factoring algorithms. PDF.

Cohen and Frey. Handbook of elliptic and hyperelliptic curve cryptography. PDF.