Razvan Barbulescu

Razvan Barbulescu, Pierrick Gaudry, Aurore Guillevic et al.

We propose various strategies for improving the computation of discrete logarithms in non-prime fields of medium to large characteristic using the Number Field Sieve. This includes new methods for selecting the polynomials; the use of explicit automorphisms; explicit computations in the number fields; and prediction that some units have a zero virtual logarithm. On the theoretical side, we obtain a new complexity bound of $L_{p^n}(1/3,\sqrt[3]{96/9})$ in the medium characteristic case. On the practical side, we computed discrete logarithms in $F_{p^2}$ for a prime number $p$ with $80$ decimal digits.Warning: This unpublished version contains some inexact statements.

Razvan Barbulescu, Armand Lachand

In this work, we consider the proportion of smooth (free of large prime factors) values of a binary form $F(X_1,X_2)\in\Z[X_1,X_2]$. In a particular case, we give an asymptotic equivalent for this proportion which depends on $F$. This is related to Murphy's $α$ function, which is known in the cryptographic community, but which has not been studied before from a mathematical point of view. Our result proves that, when $α(F)$ is small, $F$ has a high proportion of smooth values. This has consequences on the first step, called polynomial selection, of the Number Field Sieve, the fastest algorithm of integer factorization.

Razvan Barbulescu, Pierrick Gaudry, Antoine Joux et al.

In the present work, we present a new discrete logarithm algorithm, in the same vein as in recent works by Joux, using an asymptotically more efficient descent approach. The main result gives a quasi-polynomial heuristic complexity for the discrete logarithm problem in finite field of small characteristic. By quasi-polynomial, we mean a complexity of type $n^{O(\log n)}$ where $n$ is the bit-size of the cardinality of the finite field. Such a complexity is smaller than any $L(\varepsilon)$ for $ε>0$. It remains super-polynomial in the size of the input, but offers a major asymptotic improvement compared to $L(1/4+o(1))$.

Razvan Barbulescu

The Function Field Sieve algorithm is dedicated to computing discrete logarithms in a finite field GF(q^n), where q is small an prime power. The scope of this article is to select good polynomials for this algorithm by defining and measuring the size property and the so-called root and cancellation properties. In particular we present an algorithm for rapidly testing a large set of polynomials. Our study also explains the behaviour of inseparable polynomials, in particular we give an easy way to see that the algorithm encompass the Coppersmith algorithm as a particular case.

Razvan Barbulescu, Joppe W. Bos, Cyril Bouvier et al.

In this paper we prove some divisibility properties of the cardinality of elliptic curves modulo primes. These proofs explain the good behavior of certain parameters when using Montgomery or Edwards curves in the setting of the elliptic curve method (ECM) for integer factorization. The ideas of the proofs help us to find new families of elliptic curves with good division properties which increase the success probability of ECM.