809 bit finite field discrete logarithms

A couple of weeks ago, Barbulescu, Bouvier, Detrey, Gaudry, Jeljeli, Thome, Videau and Zimmermann announced a new finite field discrete logarithm record.  They have used the function field sieve algorithm to solve the DLP in GF( 2^{809} ), which is a prime field degree.

It would be easy for this result to be eclipsed by the recent discrete log computations in GF( 2^n ) where n is highly composite.  However, the case of GF( 2^{809} ) is a major advance over the previous records (namely GF( 2^{613} ) and GF( 2^{619} )), and it is a significant computation.

At some point it may turn out to be more efficient to solve discrete logs in GF( 2^p ), where p is prime, by embedding them into fields GF( 2^{p*m} ).  But for the moment, the best way to solve such problems appears to be the traditional use of the function field sieve. And so this new discrete log record deserves just as much acclaim as the previous results.

  — Steven Galbraith

This entry was posted in Uncategorized. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s