Fast computation of isomorphisms between finite fields using elliptic curves

DOI10.1007/978-3-030-05153-2_4MaRDI QIDQ1725937zbMATH OpenOpenAlexFDO

Authors Anand Kumar Narayanan

Publication date 15 February 2019

Full work available at URL https://arxiv.org/abs/1604.03072

Mathematics Subject Classification ID

Curves over finite and local fields (11G20) Structure theory for finite fields and commutative rings (number-theoretic aspects) (11T30)

Abstract: We propose a randomized algorithm to compute isomorphisms between finite fields using elliptic curves. To compute an isomorphism between two fields of cardinality $q^n$, our algorithm takes ${\displaystyle }$n^{1+o(1)} log^{1+o(1)}q + max_{ell} left(ell^{n_ell + 1+o(1)} log^{2+o(1)} q + O(ell log^5q) ight)${\displaystyle }$ time, where $ell$ runs through primes dividing $n$ but not $q(q-1)$ and $n_{e}ll$ denotes the highest power of $ell$ dividing $n$. Prior to this work, the best known run time dependence on $n$ was quadratic. Our run time dependence on $n$ is at worst quadratic but is subquadratic if $n$ has no large prime factor. In particular, the $n$ for which our run time is nearly linear in $n$ have natural density at least $3/10$. The crux of our approach is finding a point on an elliptic curve of a prescribed prime power order or equivalently finding preimages under the Lang map on elliptic curves over finite fields. We formulate this as an open problem whose resolution would solve the finite field isomorphism problem with run time nearly linear in $n$.

Recommendations

• Finding Isomorphisms Between Finite Fields
• scientific article; zbMATH DE number 1210368
• Fast computation of elliptic curve isogenies in characteristic two
• Computing isomorphisms and embeddings of finite fields
• Fast algorithms for computing isogenies between elliptic curves

Cited in

(6)

• Fast computation of elliptic curve isogenies in characteristic two
• Computing isomorphisms and embeddings of finite fields
• On the hardness of the finite field isomorphism problem
• Computing isogenies between elliptic curves over $F_{p^n}$ using Couveignes's algorithm
• On the complexity exponent of polynomial system solving
• Fast algorithms for computing isogenies between ordinary elliptic curves in small characteristic

This page was built for publication: Fast computation of isomorphisms between finite fields using elliptic curves

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1725937)