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 to reserve it. First come first serve.


  1. Generic factoring methods; mathematical background (April 2) [Shachar]
  2. Elliptic curves and ECM (April 9) [Sorina]
  3. L(1/2) algorithms: CFRAC, Linear Sieve, Quadratic Sieve (April 16) [Michael]
  4. The (Special and General) Number Field Sieve - Factoring(April 23) [Kaave]
  5. Discrete logarithm in GF(p) using the Number Field Sieve(April 30) [Semih]
  6. Linear algebra with sparse matrices (May 7) [Leo]
  7. the Function Field Sieve (May 14) [Shachar]
  8. Actual implementations and hardware considerations (May 21) [Keaton]
  9. Recent breakthrough: L(1/4) and quasi-polynomial for small-char (May 28) [Sorina]
  10. Applications to cryptography: Pairing-based crypto (June 4) [Hovav]