Fast evaluation of high-degree elliptic-curve isogenies

Definitions and mathematical statement

Let $q$ be a prime power and $E/{\mathbb{F}}_q$ an elliptic curve, given in a specified finite-field representation, with $P\in E({\mathbb{F}}_q)$. An isogeny $\psi:E\to E'$ is a nonconstant algebraic group morphism and has positive finite degree $D=\deg\psi$. If $E'$ and $\psi$ are defined over ${\mathbb{F}}_q$, the output $\psi(P)$ lies in $E'({\mathbb{F}}_q)$; otherwise the output extension field and its representation must be included in the problem data.

The question is to characterize representations/families of such maps permitting uniform evaluation in time polynomial in \[ \log D\quad\text{and}\quad\log q, \] ideally $O(\log D\,(\log q)^2)$. The logarithmic-degree expression is an asymptotic target for $D\ge2$; degree-one maps require a separate convention such as $1+\log D$, not a literal zero-time bound. Constant maps have degree zero and are not included in this isogeny formulation.

The representation of $\psi$ is essential. Dense rational functions of degree comparable to $D$ can have description length far exceeding $\operatorname{poly}(\log D,\log q)$; a succinct composition/circuit description is different input. The source gives neither encoding nor a cost for finding that encoding. It also does not separate preprocessing of $\psi$ from online evaluation at $P$. Unrestricted precomputed tables would make a small online lookup time an inadequate characterization. A precise theorem must therefore account for input length, preprocessing, field-operation versus bit complexity, and uniformity over $P$.

The source also says maps or isogenies, without specifying the larger map class, separability, or field of definition. Those are not silently restricted to ordinary curves or to a favorable endomorphism case. The supplied research summary reports both positive and negative results and says no general logarithmic-degree algorithm/characterization is established, especially in large-discriminant ordinary settings; it gives no precise theorem or lower-bound reference.

Short English statement

Which succinctly represented elliptic-curve isogenies can be evaluated in time polynomial in $\log\deg\psi$ and $\log q$, ideally near the stated product bound? Encoding, preprocessing, field of definition, and computation model are part of the question.

Sources

• Local UnsolvedMath registry, permanent ID $8800001$, exact source code catalogue entry, "Fast evaluation of high-degree elliptic-curve isogenies." Proposer Denis Charles.
• IPAM Workshop on Number Theory and Cryptography --- Open Problems (2006), attachment 6218, recorded PDF page 1; schedule source https://www.ipam.ucla.edu/programs/workshops/workshop-i-number-theory-and-cryptography-open-problems/?tab=schedule. Recorded access 2026-07-29; pdf-and-legacy-ppt visual-audit extraction.
• Supplied PARTIAL-PROGRESS research summary states positive/negative results exist but supplies no exact algorithm, lower bound, or complete publication citation.