14 citations
Counting papers with at most 25 authors, so collaboration author lists do not stand in for the people here.
- Centre National de la Recherche ScientifiqueFR6 papers
- Université de LorraineFR5 papers
- Institut national de recherche en sciences et technologies du numériqueFR4 papers
- Centre Inria de l'Université de LorraineFR2 papers
- Laboratoire Lorrain de Recherche en Informatique et ses ApplicationsFR2 papers
- ARIC: Arithmétiques des ordinateurs, méthodes formelles, génération de codeFR1 paper
- CANARI: Analyse cryptographique et arithmétiqueFR1 paper
- CanarieCA1 paper
- CAPSULE: Cryptographie Appliquée et Sécurité des ImplémentationsFR1 paper
- Cara Therapeutics (United States)US1 paper
- Centre Inria de SaclayFR1 paper
- École PolytechniqueFR1 paper
15 papers
A Tight Quantum Algorithm for Multiple Collision Search
Xavier Bonnetain, Johanna Loyer, André Schrottenloher +1
Searching for collisions in random functions is a fundamental computational problem, with many applications in symmetric and asymmetric cryptanalysis. When one searches for a singl…
Fast evaluation of Riemann theta functions in any dimension
Noam D. Elkies, Jean Kieffer
We describe an algorithm to numerically evaluate Riemann theta functions in any dimension in quasi-linear time in terms of the required precision, uniformly on reduced input. This…
Computing Isomorphisms between Products of Supersingular Elliptic Curves
Pierrick Gaudry, Julien Soumier, Pierre-Jean Spaenlehauer
The Deligne-Ogus-Shioda theorem guarantees the existence of isomorphisms between products of supersingular elliptic curves over finite fields. In this paper, we present methods for…
Algorithms for computing norms and characteristic polynomials on general Drinfeld modules
Xavier Caruso, Antoine Leudière
We provide two families of algorithms to compute characteristic polynomials of endomorphisms and norms of isogenies of Drinfeld modules. Our algorithms work for Drinfeld modules of…
Evaluating modular equations for abelian surfaces
Jean Kieffer
We design efficient algorithms to evaluate modular equations of Siegel and Hilbert type for abelian surfaces over number fields or finite fields using complex approximations. Their…
Refined Analysis of the Asymptotic Complexity of the Number Field Sieve
Aude Le Gluher, Pierre-Jean Spaenlehauer, Emmanuel Thomé
The classical heuristic complexity of the Number Field Sieve (NFS) is the solution of an optimization problem that involves an unknown function, usually noted and called $ξ(…
Computing isogenies from modular equations in genus two
Jean Kieffer, Aurel Page, Damien Robert
We present an algorithm solving the following problem: given two genus 2 curves over a field k with isogenous Jacobians, compute such an isogeny explicitly. This isogeny can be eit…
A Fast Randomized Geometric Algorithm for Computing Riemann-Roch Spaces
Aude Le Gluher, Pierre-Jean Spaenlehauer
We propose a probabilistic variant of Brill-Noether's algorithm for computing a basis of the Riemann-Roch space associated to a divisor on a projective nodal plane curve…
Faster individual discrete logarithms in finite fields of composite extension degree
Aurore Guillevic
Computing discrete logarithms in finite fields is a main concern in cryptography. The best algorithms in large and medium characteristic fields (e.g., {GF}, {GF})…
Improved Complexity Bounds for Counting Points on Hyperelliptic Curves
Simon Abelard, Pierrick Gaudry, Pierre-Jean Spaenlehauer
We present a probabilistic Las Vegas algorithm for computing the local zeta function of a hyperelliptic curve of genus defined over . It is based on the approache…
Determinism and Computational Power of Real Measurement-based Quantum Computation
Simon Perdrix, Luc Sanselme
Measurement-based quantum computing (MBQC) is a universal model for quantum computation. The combinatorial characterisation of determinism in this model, powered by measurements, a…
Twelve new primitive binary trinomials
Richard P. Brent, Paul Zimmermann
We exhibit twelve new primitive trinomials over GF(2) of record degrees , , and . In addition we report the first Mersenne exponent not ruled out by S…
Computing Small Certificates of Inconsistency of Quadratic Fewnomial Systems
Jean-Charles Faugere, Pierre-Jean Spaenlehauer, Jules Svartz
B{é}zout 's theorem states that dense generic systems of n multivariate quadratic equations in n variables have 2 n solutions over algebraically closed fields. When only a small su…
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…