- Antoine Joux: A Simplified ...
- Edit Event
- Cancel Event
- Preview Reminder
- Send Reminder
- Other events happening in April 2015

## Antoine Joux: A Simplified Setting for Discrete Logarithms in Small Characteristics Finite Fields

**Speaker:**
Antoine Joux

**Date:**
Tuesday, April 07, 2015

**Time:**
4:15 PM to 5:15 PM
** Note: all times are in the Eastern Time Zone**

**Refreshments:**
4:00 PM

**Public:**
Yes

**Location:**
G449 Patil/Kiva

**Event Type:**

**Room Description:**

**Host:**
Costis Daskalakis, Ankur Moitra, Dana Moshkovitz and Vinod Vaikuntanathan

**Contact:**
Deborah Lehto, 617.324.7303, dlehto@csail.mit.edu

**Speaker URL:**
None

**Speaker Photo:**

None

**Reminders to:**
cis-seminars@csail.mit.edu, theory-seminars@csail.mit.edu, seminars@csail.mit.edu

**Reminder Subject:**
TALK: Antoine Joux: A Simplified Setting for Discrete Logarithms in Small Characteristics Fin

Abstract:

The hardness of computing discrete logarithms in finite field has served as a foundation for many public key cryptosystems. In the last two years, tremendous progress have been made in the case of small characteristic finite fields.

In this talk, we present a simplified description of the algorithmic framework that has been developed to solve this problem faster.

This framework is an index calculus approach that relies on two main ingredients, the definition of the extension field and the generation of multiplicative relations in this field. Given a base field GF(q), we construct its extension field GF(q^k) in the following way: we find two polynomials of low degree h0 and h1 with coefficients in GF(q) such that x^q h1(x)-h0(x) has an irreducible factor of

degree k over GF(q).

To generate relations, we start from the well-known identity:

X^q-X=Prod_(c in GF(q)) X-c.

Combining substitution of X by a fraction in the identity with the field definition, we easily obtain many multiplicative relations. This is enough to obtain the logarithms of a factor base of small degree elements in polynomial time.

Once this is done, we use a descent procedure to recursively express any element of the finite field GF(q) into elements represented by polynomials of lower degree. This procedure is quite complex but ultimately leads to a quasi-polynomial time algorithm for the discrete logarithm problem in small characteristic finite fields.

**Research Areas:**

**Impact Areas:**

Created by Deborah Goodwin at Tuesday, March 10, 2015 at 3:27 PM.