BZPEERPapers, people, evidence and research pathsDiscover
Research tools
Network
Opportunities
Account
Source author record
Jean-Marc Couveignes appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.
Catalog footprint
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Published work
We study the complexity of multiplication of two elements in a finite field extension given by their coordinates in a normal basis. We show how to control this complexity using the arithmetic and geometry of algebraic curves.
We show how to efficiently compute functions on jacobian varieties and their quotients. We deduce a quasi-optimal algorithm to compute $(l,l)$ isogenies between jacobians of genus two curves.
We explore parameterizations by radicals of low genera algebraic curves. We prove that for $q$ a prime power that is large enough and prime to $6$, a fixed positive proportion of all genus 2 curves over the field with $q$ elements can be parameterized by $3$-radicals. This results in the existence of a deterministic encoding into these curves when $q$ is congruent to $2$ modulo $3$. We extend this construction to parameterizations by $\ell$-radicals for small odd integers $\ell$, and make it explicit for $\ell=5$.
This article gives an introduction for mathematicians interested in numerical computations in algebraic geometry and number theory to some recent progress in algorithmic number theory, emphasising the key role of approximate computations with modular curves and their Jacobians. These approximations are done in polynomial time in the dimension and the required number of significant digits. We explain the main ideas of how the approximations are done, illustrating them with examples, and we sketch some applications in number theory.
We present a randomized algorithm that on input a finite field $K$ with $q$ elements and a positive integer $d$ outputs a degree $d$ irreducible polynomial in $K[x]$. The running time is $d^{1+ε(d)} \times (\log q)^{5+ε(q)}$ elementary operations. The function $ε$ in this expression is a real positive function belonging to the class $o(1)$, especially, the complexity is quasi-linear in the degree $d$. Once given such an irreducible polynomial of degree $d$, we can compute random irreducible polynomials of degree $d$ at the expense of $d^{1+ε(d)} \times (\log q)^{1+ε(q)}$ elementary operations only.
We show how the study of the geometry of the nine flex tangents to a cubic produces pseudo-parameterizations, including the ones given by Icart, Kammerer, Lercier, Renault and Farashahi, and infinitely many new ones.
This is a book about computational aspects of modular forms and the Galois representations attached to them. The main result is the following: Galois representations over finite fields attached to modular forms of level one can, in almost all cases, be computed in polynomial time in the weight and the size of the finite field. As a consequence, coefficients of modular forms can be computed fast via congruences, as in Schoof's algorithm for the number of points of elliptic curves over finite fields. The most important feature of the proof of the main result is that exact computations involving systems of polynomial equations in many variables are avoided by approximations and height bounds, i.e., bounds for the accuracy that is necessary to derive exact values from the approximations.
We show how to transport descent obstructions from the category of covers to the category of varieties. We deduce examples of curves having $\QQ$ as field of moduli, that admit models over every completion of $\QQ$, but have no model over $\QQ$.
We address the problem of computing in the group of $\ell^k$-torsion rational points of the jacobian variety of algebraic curves over finite fields, with a view toward computing modular representations.
We construct two new families of basis for finite field extensions. Basis in the first family, the so-called elliptic basis, are not quite normal basis, but they allow very fast Frobenius exponentiation while preserving sparse multiplication formulas. Basis in the second family, the so-called normal elliptic basis are normal basis and allow fast (quasi linear) arithmetic. We prove that all extensions admit models of this kind.