25 citations · 66 across the 10 of their papers we have counts for
14 papers
A kilobit hidden SNFS discrete logarithm computation
Joshua Fried, Pierrick Gaudry, Nadia Heninger +1
We perform a special number field sieve discrete logarithm computation in a 1024-bit prime field. To our knowledge, this is the first kilobit-sized discrete logarithm computation e…
Solving discrete logarithms on a 170-bit MNT curve by pairing reduction
Aurore Guillevic, François Morain, Emmanuel Thomé
Pairing based cryptography is in a dangerous position following the breakthroughs on discrete logarithms computations in finite fields of small characteristic. Remaining instances…
A modified block Lanczos algorithm with fewer vectors
Emmanuel Thomé
The block Lanczos algorithm proposed by Peter Montgomery is an efficient means to tackle the sparse linear algebra problem which arises in the context of the number field sieve fac…
Linear Time Interactive Certificates for the Minimal Polynomial and the Determinant of a Sparse Matrix
Jean-Guillaume Dumas, Erich Kaltofen, Emmanuel Thomé +1
Computational problem certificates are additional data structures for each output, which can be used by a-possibly randomized-verification algorithm that proves the correctness of…
Interactive certificate for the verification of Wiedemann's Krylov sequence: application to the certification of the determinant, the minimal and the characteristic polynomials of sparse matrices
Jean-Guillaume Dumas, Erich Kaltofen, Emmanuel Thomé
Certificates to a linear algebra computation are additional data structures for each output, which can be used by a-possibly randomized- verification algorithm that proves the corr…
Fast integer multiplication using generalized Fermat primes
Svyatoslav Covanov, Emmanuel Thomé
For almost 35 years, Sch{ö}nhage-Strassen's algorithm has been the fastest algorithm known for multiplying integers, with a time complexity O(n log n log log n) f…
Isogeny graphs with maximal real multiplication
Sorina Ionica, Emmanuel Thomé
An isogeny graph is a graph whose vertices are principally polarized abelian varieties and whose edges are isogenies between these varieties. In his thesis, Kohel described the str…
Computation with No Memory, and Rearrangeable Multicast Networks
Serge Burckel, Emeric Gioan, Emmanuel Thomé
We investigate the computation of mappings from a set S^n to itself with "in situ programs", that is using no extra variables than the input, and performing modifications of one co…
A quasi-polynomial algorithm for discrete logarithm in finite fields of small characteristic
Razvan Barbulescu, Pierrick Gaudry, Antoine Joux +1
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 r…
Computing class polynomials for abelian surfaces
Andreas Enge, Emmanuel Thomé
We describe a quasi-linear algorithm for computing Igusa class polynomials of Jacobians of genus 2 curves via complex floating-point approximations of their roots. After providing…
Root optimization of polynomials in the number field sieve
Shi Bai, Richard P. Brent, Emmanuel Thomé
The general number field sieve (GNFS) is the most efficient algorithm known for factoring large integers. It consists of several stages, the first one being polynomial selection. T…
Visualizing elements of Sha[3] in genus 2 jacobians
Nils Bruin, Sander R. Dahmen
Mazur proved that any element xi of order three in the Shafarevich-Tate group of an elliptic curve E over a number field k can be made visible in an abelian surface A in the sense…
An Discrete Logarithm Algorithm for Low Degree Curves
Andreas Enge, Pierrick Gaudry, Emmanuel Thomé
We present an algorithm for solving the discrete logarithm problem in Jacobians of families of plane curves whose degrees in and are low with respect to their genera. The f…
Time- and Space-Efficient Evaluation of Some Hypergeometric Constants
Howard Cheng, Guillaume Hanrot, Emmanuel Thomé +2
The currently best known algorithms for the numerical evaluation of hypergeometric constants such as to decimal digits have time complexity and space…