home page

The main area of my research is Algorithmic Number Theory. Originally, the topic developed when number theorists needed to solve effective problems like deciding if a number is prime, finding the rational roots of a polynomial or even computing its Galois group. Gauss studied factorization and primality while Bouniakowski considered the discrete logarithm problem, but none made a breakthrough. Then, in the begining of the XXth century, Pocklington found a method to decide if a Fermat number is prime, Kraitchik dramatically speeded up factorization and discrete logarithm, while Lehmer used the continued fractions in a factorization algorithm. After the first computer was built, the field developed and major discoveries followed. Some of the most famous are those of Karatsuba and Strassen who invented new methods for multiplying polynomials and matrices. The topic was both mathematics and computer science because the objects of study were mathematical while the methods of study were algorithmic.

But it wasn't all. When different algorithms were created for the same goal, comparing them became crucial. This is how new questions were aked: What are the algebraic groups over Fp with approximatively p elements? How many elliptic curves over Fp have the same cardinal? What is the probability that a number at distance at most √x from x has all its prime factors less than y? Here the objects were computer scienctist (algorithms), while the methods were mathematical (pen, paper and proofs).

In 1976 Diffie and Hellman proposed to "lock" a piece of information using mathematical padlocks. These padlocks were bijective functions, easy to lock, i.e. quickly computable in one way, and hard to break, i.e. difficult to compute the other way around (unless if you have a secret hint). They said we have to search for good one-way functions and suggested that the pair (exponentiation,dicrete logarithm) might work. In 1978 Rivest Shamir and Adleman proposed the pair (multiplication, factorization) which is still used on the credit card and the mobile phone in your pocket.

As for my specific topic, it is the descrete logarithm problem in Fpn. The reason is the increasing use of pairings in cryptography. A pairing is a bilinear, non degenerated map φ:G1×G2 → G3 with G1, G2 and G3 abelian groups. A good pairing has to be easy to compute and needs that the discrete logarithm problem in all the three groups be hard. For the moment the best pairings known use elliptic curves as G1 and G2 and Fpn as G3. Therefore the security of the new cryptosystems depends on the difficulty of the discrete logarithm problem.