CS Paper Radar

Supersingular Elliptic Curves Without Inseparable Small Degree Endomorphisms

Nicolas Swanson

cs.CR math.NT ·submitted 2026-09-03 13:36 UTC · v1
theorycode/dataunusual

Abstract

For a fixed characteristic $p$, let $δ(p)$ denote the smallest degree needed to guarantee the existence of an isogeny from any supersingular curve $E$ to its Frobenius conjugate $E^{(p)}$. We translate existence questions concerning $δ(p)$ into questions about positive definite integral ternary quadratic forms and use Voronoi's theory of perfect forms in dimension three to characterize when $δ(p)$ is nearly maximal. For sufficiently large primes, we show that $δ(p)$ attains its upper bound precisely when $p$ is represented by one of nine explicit cubic polynomials, reducing the infinitude of such primes to whether one of these cubics takes prime values infinitely often. We also prove that, for almost all primes, $δ(p)$ lies at least $p^{1/6-o(1)}$ below its upper bound.

Comment
Computational supplement available at https://github.com/Nicswansonwaterloo/MaxFrobeniusConj

Closest papers

Nearest neighbours by meaning across the whole index.

Smoothness of Shortest Isogenies to Frobenius Conjugates

cs.CR math.NT ·2026-10-15 ·Yi Ouyang, Wei Wei, Zheng Xu
similarity 0.74
Abstract

Let $E$ be chosen uniformly from the geometric isomorphism classes of supersingular elliptic curves over $\overline{\mathbb{F}}_p$ and $δ_E$ be the minimum degree of isogenies from $E$ to its Frobenius conjugate $E^{(p)}$. We establish bounds for the smoothness probability of $δ_E$ and hence affirm Wesolowski's $p^{1/3+o(1)}$ attack on the supersingular endomorphism ring problem is unconditional. We also establish a uniform asymptotic formula, with a main term expressed in terms of Dirichlet $L$ values, for the probability that a connection isogeny of degree $n$ exists between $E$ and $E^{(p)}$.

0.11

Superspecial curves of genus two over prime fields: Frobenius types and rational (2,2)-kernels

cs.CR math.NTmath.AG ·2026-11-18 ·Hung Dang
similarity 0.68
Abstract · 55 pages, 9 tables. Code, logs and data: [Zenodo DOI, add after upload]

Superspecial curves of genus two over a prime field $\mathbb{F}_p$, and the rational $(2,2)$-isogenies between their Jacobians, are the vertices and edges of the graph on which genus-two isogeny-based cryptography is built. Let $C$ be such a curve, with Jacobian $J$ and Frobenius endomorphism $π$. We show that $π^2 = p\,α_*$ for a unique automorphism $α$ of $C$ over $\mathbb{F}_p$ whose action on the Weierstrass points is the square of that of Frobenius. For $p \ge 7$ this gives the list of Frobenius types of the Weierstrass points: eight types, each with its Weil polynomial, a congruence condition on $p$, and its number 15, 3, 3, 7, 1, 1, 3 or 1 of $\mathbb{F}_p$-rational $(2,2)$-kernels; when all Weierstrass points are rational, the 2-Tate pairing on $J[2]$ is determined by $p \bmod 8$. We then prove closed formulas, in terms of class numbers of imaginary quadratic orders and of $ζ_{\mathbb{Q}(\sqrt p)}(-1)$, for the mass of the curves of each type and for the mass of the rational kernels whose quotient is a product of elliptic curves. For $π^2 = \pm p$ the total masses are due to Ibukiyama and to Xue and Yu; our proofs use the 2-adic Tate modules, the symmetry of the Richelot correspondence and Eichler's mass formula, and, for the other curves, modules over orders of a quartic CM field. The kernels are counted through gluings of supersingular elliptic curves. As a consequence, the proportion of rational kernels with decomposed quotient is of order $p^{-1/2}(1+L(1,χ))$, where $χ$ is the quadratic character of $\mathbb{Q}(\sqrt{-p})$. All formulas agree with an exact enumeration for the 37 primes $7 \le p \le 173$. Finally we describe the graph of $\mathbb{F}_p$-rational Richelot isogenies, which is far from connected in the range computed, and discuss what these results say about its use in isogeny-based cryptography.

0.33

The Supersingular Isogeny Problem in Time and Memory $p^{1/3+o(1)}$, Unconditionally

cs.CR ·2026-09-18 ·José Luis Delgado
similarity 0.66
Abstract

Given a supersingular elliptic curve $E/\mathbb{F}_{p^2}$, the $\mathsf{OneEnd}$ problem asks for a non-scalar endomorphism of $E$. By known reductions, solving this problem also solves the supersingular endomorphism ring and isogeny problems. Wesolowski obtained exponent $1/3$ under an assumption on the factorization of a small degree, whereas the previous unconditional exponent was $2/5$. We give a Las Vegas algorithm, analyzed without a smoothness heuristic, with expected time and memory \[ p^{1/3}\exp\bigl(O(\sqrt{\log p\,\log\log p})\bigr) = p^{1/3+o(1)}. \] The algorithm fixes in advance a family of degrees that are products of small primes. Known counting results provide many isogenies of these degrees from curves to their Frobenius conjugates, and a collision estimate shows that the isogenies occur on sufficiently many distinct curves for a random walk to reach one of them. From such a curve, the algorithm splits a degree into two parts, enumerates two lists of shorter isogenies, and matches their targets to obtain an isogeny to the conjugate, whose composition with Frobenius gives the required endomorphism.

0.16

Memetic Search for Supersingular Elliptic Curves over $\mathbb{F}_p$

cs.CR ·2026-09-03 ·Ismel Martínez-Díaz
unusual similarity 0.59
Abstract

The search for supersingular elliptic curves is a fundamental computational problem in isogeny-based cryptography. A recent metaheuristic formulation over $\mathbb{F}_{p^2}$ introduced the NonMultiplicity Distance (NMD) objective, measuring the deviation of the Frobenius trace from a multiple of $p$, and showed that uninformed random search fails beyond $\approx 10^{13}$ candidates. This work investigates metaheuristic search over the prime field $\mathbb{F}_p$, the setting for oriented isogeny protocols such as CSIDH, OSIDH, and SQISign. Although the candidate space decreases from $p^2$ to $p$, the supersingular locus is asymptotically sparse ($O(\sqrt{p}\log p)$ curves), keeping the search exponentially difficult. We formulate a memetic algorithm tailored to $\mathbb{F}_p$ using a one-dimensional $j$-invariant chromosome, bit-level recombination, adaptive mutation, and periodic local search under the NMD objective. Benchmarks across 30 independent seeds at 40-bit, 46-bit, and 51-bit prime sizes ($p \approx 1.13\times 10^{15}$) show that the algorithm discovers an exact supersingular curve at 46 bits and consistently converges to ``near-supersingular'' ordinary curves with Frobenius traces remarkably close to zero: best NMD values of 19 at 40 bits and 3 at 51 bits, corresponding to relative trace deviations of $1.3\times 10^{-5}$ and $4.5\times 10^{-8}$ across the Hasse interval. These results demonstrate that NMD-driven memetic search effectively navigates the sparse $\mathbb{F}_p$ landscape and systematically locates near-supersingular structures.

0.35

A linear-in-$q$ range of dimensions for the MDS conjecture over $\mathbb F_q$ in odd characteristic

cs.IT math.CO ·2026-09-22 ·Xiang Fan
theory similarity 0.58
Abstract · 23 pages. The proof has been reorganized to make its homological structure explicit. Other versions of this preprint are available on Zenodo…

Let $q$ be a power of an odd prime $p$. We prove the MDS conjecture over $\mathbb F_q$ in every dimension $k$ satisfying \[ 2\leqslant k\leqslant B(p,q) \quad\text{or}\quad q+2-B(p,q)\leqslant k\leqslant q, \qquad B(p,q)=\left\lfloor\frac{(p-2)q+6p-10}{2p-3}\right\rfloor. \] For fixed $p$, the first interval is linear in $q$; together with duality, the theorem covers an asymptotic proportion $1-1/(2p-3)$ of all dimensions. The proof rests on a vanishing theorem for determinant relations over an arbitrary field of characteristic $p>0$. It yields full row rank for Chowdhury's matrices over a larger range of arc sizes. In particular, at $|G|=2k-3+n$ it proves Chowdhury's full-row-rank conjecture without the $q$-dependent restriction. Specialization to $\mathbb F_q$, together with the Ball--Lavrauw construction, gives the stated MDS range. We also prove that, for every odd prime power $q$, every normal rational curve in $\mathrm{PG}(N,q)$ is complete for $2\leqslant N\leqslant q-2$, and every projective Reed--Solomon code of length $q+1$ and dimension $2\leqslant k\leqslant q-2$ has covering radius $q-k$.

0.59

Cubic lower bounds for the permanent in odd characteristic, for Pfaffian representations, and for polynomial entries

cs.CC math.AC ·2026-10-29 ·Karthik Sheshadri
theory similarity 0.58
Abstract · 18 pages; stand-alone; submitted to International Mathematical Research Notices

The determinantal complexity of a polynomial is the order of the smallest matrix whose entries are polynomials of degree at most one and whose determinant equals the polynomial. A lower bound for the permanent in this measure is the algebraic form of the question whether the permanent is harder to compute than the determinant. Over the complex numbers, the best known lower bound grows cubically in the size of the permanent. It holds even when the permanent only has to be a limit of such determinants. I prove that the cubic lower bound holds over every algebraically closed field of odd characteristic $p$, with a constant that depends on $p$. Hence the cubic bound does not depend on characteristic zero. I also prove the bound for Pfaffians, which are square roots of determinants of skew symmetric matrices. Lower bounds for Pfaffians imply the same bounds for determinants. Further, I prove the bound, divided by $a$, for matrices whose entries are polynomials of degree at most $a$. All three results come from one lower bound for smooth hypersurfaces. I prove it in every characteristic by counting intersection points together with their multiplicities.

0.28

Small sums of roots of unity: polylogarithmic exceptional sets and conditional separation

cs.CC math.NT ·2026-10-19 ·Qi Cheng
theory similarity 0.56
Abstract

We prove a polylogarithmic exceptional-set estimate for symmetric five-term sums of roots of unity of arbitrary order. More precisely, at most $O((\log(2N))^{11})$ points of the $N$-grid satisfy $|1+2\cos(2πx)+2\cos(2πy)|<\exp(-C(\log(2N))^{13})$. This implies the corresponding bound for small conjugates at the reduced conductor: outside polylogarithmically many real embeddings, every such sum is at least quasipolynomially large. The proof is unconditional and combines a polynomial-vector-field multiplicity estimate, arithmetic jet determinants, analytic propagation, and interpolation determinants for nearby grid points. As a companion result, assuming a uniform number-field $abc$ conjecture, we prove that every sum of a fixed number of distinct prime-order roots of unity has modulus at least $\exp(-\varepsilon p)$ for every $\varepsilon>0$ and all sufficiently large primes $p$, uniformly in the exponents. That proof uses simultaneous compression of the exponents, discriminant estimates, and cyclic resultants.

0.34

Geometric Obstructions and Sharp Genus Dependence in LCD Scalings

cs.IT math.AG ·2026-11-03 ·Rahim Rahmati-Asghar
theory similarity 0.56
Abstract · All comments are welcome

We study the least pole order of a rational function whose nonzero evaluations scale a prescribed code to a Euclidean LCD code. A residue-one differential yields an obstruction for odd-dimensional one-point AG codes in characteristic two: for $C=C_L(D,aQ)$ with $0\le a<n$ and odd dimension, the threshold is at least $n+2g-a-1$. The obstruction uses alternating Gram matrices and does not require the scaled code to be self-orthogonal. For the dimension-three codes $C_L(D,(r+1)Q)$ on Hermitian curves over $\F_{r^2}$, $r=2^e\ge4$, we obtain \[ n+2g-r-2\leτ_D(C;Q)\le n+2g-3. \] Consequently the leading genus contribution is asymptotically sharp even in dimension three. On the elliptic curve $y^2+y=x^3$ over $\F_4$, we prove the exact dimension-three threshold $6$ by an explicit multiplier. For repetition codes on the Hermitian family, the threshold equals the general interpolation bound $n+2g-1$. The upper bounds use information sets and hold for $q>3k$, and for $q>2k$ in characteristic two.

0.07