BZPEERSource author record
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
Catalog footprint
Published work
Let E/Fq be an elliptic curve, and P a point in E(Fq) of prime order ℓ. Vélu's formulae let us compute a quotient curve E′=E/⟨P⟩ and rational maps defining a quotient isogeny ϕ:E→E′ in O~(ℓ) Fq-operations, where the O~ is uniform in q.This article shows how to compute E′, and ϕ(Q) for Q in E(Fq), using only O~(ℓ) Fq-operations, where the O~ is again uniform in q.As an application, this article speeds up some computations used in the isogeny-based cryptosystems CSIDH and CSURF.
Lattices of compatibly embedded finite fields are useful in computer algebra systems for managing many extensions of a finite field Fp at once. They can also be used to represent the algebraic closure Fˉp, and to represent all finite fields in a standard manner. The most well known constructions are Conway polynomials, and the Bosma-Cannon-Steel framework used in Magma. In this work, leveraging the theory of the Lenstra-Allombert isomorphism algorithm, we generalize both at the same time. Compared to Conway polynomials, our construction defines a much larger set of field extensions from a small pre-computed table; however it is provably as inefficient as Conway polynomials if one wants to represent all field extensions, and thus yields no asymptotic improvement for representing Fˉp. Compared to Bosma-Cannon-Steel lattices, it is considerably more efficient both in computation time and storage: all algorithms have at worst quadratic complexity, and storage is linear in the number of represented field extensions and their degrees. Our implementation written in C/Flint/Julia/Nemo shows that our construction in indeed practical.
Let Fq be a finite field. Given two irreducible polynomials f,g over Fq, with degf dividing degg, the finite field embedding problem asks to compute an explicit description of a field embedding of Fq[X]/f(X) into Fq[Y]/g(Y). When degf=degg, this is also known as the isomorphism problem. This problem, a special instance of polynomial factorization, plays a central role in computer algebra software. We review previous algorithms, due to Lenstra, Allombert, Rains, and Narayanan, and propose improvements and generalizations. Our detailed complexity analysis shows that our newly proposed variants are at least as efficient as previously known algorithms, and in many cases significantly better. We also implement most of the presented algorithms, compare them with the state of the art computer algebra software, and make the code available as open source. Our experiments show that our new variants consistently outperform available software.
Inspired by previous work of Shoup, Lenstra-De Smit and Couveignes-Lercier, we give fast algorithms to compute in (the first levels of) the ell-adic closure of a finite field. In many cases, our algorithms have quasi-linear complexity.
The problem of computing an explicit isogeny between two given elliptic curves over F_q, originally motivated by point counting, has recently awaken new interest in the cryptology community thanks to the works of Teske and Rostovstev & Stolbunov. While the large characteristic case is well understood, only suboptimal algorithms are known in small characteristic; they are due to Couveignes, Lercier, Lercier & Joux and Lercier & Sirvent. In this paper we discuss the differences between them and run some comparative experiments. We also present the first complete implementation of Couveignes' second algorithm and present improvements that make it the algorithm having the best asymptotic complexity in the degree of the isogeny.
An Artin-Schreier tower over the finite field F_p is a tower of field extensions generated by polynomials of the form X^p - X - a. Following Cantor and Couveignes, we give algorithms with quasi-linear time complexity for arithmetic operations in such towers. As an application, we present an implementation of Couveignes' algorithm for computing isogenies between elliptic curves using the p-torsion.
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.