# The supersingular Endomorphism Ring and One Endomorphism problems are equivalent

Aurel Page, Benjamin Wesolowski

► To cite this version:

Aurel Page, Benjamin Wesolowski. The supersingular Endomorphism Ring and One Endomorphism problems are equivalent. Advances in Cryptology – EUROCRYPT 2024, May 2024, Zurich (CH), Switzerland. pp.388-417, 10.1007/978-3-031-58751-1_14. hal-04209824v2

HAL Id: hal-04209824

https://inria.hal.science/hal-04209824v2

Submitted on 12 Oct 2023

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
# The supersingular Endomorphism Ring and One Endomorphism problems are equivalent

Aurel Page<fnref n="1" /> and Benjamin Wesolowski<fnref n="2" />

**Abstract.** The supersingular Endomorphism Ring problem is the following: given a supersingular elliptic curve, compute all of its endomorphisms. The presumed hardness of this problem is foundational for isogeny-based cryptography. The One Endomorphism problem only asks to find a single non-scalar endomorphism. We prove that these two problems are equivalent, under probabilistic polynomial time reductions.

We prove a number of consequences. First, assuming the hardness of the endomorphism ring problem, the Charles-Goren-Lauter hash function is collision resistant, and the SQIsign identification protocol is sound. Second, the endomorphism ring problem is equivalent to the problem of computing arbitrary isogenies between supersingular elliptic curves, a result previously known only for isogenies of smooth degree. Third, there exists an unconditional probabilistic algorithm to solve the endomorphism ring problem in time $\tilde{O}(p^{1/2})$, a result that previously required to assume the generalized Riemann hypothesis.

To prove our main result, we introduce a flexible framework for the study of isogeny graphs with additional information. We prove a general and easy-to-use rapid mixing theorem.

# 1 Introduction

The endomorphism ring problem lies at the foundation of isogeny-based cryptography. On one hand, its presumed hardness is necessary for the security of all cryptosystems of this family (see for instance the reductions in [Wes22a]). On the other hand, many cryptosystems of this family can be proven secure if this problem (or some variant) is hard (the earliest example being [CLG09]). Isogeny-based cryptography takes its name from the *isogeny problem*. An isogeny is a certain kind of map between two elliptic curves, and the isogeny problem consists in finding such a map, given the two curves. Formalising the meaning of “finding an isogeny” can lead to several versions of the isogeny problem, the most prominent being the *ℓ-isogeny path problem*. In isogeny-based cryptography, one typically restricts to supersingular elliptic curves, for which this problem is believed to be hard.

Fix a supersingular elliptic curve $E$. An endomorphism of $E$ is an isogeny from $E$ to itself (or the zero morphism). The collection of all endomorphisms of

<footnote n="1">¹ Univ. Bordeaux, CNRS, INRIA, Bordeaux INP, IMB, UMR 5251, F-33400 Talence, France</footnote>

<footnote n="2">² ENS de Lyon, CNRS, UMPA, UMR 5669, Lyon, France</footnote>
$E$ forms the endomorphism ring $End(E)$. The *supersingular endomorphism ring problem*, or $ENDRING$, consists in computing $End(E)$, when given $E$. Assuming the generalised Riemann hypothesis, this problem is equivalent to the $\ell$-isogeny path problem (see [Wes22b], and the earlier heuristic equivalence [EHL$^{+18$]), cementing its importance in the field.

The endomorphism ring contains scalars $Z \subseteq \mathrm{End}(E)$, simple elements which are always easy to compute. While $ENDRING$ asks to find all endomorphisms, it has long been believed that finding even a single non-scalar endomorphism is hard. We call this the *one endomorphism problem*, or `ONEEND`. Unfortunately, former heuristic arguments suggesting that `ONEEND` should be as hard as $ENDRING$ do not withstand close scrutiny, and actually fail in simple cases. Yet, the connection between these two problems bears important consequences on the hardness of $ENDRING$, on its connection with variants of the isogeny problem, and on the security of cryptosystems such as the CGL hash function [CLG09] or the SQIsign digital signature scheme [DKL$^{+20}$].

## 1.1 Contributions

In this article, we prove the following theorem.

**Theorem 1.1.** The $ENDRING$ and `ONEEND` problems are equivalent, under probabilistic polynomial time reductions.

Formal definitions are provided in Section 2, and the proof is the object of Section 7. The reduction from `ONEEND` to $ENDRING$ is obvious, and the other direction is stated more precisely in Theorem 7.2. As a consequence of the main theorem, we prove the following:

- If $ENDRING$ is hard, then the CGL hash function is collision resistant (Theorem 8.1), and the SQIsign identification scheme is sound (Theorem 8.2). Previous security proofs relied on the hardness of `ONEEND` (see [DKL$^{+20}$, Theorem 1]), or on flawed heuristic reductions (see [EHL$^{+18}$, Algorithm 8], and the flaws discussed Section 1.2). This is the object of Section 8.1 and Section 8.2.

- $ENDRING$ reduces to the isogeny problem (Theorem 8.5). Here, the isogeny problem refers to the problem of finding *any* isogeny between two elliptic curves. Previous results [EHL$^{+18}$,Wes22b] only applied to isogenies of smooth degree (like the $\ell$-isogeny path problem), and were conditional on the generalised Riemann hypothesis. This is the object of Section 8.3.

- There is an algorithm solving $ENDRING$ in expected time $\tilde{O}(p^{1/2})$ (Theorem 8.7), where $p > 0$ is the characteristic. Previous algorithms were conditional on the generalised Riemann hypothesis (via the conditional equivalence with the $\ell$-isogeny path problem [Wes22b]; see also [FIK$^{+23}$, Theorem 5.7] for a more direct approach). Previous unconditional algorithms ran in time $\tilde{O}(p)$ and only returned a full-rank subring [Koh96, Theorem 75]. This is the object of Section 8.4.
Our main technical tool is an equidistribution result for isogeny walks in
the graph of supersingular elliptic curves equipped with an endomorphism mod-
ulo N. In fact, we prove a more general equidistribution result generalising the
classical one (see [Mes86,Piz90] and Proposition 2.7), which we think is of inde-
pendent interest. We state this result informally here, refering the reader to the
body of the paper for a formal statement.

**Definition 1.2.** Equipping the set of supersingular elliptic curves with extra data consists in defining for each such curve $E$ a finite set $\mathcal{F}(E)$, and for every isogeny $\varphi: E \to E'$ a map $\mathcal{F}(\varphi): \mathcal{F}(E) \to \mathcal{F}(E')$, compatible under composition of isogenies (see Definitions 2.8 and 3.1). We obtain the isogeny graph $\mathcal{G}_{\mathcal{F}}$ of pairs $(E, x)$ where $x \in \mathcal{F}(E)$ (see Definition 3.4).

Let $N \ge 1$ be an integer. The extra data satisfies the (mod $N$)-congruence property if for every curve $E$, pairs of endomorphisms of $E$ that are congruent modulo $N$ act identically on $\mathcal{F}(E)$ (see Definition 3.7).

Our equidistribution result, stated informally, reads as follows.

**Theorem 1.3.** Let $N \ge 1$ be an integer. Random walks in the isogeny graph of supersingular elliptic curves equipped with extra data satisfying the (mod $N$)-congruence property equidistribute optimally.

We refer to Theorem 3.10 for a formal statement. The optimality refers to the fact that the graphs can be disconnected or multipartite, resulting in the adjacency matrix having several forced eigenvalues (see Proposition 3.11 and Remark 3.12), but all the remaining eigenvalues are as small as possible. A similar general result was recently proved by Codogni and Lido [CL23], so we point out some similarities and differences. In [CL23], the extra data needs to be expressed in terms of $N$-torsion points (a level structure), whereas we allow for extra data of arbitrary nature, only requiring it to satisfy a simple property (the (mod $N$)-congruence property). We hope that this makes our theorem flexible, and easy to use in a variety of situations. In particular, the extra data used in our main application trivially fits within our framework; in contrast, this data is not a level structure, so does not directly fit the framework of [CL23]. Moreover, we allow $p$ to divide $N$, contrary to the results in [CL23]. Both proofs use Deligne’s bounds, but the proof in [CL23] is purely algebro-geometric, whereas ours proceeds via the Deuring correspondence and the Jacquet–Langlands correspondence; as a result, the two proofs could have different interesting generalisations.

**1.2 Technical overview**

The ideas behind our reduction are as follows. Assume we have an oracle $\mathcal{O}$ for ONEEND and we want to compute End$(E)$ for a given $E$.

The ring End$(E)$ is a lattice of dimension 4 and volume $p/4$. Computing End$(E)$ consists in finding a basis: four endomorphisms that generate all the others. Given a collection of endomorphisms, one can compute the volume of the lattice they generate, and easily check whether they generate End$(E)$.
**A first flawed attempt.** We thus need a way to generate several endomorphisms of $E$. Naively, one could repeatedly call $\mathcal{O}(E)$, hoping to eventually obtain a generating set. This can fail, for instance if the oracle is deterministic and $\mathcal{O}(E)$ always returns the same endomorphism.

To circumvent this issue, it was proposed in [EHL+18] to randomise the curve. More precisely, one constructs a richer, randomised oracle $\text{RICH}^{\mathcal{O}}$ from $\mathcal{O}$ as follows. On input $E$, walk randomly on the 2-isogeny graph, resulting in an isogeny $\varphi: E \to E'$. This graph has rapid mixing properties, so $E'$ is close to uniformly distributed among supersingular curves. Now, call the oracle $\mathcal{O}$ on $E'$, to get an endomorphism $\beta \in \text{End}(E')$. The composition $\alpha = \hat{\varphi} \circ \beta \circ \varphi$ is an endomorphism of $E$, the output of $\text{RICH}^{\mathcal{O}}$.

With this randomisation, there is hope that calling $\text{RICH}^{\mathcal{O}}$ repeatedly on $E$ could yield several independent endomorphisms that would eventually generate $\text{End}(E)$. This method is essentially [EHL+18, Algorithm 8]. In that article, it is heuristically assumed that endomorphisms produced by $\text{RICH}^{\mathcal{O}}$ are very nicely distributed, and they deduce that a generating set for $\text{End}(E)$ is rapidly obtained. This heuristic has a critical flaw: one can construct oracles that contradict it. Consider an integer $M > 1$, and suppose that for any input $E$, the oracle $\mathcal{O}$ returns an endomorphism from the strict subring $\mathbb{Z}+M\text{End}(E)$. Then, the above algorithm would fail, because the randomisation $\text{RICH}^{\mathcal{O}}$ would still be stuck within the subring $\mathbb{Z}+M\text{End}(E)$. Worse, juggling with several related integers $M$, we will see that there are oracles for which this algorithm only stabilises after an exponential time.

**Identifying and resolving obstructions.** The core of our method rests on the idea that this issue is, in essence, the only possible obstruction. The key is *invariance by conjugation*. If $\varphi, \varphi': E \to E'$ are two random walks of the same length, and $\beta$ is an endomorphism of $\text{End}(E')$, the elements $\alpha = \hat{\varphi} \circ \beta \circ \varphi$ and $\alpha' = \hat{\varphi}' \circ \beta \circ \varphi'$ are equally likely outputs of $\text{RICH}^{\mathcal{O}}$. These two elements are conjugates of each other in $\text{End}(E)/N\text{End}(E)$ for any odd integer $N$, as

$$ \alpha = \frac{\hat{\varphi} \circ \hat{\varphi}'}{[\text{deg}(\varphi')]} \circ \alpha' \circ \frac{\varphi' \circ \varphi}{[\text{deg}(\varphi')]} \mod N. $$

From there, one can prove that the output of $\text{RICH}^{\mathcal{O}}$ follows a distribution that is invariant by conjugation: each output is as likely as any of its conjugates, modulo odd integers $N$ (up to some bound). Intuitively, for the outputs of $\text{RICH}^{\mathcal{O}}$ to be “stuck” in a subring (such as $\mathbb{Z}+M\text{End}(E)$ above), that subring must itself be stable by conjugation (modulo odd integers $N$). There comes the next key: every subring of $\text{End}(E)$ (of finite index not divisible by $p$) stable by conjugation modulo all integers is of the form $\mathbb{Z}+M\text{End}(E)$. From a basis of $\mathbb{Z}+M\text{End}(E)$, it is easy to recover a basis of $\text{End}(E)$ essentially by dividing by $M$ (using a method due to Robert [Rob22] that stems from the attacks on SIDH).

This intuition does not immediately translate into an algorithm, as an oracle could be “bad” without really being stuck in a subring. Imagine an oracle that
outputs an element of $Z+2^e \operatorname{End}(E)$ (and not in $Z+2^{e+1} \operatorname{End}(E)$) with probability $2^{e-n}$ for each $e \in [0, \dots, n-1]$. A sequence of samples $(\alpha_i)_i$ could eventually generate $\operatorname{End}(E)$, but only after an amount of time exponential in $n$. This particular case could be resolved as follows: for each sample $\alpha$, identify the largest $e$ such that $\beta = (2\alpha - \operatorname{Tr}(\alpha))/2^e$ is an endomorphism. A sequence of samples $(\beta_i)_i$ could rapidly generate $Z+2 \operatorname{End}(E)$, from which one easily recovers $\operatorname{End}(E)$. This resolution first identifies the prime 2 as the source of the obstruction, then "reduces" each sample "at 2". In general, such obstructive primes would appear as factors of $\operatorname{disc}(\alpha)$. Identifying these primes, and ensuring that each sample is "reduced" at each of them, one gets, in principle, a complete algorithm. However, factoring $\operatorname{disc}(\alpha)$ could be hard. Instead, we implement an optimistic approach: we identify obstructive pseudo-primes using a polynomial time partial-factoring algorithm. The factors may still be composite, but it is fine: the algorithm will either behave as if they were prime, or reveal a new factor.

**Equidistribution in isogeny graphs.** The technical core of our result is the proof that the distribution of $\operatorname{RICH}^\theta$ is indeed invariant by conjugation. It is a consequence of Theorem 1.3, our general equidistribution result. The proof of Theorem 1.3 proceeds as follows. We use a categorical version of the Deuring correspondence to bring everything to the quaternion world. We then use a technical result (Theorem 3.27) to show that extra data satisfying the congruence property yield graphs isomorphic to special ones constructed from quaternionic groups. Finally, these special graphs are directly related to automorphic forms, so we can apply the Jacquet–Langlands correspondence and Deligne’s bounds on coefficients of modular forms. The resulting bounds on the eigenvalues of the adjacency operators give the desired fast mixing result.

## Acknowledgements

The authors would like to thank Damien Robert for discussions about this project. The authors were supported by the Agence Nationale de la Recherche under grant ANR MELODIA (ANR-20-CE40-0013), ANR CIAO (ANR-19-CE48-0008), and the France 2030 program under grant agreement No. ANR-22-PETQ-0008 PQ-TLS.

# 2 Preliminaries

## 2.1 Notation

We write $Z$, $Q$, $R$ and $C$ for the ring of integers, the fields of rational, real, and complex numbers. For any prime $\ell$, we write $Z_\ell$ and $Q_\ell$ for the ring of $\ell$-adic integers and the field of $\ell$-adic numbers. For any prime power $q$, we write $F_q$ for the finite field with $q$ elements. For any field $K$, we write $\overline{K}$ for its algebraic closure. For any set $S$, we write $\#S$ for its cardinality. We write $f = O(g)$ for
the classic big O notation, and equivalently $g = \Omega(f)$ for the classic $\Omega$ notation. We also write $f = \Theta(g)$ if we have both $f = O(g)$ and $f = \Omega(g)$. We use the soft O notation $\tilde{O}(g) = \log(g)^{O(1)} \cdot O(g)$. We also write $\text{poly}(f_1, \dots, f_n) = (f_1 + \dots + f_n)^{O(1)}$. The logarithm function $\log$ is in base 2. For any ring $R$, we write $R^\times$ the multiplicative group of invertible elements, and $M_2(R)$ the ring of $2 \times 2$ matrices with coefficients in $R$.

## 2.2 Quaternion algebras

A general reference for this section is [Voi21]. A quaternion algebra over $\mathbb{Q}$ is a ring $B$ having a $\mathbb{Q}$-basis $1, i, j, k$ satisfying the multiplication rules $i^2 = a, j^2 = b$ and $k = ij = -ji$, for some $a, b \in \mathbb{Q}^\times$. Let $w = x + yi + zj + tk \in B$. The reduced trace of $w$ is $\text{trd}(w) = 2x$. The reduced norm of $w$ is $\text{ndr}(w) = x^2 - ay^2 - bz^2 - abt^2$. The reduced norm map is multiplicative.

A lattice in a $\mathbb{Q}$-vector space $V$ of finite dimension $d$ is a subgroup $L \subset V$ of rank $d$ over $\mathbb{Z}$ and such that $V = L\mathbb{Q}$. The discriminant of a lattice $L$ in $B$ is $\text{disc}(L) = \det(\text{trd}(b_ib_j)) \neq 0$ where $(b_i)$ is a $\mathbb{Z}$-basis of $L$. When $L' \subset L$ is a sublattice, we have $\text{disc}(L') = [L : L']^2 \text{disc}(L)$.

An order in $B$ is a subring $O \subset B$ that is also a lattice. A maximal order is an order that is not properly contained in another order.

The algebra $B$ is ramified at $\infty$ if $B \otimes \mathbb{R} \not\cong M_2(\mathbb{R})$. Let $\ell$ be a prime number. The algebra $B$ is ramified at $\ell$ if $B_\ell := B \otimes_{\mathbb{Q}_\ell} \not\cong M_2(\mathbb{Q}_\ell)$. If $\ell$ is unramified and $O$ a maximal order, then $O_\ell := O \otimes_{\mathbb{Z}_\ell} \cong M_2(\mathbb{Z}_\ell)$. The discriminant of a maximal order in $B$ is the square of the product of the ramified primes of $B$. When $B$ is ramified at $\infty$, the quadratic form $\text{ndr}$ is positive definite, and for every lattice $L$ in $B$, the volume $\text{Vol}(L)$ satisfies $\text{disc}(L) = 16 \text{Vol}(B)^2$.

## 2.3 Elliptic curves

A general reference for this section is [Sil86]. An elliptic curve over a field $K$ is a genus 1 projective curve with a specified base point $O$. An elliptic curve has a unique group law (defined algebraically) with neutral element $O$. An algebraic morphism between elliptic curves (preserving the base point) is automatically a group morphism, and is either a constant map or has a finite kernel. In the latter case, we say that the morphism is an isogeny. The degree of an isogeny $\varphi$, written $\deg(\varphi)$, is its degree as a rational map. If $\varphi$ is separable, we have $\deg(\varphi) = \#\ker(\varphi)$. An isogeny of degree $d$ is also called a $d$-isogeny. For every integer $n \neq 0$, the multiplication-by-$n$ map $[n]: E \to E$ is an isogeny of degree $n^2$. Every isogeny $\varphi: E \to E'$ has a dual isogeny $\hat{\varphi}: E' \to E$ such that $\varphi\hat{\varphi} = [\deg \varphi]$ and $\hat{\varphi}\varphi = [\deg \varphi]$. An endomorphism of an elliptic curve $E$ is a morphism from $E$ to $E$. We denote $\text{End}(E)$ the ring of endomorphisms of $E$ defined over $\overline{K}$. The degree map is a positive definite quadratic form on $\text{End}(E)$. For $\alpha \in \text{End}(E)$, the endomorphism $\alpha + \hat{\alpha}$ equals the multiplication map by an integer, the trace $\text{Tr}(\alpha)$ of $\alpha$, and we have $\text{Tr}(\alpha)^2 \leq 4 \deg(\alpha)$; we also define the discriminant $\text{disc}(\alpha) = \text{Tr}(\alpha)^2 - 4 \deg(\alpha)$, which satisfies $|\text{disc}(\alpha)| \leq 4 \deg(\alpha)$ and $\text{disc}(\alpha + [n]) = \text{disc}(\alpha)$ for all $n \in \mathbb{Z}$. If the characteristic of $K$ is not 2 or 3, we have $\text{Aut}(E) = \{\pm 1\}$ for
all $E$, except two isomorphism classes over $\overline{K}$ having respectively $\# \mathrm{Aut}(E) = 6$
and $\# \mathrm{Aut}(E) = 4$.

Assume that $K$ has positive characteristic $p$ and let $E$ be an elliptic curve
over $K$. We say that $E$ is *supersingular* if $\mathrm{End}(E)$ is an order in a quaternion
algebra. In this case, $B = \mathrm{End}(E) \otimes \mathbb{Q}$ is a quaternion algebra over $\mathbb{Q}$ with
ramification set $\{p, \infty\}$, the ring $\mathrm{End}(E)$ is a maximal order in $B$, and $E$ is
defined over $\mathbb{F}_{p^2}$. When we see a nonzero endomorphism $\alpha \in \mathrm{End}(E)$ as a
quaternion $a \in B$, we have $\deg(\alpha) = \mathrm{nrd}(a)$ and $\mathrm{Tr}(\alpha) = \mathrm{trd}(a)$.

## 2.4 Computing with isogenies

Let us formalise how one can computationally encode isogenies. All we need is
a notion of *efficient representation*: some data efficiently represents an isogeny
if it allows to evaluate it efficiently on arbitrary inputs.

**Definition 2.1 (Efficient representation).** Let $\mathcal{A}$ be an algorithm, and
let $\varphi : E \to E'$ be an isogeny over a finite field $\mathbb{F}_q$. An efficient representa-
tion of $\varphi$ (with respect to $\mathcal{A}$) is some data $D_\varphi \in \{0,1\}^*$ such that

- $D_{\varphi} \in \{0,1\}^*$ has size polynomial in $\log(\deg(\varphi))$ and $\log q$, and

- on input $D_{\varphi}$ and $P \in E(\mathbb{F}_{q^k})$, the algorithm $\mathcal{A}$ returns $\varphi(P)$, and runs in polynomial time in $\log(\deg(\varphi))$, $\log q$, and $k$.

*Remark 2.2.* When we say that an isogeny is in efficient representation, the algorithm $\mathcal{A}$ is often left implicit. There are only a handful of known algorithms to evaluate isogenies, so one can think of $\mathcal{A}$ as an algorithm that implements each of these, and $D_\varphi$ would start with an indicator of which algorithm to use.

We will use the following proposition.

**Proposition 2.3.** There is an algorithm DIVIDE which takes as input

- a supersingular elliptic curve $E/\mathbb{F}_{p^2}$,

- an endomorphism $\alpha$ of $E$ in efficient representation, and

- an integer $N$,

and returns an efficient representation of $\alpha/N$ if $\alpha \in N \mathrm{End}(E)$, and $\perp$ other-
wise, and runs in time polynomial in the length of the input.

*Proof.* This is the division algorithm introduced by Robert [Rob22] that was de-
rived from the attacks on SIDH [CD23,MMP$^+23$,Rob23]. Note that in [Rob22],
the algorithm is only presented for particular endomorphisms (translates of the
Frobenius), but it works, mostly unchanged, in all generality. The general state-
ment and detailed proof can be found in [HLMW23].
$\square$
## 2.5 Computational problems

The endomorphism ring problem is the following.

**Problem 2.4 (ENDRING)** Given a prime $p$ and a supersingular elliptic curve $E$ over $\mathbb{F}_{p^2}$, find four endomorphisms in efficient representation that form a basis of $\mathrm{End}(E)$ as a lattice.

As the endomorphism ring problem asks to find, in a sense, all the endomorphisms, it is natural to study the problem of finding even a single one. Scalar multiplications $[m]$ for $m \in \mathbb{Z}$ are trivial to find, so we exclude them.

**Problem 2.5 (ONEEND)** Given a prime $p$ and a supersingular elliptic curve $E$ over $\mathbb{F}_{p^2}$, find an endomorphism in $\mathrm{End}(E) \setminus \mathbb{Z}$ in efficient representation.

There exists arbitrarily large endomorphisms, so it is convenient to introduce a bounded version of this problem. Given a function $\lambda$: $\mathbb{Z}_{>0} \to \mathbb{Z}_{>0}$, the ONEEND$_\lambda$ problem denotes the ONEEND problem where the solution $\alpha$ is required to satisfy $\log(\deg \alpha) \le \lambda(\log p)$ (in other words, the length of the output is bounded by a function of the length of the input).

The $\ell$-isogeny path problem is a standard problem in isogeny-based cryptography. Fix a prime $\ell$. An $\ell$-isogeny path is a sequence of isogenies of degree $\ell$ such that the target of each isogeny is the source of the next.

**Problem 2.6 (ℓ-ISOGENYPATH)** Given a prime $p$ and two supersingular elliptic curves $E$ and $E'$ over $\mathbb{F}_{p^2}$, find an $\ell$-isogeny path from $E$ to $E'$.

## 2.6 Probabilities

Given a random variable $X$ with values in a discrete set $\mathcal{X}$, we say it has distribution $f$ if $f(x) = \mathrm{Pr}[X = x]$ for every $x \in \mathcal{X}$. We also write $f(A) = \sum_{x \in A} f(x)$ for any $A \subseteq \mathcal{X}$. For two distributions $f_1$ and $f_2$ over the same set $\mathcal{X}$, their statistical distance (or total variation distance) is

$$ \frac{1}{2} \|f_1 - f_2\|_1 = \frac{1}{2} \sum_{x \in \mathcal{X}} |f_1(x) - f_2(x)| = \sup_{A \subseteq \mathcal{X}} |f_1(A) - f_2(A)|. $$

Random walks play a key role in isogeny-based cryptography. Fix a field $\mathbb{F}_{p^2}$ and a prime number $\ell \neq p$. The supersingular $\ell$-isogeny graph has vertices the (finitely many) isomorphism classes of supersingular elliptic curves over $\mathbb{F}_{p^2}$, and edges are the $\ell$-isogenies between them (up to isomorphism of the target). At the heart of the Charles-Goren-Lauter hash function [CLG09], one of the first isogeny-based constructions, lies the fact that random walks in supersingular $\ell$-isogeny graphs have rapid-mixing properties: they are Ramanujan graphs. This is the following well-known proposition. It is a particular case of our more general Theorem 3.10.
**Proposition 2.7.** Let $E$ be a supersingular elliptic curve over $\mathbb{F}_{p^2}$, and $\ell \neq p$ a prime number. Let $\varepsilon > 0$. There is a bound $n = O(\log_{\ell}(p) - \log_{\ell}(\varepsilon))$ such that the endpoint of a uniform random walk of length at least $n$ from $E$ in the $\ell$-isogeny graph is at statistical distance at most $\varepsilon$ from the stationary distribution $f$, which satisfies $f(E) = \frac{24}{(p-1)\#\mathrm{Aut}(E)}$.

*Proof.* This is a standard consequence of Pizer's proof that the supersingular $\ell$-isogeny graph is Ramanujan [Piz90]. Details can be found, for instance, in [BCC$^+$23, Theorem 11] for the length of the walk, and in [BCC$^+$23, Theorem 7, Item 2] for the description of the stationary distribution. $\square$

The stationary distribution is at statistical distance $O(1/p)$ of the uniform distribution. Note that rejection sampling allows to efficiently transform a sampler for the stationary distribution into a sampler for the uniform distribution.

## 2.7 Categories

A general reference for this section is [ML98]. A category $\mathcal{C}$ consists of objects, for every objects $x, y \in \mathcal{C}$, a set of morphisms $\mathrm{Hom}_{\mathcal{C}}(x, y)$, sometimes denoted $f: x \to y$, an associative composition law for morphisms with compatible source and target, and an identity morphism $\mathrm{id}_x \in \mathrm{Hom}_{\mathcal{C}}(x, x)$ for every object $x \in \mathcal{C}$. An isomorphism is a morphism that admits a two-sided inverse. For $x, y \in \mathcal{C}$, we define the set $\mathrm{End}_{\mathcal{C}}(x) = \mathrm{Hom}_{\mathcal{C}}(x, x)$ of endomorphisms of $x$, the set $\mathrm{Isom}_{\mathcal{C}}(x, y)$ of isomorphisms from $x$ to $y$, the group $\mathrm{Aut}_{\mathcal{C}}(x) = \mathrm{Isom}_{\mathcal{C}}(x, x)$ of automorphisms of $x$. Let $\mathcal{C}, \mathcal{D}$ be categories. A functor $\mathcal{F}: \mathcal{C} \to \mathcal{D}$ is an association of an object $\mathcal{F}(x) \in \mathcal{D}$ for every object $x \in \mathcal{C}$, and of a morphism $\mathcal{F}(f): \mathcal{F}(x) \to \mathcal{F}(y)$ for every morphism $f: x \to y$ in $\mathcal{C}$, that respects composition<fnref n="3" /> and identities. Functors can be composed in the obvious way.

Let Sets be the category of sets. The following is a standard construction.

**Definition 2.8.** Let $\mathcal{C}$ be a category and $\mathcal{F}: \mathcal{C} \to \mathrm{Sets}$ be a functor. The category of elements $\mathrm{El}(\mathcal{F})$ is the category with

- objects: pairs $(c, x)$ where $c \in \mathcal{C}$ and $x \in \mathcal{F}(c)$;

- morphisms $(c, x) \to (c', x')$: morphisms $f \in \mathrm{Hom}_{\mathcal{C}}(c, c')$ s.t. $\mathcal{F}(f)(x) = x'$.

This category is equipped with the natural forgetful functor $\mathrm{El}(\mathcal{F}) \to \mathcal{C}$.

*Remark 2.9.* One could also use the contravariant version of this definition. All our results would hold in this setting, as one can compose $\mathcal{F}$ with the isogeny duality to reverse the direction of all morphisms.

Let $\mathcal{F}, \mathcal{F}': \mathcal{C} \to \mathcal{D}$ be functors. A morphism of functors $\psi: \mathcal{F} \to \mathcal{F}'$ is a collection $\psi = (\psi_x)_{x \in \mathcal{C}}$ of morphisms $\psi_x: \mathcal{F}(x) \to \mathcal{F}'(x)$ in $\mathcal{D}$ such that for every morphism $f: x \to y$ in $\mathcal{C}$, we have $\mathcal{F}'(f) \circ \psi_x = \psi_y \circ \mathcal{F}(f)$. A morphism of functors is an isomorphism if and only if every $\psi_x$ is an isomorphism in $\mathcal{D}$. A

<footnote n="3">³ All our functors are covariant.</footnote>
functor $\mathcal{F}: C \to D$ is an equivalence of categories if there exists a functor $\mathcal{G}: D \to C$ and isomorphisms of functors $\mathcal{G} \circ \mathcal{F} \cong \mathrm{id}_{\mathcal{F}}$ and $\mathcal{F} \circ \mathcal{G} \cong \mathrm{id}_{\mathcal{G}}$. The functor $\mathcal{F}$ is full if all the corresponding maps $\mathrm{Hom}_{\mathcal{C}}(x, y) \to \mathrm{Hom}_{\mathcal{D}}(\mathcal{F}(x), \mathcal{F}(y))$ are surjective, and faithful if they are all injective. The functor $\mathcal{F}$ is essentially surjective if every object in $\mathcal{D}$ is isomorphic to the image of some object in $\mathcal{C}$ under $\mathcal{F}$. A functor is an equivalence if and only if it is full, faithful and essentially surjective. If $\mathcal{F}, \mathcal{F}': C \to \mathrm{Sets}$ are functors, every isomorphism of functors $\mathcal{F} \cong \mathcal{F}'$ induces an equivalence of categories $\mathrm{El}(\mathcal{F}) \cong \mathrm{El}(\mathcal{F}')$.

The categorical formulation of the Deuring correspondence [Deu41] provides the most versatile way of transferring problems from supersingular elliptic curves to quaternions. Let $\mathrm{SS}(p)$ denote the category with

- objects: supersingular elliptic curves over $\overline{\mathbb{F}}_p$;

- morphisms: algebraic group morphisms.

We fix a base curve $E_0 \in \mathrm{SS}(p)$. Let $\mathcal{O} = \mathrm{End}(E_0)$ and $B = \mathcal{O} \otimes \mathbb{Q}$.

Let $\mathrm{Mod}(\mathcal{O})$ denote the category with

- objects: invertible right $\mathcal{O}$-modules;

- morphisms: right $\mathcal{O}$-module homomorphisms.

Then we have the classical Deuring correspondence ([Voi21, Theorem 42.3.2], except we are using the covariant version; see also [Koh96, Theorem 45]).

**Theorem 2.10.** The association $E \mapsto \mathrm{Hom}(E_0, E)$, $(\varphi: E \to E') \mapsto (\psi \mapsto \varphi\psi)$ defines an equivalence of categories

$$ \mathrm{SS}(p) \to \mathrm{Mod}(\mathcal{O}). $$

## 2.8 Quaternionic automorphic forms

The following preliminaries concern the proof of our result on the equidistribution of isogeny random walks. The reader willing to admit Theorem 3.10 without proof does not need background on automorphic forms. A general reference for this section is [JL70]; a more gentle one, for Borel-type level, is [DV13, Section 3].

A Hilbert space $V$ is a complex vector space equipped with a Hermitian inner product $\langle \cdot, \cdot \rangle$, and complete for the induced norm $\| \cdot \|$, which is automatic if $V$ has finite dimension. Let $V$ be a finite-dimensional Hilbert space. The adjoint of a linear operator $T: V \to V$ is the unique operator $T^*$ satisfying $\langle Tv, w \rangle = \langle v, T^*w \rangle$ for all $v, w \in V$. A normal operator is an operator that commutes with its adjoint. The operator norm of an operator $T$ is

$$ \max_{v \neq 0} \frac{\|Tv\|}{\|v\|}. $$

Every normal operator stabilises the orthogonal complement of every stable subspace, is diagonalisable in an orthogonal basis, and has operator norm equal to the maximum absolute value of its eigenvalues.
Let $\hat{\mathbb{Z}} = \prod_{\ell} \mathbb{Z}_{\ell}$ be the profinite completion of $\mathbb{Z}$. For every abelian group $A$, we write $\hat{A} = A \otimes_{\mathbb{Z}} \hat{\mathbb{Z}}$. In particular $\hat{\mathbb{Q}} = \prod'_{\ell} \mathbb{Q}_{\ell}$ is the ring of finite adèles of $\mathbb{Q}$.

Let $N \ge 1$ be an integer, and let $U(N) = (1+N\hat{\mathbb{Z}}) \cap \hat{\mathbb{Z}}^\times$. Let $H \subset (\mathbb{Z}/N\mathbb{Z})^\times$ be a subgroup, and let $U \subset \hat{\mathbb{Z}}^\times$ be the preimage of $H$ under the quotient map $\hat{\mathbb{Z}}^\times \to \hat{\mathbb{Z}}^\times/U(N) = (\mathbb{Z}/N\mathbb{Z})^\times$. Then we have an isomorphism

$$ \mathbb{Q}_{>0}^{\times} \backslash \hat{\mathbb{Q}}^{\times} / U \cong \hat{\mathbb{Z}}^{\times} / U \cong (\mathbb{Z}/N\mathbb{Z})^{\times} / H. $$

Indeed, since every ideal of $\mathbb{Z}$ has a positive generator we have $\hat{\mathbb{Q}}^\times = \mathbb{Q}_{>0}^\times \hat{\mathbb{Z}}^\times$.

Let $B$ be a quaternion algebra over $\mathbb{Q}$. The group $\hat{B}^\times$ admits a measure $\mu$ that is bi-invariant under group translations, finite on compact subsets and nontrivial on open subsets, called its *Haar measure*.

Let $N \ge 1$ be an integer, let $U(N) = (1+N\hat{\mathcal{O}}) \cap \hat{\mathcal{O}}^\times$, which is a compact open subgroup of $\hat{B}^\times$, and let $U$ be a subgroup satisfying $U(N) \subseteq U \subseteq \hat{\mathcal{O}}^\times$. The set $B^\times \backslash \hat{B}^\times / U$ is finite. The space of automorphic forms of level $U$ is the Hilbert space $L^2(B^\times \backslash \hat{B}^\times / U)$, equipped with the inner product induced by the projection of the Haar measure:

$$ \langle F, G \rangle = \int_{b \in B^\times \backslash \hat{B}^\times / U} F(b) \overline{G(b)} \mu(bU). $$

Fix, for every $\ell$ that is unramified in $B$, an isomorphism $\mathcal{O}_\ell \cong M_2(\mathbb{Z}_\ell)$, and let $\delta_\ell \in \hat{B}^\times$ have component 1 at every $\ell' \ne \ell$ and that corresponds to $\begin{pmatrix} \ell & 0 \\ 0 & 1 \end{pmatrix}$ at $\ell$ via the chosen isomorphism. The Hecke operator

$$ T_\ell: L^2(B^\times \backslash \hat{B}^\times / U) \to L^2(B^\times \backslash \hat{B}^\times / U) $$

is defined by

$$ T_{\ell}F(B^{\times}xU) = \sum_{uU \in U\delta_{\ell}U/U} F(B^{\times}xuU), $$

and its adjoint admits the expression

$$ T_{\ell}^{*} F(B^{\times} x U) = \sum_{uU \in U \delta_{\ell}^{-1} U / U} F(B^{\times} x u U). $$

For $\ell$ that do not divide $N$, the Hecke operators $T_\ell$ are normal operators that pairwise commute.

### 3 Equidistribution of elliptic curves with extra data

The goal of this section is to prove Theorem 3.10. We state our results in Subsection 3.1. In Subsection 3.2, we set up a suitable version of the Deuring correspondence. The goal of Subsection 3.3 is to prove a technical result classifying extra data satisfying a simple property. In Subsection 3.4 we apply automorphic methods to prove the equidistribution theorem.
**3.1 Statement of the equidistribution theorem**

In order to avoid bad primes, we will need to restrict the possible degrees of
isogenies under consideration. Let $\Sigma$ be a set of primes, and let $N \ge 1$ be an
integer not divisible by any prime in $\Sigma$.

**Definition 3.1.** Let $\text{SS}_{\Sigma}(p)$ denote the category with

- objects: supersingular elliptic curves over $\overline{\mathbb{F}}_p$;

- morphisms $\text{Hom}_{\Sigma}(E, E')$: isogenies with degree a product of the primes in $\Sigma$.

Our results are expressed in terms of categories of elements of various func-
tors, as in Definition 2.8. For us, this is going to play the role of “equipping
with extra structure”: when $\mathcal{F}: \mathcal{C} \to$ Sets is a functor, $\text{El}(\mathcal{F})$ is the category of
“objects $c \in \mathcal{C}$ with extra structure taken from $\mathcal{F}(c)$”. A related definition can be
found in [LM23, Definition 2.1], formulated at the level of graphs. For us, an ad-
vantage of the category-theoretic formulation is that we can forget about $\text{SS}(p)$
and work in a quaternionic category, thanks to the Deuring correspondence.

*Example 3.2.* Assume $p \nmid N$. Let $\Sigma$ be the set of primes not dividing $N$. Define the functor $\text{Cyc}_N: \text{SS}_{\Sigma}(p) \to$ Sets by:

- $\text{Cyc}_N(E)$ is the set of cyclic subgroups of order $N$ of $E$;

- for every isogeny $\varphi \in \text{Hom}_{\Sigma}(E, E')$, the map $\text{Cyc}_N(\varphi)$ is $C \mapsto \varphi(C)$.

Then $\text{El}(\text{Cyc}_N)$ is the category of supersingular elliptic curves equipped with a cyclic subgroup of order $N$.

*Example 3.3.* Let $\Sigma$ be the set of primes not dividing $N$. Let $\text{End}/N$ denote the functor $\text{SS}_{\Sigma}(p) \to$ Sets defined by

- $(\text{End}/N)(E) = \text{End}(E)/N \text{End}(E)$;

- for $\varphi: E \to E'$, the map $(\text{End}/N)(\varphi)$ is $\alpha \mapsto \varphi\alpha\bar{\varphi}$.

Then $\text{El}(\text{End}/N)$ is the category of supersingular elliptic curves equipped with an endomorphism modulo $N$, which will play an important role in Section 4.

We now introduce the graphs of interest (more generally see Definition 3.28).

**Definition 3.4.** Let $\mathcal{F}: \text{SS}_{\Sigma}(p) \to$ Sets be a functor with $\mathcal{F}(E)$ finite for all $E$. We define the graph $\mathcal{G}_{\mathcal{F}}$ with:

- vertices: isomorphism classes of objects in $\text{El}(\mathcal{F})$;

- edges: let $(E, x) \in \text{El}(\mathcal{F})$; edges from $(E, x)$ are isogenies $\varphi \in \text{Hom}_{\Sigma}(E, E')$ modulo automorphisms of $(E', \mathcal{F}(\varphi)(x))$.

Let $L^2(\mathcal{G}_{\mathcal{F}})$ be the space of complex functions on vertices of $\mathcal{G}_{\mathcal{F}}$, and define

$$
\langle F, G \rangle = \sum_{(E,x) \in \mathcal{G}_{\mathcal{F}}} \frac{F(E, x) \overline{G(E, x)}}{\# \operatorname{Aut}(E, x)} \quad \text{for } F, G \in L^2(\mathcal{G}_{\mathcal{F}}).
$$
For every prime $\ell$, we define the adjacency operator $A_\ell$ on $L^2(\mathcal{G}_F)$ by

$$A_\ell F(E, x) = \sum_{(E,x) \to (E',x')} F(E', x'),$$

where the sum runs over edges of degree $\ell$ leaving $(E, x)$.

**Remark 3.5.** The graphs $\mathcal{G}_F$ have finitely many vertices, but infinitely many edges.

**Example 3.6.** Assume $p \nmid N$, and let $\ell$ a prime not dividing $Np$. The graph obtained from $\mathcal{G}_{\mathrm{Cyc}_N}$ by keeping only the edges of degree $\ell$ is the $\ell$-isogeny graph of supersingular elliptic curves with Borel structure studied in [Arp23] and [BCC$^+$23]. When $N=1$ this is the classical supersingular $\ell$-isogeny graph.

We are now in position to state our equidistribution theorem.

**Definition 3.7.** Let $\mathcal{F}$: $\mathrm{SS}_\Sigma(p) \to$ Sets be a functor and $N \ge 1$ an integer. We say that $\mathcal{F}$ satisfies the (mod $N$)-congruence property if for every $E \in \mathrm{SS}(p)$ and every $\varphi, \psi \in \mathrm{End}_\Sigma(E)$ such that $\varphi - \psi \in N \mathrm{End}(E)$, we have $\mathcal{F}(\varphi) = \mathcal{F}(\psi)$.

**Example 3.8.** Assume that $p$ does not divide $N$. The functor $\mathrm{Cyc}_N$ from Example 3.2 satisfies the (mod $N$)-congruence property: indeed, endomorphisms divisible by $N$ act as 0 on $N$-torsion points.

**Example 3.9.** The functor $\mathrm{End}/N$ from Example 3.3 has the (mod $N$)-congruence property: if $\varphi, \psi \in \mathrm{End}_\Sigma(E)$ and $\alpha, \beta \in \mathrm{End}(E)$ satisfy $\psi = \varphi + N\beta$, then $\psi\alpha\hat{\psi} = (\varphi + N\beta)\alpha(\hat{\varphi} + N\hat{\beta}) \in \varphi\alpha\hat{\varphi} + N\mathrm{End}(E)$, so that $(\mathrm{End}/N)(\varphi) = (\mathrm{End}/N)(\psi)$.

**Theorem 3.10.** Let $p$ be a prime and $N \ge 1$ an integer. Let $\Sigma$ be a set of primes that do not divide $N$, such that $\Sigma$ generates $(\mathbb{Z}/N\mathbb{Z})^\times$. Let $\mathcal{F}$: $\mathrm{SS}_\Sigma(p) \to$ Sets be a functor satisfying the (mod $N$)-congruence property and such that all sets $\mathcal{F}(E)$ are finite.

Then, for every $\ell \in \Sigma$ different from $p$, the adjacency operator $A_\ell$ is a normal operator on $L^2(\mathcal{G}_F)$ which stabilises the following subspaces:

- $L^2_{\mathrm{deg}}(\mathcal{G}_F)$, the subspace of functions that are constant on every connected component of the graph $\mathcal{G}_F$ obtained from $\mathcal{G}_F$ by keeping only the edges of degree 1 mod $N$. The operator norm of $A_\ell$ on $L^2_{\mathrm{deg}}(\mathcal{G}_F)$ is $\ell + 1$.

- $L^2_0(\mathcal{G}_F)$, the orthogonal complement of $L^2_{\mathrm{deg}}(\mathcal{G}_F)$. The operator norm of $A_\ell$ on $L^2_0(\mathcal{G}_F)$ is at most $2\sqrt{\ell}$.

Moreover, the $A_\ell$ for $\ell \in \Sigma$ pairwise commute.

In other words, the normalised operator $A'_\ell = \frac{1}{\ell+1}A_\ell$ makes functions rapidly converge to the subspace $L^2_{\mathrm{deg}}(\mathcal{G}_F)$. This operator $A'_\ell$ preserves the subset of probability distributions, and closely relates to the effect of a random walk of $\ell$-isogenies (see Appendix A.1). In simple cases (such as $N=1$), the space $L^2_{\mathrm{deg}}(\mathcal{G}_F)$ has dimension 1, is generated by the constant function 1 and the theorem says
that random walks in $\ell$-isogeny graphs rapidly converge to the unique stationary distribution $f$ with $f(E, x)$ proportional to $\frac{1}{\#\mathrm{Aut}(E,x)}$. One thus sees that the classical rapid-mixing property for isogeny graphs (Proposition 2.7) is a particular case of Theorem 3.10. More details and other illustrations of Theorem 3.10 are available in Appendix A.

In general $L_{\mathrm{deg}}^2(\mathcal{G}_F)$ could have higher dimension. This reflects the fact that the graph may be disconnected or multipartite, two obstructions for random walks to converge to a unique limit. To ease the application of Theorem 3.10 in such cases, we provide the following companion proposition that gives extra information on the graph $\mathcal{G}_F$ and an explicit description of the space $L_{\mathrm{deg}}^2(\mathcal{G}_F)$.

**Proposition 3.11.** With the same hypotheses and notations as in Theorem 3.10:

(1) for every isogeny $\varphi$ in $\mathrm{SS}_\Sigma(p)$, the map $\mathcal{F}(\varphi)$ is a bijection;

(2) for every $E, E' \in \mathrm{SS}(p)$, there exists $\varphi \in \mathrm{Hom}_\Sigma(E, E')$ of degree 1 mod $N$;

(3) the morphism $\mathrm{End}_\Sigma(E_0) \to (\mathrm{End}(E_0)/N \mathrm{End}(E_0))^\times$ is surjective, inducing an action of the group $G = (\mathrm{End}(E_0)/N \mathrm{End}(E_0))^\times$ on $\mathcal{F}(E_0)$.

Let $x_1, \dots, x_n$ denote representatives of the orbits of the action of $G$ on $\mathcal{F}(E_0)$ and for each $i$, let $H_i$ denote the stabiliser of $x_i$ in $G$. Let $\mathcal{G}_{\mathrm{deg}}$ denote the graph with edges labelled by elements of $(\mathbf{Z}/N\mathbf{Z})^\times$ and with

- vertex set $\bigsqcup_i (\mathbf{Z}/N\mathbf{Z})^\times / \mathrm{deg}(H_i)$;

- for every $i$, every $a \in (\mathbf{Z}/N\mathbf{Z})^\times / \mathrm{deg}(H_i)$ and every $d \in (\mathbf{Z}/N\mathbf{Z})^\times$, an edge $a \to b$ labelled by $d$, where $b = ad \in (\mathbf{Z}/N\mathbf{Z})^\times / \mathrm{deg}(H_i)$.

Then:

(4) there exists a unique morphism of graphs

$$ \mathrm{Deg}: \mathcal{G}_F \to \mathcal{G}_{\mathrm{deg}} $$

such that for all $i$ we have $\mathrm{Deg}(E_0, x_i) = 1 \in (\mathbf{Z}/N\mathbf{Z})^\times / \mathrm{deg}(H_i)$ and for every edge $\varphi$ of $\mathcal{G}_F$, the edge $\mathrm{Deg}(\varphi)$ is labelled by $\mathrm{deg}(\varphi) \bmod N$;

(5) the map $\mathrm{Deg}$ is surjective; and

(6) $L_{\mathrm{deg}}^2(\mathcal{G}_F)$ is the space of functions that factor through $\mathrm{Deg}$.

**Remark 3.12.**

- Properties (1) and (2) allow us to transfer what happens at $E_0$ to any other curve.

- Property (3) allows us to define the $H_i$. When $p \nmid N$, this can be used to relate $\mathcal{F}$ to the setup of [CL23], using an isomorphism $G \cong \mathrm{GL}_2(\mathbf{Z}/N\mathbf{Z})$. Note that when $p \mid N$, the group $(\mathcal{O}/NO)^\times$ is not isomorphic to $\mathrm{GL}_2(\mathbf{Z}/N\mathbf{Z})$.

- The graph $\mathcal{G}_{\mathrm{deg}}$ is the Cayley graph of the set $\bigsqcup_i (\mathbf{Z}/N\mathbf{Z})^\times / \mathrm{deg}(H_i)$ equipped with its natural action of $(\mathbf{Z}/N\mathbf{Z})^\times$.

- Property (4) amounts to stating the existence of a disconnectedness and a multipartition of $\mathcal{G}_F$.
- Property (5) ensures that the space of functions on $G_{\deg}$ injects into $L^2(G_{\mathcal{F}})$ via the map $\text{Deg}$.

- Using Properties (5) and (6), one easily obtains the spectra of the adjacency operators $A_\ell$ on $L_{\deg}^2(G_\mathcal{F})$: for every complex character $\chi$ of $(Z/NZ)^\times$, one obtains the eigenvalue $\chi(\ell)(\ell+1)$ with multiplicity equal to the number of $i$ such that $\chi(\text{deg}(H_i)) = 1$.

- From Proposition 3.11 and Theorem 3.10, since $2\sqrt{\ell} < \ell + 1$, one can simply deduce connectedness and multipartition properties of $G_\mathcal{F}$, its degree $\ell$ sub-graphs, etc. For instance, the graph $G_\mathcal{F}$ has exactly $n$ connected components: the preimages of the $(Z/NZ)^\times/\text{deg}(H_i)$ via the map $\text{Deg}$.

**Example 3.13.** Assume $p \nmid N$, let $\Sigma$ denote the set of all primes that do not divide $pN$, and apply Theorem 3.10 and Proposition 3.11 to $\mathcal{F} = \text{Cyc}_N$. Then we have an isomorphism $G \cong \text{GL}_2(Z/NZ)$ and a compatible bijection $\mathcal{F}(E_0) \cong \{\text{Z}/N\text{Z}-\text{lines in } (\text{Z}/N\text{Z})^2\}$. In particular, there is a single orbit ($n=1$) and, choosing $x_1$ corresponding to the line generated by $(1/\ell)$, the stabiliser $H = H_1$ corresponds to the subgroup of upper-triangular matrices, so that $\text{deg}(H) = (\text{Z}/N\text{Z})^\times$. The space $L_{\deg}^2(G_{\text{Cyc}_N})$ is therefore one-dimensional, generated by the constant function 1. Hence Theorem 3.10 recovers [BCC$^+$23, Theorem 8].

## 3.2 Adélic Deuring correspondence

Since automorphic forms are usually defined using adélic language, we will re-formulate the Deuring correspondence using adèles (Corollary 3.21).

The following terminology will be convenient.

**Definition 3.14.** A degree map on a category $C$ is the data, for every morphism $f$ of $C$, of an integer $\text{deg}(f) \in Z_{\ge 0}$ such that $\text{deg}(fg) = \text{deg}(f)\text{deg}(g)$ for every morphisms $f, g$ that can be composed, and such that $\text{deg}(\text{id}_x) = 1$ for all $x \in C$.

A functor $\mathcal{F}$ between categories equipped with degree maps is degree-preserving if $\text{deg}(\mathcal{F}(f)) = \text{deg}(f)$ for every morphism $f$.

When $C$ is a category with a degree map and $\mathcal{F}: C \to \text{Sets}$ is a functor, we equip the category of elements $\text{El}(\mathcal{F})$ with its inherited degree map.

**Remark 3.15.** In a category with a degree map, every isomorphism has degree 1.

**Example 3.16.** The category $\text{SS}(p)$ is equipped with a degree map: the usual degree for isogenies, and 0 for the zero morphism.

The following is the basic object underlying the adélic Deuring correspondence.

**Definition 3.17.** We define the category Cosets($\hat{\mathcal{O}}^\times$) with

- objects: cosets $[x] := x\hat{\mathcal{O}}^\times \in \hat{B}^\times/\hat{\mathcal{O}}^\times$ for $x \in \hat{B}^\times$;

- morphisms: $\text{Hom}([x], [y]) = B \cap y\hat{\mathcal{O}}x^{-1}$, using multiplication in $B$ as composition.
We equip the category Cosets($\hat{\mathcal{O}}^\times$) with a degree map as follows: for every $b \in \operatorname{Hom}([x], [y])$, we define the degree of $b$ to be the positive integer $\operatorname{deg}(b)$ such that $\operatorname{deg}(b)\hat{\mathbb{Z}} = \operatorname{ndr}(u)\hat{\mathbb{Z}}$ where $b = yux^{-1}$.

**Remark 3.18.** We warn the reader that a single element $b \in B$ can represent different morphisms, depending on the source $[x]$ and target $[y]$. Moreover, the degree of the morphism is in general not the reduced norm of $b$.

We reformulate the Deuring correspondence adélically as follows.

**Proposition 3.19.** The association $[x] \mapsto B \cap x\hat{\mathcal{O}}$, $g \in \operatorname{Hom}([x], [y]) \mapsto (b \mapsto gb)$ defines an equivalence of categories

$$ \operatorname{Cosets}(\hat{\mathcal{O}}^\times) \to \operatorname{Mod}(\mathcal{O}). $$

Its composition with the equivalence of Theorem 2.10 is a degree-preserving equivalence of categories

$$ \operatorname{Cosets}(\hat{\mathcal{O}}^\times) \to \operatorname{SS}(p). $$

*Proof.* The association described clearly defines a faithful functor.

We claim that the functor is full. Indeed, let $f \in \operatorname{Hom}(B \cap x\hat{\mathcal{O}}, B \cap y\hat{\mathcal{O}})$. Since every right $B$-module endomorphism of $B$ is a left multiplication by an element of $B$, there exists $g \in B$ such that $f(b) = gb$ for all $b \in B \cap x\hat{\mathcal{O}}$. Moreover, by weak approximation the closure of $B \cap x\hat{\mathcal{O}}$ in $\hat{B}$ is $x\hat{\mathcal{O}}$, so we must have $gx\hat{\mathcal{O}} \subset y\hat{\mathcal{O}}$ and therefore $g \in y\hat{\mathcal{O}}x^{-1}$, so that $g \in \operatorname{Hom}([x], [y])$ as claimed.

Finally, the functor is essentially surjective since every right invertible $\mathcal{O}$-module is isomorphic to a right invertible $\mathcal{O}$-ideal $I$, and such an ideal is locally principal and therefore of the form $I = B \cap x\hat{\mathcal{O}}$.

By examining the determinant of a morphism on the modules, we see that the equivalence preserves the degree.

□

Fix $\Sigma$ be a set of primes. Let $\hat{\mathcal{O}}_\Sigma$ denote the ring obtained from $\hat{\mathcal{O}}$ by inverting all primes in $\Sigma$. Then $\hat{\mathcal{O}} \cap \hat{\mathcal{O}}_\Sigma^\times$ is the set of elements $u \in \hat{\mathcal{O}}$ such that $\operatorname{ndr}(u)\hat{\mathbb{Z}}$ is generated by a product of the primes in $\Sigma$.

**Definition 3.20.** Let Cosets$_\Sigma(\hat{\mathcal{O}}^\times)$ be the category with

- objects: cosets $[x] = x\hat{\mathcal{O}}^\times \in \hat{B}^\times/\hat{\mathcal{O}}^\times$ for $x \in \hat{B}^\times$;

- morphisms: $\operatorname{Hom}_\Sigma([x], [y]) = B^\times \cap y(\hat{\mathcal{O}} \cap \hat{\mathcal{O}}_\Sigma^\times)x^{-1} = \operatorname{Hom}([x], [y]) \cap y\hat{\mathcal{O}}_\Sigma^\times x^{-1}$, using multiplication in $B$ as composition.

Equivalently, the morphisms in Cosets$_\Sigma(\hat{\mathcal{O}}^\times)$ are the morphisms in Cosets$(\hat{\mathcal{O}}^\times)$ whose degree is a product of the primes in $\Sigma$. We obtain the following corollary.

**Corollary 3.21 (Adélic Deuring correspondence).** The second equivalence from Proposition 3.19 induces a degree-preserving equivalence of categories

$$ \operatorname{Cosets}_{\Sigma}(\hat{\mathcal{O}}^{\times}) \to \operatorname{SS}_{\Sigma}(p). $$
### 3.3 Extra data of congruence type

Fix $N \ge 1$ an integer not divisible by any prime in $\Sigma$.

In this subsection, we will study categories of elements of various functors, as in Definition 2.8. We will use functors coming from quaternionic constructions, which will allow us to apply automorphic methods. The main result of this subsection is Theorem 3.27, which classifies functors satisfying a simple property in terms of adélic groups.

Let $U(N) = (1 + N\hat{O}) \cap \hat{O}^\times$, which is a finite index subgroup of $\hat{O}^\times$, and similarly $U_\Sigma(N) = (1 + N\hat{O}_\Sigma)\cap \hat{O}_\Sigma^\times$. Let $U$ be a subgroup of $\hat{O}^\times$ containing $U(N)$, and let $U_\Sigma = U \cdot U_\Sigma(N)$, so that $U = U_\Sigma \cap \hat{O}^\times$. Note that the natural map $\hat{O}^\times/U \to \hat{O}_\Sigma^\times/U_\Sigma$ is a bijection, i.e. we have $\hat{O}_\Sigma^\times = \hat{O}^\times U_\Sigma$.

It is helpful to think about these definition in terms of the product decomposition $\hat{B}^\times = \prod'_\ell B_\ell^\times$ as follows: we have

$$U = U' \times \prod_{\ell \nmid N} \mathcal{O}_\ell^\times \text{ and } U_\Sigma = U' \times \prod_{\ell \nmid N, \ell \notin \Sigma} \mathcal{O}_\ell^\times \times \prod_{\ell \in \Sigma} B_\ell^\times$$

where $U'$ is the image of $U$ in $\prod_{\ell \nmid N} \mathcal{O}_\ell^\times$.

**Definition 3.22.** Let $\mathcal{F}_U$ be the functor

$$\mathcal{F}_U: \operatorname{Cosets}_\Sigma(\hat{O}^\times) \to \text{Sets}$$

defined by

$$- \mathcal{F}_U([x]) = x \frac{\hat{O}_\Sigma^\times}{U_\Sigma},$$

$$- \text{ for } b \in \operatorname{Hom}_\Sigma([x], [y]), \text{ the map } \mathcal{F}_U(b): \mathcal{F}_U([x]) \to \mathcal{F}_U([y]) \text{ is left multiplication by } b.$$

Let $\operatorname{Cosets}_\Sigma(U)$ be the category with

$$- \text{ objects: cosets } xU \in \hat{B}^\times/U \text{ for } x \in \hat{B}^\times;$$

$$- \text{ morphisms: } \operatorname{Hom}_U(xU, yU) = B^\times \cap y(\hat{O} \cap U_\Sigma)x^{-1} = \operatorname{Hom}([x], [y]) \cap yU_\Sigma x^{-1}, \text{ using multiplication in } B \text{ as composition.}$$

In other words, morphism are required to respect $U$ at the primes dividing $N$, and to have degree a product of the primes in $\Sigma$.

**Example 3.23.** Assume that $p$ does not divide $N$. Let $\mathcal{O}_0(N) \subset \mathcal{O}$ be an Eichler order of level $N$, and let $U = \hat{O}_0(N)^\times$. Then for all $x \in \hat{B}^\times$, the set $\mathcal{F}_U([x])$ is in bijection with $\mathbf{P}^1(\mathbb{Z}/N\mathbb{Z})$, or more naturally with the set of Eichler orders contained in the maximal order $x\hat{O}x^{-1} \cap B$.

The following proposition is the bridge between functors on the quaternionic side of the Deuring correspondence and automorphic forms.

**Proposition 3.24.** The association
$$-([x], xgU_{\Sigma}) \mapsto xg'U \text{ where } xgU_{\Sigma} = xg'U_{\Sigma} \text{ and } g' \in \hat{\mathcal{O}}^{\times};$$

$$-b \in \operatorname{Hom}_{\operatorname{El}(\mathcal{F}_U)}(( [x], xgU_{\Sigma} ), ( [y], yhU_{\Sigma} )) \mapsto b \in \operatorname{Hom}_U(xg'U, yh'U)$$

defines a degree-preserving equivalence of categories

$$\operatorname{El}(\mathcal{F}_U) \to \operatorname{Cosets}_{\Sigma}(U).$$

*Proof.* First, the association is well-defined on objects: if two elements $g', g'' \in \hat{\mathcal{O}}^{\times}$ satisfy $xg'U_{\Sigma} = xg''U_{\Sigma}$, then $(g')^{-1}g'' \in U_{\Sigma} \cap \hat{\mathcal{O}}^{\times} = U$ so $xg'U = xg''U$. Next, it is well-defined on morphisms: let $b \in \operatorname{Hom}_{\operatorname{El}(\mathcal{F}_U)}(( [x], xgU_{\Sigma} ), ( [y], yhU_{\Sigma} ))$, and $xgU_{\Sigma} = xg'U_{\Sigma}$ and $yhU_{\Sigma} = yh'U_{\Sigma}$ with $g', h' \in \hat{\mathcal{O}}^{\times}$; then $bxg'U_{\Sigma} = yh'U_{\Sigma}$ so $b \in yh'U_{\Sigma}(xg')^{-1}$ and therefore $b \in \operatorname{Hom}_U(xg'U, yh'U)$. Since the association is clearly multiplicative on morphisms, it defines a functor. Moreover, the functor $\operatorname{Cosets}_{\Sigma}(U) \to \operatorname{El}(\mathcal{F}_U)$ defined by

$$-xU \mapsto ([x], xU_{\Sigma});$$

$$-b \in \operatorname{Hom}_U(xU, yU) \mapsto b$$

is clearly an inverse, so we obtain an equivalence as claimed. $\square$

We will need the following consequence of the strong approximation theorem.

**Lemma 3.25.** *Assume that $\Sigma$ contains at least one prime different from $p$ and that it generates $(\mathbb{Z}/N\mathbb{Z})^\times$. Then for every $g, x \in \hat{B}^\times$, we have*

$$\operatorname{Hom}_{\Sigma}([x], [gx]) \cap gxU_{\Sigma}(N)x^{-1} \neq \emptyset.$$

*Proof.* Let $x \in \hat{B}^\times$, and let $H = xU_{\Sigma}(N)x^{-1}$. Since $\Sigma$ contains a prime different from $p$, strong approximation holds ([Voi21, Theorem 28.5.3, see also 28.5.5]), so the reduced norm induces a bijection

$$B^\times \setminus \hat{B}^\times/H \to \mathbb{Q}_{>0}^\times \setminus \hat{\mathbb{Q}}^\times / \operatorname{nrd}(H).$$

On the other hand, the group $\mathbb{Q}_{>0}^\times \setminus \hat{\mathbb{Q}}^\times / \operatorname{nrd}(H)$ is isomorphic to a quotient of $(\mathbb{Z}/N\mathbb{Z})^\times / \langle\Sigma\rangle$. Since $\Sigma$ generates $(\mathbb{Z}/N\mathbb{Z})^\times$ the latter quotient is trivial, so $\hat{B}^\times = B^\times H$. Now let $g \in \hat{B}^\times$. Write $g = b_0xu_0^{-1}x$ with $b_0 \in B^\times$ and $u_0 \in U_{\Sigma}(N)$, so that $b_0 = gxu_0x^{-1}$. Let $\lambda$ be a product of the primes in $\Sigma$ such that $\lambda u_0 \in \hat{\mathcal{O}}$ and $\lambda \equiv 1 \bmod N$. Let $b = \lambda b_0$ and $u = \lambda u_0$, which satisfy $gxux^{-1} = b \in B^\times$ and $u \in \hat{\mathcal{O}} \cap U_{\Sigma}(N)$. Then $b \in \operatorname{Hom}_{\Sigma}([x], [gx]) \cap gxU_{\Sigma}(N)x^{-1}$, which is therefore not empty. $\square$

We are now in position to state and prove the main result of this subsection.

**Definition 3.26.** Let $\mathcal{F}$: $\operatorname{Cosets}_{\Sigma}(\hat{\mathcal{O}}^{\times}) \to$ Sets be a functor. We say that $\mathcal{F}$ is of $N$-congruence type if $\mathcal{F}$ is isomorphic to a disjoint union of functors $\mathcal{F}_U$. We say that $\mathcal{F}$ satisfies the (mod $N$)-congruence property if for every $x \in \hat{B}^\times$ and for every $a, b \in \operatorname{End}_{\Sigma}([x])$ such that $a - b \in N \cdot \operatorname{End}([x])$, we have $\mathcal{F}(a) = \mathcal{F}(b)$.
**Theorem 3.27.** Assume that $\Sigma$ contains at least one prime different from $p$ and that it generates $(\mathbb{Z}/N\mathbb{Z})^\times$. Let $\mathcal{F}$: Cosets$_\Sigma(\hat{\mathcal{O}}^\times) \to$ Sets be a functor. Then $\mathcal{F}$ is of $N$-congruence type if and only if $\mathcal{F}$ satisfies the (mod $N$)-congruence property. More precisely, assume that $\mathcal{F}$ satisfies the (mod $N$)-congruence property. Then:

(1) for every morphism $f$ in Cosets$_\Sigma(\hat{\mathcal{O}}^\times)$, the map $\mathcal{F}(f)$ is a bijection; and

(2) the morphism $\mathrm{End}_\Sigma([1]) \to (\mathcal{O}/\mathcal{NO})^\times$ is surjective, inducing an action of the group $G = (\mathcal{O}/\mathcal{NO})^\times$ on $\mathcal{F}([1])$.

Choose a $G$-equivariant bijection $\mathcal{F}([1]) \cong \bigsqcup_i G/H_i$, and for all $i$, let $U_i$ be the preimage of $H_i$ under the quotient map $\hat{\mathcal{O}}^\times \to (\mathcal{O}/\mathcal{NO})^\times$. Then:

(3) there exists an isomorphism of functors

$$ \mathcal{F} \cong \bigsqcup_i \mathcal{F}_{U_i}. $$

*Proof.* First, every functor of $N$-congruence type clearly satisfies the (mod $N$)-congruence property.

Assume that $\mathcal{F}$ satisfies the (mod $N$)-congruence property.

**Step 1.** We claim that all $\mathcal{F}(f)$ are bijections. Indeed, let $f \in \mathrm{End}_\Sigma([x])$ be an endomorphism in Cosets$_\Sigma(\hat{\mathcal{O}}^\times)$. Then its reduction modulo $N$ has finite order, say $k$, so that $f^k - 1 \in Nx\hat{\mathcal{O}}x^{-1}$. By the (mod $N$)-congruence property this implies $\mathcal{F}(f)^k = \mathcal{F}(1) = \mathrm{id}$, so that $\mathcal{F}(f)$ is invertible. Now let $f: [x] \to [y]$ be an arbitrary morphism in Cosets$_\Sigma(\hat{\mathcal{O}}^\times)$. Then there exists a morphism $g: [y] \to [x]$ such that $fg = \mathrm{deg}(f) \in \mathrm{End}_\Sigma([y])$ and $gf = \mathrm{deg}(f) \in \mathrm{End}_\Sigma([x])$. By the endomorphism case, this proves that $\mathcal{F}(fg)$ and $\mathcal{F}(gf)$ are invertible, hence that $\mathcal{F}(f)$ is. This proves (1).

**Step 2.** We claim that for all $x, y \in \hat{B}^\times$ and all $a, b \in \mathrm{Hom}_\Sigma([x], [y])$, if $a-b \in Ny\hat{\mathcal{O}}x^{-1}$ then $\mathcal{F}(a) = \mathcal{F}(b)$. Indeed under these conditions there exists $c \in \mathrm{Hom}_\Sigma([y], [x])$. Then $ca-cb \in \mathrm{End}_\Sigma([x]) \cap Nx\hat{\mathcal{O}}x^{-1}$. By the (mod $N$)-congruence property we have $\mathcal{F}(ca) = \mathcal{F}(cb)$. Since $\mathcal{F}(c)$ is invertible, this proves $\mathcal{F}(a) = \mathcal{F}(b)$.

We also claim that for all $x, y \in \hat{B}^\times$ and all $a, b \in \mathrm{Hom}_\Sigma([x], [y])$, if $b \in axU_\Sigma(N)x^{-1}$ then $\mathcal{F}(a) = \mathcal{F}(b)$. Indeed the condition implies that

$$ b \in a(1 + Nx\hat{\mathcal{O}}_\Sigma x^{-1}) = a + Nax\hat{\mathcal{O}}_\Sigma x^{-1} = a + Ny\hat{\mathcal{O}}_\Sigma x^{-1}. $$

Since $\hat{\mathcal{O}} \cap N\hat{\mathcal{O}}_\Sigma = N\hat{\mathcal{O}}$, the previous claim applies, and therefore $\mathcal{F}(a) = \mathcal{F}(b)$.

**Step 3.** Inspired by Proposition 3.24, we are going to define an action of $\hat{B}^\times$ on $\bigsqcup_{[x]} \mathcal{F}([x])$. Let $g, x \in \hat{B}^\times$. By Lemma 3.25, there exists $b \in \mathrm{Hom}_\Sigma([x], [gx]) \cap gxU_\Sigma(N)x^{-1}$. For $A \in \mathcal{F}([x])$, we define $g \cdot A = \mathcal{F}(b)(A) \in \mathcal{F}([gx])$. To see that this is well-defined, let $b' \in \mathrm{Hom}_\Sigma([x], [gx]) \cap gxU_\Sigma(N)x^{-1}$ be another element. We have $b' \in bxU_\Sigma(N)x^{-1}$, so that $\mathcal{F}(b) = \mathcal{F}(b')$.

The defined action is multiplicative, because when $d \in \mathrm{Hom}_\Sigma([x], [hx]) \cap hxU_\Sigma(N)x^{-1}$ and $c \in \mathrm{Hom}_\Sigma([hx], [ghx]) \cap ghxU_\Sigma(N)(hx)^{-1}$ we have $cd \in \mathrm{Hom}_\Sigma([x], [ghx]) \cap ghxU_\Sigma(N)x^{-1}$: the action of $gh$ is given by $\mathcal{F}(cd) = \mathcal{F}(c)\mathcal{F}(d)$.
We therefore get an action of $\hat{B}^\times$ on $\bigsqcup_{[x]} \mathcal{F}([x])$ with the following properties for $g, x \in \hat{B}^\times$:

- the action of $g$ induces a bijection $\mathcal{F}([x]) \to \mathcal{F}([gx])$;

- $x\hat{\mathcal{O}}^\times x^{-1}$ stabilises $\mathcal{F}([x])$;

- $xU(N)x^{-1}$ acts trivially on $\mathcal{F}([x])$.

In particular, we obtain an action of $\hat{\mathcal{O}}^\times$ on $\mathcal{F}([1])$. By decomposing this action into orbits, we obtain an $\hat{\mathcal{O}}^\times$-equivariant bijection

$$ \psi_{[1]}: \bigsqcup_{i \in I} \hat{\mathcal{O}}^\times / U_i \to \mathcal{F}([1]), $$

where the $U_i$ are subgroups of $\hat{\mathcal{O}}^\times$ containing $U(N)$. Recalling the definition of the functors $\mathcal{F}_{U_i}$ (Definition 3.22) we see that this is the same as an $\hat{\mathcal{O}}^\times$-equivariant bijection

$$ \psi_{[1]}: \bigsqcup_{i \in I} \mathcal{F}_{U_i}([1]) \to \mathcal{F}([1]). $$

In fact, the action of $\hat{\mathcal{O}}^\times$ factors through $\hat{\mathcal{O}}^\times \to \hat{\mathcal{O}}^\times / U(N) \cong (\mathcal{O}/N\mathcal{O})^\times$, and comes from the application of Lemma 3.25 to $x=1$ and $g \in \hat{\mathcal{O}}^\times$, from which we see that (2) holds and one can choose the $U_i$ compatibly with the $H_i$ from the statement of the theorem.

**Step 4.** We extend $\psi_{[1]}$ to an isomorphism of functors $\psi: \bigsqcup_{i \in I} \mathcal{F}_{U_i} \to \mathcal{F}$. Let $x \in \hat{B}^\times$. We define

$$ \psi_{[x]}: \bigsqcup_{i \in I} \mathcal{F}_{U_i}([x]) \to \mathcal{F}([x]) $$

by setting for every $U = U_i$ and every $xgU_\Sigma \in \mathcal{F}_U([x])$ with $g \in \hat{\mathcal{O}}_\Sigma^\times$,

$$ \psi_{[x]}(xgU_\Sigma) = x \cdot \psi_{[1]}(gU_\Sigma). $$

The map $\psi_{[x]}$ is well-defined since $xgU_\Sigma = xg'U_\Sigma$ implies $gU_\Sigma = g'U_\Sigma$. In addition, $\psi_{[x]}$ depends only on $[x]$: for all $u \in \hat{\mathcal{O}}^\times$ we have $(xu) \cdot \psi_{[1]}(u^{-1}gU_\Sigma) = x \cdot \psi_{[1]}(gU_\Sigma)$ by $\hat{\mathcal{O}}^\times$-equivariance. Since the multiplication by $x^{-1}$ from $\mathcal{F}_U([x])$ to $\mathcal{F}_U([1])$, the map $\psi_{[1]}$ and the action of $x$ from $\mathcal{F}([1])$ to $\mathcal{F}([x])$ are all bijections, the map $\psi_{[x]}$ is a bijection. We now prove that $\psi = (\psi_{[x]})_{[x]}$ is a morphism of functors.
The proof will follow the following diagram:

<figure><img src="image_2.png" /></figure>

Let $x, y \in \hat{B}^\times$, $f \in \operatorname{Hom}_\Sigma([x], [y])$ and $U$ be one of the $U_i$; we will prove that $\mathcal{F}(f) \circ \psi_{[x]} = \psi_{[y]} \circ \mathcal{F}_U(f)$ holds on $\mathcal{F}_U([x])$. Let $xgU_\Sigma \in \mathcal{F}_U([x])$. We have

$$ \mathcal{F}(f) \circ \psi_{[x]}(xgU_{\Sigma}) = \mathcal{F}(f)(x \cdot \psi_{[1]}(gU_{\Sigma})) = \mathcal{F}(fb)\psi_{[1]}(gU_{\Sigma}), $$

where $b \in \operatorname{Hom}_\Sigma([1], [x]) \cap xU_\Sigma(N)$. Write $f = yux^{-1}$ with $u \in \hat{O} \cap \mathcal{O}_\Sigma^\times$, and note that $fxgU_\Sigma = yugU_\Sigma \in \mathcal{F}_U([y])$. We therefore have

$$ \psi_{[y]} \circ \mathcal{F}_U(f)(xgU_\Sigma) = \psi_{[y]}(fxgU_\Sigma) = y \cdot \psi_{[1]}(ugU_\Sigma) = \mathcal{F}(c)\psi_{[1]}(ugU_\Sigma) $$

where $c \in \operatorname{Hom}_\Sigma([1], [y]) \cap yU_\Sigma(N)$. Now $u \in vU_\Sigma(N)$ for some $v \in \hat{O}^\times$, so that $ugU_\Sigma = vgU_\Sigma$ since $\hat{O}_\Sigma^\times$ normalises $U_\Sigma(N)$, and by equivariance of $\psi_{[1]}$ we have

$$ \psi_{[1]}(ugU_\Sigma) = \psi_{[1]}(vgU_\Sigma) = v \cdot \psi_{[1]}(gU_\Sigma) = \mathcal{F}(d)\psi_{[1]}(gU_\Sigma) $$

where $d \in \operatorname{End}_\Sigma([1]) \cap vU_\Sigma(N)$. We get

$$ \psi_{[y]} \circ \mathcal{F}_U(f)(xgU_\Sigma) = \mathcal{F}(cd)\psi_{[1]}(gU_\Sigma). $$

We finally compare $fb$ and $cd$. We have

$$ fb \in (yux^{-1})xU_\Sigma(N) = yuU_\Sigma(N), $$

and

$$ cd \in yU_\Sigma(N)vU_\Sigma(N) = yvU_\Sigma(N) = yuU_\Sigma(N). $$

Since $fb$ and $cd$ both belong to $\operatorname{Hom}_\Sigma([1], [y]) = \operatorname{Hom}_\Sigma([1], [yu])$, this proves that $\mathcal{F}(fb) = \mathcal{F}(cd)$. This proves that $\psi$ is an isomorphism of functors, so that $\mathcal{F}$ is of $N$-congruence type, proving (3) and concluding the proof. $\square$

## 3.4 Associated graphs and equidistribution

In this subsection, we study the graphs of interest and prove our main equidistribution theorem: Theorem 3.10 and its companion Proposition 3.11.

We first introduce a categorical construction of graphs generalising Definition 3.4.
**Definition 3.28.** Let $\mathcal{C}$ be category with finitely many isomorphism classes of objects, finite automorphism groups, and equipped with a degree map. We define the graph Graph($\mathcal{C}$) with:

- vertices: isomorphism classes of objects in $\mathcal{C}$;

- edges: let $x \in \mathcal{C}$; the set of edges from the vertex corresponding to $x$ is the set of classes of morphisms from $x$ modulo the relation ($f: x \to y$) $\sim$ ($g: x \to z$) if and only there exists $u \in \text{Isom}_{\mathcal{C}}(y, z)$ such that $g = uf$; the endpoint of the edge corresponding to $f: x \to y$ is the isomorphism class of $y$. In other words, the set of edges between the classes of $x, y \in \mathcal{C}$ is $\text{Aut}(y)\setminus\text{Hom}(x, y)$.

The degree of an edge is the degree of the corresponding morphism.

We define a measure on the set of vertices of Graph($\mathcal{C}$) by giving each vertex $v$ measure $\frac{1}{|\text{Aut}(v)|}$ where $v$ corresponds to $x \in \mathcal{C}$, and we write $L^2(\text{Graph}(\mathcal{C}))$ the Hilbert space of complex functions on the set of vertices of Graph($\mathcal{C}$).

For every prime $\ell$, we define an adjacency operator $A_\ell$ on $L^2(\text{Graph}(\mathcal{C}))$ given by

$$A_{\ell}F(x) = \sum_{x \to y} F(y),$$

where the sum runs over edges of degree $\ell$ leaving $x$.

**Remark 3.29.** For every functor $\mathcal{F}$ as in Definition 3.4, we have $\mathcal{G}_{\mathcal{F}} = \text{Graph}(\text{El}(\mathcal{F}))$. Every degree-preserving equivalence of categories $\mathcal{C} \cong \mathcal{D}$ induces an isomorphism of graphs Graph($\mathcal{C}$) $\cong$ Graph($\mathcal{D}$) compatible with all the structure from Definition 3.28.

The following lemma relates the graphs obtained from our quaternionic categories to automorphic forms.

**Lemma 3.30.** The category Cosets$_{\Sigma}$(U) and its associated graph have the following properties:

(1) Two objects $x, y \in \hat{B}^\times/U$ are isomorphic if and only if they have the same image in the quotient $B^\times\setminus\hat{B}^\times/U$.

(2) The projection to $B^\times\setminus\hat{B}^\times/U$ of a Haar measure on $\hat{B}^\times$ coincides with the measure on the set of vertices of Graph(Cosets$_{\Sigma}$(U)).

(3) For every $x \in \hat{B}^\times$, the map

$$\text{edg}: u \in \hat{O} \cap U_{\Sigma} \mapsto 1 \in \text{Hom}_{U}(xU, xu^{-1}U)$$

induces a bijection between $U\setminus(\hat{O} \cap U_{\Sigma})$ and the set of edges leaving the vertex $B^\times xU$ in Graph(Cosets$_{\Sigma}$(U)).

(4) For every prime $\ell \in \Sigma$ different from $p$, the adjacency operator $A_\ell$ coincides with the adjoint of the Hecke operator $T_\ell$ on $L^2(B^\times\setminus\hat{B}^\times/U)$.

*Proof.*
(1) Isomorphisms in Cosets$_{Σ}$(U) are exactly morphisms of degree 1, so that the set of isomorphisms between two cosets xU, yU is B$^{×}$ ∩ yUx$^{-1}$, i.e. the set of elements b ∈ B$^{×}$ such that bxU = yU. This proves the claim.

(2) Since cosets of U are open and form a disjoint union, by translation in-
variance every element of $\hat{B}^\times/U$ has the same nonzero measure. We nor-
malise the Haar measure so that each coset of U has measure 1. For ev-
ery $x \in \hat{B}^\times$, every fiber of the projection map $xU \mapsto B^\times xU$ has cardinal-
ity $\#(B^\times \cap xUx^{-1}) = \#\mathrm{Aut}_U(xU)$, so the projected measure of $B^\times xU$ is
the inverse of this cardinality, as claimed.

(3) Let $x \in \hat{B}^\times$. For every $u \in \hat{O} \cap U_\Sigma$, we have $1 = (xu^{-1})ux \in xu^{-1}(\hat{O} \cap U_\Sigma)x \cap B^\times = \operatorname{Hom}_U(xU, xu^{-1}U)$, so the map edg is well-defined. Let $f \in \operatorname{Hom}_U(xU, yU)$ represent an edge $x \to y$ in $\operatorname{Graph}(\operatorname{Cosets}_\Sigma(U))$. Then $1 \in \operatorname{Hom}_U(xU, f^{-1}yU)$ represents the same edge, which is therefore edg$(y^{-1}fx)$. Moreover, two morphisms $f \in \operatorname{Hom}_U(xU, yU)$ and $g \in \operatorname{Hom}_U(xU, zU)$ represent the same edge if and only if there exists $b \in B^\times$ such that $g = bf$. For morphisms in the image of edg, this can only happen with $b = 1$, so the edge edg($u$) is completely determined by its endpoint $xu^{-1}U$, i.e. by the coset $Uu$.

(4) Consider the cosets $Uu \in U \setminus (\hat{O} \cap U_\Sigma)$ such that $\mathrm{nrd}(u)\hat{Z} = \ell\hat{Z}$. Then for every $\ell' \neq \ell$, the $\ell'$-component of $u$ is in the $\ell'$-component of $U$, so we may replace it by 1. Choosing an isomorphism $\mathcal{O} \otimes \mathbf{Z}_\ell \cong M_2(\mathbf{Z}_\ell)$, the possible cosets correspond to the cosets in $\mathrm{GL}_2(\mathbf{Z}_\ell) \setminus \mathrm{GL}_2(\mathbf{Q}_\ell)$ whose determinant has valuation 1: these are exactly the cosets of $\mathrm{GL}_2(\mathbf{Z}_\ell)$ that belong to the double coset

$$
\mathrm{GL}_2(\mathbf{Z}_\ell) \begin{pmatrix} \ell & 0 \\ 0 & 1 \end{pmatrix} \mathrm{GL}_2(\mathbf{Z}_\ell).
$$

Let $F \in L^2(\operatorname{Graph}(\operatorname{Cosets}_U(\Sigma)))$. From the above we have

$$
A_{\ell} F(B^{\times} x U) = \sum_{U u \in U \setminus U \delta_{\ell} U} F(B^{\times} x u^{-1} U).
$$

This is the adjoint of the Hecke operator $T_\ell$, as claimed.

□

The following proposition is the quaternionic version of our equidistribution
result.

**Proposition 3.31.** Let $L^2_{\mathrm{ndr}}(\mathrm{Graph}(\mathrm{Cosets}_\Sigma(U))) \subset L^2(\mathrm{Graph}(\mathrm{Cosets}_\Sigma(U)))$
denote the subspace of functions that factor through the reduced norm map

$$
B^{\times} \setminus \hat{B}^{\times} / U \to \mathbf{Q}_{>0}^{\times} \setminus \hat{\mathbf{Q}}^{\times} / \mathrm{nrd}(U),
$$

and let $L_0^2(\mathrm{Graph}(\mathrm{Cosets}_\Sigma(U)))$ denote the orthogonal complement of the sub-
space $L_{\mathrm{ndr}}^2(\mathrm{Graph}(\mathrm{Cosets}_\Sigma(U)))$. Then, for every $\ell \in \Sigma$ different from $p$, the
adjacency operator $A_\ell$ is a normal operator, stabilises $L_{\mathrm{ndr}}^2(\mathrm{Graph}(\mathrm{Cosets}_\Sigma(U)))$
and $L_0^2(\mathrm{Graph}(\mathrm{Cosets}_\Sigma(U)))$, and its operator norm on $L_0^2(\mathrm{Graph}(\mathrm{Cosets}_\Sigma(U)))$
is at most $2\sqrt{\ell}$. Moreover, the $A_\ell$ for $\ell \in \Sigma$ pairwise commute.
*Proof.* It is clear that $L_{\text{nrd}}^2(\text{Graph}(\text{Cosets}_{\Sigma}(U)))$ is stable under $A_{\ell}$. The operators $A_{\ell}$ are normal and pairwise commute by Lemma 3.30 (4), and therefore leave $L_0^2(\text{Graph}(\text{Cosets}_{\Sigma}(U)))$ stable and are diagonalisable. We bound the operator norm of $A_{\ell}$ by bounding its eigenvalues, equivalently by bounding the eigenvalues of the Hecke operator $T_{\ell}$. The space $L_{\text{nrd}}^2(\text{Graph}(\text{Cosets}_{\Sigma}(U)))$ is exactly the subspace of $L^2(B^\times \setminus \hat{B}^\times / U)$ of automorphic forms that generate a one-dimensional automorphic representation (i.e. of the form $g \mapsto \chi(\text{nrd} g)$ for some Dirichlet character $\chi$). Therefore, by the Jacquet–Langlands correspondence [JL70, Theorem 14.4], every system of Hecke eigenvalues appearing in $L_0^2(\text{Graph}(\text{Cosets}_{\Sigma}(U)))$ is also the one attached to a cuspidal modular new-form of weight 2 ramified only at primes dividing $pN$. Therefore, by Deligne’s theorem [Del73, Theorem 8.2], the absolute values of the eigenvalues of $T_{\ell}$ are bounded by $2\sqrt{\ell}$. This proves the proposition. $\square$

*Remark 3.32.* Using the full statement of the Jacquet–Langlands correspondence, one could obtain the exact eigenvalues in terms of classical modular forms. This is not needed in our applications.

We can finally prove Theorem 3.10 and Proposition 3.11.

*Proof (Theorem 3.10 and Proposition 3.11).* First, we use Corollary 3.21 to transfer the entire situation to the quaternionic category $\text{Cosets}_{\Sigma}(\hat{O}^\times)$; in particular $\mathcal{F}$ induces a functor $\mathcal{F}'$: $\text{Cosets}_{\Sigma}(\hat{O}^\times) \to \text{Sets}$. Since the equivalence of Proposition 3.19 is additive, the functor $\mathcal{F}'$ satisfies the (mod $N$)-congruence property in the sense of Definition 3.26, so that we can apply Theorem 3.27. From (1) and (2) of Theorem 3.27, we obtain (1) and (3) respectively. Moreover, we can choose the $H_i$ of Theorem 3.27 to coincide with those of Proposition 3.11.

Let $E \in \text{SS}(p)$. It is standard that there exists $\psi \in \text{Hom}_{\Sigma}(E_0, E)$. By (3), there exists $\alpha \in \text{End}_{\Sigma}(E_0)$ whose degree is the inverse of $\text{deg}(\psi)$ mod $N$, so that $\varphi = \psi\alpha \in \text{Hom}_{\Sigma}(E_0, E)$ has degree 1 mod $N$. This proves (2) when one of the curves is $E_0$, and therefore in general by going via $E_0$.

By (2), every vertex of $\mathcal{G}_{\mathcal{F}}$ is connected to one above $E_0$. Moreover, two vertices above $E_0$ are connected if and only if they are related by an element of $\text{End}_{\Sigma}(E_0)$, if and only if they are in the same orbit under $\mathcal{G}$. In particular there is exactly one vertex of the form $(E_0, x_i)$ in each connected component of $\mathcal{G}_{\mathcal{F}}$. Since every vertex of $\mathcal{G}_{\text{deg}}$ has exactly one outgoing edge labelled by each element of $(\mathbb{Z}/N\mathbb{Z})^\times$, this proves that there is at most one morphism of graphs satisfying the properties of (4).

We now prove the existence of $\text{Deg}$. Let $U_i$ be as in Theorem 3.27. Applying (3) of that theorem and Proposition 3.24 we obtain a degree-preserving equivalence of categories

$$ \mathrm{El}(\mathcal{F}) \cong \bigsqcup_i \mathrm{Cosets}_{\Sigma}(U_i), $$

inducing an isomorphism of graphs

$$ \mathcal{G}_{\mathcal{F}} \cong \bigsqcup_i \mathrm{Graph}(\mathrm{Cosets}_{\Sigma}(U_i)). $$
By Lemma 3.30 (1) and (3), the reduced norm map

$$ \text{nrd: } B^\times \setminus \hat{B}^\times / U_i \to \mathbf{Q}_{>0}^\times \setminus \hat{\mathbf{Q}}^\times / \text{nrd}(U_i) $$

combined with the isomorphism

$$ \mathbf{Q}_{>0}^\times \setminus \hat{\mathbf{Q}}^\times / \text{nrd}(U_i) \cong (\mathbf{Z}/N\mathbf{Z})^\times / \text{nrd}(H_i) $$

translates into a graph morphism

$$ \text{Deg: } \mathcal{G}_{\mathcal{F}} \to \mathcal{G}_{\text{deg}} $$

satisfying the properties of (4). Since the adélic reduced norm map $\hat{B}^\times \to \hat{\mathbf{Q}}^\times$ is surjective, so is $\text{Deg}$, proving (5).

Let $L_{\text{Deg}}^2(\mathcal{G}_{\mathcal{F}}) \subset L^2(\mathcal{G}_{\mathcal{F}})$ be the subspace of functions that factor through $\text{Deg}$. Since vertices connected by an edge of degree 1 mod $N$ clearly have the same image under $\text{Deg}$, we have $L_{\text{Deg}}^2(\mathcal{G}_{\mathcal{F}}) \subseteq L_{\text{deg}}^2(\mathcal{G}_{\mathcal{F}})$. Moreover, if two vertices have the same image under $\text{Deg}$, then they are in the same connected component of $\mathcal{G}_{\mathcal{F}}$ from the above analysis, and are therefore connected by a single edge by composing the morphisms corresponding to a path between them; the degree of this edge must therefore be 1 mod $N$ by the properties of $\text{Deg}$. So we have the reverse inclusion, and $L_{\text{Deg}}^2(\mathcal{G}_{\mathcal{F}}) = L_{\text{deg}}^2(\mathcal{G}_{\mathcal{F}})$. This proves (6) and concludes the proof of Proposition 3.11.

Finally, applying Proposition 3.31 to each $U_i$, and the isomorphisms above, yields Theorem 3.10. □

# 4 Enriching a ONEEND oracle

In this section, we show how to turn an oracle for the ONEEND problem into a richer oracle with better distributed output. The quality of this enrichment is quantified in Theorem 4.2. The proof is an application of the equidistribution results of Section 3.

The following lemma relates conjugation-invariance of distributions to the abstract setup of Section 3.

**Lemma 4.1.** Let $p > 3$ be a prime, let $N \ge 1$ and let $E \in \text{SS}(p)$. Let $g \in (\text{End}(E)/N \text{End}(E))^\times$ be an element of degree $1 \in (\mathbf{Z}/N\mathbf{Z})^\times$. Define the linear operator $c_g: L^2(\mathcal{G}_{\text{End}/N}) \to L^2(\mathcal{G}_{\text{End}/N})$ by

$$ c_g F(E, \alpha) = F(E, g\alpha g^{-1}) \text{ and } c_g F(E', \alpha') = F(E', \alpha') \text{ for all } E' \neq E. $$

Then:

(1) for all $F \in L^2(\mathcal{G}_{\text{End}/N})$, we have $\|c_g F\|^2 \le 3\|F\|^2$;

(2) for all $G \in L_{\text{deg}}^2(\mathcal{G}_{\text{End}/N})$, we have $c_g G = G$; and
(3) for every $F = F_0 + F_1 \in L^2(\mathcal{G}_{\text{End}/N})$ with $F_0 \in L_0^2(\mathcal{G}_{\text{End}/N})$ and $F_1 \in L_{\text{deg}}^2(\mathcal{G}_{\text{End}/N})$, we have

$$ \|F - c_g F\| \le (1 + \sqrt{3}) \|F_0\|. $$

Proof.

(1) Let $F \in L^2(\mathcal{G}_{\text{End}/N})$. We have, where $E'$ ranges over the set of supersingular curves up to isomorphism except $E$, the elements $\alpha$ and $\beta$ range over $\text{End}(E)/N \text{ End}(E)$ and $\alpha'$ over $\text{End}(E')/N \text{ End}(E')$,

$$ \|F\|^2 = \sum_{(E, \alpha)} \frac{1}{\# \text{Aut}(E, \alpha)} |F(E, \alpha)|^2 + \sum_{(E', \alpha')} \frac{1}{\# \text{Aut}(E', \alpha')} |F(E', \alpha')|^2, $$

and

$$ \begin{aligned} \|c_g F\|^2 &= \sum_{(E, \alpha)} \frac{|F(E, g\alpha g^{-1})|^2}{\# \text{Aut}(E, \alpha)} + \sum_{(E', \alpha')} \frac{|F(E', \alpha')|^2}{\# \text{Aut}(E', \alpha')} \\ &= \sum_{(E, \beta)} \frac{|F(E, \beta)|^2}{\# \text{Aut}(E, g^{-1}\beta g)} + \sum_{(E', \alpha')} \frac{|F(E', \alpha')|^2}{\# \text{Aut}(E', \alpha')} \\ &= \sum_{(E, \beta)} \frac{\# \text{Aut}(E, \beta)}{\# \text{Aut}(E, g^{-1}\beta g)} \frac{|F(E, \beta)|^2}{\# \text{Aut}(E, \beta)} + \sum_{(E', \alpha')} \frac{|F(E', \alpha')|^2}{\# \text{Aut}(E', \alpha')} \\ &\le 3 \sum_{(E, \beta)} \frac{|F(E, \beta)|^2}{\# \text{Aut}(E, \beta)} + \sum_{(E', \alpha')} \frac{|F(E', \alpha')|^2}{\# \text{Aut}(E', \alpha')} \le 3 \|F\|^2, \end{aligned} $$

where the inequality comes from $\# \text{Aut}(E, \beta) \le 6$ and $\# \text{Aut}(E, g^{-1}\beta g) \ge 2$.

(2) Let $h \in \text{End}_{\Sigma}(E)$ be a lift of $g$, which exists by Proposition 3.11 (3). Let $G \in L_{\text{deg}}^2(\mathcal{G}_{\text{End}/N})$. For every $E' \ne E$ we have $c_g G(E', \alpha) = G(E', \alpha)$. Moreover, $h$ defines an edge $(E, \alpha) \to (E, h\alpha h^{-1}) = (E, h\alpha h^{-1})$ in $\mathcal{G}_{\text{End}/N}$ of degree 1 mod $N$, so $G(E, \alpha) = G(E, h\alpha h^{-1})$. Since $c_g G(E, \alpha) = G(E, g\alpha g^{-1}) = G(E, h\alpha h^{-1})$, this proves that $c_g G = G$.

(3) Let $F = F_0 + F_1 \in L^2(\mathcal{G}_{\text{End}/N})$ with $F_0 \in L_0^2(\mathcal{G}_{\text{End}/N})$ and $F_1 \in L_{\text{deg}}^2(\mathcal{G}_{\text{End}/N})$. Then

$$ \begin{aligned} \|F - c_g F\| &\le \|F_0 - c_g F_0\| + \|F_1 - c_g F_1\| \\ &= \|F_0 - c_g F_0\| \quad \text{since } c_g F_1 = F_1 \text{ by (2)} \\ &\le (1 + \sqrt{3}) \|F_0\| \quad \text{by (1).} \end{aligned} $$

□

We can now prove the main result of this section.

**Theorem 4.2.** Let $p > 3$ be a prime and $N$ an odd integer. Let $\mathcal{O}$ be an oracle for ONEEND. Let $E$ be a supersingular elliptic curve defined over $\mathbb{F}_{p^2}$ and let $\alpha$ be the random endomorphism produced by $\text{RICH}_k^{\mathcal{O}}(E)$. Then for every element $g \in$
**Algorithm 1 RICH<sub>k</sub><sup>O</sup>:** turning an oracle $\mathcal{O}$ for ONEEND into a 'richer' oracle RICH<sub>k</sub><sup>O</sup>, with guarantees on the distribution of the output.

**Require:** A supersingular elliptic curve $E/\mathbb{F}_{p^2}$, and a parameter $k \in \mathbb{Z}_{>0}$. We suppose access to an oracle $\mathcal{O}$ that solves the ONEEND problem.

**Ensure:** An endomorphism $\alpha \in \text{End}(E)$.

1: $\varphi \leftarrow$ a 2-isogenies random walk of length $k$ from $E$

2: $E' \leftarrow$ endpoint of $\varphi$

3: $\alpha \leftarrow \mathcal{O}(E')$, a non-scalar endomorphism of $E'$

4: **return** $\hat{\varphi} \circ \alpha \circ \varphi$

($\text{End}(E)/N \text{ End}(E))^\times$ of degree $1 \in (\mathbb{Z}/N\mathbb{Z})^\times$, the statistical distance between the distribution of $\alpha \mod N$ and the distribution of $g^{-1}(\alpha \mod N)g$ is at most

$$ \frac{1 + \sqrt{3}}{4} \lambda^k N^2 \sqrt{p + 13} = O(\lambda^k N^2 \sqrt{p}), $$

where $\lambda = \frac{2\sqrt{2}}{3} \approx 0.94$.

*Proof.* Define $F \in L^2(\mathcal{G}_{\text{End}/N})$ by the following formula for every vertex $(E', \beta)$:

$$ F(E', \beta) = \text{Pr}[\mathcal{O}(E') \mod N = \beta], $$

so that

$$ \left(\frac{A_2}{3}\right)^k F(E, \beta) = \text{Pr}[\text{RICH}_k^\mathcal{O}(E) \mod N = 4^k \beta]. $$

Indeed, $(\frac{A_2}{3})^k F(E, \beta)$ is the average, over all random walks $\varphi: E \to E'$ that Algorithm 4 could follow from $E$, of $\text{Pr}[\mathcal{O}(E') \mod N = \varphi\beta\hat{\varphi}]$, and the equality $\mathcal{O}(E') \mod N = \varphi\beta\hat{\varphi}$ is equivalent to $\hat{\varphi}\mathcal{O}(E')\varphi \mod N = \text{deg}(\varphi)\beta\text{deg}(\hat{\varphi}) = 4^k\beta$ since 2 is invertible mod $N$.

We have, where $E'$ ranges over isomorphism classes in $\text{SS}(p)$ and $\beta$ over the set $\text{End}(E')/N \text{ End}(E')$,

$$ \begin{aligned} \|F\|^2 &= \sum_{(E', \beta)} \frac{1}{\# \text{Aut}(E', \beta)} \text{Pr}[\mathcal{O}(E') \mod N = \beta]^2 \\ &\le \frac{1}{2} \sum_{(E', \beta)} \text{Pr}[\mathcal{O}(E') \mod N = \beta] \\ &= \frac{1}{2} \sum_{E'} 1 \le \frac{p+13}{24} \text{ by [Sil86, Theorem 4.1 (c)]}. \end{aligned} $$

Write $F = F_0 + F_1$ with $F_0 \in L_0^2(\mathcal{G}_{\text{End}/N})$ and $F_1 \in L_{\text{deg}}^2(\mathcal{G}_{\text{End}/N})$. Since $A_2$ preserves the orthogonal decomposition $L_0^2(\mathcal{G}_{\text{End}/N}) \oplus L_{\text{deg}}^2(\mathcal{G}_{\text{End}/N})$, we may apply Lemma 4.1 (3) to $A_2^k F = A_2^k F_0 + A_2^k F_1$, giving

$$ \|A_2^k F - c_g A_2^k F\| \le (1 + \sqrt{3}) \|A_2^k F_0\|. $$
On the other hand, by Theorem 3.10 we have

$$ \left\| \left( \frac{A_2}{3} \right)^k F_0 \right\| \le \lambda^k \|F_0\| \le \lambda^k \|F\|. $$

Finally, with $\beta$ ranging over $End(E)/N \cdot End(E)$, the statistical distance in the statement of the theorem is

$$
\begin{align*}
& \frac{1}{2} \sum_{\beta} \left| \Pr[\mathrm{RICH}_k^\mathcal{O}(E) \bmod N = \beta] - \Pr[\mathrm{RICH}_k^\mathcal{O}(E) \bmod N = g\beta g^{-1}] \right| \\
&= \frac{1}{2} \sum_{\beta} \left| \left(\frac{A_2}{3}\right)^k F(E, 4^{-k}\beta) - c_g \left(\frac{A_2}{3}\right)^k F(E, 4^{-k}\beta) \right| \\
&= \frac{1}{2} \sum_{\beta} \left| \left(\frac{A_2}{3}\right)^k F(E, \beta) - c_g \left(\frac{A_2}{3}\right)^k F(E, \beta) \right| \quad \text{since } \beta \mapsto 4^k\beta \text{ is a bijection} \\
&\le \frac{1}{2} \left( N^4 \sum_{\beta} \left| \left(\frac{A_2}{3}\right)^k F(E, \beta) - c_g \left(\frac{A_2}{3}\right)^k F(E, \beta) \right|^2 \right)^{\frac{1}{2}} \quad \text{by the Cauchy-Schwarz inequality} \\
&\le \frac{1}{2} N^2 \sqrt{6} \left\| \left(\frac{A_2}{3}\right)^k F - c_g \left(\frac{A_2}{3}\right)^k F \right\| \quad \text{since } \# \mathrm{Aut}(E, \beta) \le 6 \\
&\le \frac{1}{2} (1 + \sqrt{3}) N^2 \sqrt{6} \left\| \left(\frac{A_2}{3}\right)^k F_0 \right\| \le \frac{1}{2} (1 + \sqrt{3}) \lambda^k N^2 \sqrt{6} \|F\| \\
&\le \frac{1}{2} (1 + \sqrt{3}) \lambda^k N^2 \sqrt{6 \cdot \frac{p+13}{24}} = \frac{1}{4} (1 + \sqrt{3}) \lambda^k N^2 \sqrt{p+13}, \text{ as claimed.}
\end{align*}
$$

□

# 5 On conjugacy-invariant distributions

Theorem 4.2 proves that given a ONEEND oracle, the randomization method allows one to sample endomorphisms from a distribution which is (locally) invariant under conjugation by $(End(E)/N \cdot End(E))^\times$. In this section, we study such conjugacy-invariant distributions, and show that with good probability, such endomorphisms generate interesting suborders. In the whole section, fix $B$ a quaternion algebra over $\mathbb{Q}$ and $O \subset B$ a maximal order.

## 5.1 The local case

We start by studying the local case. Let $\ell$ be a prime unramified in $B$. In this subsection, we study distributions on $M_2(\mathbb{F}_\ell) \cong O/\ell O$ and $M_2(\mathbb{Z}_\ell) \cong O_\ell$.

**Definition 5.1.** The distribution of a random $\alpha \in M_2(\mathbb{F}_\ell)/\mathbb{F}_\ell$ is $\varepsilon$-close to $\mathrm{SL}_2(\mathbb{F}_\ell)$-invariant if, for every $g \in \mathrm{SL}_2(\mathbb{F}_\ell)$, the statistical distance between the distributions of $\alpha$ and of $g^{-1}\alpha g$ is at most $\varepsilon$. When the distributions are the same (i.e., $\varepsilon = 0$), we say that the distribution of $\alpha$ is $\mathrm{SL}_2(\mathbb{F}_\ell)$-invariant.
A key observation is that a conjugacy class cannot be stuck in a subspace.

**Lemma 5.2.** Suppose $\ell > 2$. Let $\alpha \in M_2(\mathbf{F}_\ell) \setminus \mathbf{F}_\ell$. Let $V \subsetneq M_2(\mathbf{F}_\ell)/\mathbf{F}_\ell$ be an $\mathbf{F}_\ell$-linear subspace. Let $\beta \in M_2(\mathbf{F}_\ell)$ be a random element uniformly distributed in the $\text{SL}_2(\mathbf{F}_\ell)$-conjugacy class of $\alpha$. Then, $\beta \in V$ with probability at most $1/2$.

*Proof.* The size of the orbit $X$ of $\alpha$ is $\#\text{SL}_2(\mathbf{F}_\ell)/\#C$, where $C$ is the centraliser of $\alpha$ in $\text{SL}_2(\mathbf{F}_\ell)$. The size of this centraliser can be $\ell+1$, $\ell-1$ or $2\ell$, so $\#X \ge \frac{\ell^2-1}{2}$.

We now bound $\#(X \cap V)$ by noting that every element $v$ of this intersection satisfies the quadratic equation $\text{disc}(v) = \text{disc}(\alpha)$. The discriminant quadratic form on $M_2(\mathbf{F}_\ell)/\mathbf{F}_\ell$ is isomorphic to $x^2 - yz$, so the maximal dimension of a totally isotropic subspace is 1. If $\dim V = 1$, the number of solutions is at most $\ell$. If $\dim V = 2$, either the equation is degenerate and has at most $2\ell$ solutions, or it represents a conic and has at most $\ell+1$ solutions.

So the probability of $\beta \in V$ is at most $2\ell/\frac{\ell^2-1}{2} = \frac{4\ell}{\ell^2-1}$, which is less than $1/2$ for $\ell \ge 11$. We check the bound by brute-force enumeration for $\ell \in \{3, 5, 7\}$. $\square$

**Lemma 5.3.** Suppose $\ell > 2$. Let $\alpha_1, \alpha_2, \alpha_3 \in M_2(\mathbf{F}_\ell)/\mathbf{F}_\ell$ be independent non-zero $\text{SL}_2(\mathbf{F}_\ell)$-invariant elements. Then, $(\alpha_1, \alpha_2, \alpha_3)$ is a basis of $M_2(\mathbf{F}_\ell)/\mathbf{F}_\ell$ with probability at least $1/8$.

*Proof.* Let $V_1 = \{0\}$ and $V_i = V_{i-1} + \mathbf{F}_\ell \cdot \alpha_i$. By dimensionality, we have $V_i \ne M_2(\mathbf{F}_\ell)/\mathbf{F}_\ell$ for every $i < 3$. Lemma 5.2 implies that with probability at least $1/8$, we have $\alpha_i \notin V_{i-1}$ for each $i$. When this occurs, each $V_i$ is an $\mathbf{F}_\ell$-vector space of dimension $i$, hence, $V_3 = M_2(\mathbf{F}_\ell)/\mathbf{F}_\ell$. $\square$

In our application, we will only approach $\text{SL}_2(\mathbf{F}_\ell)$-invariance, so we now derive the corresponding result for distributions that are close to $\text{SL}_2(\mathbf{F}_\ell)$-invariant.

**Proposition 5.4.** Suppose $\ell > 2$. Let $\alpha_1, \alpha_2, \alpha_3 \in M_2(\mathbf{F}_\ell)/\mathbf{F}_\ell$ be independent non-zero random elements which are $\varepsilon$-close to $\text{SL}_2(\mathbf{F}_\ell)$-invariant. Then, $(\alpha_1, \alpha_2, \alpha_3)$ is a basis of $M_2(\mathbf{F}_\ell)/\mathbf{F}_\ell$ with probability at least $1/8 - 3\varepsilon$.

*Proof.* Let $g_i \in \text{SL}_2(\mathbf{F}_\ell)$ be uniformly distributed and independent. Let $\beta_i = g_i^{-1}\alpha_i g_i$, three independent variables. For each $i$, the statistical distance between $\alpha_i$ and $\beta_i$ is at most $\varepsilon$. By the triangle inequality, the statistical distance between $(\alpha_1, \alpha_2, \alpha_3)$ and $(\beta_1, \beta_2, \beta_3)$ is at most $3\varepsilon$. From Lemma 5.3, $(\beta_1, \beta_2, \beta_3)$ is a basis of $M_2(\mathbf{F}_\ell)/\mathbf{F}_\ell$ with probability at least $1/8$. Therefore, $(\alpha_1, \alpha_2, \alpha_3)$ is a basis of $M_2(\mathbf{F}_\ell)/\mathbf{F}_\ell$ with probability at least $1/8 - 3\varepsilon$. $\square$

We now show that these results about $M_2(\mathbf{F}_\ell)$ have consequences in $M_2(\mathbf{Z}_\ell)$.

**Definition 5.5.** The level of $\alpha \in M_2(\mathbf{Z}_\ell) \setminus \mathbf{Z}_\ell$ at $\ell$ is the largest integer $\text{lev}_\ell(\alpha)$ such that $\alpha \in \mathbf{Z}_\ell + \ell^{\text{lev}_\ell(\alpha)} M_2(\mathbf{Z}_\ell)$.

**Proposition 5.6.** Suppose $\ell > 2$. Let $\alpha_1, \alpha_2, \alpha_3 \in M_2(\mathbf{Z}_\ell) \setminus \mathbf{Z}_\ell$ be three elements of level $a$. Then $(1, \alpha_1, \alpha_2, \alpha_3)$ is a $\mathbf{Z}_\ell$-basis of $\mathbf{Z}_\ell + \ell^a M_2(\mathbf{Z}_\ell)$ if and only if $(\alpha_1, \alpha_2, \alpha_3)$ is an $\mathbf{F}_\ell$-basis of $(\mathbf{Z}_\ell + \ell^a M_2(\mathbf{Z}_\ell))/(\mathbf{Z}_\ell + \ell^{a+1} M_2(\mathbf{Z}_\ell)) \cong M_2(\mathbf{F}_\ell)/\mathbf{F}_\ell$.

*Proof.* The forward implication is clear. The converse is Nakayama's lemma. $\square$
## 5.2 Dealing with hard-to-factor numbers

In the previous section, we have studied the properties of conjugacy-invariant distributions locally at a prime $\ell$. However, in our application, we may be confronted to local obstructions at an integer $N$ which is hard to factor; it is then not possible to isolate the primes $\ell$ to apply the results of the previous section.

In this section, fix a positive integer $N$. We imagine that $N$ is hard to factor, and rework the previous results “locally at $N$”. We suppose that $B$ does not ramify at any prime factor of $N$. Recall that $O \subset B$ is a maximal order.

**Definition 5.7.** An element $\alpha \in O$ is $N$-reduced if $\alpha \notin \mathbb{Z}+NO$.

**Lemma 5.8.** Let $\alpha \in O$ be a random variable supported on $N$-reduced elements. Then, there exist a prime factor $\ell$ of $N$ and an integer $a$ such that $\ell^{a+1}$ divides $N$ and $\mathrm{Pr}[\mathrm{lev}_{\ell}(\alpha) = a] \ge (\log N)^{-1}$.

*Proof.* Write the prime factorisation $N = \prod_{i=1}^t \ell_i^{e_i}$. Let $i$ and $a < e_i$ which maximise the probability $q = \mathrm{Pr}[\mathrm{lev}_{\ell_i}(\alpha) = a]$. We have

$$ \sum_{j=1}^{t} \mathrm{Pr}[\mathrm{lev}_{\ell_j}(\alpha) < e_j] = \sum_{\beta} \mathrm{Pr}[\alpha = \beta] \cdot \#\{j \mid \mathrm{lev}_{\ell_j}(\beta) < e_j\} \ge 1, $$

where the last inequality follows from the fact that the distribution is supported on $N$-reduced elements, so for every $\beta$, there exists $j$ such that $\mathrm{lev}_{\ell_j}(\beta) < e_j$. We get

$$ 1 \le \sum_{j=1}^{t} \mathrm{Pr}[\mathrm{lev}_{\ell_j}(\alpha) < e_j] = \sum_{j=1}^{t} \sum_{x < e_j} \mathrm{Pr}[\mathrm{lev}_{\ell_j}(\alpha) = x] \le q \sum_{j=1}^{t} e_j \le q \log(N). $$

We deduce $q \ge (\log N)^{-1}$. $\square$

**Definition 5.9.** Let $M$ be a ring with an isomorphism $\iota: M_2(\mathbb{Z}/N\mathbb{Z}) \to M$. The distribution of a random $\alpha \in M/\iota(\mathbb{Z}/N\mathbb{Z})$ is $\varepsilon$-close to $\mathrm{SL}_2(\mathbb{Z}/N\mathbb{Z})$-invariant if, for every $g \in \iota(\mathrm{SL}_2(\mathbb{Z}/N\mathbb{Z}))$, the statistical distance between the distributions of $\alpha$ and of $g^{-1}\alpha g$ is at most $\varepsilon$.

**Lemma 5.10.** Let $R = \mathbb{Z}/N\mathbb{Z}$, $M = O/NO \cong M_2(R)$ and $\overline{M} = M/R$. Let $\ell$ be a prime factor of $N$, and a an integer such that $\ell^{a+1} | N$. Consider a distribution $\nu$ on $\overline{M}$ that is $\varepsilon$-close to $\mathrm{SL}_2(R)$-invariant. For $\alpha$ sampled from $\nu$, let $q$ be the probability that $\alpha \ne 0$ and that a is the largest integer such that $\alpha \in \ell^a \overline{M}$.

1. Let $\alpha_1, \alpha_2, \alpha_3 \in \overline{M}$ independent random elements with distribution $\nu$. Let $\Lambda$ be the subgroup generated by $(\alpha_1, \alpha_2, \alpha_3)$. We have $\Lambda/\ell^{a+1}\overline{M} = \ell^a \overline{M}/\ell^{a+1}\overline{M}$ with probability at least $q^3/8 - 3\varepsilon$.

2. Let $\alpha_1, \alpha_2, \alpha_3 \in O$ be independent random elements such that $\alpha_i \mod \mathbb{Z}+NO$ follows the distribution $\nu$. Let $\Lambda$ be the lattice generated by $(1, \alpha_1, \alpha_2, \alpha_3)$. Then $\Lambda \otimes \mathbb{Z}_\ell = (\mathbb{Z}+\ell^a O) \otimes \mathbb{Z}_\ell$ with probability at least $q^3/8 - 3\varepsilon$.
**Proof.** Item 1, with $\varepsilon = 0$. For any $\alpha \in M$, let $\text{lev}_\ell(\alpha)$ be the largest integer such that $\alpha \in R + \ell^a M$ when it exists, and $\text{lev}_\ell(\alpha) = \infty$ otherwise. Let $L$ be the event that $\text{lev}_\ell(\alpha_i) = a$ for all $i \in \{1, 2, 3\}$. Note that the level is constant over any $\text{SL}_2(R)$-conjugacy class, so conditional on $L$, the variables $\alpha_i$ are still $\text{SL}_2(R)$-invariant. If $L$ occurs, the random variables $\alpha_i$ mod $\ell^{a+1}M$ are non-zero and $\text{SL}_2(R)$-invariant in $\ell^a M / \ell^{a+1}M \cong M_2(F_\ell)/F_\ell$. The result follows from Lemma 5.3 and the fact that $\text{Pr}[L] = q^3$.

**Item 1, with** $\varepsilon > 0$. By the triangular inequality, the triple $(\alpha_1, \alpha_2, \alpha_3)$ is $3\varepsilon$-close to a triple of $\text{SL}_2(\mathbb{Z}/N\mathbb{Z})$-invariant elements. The result thus follows from the case $\varepsilon = 0$ and the defining property of the statistical distance.

**Item 2.** This is the combination of Item 1 with Proposition 5.6. $\square$

**Proposition 5.11.** Assume that $N$ is not a cube. Let $\alpha_1, \alpha_2, \alpha_3 \in \mathcal{O}$ be three independent random elements from a distribution $\alpha$ that satisfies the following properties:

(1) $\alpha$ is supported on $N$-reduced elements;

(2) $\alpha$ mod $\mathbb{Z}+N\mathcal{O}$ is $\varepsilon$-close to $\text{SL}_2(\mathbb{Z}/N\mathbb{Z})$-invariant for $\varepsilon < \frac{1}{6000000-(\log N)^2}$.

Let $\Lambda$ be the lattice generated by $(1, \alpha_1, \alpha_2, \alpha_3)$. With probability $\Omega((\log N)^{-12})$, either $\text{gcd}(N, [\mathcal{O}:\Lambda]) = 1$, or $[\mathcal{O}:\Lambda] = N^n K$ with $\text{gcd}(N, K) \notin \{1, N\}$.

**Remark 5.12.** The exhibited event either produces a lattice $\Lambda$ that is saturated at every prime factor of $N$ (when $\text{gcd}(N, [\mathcal{O}:\Lambda]) = 1$), or reveals a non-trivial factor of $N$.

**Proof.** Let Success be the event that either $\text{gcd}(N, [\mathcal{O}:\Lambda]) = 1$, or $[\mathcal{O}:\Lambda] = N^n K$ where $\text{gcd}(N, K) \notin \{1, N\}$. Write the prime factorisation $N = \prod_{i=1}^t \ell_i^{e_i}$. Since $N$ is not a cube, we may assume without loss of generality that $\text{gcd}(e_1, 3) = 1$. Write $\mathcal{O}_i = \mathcal{O} \otimes \mathbb{Z}_{\ell_i}$ and $\Lambda_i = \Lambda \otimes \mathbb{Z}_{\ell_i}$.

We now split the proof in two cases, depending on the value of

$$q_+ = \text{Pr}[\text{lev}_{\ell_1}(\alpha) \geq e_1].$$

**Case 1:** suppose $q_+^3 > 1 - \frac{1}{2} \left( \frac{1}{8 \cdot (\log N)^3} - 3\varepsilon \right)$. Let $\ell_i$ and $a_i$ be the $\ell$ and $a$ from Lemma 5.8. Let $q = \text{Pr}[\text{lev}_{\ell_i}(\alpha) = a_i] > (\log N)^{-1}$. Let $E$ be the event that $\Lambda_i = \mathbb{Z}_{\ell_i} + \ell_i^{a_i} \mathcal{O}_i$, and let $F$ be the event that $\Lambda_1 \subseteq \mathbb{Z}_{\ell_1} + \ell_1^{e_1} \mathcal{O}_1$. Suppose $E$ and $F$ both happen. In that situation, $[\mathcal{O}_i : \Lambda_i] = \ell_i^{3a_i} < \ell_i^{3e_i}$, and $[\mathcal{O}_1 : \Lambda_1] \geq [\mathcal{O}_1 : \mathbb{Z}_{\ell_1} + \ell_1^{e_1} \mathcal{O}_1] \geq \ell_1^{3e_1}$, hence if $[\mathcal{O}:\Lambda] = N^n K$, then $\text{gcd}(K, N) \notin \{1, N\}$. So if $E$ and $F$ both happen, then Success happens. We have

$$\text{Pr}[F] = \text{Pr} \left[ \bigwedge_{j=1}^{3} (\text{lev}_{\ell_1}(\alpha_j) \geq e_1) \right] = \prod_{j=1}^{3} \text{Pr}[\text{lev}_{\ell_1}(\alpha_j) \geq e_1] = q_+^3.$$
From Lemma 5.10, $\Pr[E] = q^3/8 - 3\varepsilon$. We deduce

$$ \Pr[\text{Success}] \ge \Pr[E \land F] \ge \Pr[E] + \Pr[F] - 1 \\ = \frac{q^3}{8} - 3\varepsilon + q_+^3 - 1 \ge \frac{3}{2} \left( \frac{1}{24 \cdot (\log N)^3} - \varepsilon \right) \ge \frac{1}{32 \cdot (\log N)^3}. $$

**Case 2:** suppose $q_+^3 \le 1 - \frac{1}{2} \left( \frac{1}{8 \cdot (\log N)^3} - 3\varepsilon \right)$. Let $a_1 < e_1$ which maximises the probability

$$ q = \Pr[\text{lev}_{\ell_1}(\alpha) = a_1]. $$

We have

$$ 1 - q_+ = \sum_{x < e_1} \Pr[\text{lev}_{\ell_1}(\alpha) = x] \le e_1 q. $$

Then

$$ q \ge \frac{1 - q_+}{\log(N)} \ge \frac{1 - q_+^3}{3 \log(N)} \ge \frac{1}{48 \cdot (\log N)^4} - \frac{\varepsilon}{2 \log(N)}. $$

Let $G$ be the event that $\Lambda_1 = \mathbf{Z}_{\ell_1} + \ell_1^{a_1} M_1$. If $G$ happens and $[\mathcal{O} : \Lambda]$ is of the form $N^n K$ with $\gcd(N, K) = 1$, then $3a_1 = ne_1$. In that situation, $\gcd(e_1, 3) = 1$ implies that 3 divides $n$, and $a_1 < e_1$ implies that $n < 3$; together, these imply $n = 0$, so $\gcd(N, [\mathcal{O} : \Lambda]) = 1$. This proves that when $G$ happens, then Success happens. We deduce

$$ \Pr[\text{Success}] \ge \Pr[G] \ge \frac{q^3}{8} - 3\varepsilon = \left( \frac{1}{96 \cdot (\log N)^4} - \frac{\varepsilon}{4 \log(N)} \right)^3 - 3\varepsilon \\ \ge 3 \left( \frac{1}{3 \cdot 100^3 \cdot (\log N)^{12}} - \varepsilon \right) \\ \ge \frac{1}{2000000 \cdot (\log N)^{12}}, $$

which concludes the proof. □

# 6 Saturation and reduction

In this section, we present three algorithms to saturate a known order of endomorphisms of a supersingular curve, and to reduce an endomorphism (in the sense of Definition 5.7). The overall strategy is folklore, but only a crucial new ingredient allows it to work in polynomial time: the division algorithm due to Robert [Rob22] (see Proposition 2.3).

Let us start with saturation, which is used to deal with problematic primes in the main reduction. The running time of $\text{SATURATE}_\ell$ is polynomial in $\ell$, not in $\log \ell$, so we only use it for small $\ell$.

**Proposition 6.1.** *Algorithm 2 (SATURATE$_\ell$) is correct and runs in time polynomial in $\ell$ and the size of the input.*
**Algorithm 2** SATURATE<sub>ℓ</sub>(R<sub>0</sub>): turns an order into a super-order which is maximal at ℓ.

**Require:** A supersingular elliptic curve $E/\mathbb{F}_{p^2}$, a prime $ℓ \neq p$, and an order $R_0 \subset \text{End}(E)$.

**Ensure:** An order $R$ such that $R_0 \subseteq R \subseteq \text{End}(E)$ and $R \otimes \mathbb{Z}_\ell$ is maximal.

1: $L \leftarrow R_0$

2: **while** $\text{gcd}(\text{disc}(L), \ell) \neq 1$ **do**

3: &nbsp;&nbsp;&nbsp;&nbsp;**for** lattices $L'$ such that $[L' : L] = \ell$ **do**

4: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$\alpha \leftarrow$ an element of $L$ such that $\alpha/\ell \in L' \setminus L$

5: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$\beta \leftarrow \text{DIVIDE}(\alpha, \ell)$ an efficient representation of $\alpha/\ell$ {Proposition 2.3}

6: &nbsp;&nbsp;&nbsp;&nbsp;**if** $\beta \neq \perp$ **then**

7: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$L \leftarrow L + \mathbb{Z}\beta$

8: &nbsp;&nbsp;&nbsp;&nbsp;**end if**

9: **end for**

10: **end while**

11: **return** $L$

**Algorithm 3** SATURATERAM(R<sub>0</sub>): turns an order into a super-order which is maximal at $p$.

**Require:** A supersingular elliptic curve $E/\mathbb{F}_{p^2}$, and an order $R_0 \subset \text{End}(E)$.

**Ensure:** An order $R$ such that $R_0 \subseteq R \subseteq \text{End}(E)$ and $R \otimes \mathbb{Z}_p$ is maximal.

1: $(O_0, \iota) \leftarrow$ an order $O_0$ given by multiplication table, and an isomorphism $\iota: O_0 \to R_0$

2: $O \leftarrow$ an order containing $O_0$, maximal at $p$ with $[O : O_0]$ a power of $p$ {[IR93] or [Voi13]}

3: $(1, b_1, b_2, b_3) \leftarrow$ a basis of $O$

4: **for** $i \in \{1, 2, 3\}$ **do**

5: &nbsp;&nbsp;&nbsp;&nbsp;Write $b_i = a_i/p^{k_i}$ with $a_i \in O_0$

6: &nbsp;&nbsp;&nbsp;&nbsp;$\alpha_i \leftarrow \iota(a_i)$

7: &nbsp;&nbsp;&nbsp;&nbsp;$\beta_i \leftarrow \text{DIVIDE}(\alpha_i, p^{k_i})$ an efficient representation of $\alpha_i/p^{k_i}$ {Proposition 2.3}

8: **end for**

9: **return** $\mathbb{Z} + \mathbb{Z}\beta_1 + \mathbb{Z}\beta_2 + \mathbb{Z}\beta_3$

*Proof.* Since $\ell \neq p$, the discriminant of the maximal order $\text{End}(E)$ is coprime to $\ell$. Therefore, at each iteration, there is at least one $L'$ that is contained in $\text{End}(E)$, so that the division succeeds. Every iteration divides the discriminant by $\ell^2$, so the number of iterations is half the valuation of $\text{disc}(R_0)$ at $\ell$, which is polynomial. At every iteration, there are $O(\ell^3)$ lattices $L'$ since they correspond exactly to lines $\ell L'/\ell L \subseteq L/\ell L$. Every operation performed in the loops takes polynomial time. This proves that the algorithm terminates within the claimed running time. Consider the following properties for a lattice $M$ in $\text{End}(E)$:

(1) $R_0 \subseteq M \subseteq \text{End}(E)$;

(2) $[M : R_0]$ is a power of $\ell$;

(3) $[\text{End}(E) : M]$ is coprime to $\ell$.
There exists at most one $M$ satsifying (1)–(3). When the algorithm terminates,
the lattice $L$ satisfies (1)–(3). On the other hand, there exists an order $R$ satis-
fying (1)–(3). Therefore $R = L$, as claimed.
$\square$

**Proposition 6.2.** *Algorithm 3 (SATURATERAM) is correct and runs in polynomial time.*

*Proof.* Since $R_0 \otimes Q$ is ramified at $p$, there is a unique order $R$ containing $R_0$, maximal at $p$ with $[R : R_0]$ a power of $p$, and this order is contained in $\text{End}(E)$. This imples $(\iota \otimes Q)(\mathcal{O}) = R \subset \text{End}(E)$, so all the divisions succeed, the family $(1, \beta_1, \beta_2, \beta_3)$ is a basis of $R$, and the algorithm is correct. All the operations take polynomial time.
$\square$

We now present an algorithm to reduce endomorphisms at odd integers.

**Algorithm 4 REDUCE<sub>N</sub>(α): reduces an endomorphism α at N.**

**Require:** An endomorphism $\alpha \in \text{End}(E) \setminus \mathbb{Z}$ in efficient representation, and an odd integer $N$.

**Ensure:** An $N$-reduced endomorphism (Definition 5.7) $\beta = \frac{\alpha-t}{Ne}$ with $t, e \in \mathbb{Z}$.

1: $\gamma \leftarrow 2\alpha - \text{Tr}(\alpha)$

2: **repeat**

3: $\beta \leftarrow \gamma$

4: $\gamma \leftarrow \text{DIVIDE}(\beta, N)$ an efficient representation of $\beta/N$ {Proposition 2.3}

5: **until** $\gamma = \perp$

6: **if** $\text{Tr}(\beta) \equiv 0 \bmod 4$ **then**

7: **return** $\text{DIVIDE}(\beta, 2)$

8: **else**

9: **return** $\text{DIVIDE}(\beta + 1, 2)$

10: **end if**

**Proposition 6.3.** *Algorithm 4 (REDUCE<sub>N</sub>) is correct and runs in polynomial time.*

*Proof.* Let $e$ be the largest integer such that $\alpha \in \mathbb{Z}+N^e\text{End}(E)$. At Step 1, we have that $\gamma \in N^e\text{End}(E)$ and $\gamma \notin \mathbb{Z}+N^{e+1}\text{End}(E)$. Therefore, at the end of the loop, $\beta \in \text{End}(E)$ and $\beta \notin \mathbb{Z}+N\text{End}(E)$, i.e., $\beta$ is $N$-reduced. The last division removes the extra factor 2 introduced in Step 1, to ensure the result is of the form $\beta = \frac{\alpha-t}{Ne}$ with $t \in \mathbb{Z}$.

Let us prove that it runs in polynomial time. We have $N^{2e} | \text{disc}(\alpha)$, and at each iteration of the loop, $\text{disc}(\beta)$ gets divided by $N^2$. So the number of iterations is bounded by $e \le \log(\text{disc}(\alpha)) = O(\log \text{deg}(\alpha))$, which concludes the proof. $\square$

# 7 The reduction

In this section, we prove the main result of the paper (Theorem 1.1). We start
with a lemma putting together results from the previous sections.
<caption>**Algorithm 5** Turning an oracle $\mathcal{O}$ for ONEEND into an ENDRING algorithm</caption>

**Require:** A supersingular elliptic curve $E/\mathbb{F}_{p^2}$, and a parameter $k > 0$. We suppose access to an oracle $\mathcal{O}$ that solves the ONEEND problem.

**Ensure:** The endomorphism ring $\text{End}(E)$.

$$1: k_1 \leftarrow \left\lfloor \frac{\log(12 \cdot 9 \cdot (1+\sqrt{3}) \cdot \sqrt{p+13})}{\log(\frac{3}{2\sqrt{2}})} \right\rfloor$$

$$2: R \leftarrow \mathbb{Z}$$

$$3: \textbf{while} \ \text{rank}_{\mathbb{Z}}(R) \neq 4 \ \textbf{do}$$

$$4: \alpha \leftarrow \text{RICH}_{k_1}^{\mathcal{O}}(E), \text{ a random endomorphism of } E \text{ {Algorithm 1}}$$

$$5: R \leftarrow \text{the ring generated by } R \text{ and } \alpha$$

$$6: \textbf{end while}$$

$$7: R \leftarrow \text{SATURATE}_2(R) \{\text{Algorithm 2}\}$$

$$8: R \leftarrow \text{SATURATERAM}(R) \{\text{Algorithm 3}\}$$

$$9: [\text{End}(E) : R] \leftarrow \sqrt{\text{disc}(R)/p}$$

$10: \text{Factor } [\text{End}(E) : R] = \prod_{i=1}^{t} N_i^{e_i} \text{ where no } N_i \text{ is a cube } \{\text{a complete prime factorisation is not required; the somewhat trivial factorisation } [\text{End}(E) : R] = N_1^{3n} \text{ where } N_1^{1/3} \notin \mathbb{Z} \text{ and } n \ge 0 \text{ is sufficient as a starting point, and the subsequent steps of the algorithm may refine it}\}$

$11: \textbf{while} \ [\text{End}(E) : R] \neq 1 \ \textbf{do}$

$$12: N \leftarrow N_t$$

$$13: k_2 \leftarrow \left\lfloor 12 \cdot \log (4100000 \cdot (\log N)^{12} N^2 \sqrt{p+13}) \right\rfloor$$

$14: \text{Let } \mathcal{O}_N \text{ the oracle which given } E, \text{ runs } \alpha \leftarrow \mathcal{O}(E) \text{ and returns } \text{REDUCEN}(\alpha)$

$15: \alpha_i \leftarrow \text{RICH}_{k_2}^{\mathcal{O}_N}(E) \text{ for } i \in \{1, 2, 3\}, \text{ random endomorphisms of } E \text{ {Algorithm 1}}$

$16: \Lambda \leftarrow \text{the lattice generated by } (1, \alpha_1, \alpha_2, \alpha_3)$

$17: \textbf{if} \ \text{rank}_{\mathbb{Z}}(\Lambda) = 4 \ \textbf{then}$

$18: n \leftarrow \text{the largest integer such that } N^n \text{ divides } [\text{End}(E) : \Lambda]$

$19: d \leftarrow \text{gcd}([\text{End}(E) : \Lambda]/N^n, N)$

$20: \textbf{if} \ d \neq 1 \ \textbf{then}$

$21: \text{Update the factorisation of } [\text{End}(E) : R] \text{ with } N = d \cdot (N/d)$

$22: \textbf{end if}$

$23: \textbf{if} \ \Lambda \not\subset R \ \textbf{then}$

$24: R \leftarrow \text{the order generated by } R \text{ and } \Lambda$

$25: \text{Recompute } [\text{End}(E) : R] = \sqrt{\text{disc}(R)/p}, \text{ and update its factorisation}$

$26: \textbf{end if}$

$27: \textbf{end if}$

$28: \textbf{end while}$

$29: \textbf{return } R$

**Lemma 7.1.** Let $\mathcal{O}$ be an oracle for ONEEND, and $N$ an odd integer. Let $\mathcal{O}_N$ be the oracle which on input $E$, samples $\alpha \leftarrow \mathcal{O}(E)$, and returns $\text{REDUCEN}(\alpha)$. For any

$$k \ge 12 \cdot \log (4100000 \cdot (\log N)^{12} N^2 \sqrt{p+13}),$$

the output of $\text{RICH}_k^{\mathcal{O}_N}$ satisfies the conditions of Proposition 5.11.

*Proof.* Let $\varphi: E \to E'$ of degree a power of 2. For any endomorphism $\beta \in \text{End}(E')$, since $N$ is odd, we have that $\beta$ is $N$-reduced if and only if $\varphi \circ \beta \circ \varphi$
is $N$-reduced. The output of $\text{RICH}_k^{\mathcal{O}_N}$ is of the form $\hat{\phi} \circ \text{REDUCE}_N(\alpha) \circ \varphi$, so is $N$-reduced. So the distribution of $\text{RICH}_k^{\mathcal{O}_N}$ satisfies Item 1 of Proposition 5.11.

From Theorem 4.2, $\text{RICH}_k^{\mathcal{O}_N}$ mod $N$ is $\varepsilon$-close to $\text{SL}_2(\mathbb{Z}/N\mathbb{Z})$-invariant for

$$ \varepsilon = \frac{1 + \sqrt{3}}{4} \left( \frac{2\sqrt{2}}{3} \right)^k N^2 \sqrt{p+13}. $$

With

$$ k \ge \frac{\log \left( 6000000 \cdot (\log N)^{12} \cdot \frac{1+\sqrt{3}}{4} N^2 \sqrt{p+13} \right)}{\log \left( \frac{3}{2\sqrt{2}} \right)}, $$

we have $\varepsilon \le (6000000 \cdot (\log N)^{12})^{-1}$, satisfying Item 2 of Proposition 5.11. $\square$

We now have all the ingredients to prove our main result.

**Theorem 7.2 (ENDRING reduces to ONEEND).** *Algorithm 5 is a reduction from ENDRING to ONEEND$_\lambda$ of expected polynomial time in $\log(p)$ and $\lambda(\log p)$.*

*Proof.* The correctness is clear as at any time, $R$ is a subring of $\text{End}(E)$, and the success condition $[\text{End}(E) : R] = 1$ implies $R = \text{End}(E)$.

We now analyse the expected running time.

**First loop (Step 3 to Step 6).** First, let us analyse the expected number of iterations of the first loop. From Theorem 4.2, each $\alpha$ generated during this loop is $\varepsilon$-close to $\text{SL}_2(\mathbb{F}_3)$-invariant with

$$ \varepsilon = \frac{1 + \sqrt{3}}{4} \left( \frac{2\sqrt{2}}{3} \right)^{k_1} 3^2 \sqrt{p+13}. $$

Choosing $k_1 = O(\log p)$ as in Step 1, we have $\varepsilon \le 1/48$.

Consider any three consecutively generated elements $\alpha_1, \alpha_2, \alpha_3$. Let $t = \max_i \text{lev}_3(\alpha_i)$, and $\beta_i = 3^{t-\text{lev}_3(\alpha_i)} \alpha_i$, so all $\beta_i$ are at the same level $t$. Like the variables $\alpha_i$, the variables $\beta_i$ are $\varepsilon$-close to $\text{SL}_2(\mathbb{F}_3)$-invariant. Combining Proposition 5.4 and Proposition 5.6, the tuple $(1, \beta_1, \beta_2, \beta_3)$ generates a full-rank lattice with probability at least $1/8 - 3\varepsilon$, and so does $(1, \alpha_1, \alpha_2, \alpha_3)$. Choosing $k_1$ as above, this probability is at least $1/16$. We deduce that the loop terminates after an expected $O(1)$ number of iterations.

Let us now analyse the output of this loop. Let $R_1$ be the order $R$ obtained at the end of the first loop. Let $\alpha_i$ be any three elements generated during the loop such that $(1, \alpha_1, \alpha_2, \alpha_3)$ are independent. Combining the bound $\text{deg}(\alpha_i) \le 2^{2k_1\lambda(\log p)}$ and Hadamard's inequality, we get

$$ \text{disc}(R_1) = 16 \cdot \text{Vol}(R_1)^2 \le 16 \cdot \prod_{i=1}^{3} \sqrt{\text{deg}(\alpha_i)} \le 16 \cdot 2^{6k_1\lambda(\log p)}. $$

We deduce that

$$ [\text{End}(E) : R_1] \le 2^{3k_1\lambda(\log p)+2}/p = 2^{O(\log(p)\cdot\lambda(\log p))}. \quad (1) $$
**Second loop (Step 11 to Step 28).** It remains to analyse the second loop. An iteration of this loop is a success if either Step 21 or Step 24 is reached. In case of success, either a new factor of $[\mathrm{End}(E) : R]$ is found (Step 21), or $[\mathrm{End}(E) : R]$ gets divided by an integer at least 2 (Step 24). The number of successes is thus polynomially bounded in $\log([\mathrm{End}(E) : R_1])$, hence in $\mathrm{poly}(\log p, \lambda(\log p))$ (thanks to Equation (1)). Therefore, we only have to prove that as long as $R \neq \mathrm{End}(E)$, each iteration has a good probability of success.

The event analysed in Proposition 5.11 corresponds precisely to a success. By Lemma 7.1, the distribution of $\alpha_i$ satisfies the conditions of Proposition 5.11. Therefore, Proposition 5.11 implies that each iteration has a probability of success $\Omega((\log N)^{-12})$, which concludes the proof. □

# 8 Applications

In this section we describe four applications of our main result.

## 8.1 Collision resistance of the Charles–Goren–Lauter hash function

The first cryptographic construction based on the supersingular isogeny problem is a hash function proposed by Charles, Goren and Lauter [CLG09], the CGL hash function. Fix a (small) prime number $\ell$, typically $\ell = 2$. For any elliptic curve $E$, there are $\ell + 1$ outgoing $\ell$-isogenies $E \to E'$ (up to isomorphism of the target), so given a curve and an incoming $E'' \to E$, there remain $\ell$ non-backtracking $\ell$-isogenies from $E$, which can be arbitrarily labelled by the set $\{0, \dots, \ell - 1\}$. Then, fixing an initial curve $E_0$ and an arbitrary isogeny $E_{-1} \to E_0$, the set $\{0, \dots, \ell - 1\}^*$ encodes non-backtracking paths from $E_0$ in the $\ell$-isogeny graph. The CGL hash function

$$ \mathrm{CGL}_{E_0} : \{0, \dots, \ell - 1\}^* \to \mathbf{F}_{p^2} $$

associates to any sequence $(x_i)_i$ the $j$-invariant of the endpoint of the walk from $E_0$ it encodes. Clearly, this function is pre-image resistant if and only if $\ell$-ISOGENYPATH is hard. However, if $\mathrm{End}(E_0)$ is known, one can find collisions in polynomial time [KLPT14,EHL$^{+}$18]. Therefore, it was proposed to sample the starting curve randomly. Let SAMPLESS($p$) be an algorithm sampling a uniformly random supersingular elliptic curve over $\mathbf{F}_{p^2}$. We define the advantage of a collision-finding algorithm $\mathcal{A}$ for the CGL family of hash functions as

$$ \mathrm{Adv}_{\mathrm{CGL}}^{\mathcal{A}}(p) = \mathrm{Pr} \left[ \begin{array}{l} m \neq m' \text{ and} \\ \mathrm{CGL}_E(m) = \mathrm{CGL}_E(m') \end{array} \middle| \begin{array}{l} E \leftarrow \mathrm{SAMPLESS}(p) \\ (m, m') \leftarrow \mathcal{A}(E) \end{array} \right]. $$

It was heuristically argued in [EHL$^{+}$18] that the collision resistance of this construction is equivalent to ENDRING. The flaws of the heuristics are discussed in Section 1.2. With our main theorem, we can now prove this resistance.

**Theorem 8.1 (Collision resistance of the CGL hash function).** For any algorithm $\mathcal{A}$, there is an algorithm to solve ENDRING in expected polynomial time in $\log(p)$, in $\mathrm{Adv}_{\mathrm{CGL}}^{\mathcal{A}}(p)^{-1}$ and in the expected running time of $\mathcal{A}$.
*Proof.* Since ENDRING is equivalent to ONEEND (Theorem 1.1), it is sufficient to prove that $\mathcal{A}$ can be used to solve ONEEND. First, let us prove that a successful collision for CGL$_E$ gives a non-scalar endomorphism of $E$. Let $\varphi, \psi: E \to E'$ be two distinct non-backtracking walks, i.e., isogenies of cyclic kernel of order $\ell^a$ and $\ell^b$ respectively. If $\hat{\varphi} \circ \psi$ is scalar, the degrees imply that $a + b$ is even and $\hat{\varphi} \circ \psi = [\ell^{\frac{a+b}{2}}]$. Without loss of generality, suppose $b \ge a$. From the defining property of the dual isogeny, we deduce that $\hat{\psi} = [\ell^{\frac{b-a}{2}}]\hat{\varphi}$. Taking the dual again, we get $\psi = [\ell^{\frac{b-a}{2}}]\varphi$. If $b > a$, then $\{0_E\} \ne E[\ell^{\frac{b-a}{2}}] \subseteq \ker \psi$, contradicting the cyclicity of $\ker \psi$. Therefore $b = a$, and we conclude that $\psi = \varphi$, a contradiction. So $\hat{\varphi} \circ \psi$ is non-scalar.

Now, given a curve $E$, we can solve ONEEND as follows:

1. First take a random walk $\eta: E \to E'$, so that $E'$ has statistical distance $\varepsilon = O(1/p)$ from uniform (Proposition 2.7);

2. Then call $\mathcal{A}(E')$, which gives a non-scalar endomorphism $\alpha$ of $E'$ with probability at least $\mathrm{Adv}_{\mathrm{CGL}}(p) - \varepsilon$,

3. Return $\hat{\eta} \circ \alpha \circ \eta$.

The algorithm is successful after an expected $(\mathrm{Adv}_{\mathrm{CGL}}^\mathcal{A}(p) - \varepsilon)^{-1}$ number of attempts. This works within the claimed running time if $\mathrm{Adv}_{\mathrm{CGL}}(p) > 2\varepsilon$. Otherwise, we have $(\mathrm{Adv}_{\mathrm{CGL}}^\mathcal{A}(p))^{-1} = \Omega(p)$, and one can indeed solve ENDRING in time polynomial in $p$ (see [Koh96, Theorem 75] for the first such algorithm, in time $\tilde{O}(p)$, or Theorem 8.7 below for time $\tilde{O}(p^{1/2})$). $\square$

## 8.2 Soundness of the SQIsign identification scheme

SQIsign is a digital signature scheme proposed in [DKL$^{+}$20]. SQIsign, and its variant SQIsignHD [DLRW23], offer the most compact public keys and signatures of all known post-quantum constructions. Note that the results from this section apply equally to SQIsign and SQIsignHD. This digital signature scheme is constructed as an identification protocol, turned into a signature by the Fiat-Shamir transform. The protocol proves knowledge of a witness for a problem that closely resembles ONEEND. While [DKL$^{+}$20] heuristically argues that the protocol is sound if ENDRING is hard, our main theorem allows us to prove it.

Let SQISIGN.PARAM be the SQIsign public parameter generation procedure, which on input a security level $k$, outputs data pp which encodes, among other things, a prime number $p = \Theta(2^{2k})$. Let SQISIGN.KEYGEN be the SQIsign key generation procedure, which on input pp, outputs a pair (pk, sk). The public key pk is a supersingular elliptic curve over $\mathbb{F}_{p^2}$, and sk is its endomorphism ring.

Let $\mathcal{V}$ be an honest verifier for the SQIsign identification protocol. For any (malicious) prover $\mathcal{P}^*$ and parameters pp, run the following experiment: first, sample a key pair (pk, sk) $\leftarrow$ SQISIGN.KEYGEN(pp), and give pk to $\mathcal{P}^*$. Then, run the SQIsign identification protocol between $\mathcal{P}^*$ and $\mathcal{V}$ with input pk. Let $\pi^{\mathcal{P}^*}(pp)$ be the probability that $\mathcal{V}$ outputs $\top$ at the end of the protocol. We define the soundness advantage $\mathrm{Adv}_{\mathrm{SQIsound}}^{\mathcal{P}^*}(pp) = \pi^{\mathcal{P}^*}(pp) - 1/c$, where $c = \Theta(2^k)$ is the size of the challenge space.
In other words, $\pi^{\mathcal{P}^*}(\mathbf{pp})$ is the probability that $\mathcal{P}^*$ successfully fools an honest verifier, for a random key. Since there is a simple malicious prover achieving $\pi^{\mathcal{P}^*}(\mathbf{pp}) = 1/c$ (by guessing the challenge at the start of the protocol), the advantage $\mathrm{Adv}_{\mathrm{SQIsound}}^{\mathcal{P}^*}(\mathbf{pp})$ measures how much better $\mathcal{P}^*$ performs.

**Theorem 8.2 (Soundness of SQIsign).** Let $\mathcal{P}^*$ be a malicious prover. Consider public parameters $\mathbf{pp}$, encoding the prime $p$. There is an algorithm to solve ENDRING for curves over $\mathbf{F}_{p^2}$ in expected polynomial time in $\log(p)$, in $\mathrm{Adv}_{\mathrm{SQIsound}}^{\mathcal{P}^*}(\mathbf{pp})^{-1}$ and in the expected running time of $\mathcal{P}^*$.

*Proof.* Let $r$ denote the expected running time of $\mathcal{P}^*$. From [DKL$^+$20, Theorem 1], there is an algorithm of expected running time

$$r' = O\left(\frac{r}{\mathrm{Adv}_{\mathrm{SQIsound}}^{\mathcal{P}^*}(\mathbf{pp})}\right)$$

for the supersingular smooth endomorphism problem, with solutions of length $O(\log p)$. The supersingular smooth endomorphism problem is defined as ONEEND with the additional constraint that the output has smooth degree. Therefore, the same algorithm solves ONEEND. The result follows from the equivalence between ONEEND and ENDRING (Theorem 1.1). □

The same theorem is true with the quantity $\pi^{\mathcal{P}^*}(\mathbf{pp})^{-1}$ in place of $\mathrm{Adv}_{\mathrm{SQIsound}}^{\mathcal{P}^*}(\mathbf{pp})^{-1}$, which may be more natural. In the proof, we would get

$$r' = O\left(\frac{r}{\pi^{\mathcal{P}^*}(\mathbf{pp}) - 1/c}\right).$$

Note that $r'$ is not necessarily polynomial in $\pi^{\mathcal{P}^*}(\mathbf{pp})^{-1}$, as $\pi^{\mathcal{P}^*}(\mathbf{pp})$ could be arbitrarily close to $1/c$. We can consider two cases: first, if $\pi^{\mathcal{P}^*}(\mathbf{pp}) > 2/c$, we have $\pi^{\mathcal{P}^*}(\mathbf{pp}) - 1/c > \pi^{\mathcal{P}^*}(\mathbf{pp})/2$ and we can conclude as above. Second, if $\pi^{\mathcal{P}^*}(\mathbf{pp}) \le 2/c$, then $\pi^{\mathcal{P}^*}(\mathbf{pp})^{-1} \ge c/2 = \Omega(2^k) = \Omega(p^{1/2})$, so we can conclude from the fact that there exists an algorithm for ENDRING in expected time $\tilde{O}(p^{1/2})$ (see Theorem 8.7).

## 8.3 The endomorphism ring problem is equivalent to the isogeny problem

It is known that the problem ENDRING is equivalent to the $\ell$-isogeny path problem (assuming the generalised Riemann hypothesis [Wes22b]). The same technique shows that ENDRING is equivalent to the problem of finding isogenies of smooth degree. Lifting this restriction yields the more general ISOGENY problem.

**Problem 8.3 (ISOGENY)** Given a prime $p$ and two supersingular elliptic curves $E$ and $E'$ over $\mathbf{F}_{p^2}$, find an isogeny from $E$ to $E'$ in efficient representation.
Given a function $\lambda: \mathbb{Z}_{>0} \to \mathbb{Z}_{>0}$, the ISOGENY$_\lambda$ problem denotes the ISOGENY problem where the solution $\varphi$ is required to satisfy $\log(\deg \varphi) \le \lambda(\log p)$ (the length of the output is bounded by a function of the length of the input).

From previous literature, it is easy to see that ISOGENY reduces to ENDRING.

**Proposition 8.4 (ISOGENY reduces to ENDRING).** *Assuming the generalised Riemann hypothesis, the problem ISOGENY$_\lambda$ reduces to ENDRING in probabilistic polynomial time (with respect to the length of the instance), for some function $\lambda(\log p) = O(\log p)$.*

*Proof.* ISOGENY immediately reduces to $\ell$-ISOGENYPATH. It is already known that the $\ell$-isogeny path problem (with paths of length $O(\log p)$) is equivalent to ENDRING [Wes22b], so ISOGENY$_\lambda$ reduces to ENDRING. $\square$

The converse reduction is trickier. As a solution to ISOGENY is not guaranteed to have smooth degree, previous techniques have failed to prove that it is equivalent to ENDRING. Theorem 1.1 unlocks this equivalence. Better yet, contrary to previous results of this form, Theorem 8.5 below is unconditional. In particular, it implies that ENDRING reduces to the $\ell$-isogeny path problem independently of the generalised Riemann hypothesis.

**Theorem 8.5 (ENDRING reduces to ISOGENY).** *Given an oracle for ISOGENY$_\lambda$, there is an algorithm for ENDRING that runs in expected polynomial time in $\log(p)$ and $\lambda(\log p)$.*

**Algorithm 6 Solving ONEEND given an ISOGENY oracle.**

**Require:** A supersingular elliptic curve $E/\mathbb{F}_{p^2}$, a parameter $\epsilon > 0$, an oracle $\tilde{O}_{\text{ISOGENY}}$ solving the ISOGENY$_\lambda$ problem.

**Ensure:** An endomorphism $\alpha \in \text{End}(E) \setminus \mathbb{Z}$ in efficient representation.

1: $P \leftarrow$ an arbitrary nonzero point in $E[2]$

2: $n \leftarrow \lceil 2 \log_3(p) - 4 \log_3(\epsilon) \rceil$

3: **while** true **do**

4: &nbsp;&nbsp;&nbsp;&nbsp; $\varphi \leftarrow$ a non-backtracking random walk $\varphi: E \to E'$ of length $n$ in the 3-isogeny graph

5: &nbsp;&nbsp;&nbsp;&nbsp; $\nu \leftarrow$ the isogeny $\nu: E' \to E''$ of kernel $\langle\varphi(P)\rangle$

6: &nbsp;&nbsp;&nbsp;&nbsp; $\psi \leftarrow \tilde{O}_{\text{ISOGENY}}(E'', E)$, an isogeny $\psi: E'' \to E$

7: &nbsp;&nbsp;&nbsp;&nbsp; $\alpha \leftarrow (\psi \circ \nu \circ \varphi)/2^e \in \text{End}(E)$ for the largest possible $e$

8: &nbsp;&nbsp;&nbsp;&nbsp; **if** $2 | \text{deg}(\alpha)$ **then**

9: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; **return** $\alpha$

10: **end if**

11: **end while**

*Proof.* Since ENDRING is equivalent to ONEEND (Theorem 1.1), let us prove that ONEEND reduces to ISOGENY. Suppose we have an oracle $\tilde{O}_{\text{ISOGENY}}$ for ISOGENY$_\lambda$. Let $E$ be a supersingular curve for which we want to solve ONEEND. Consider
a parameter $\varepsilon$. The reduction is described in Algorithm 6. Step 7 and Step 8 ensure that $\alpha$ is not a scalar (indeed, they ensure that upon return, at Step 9, we have $2 \nmid \alpha$ yet $2 \mid \deg(\alpha)$), so is a valid solution to ONEEND.

Let us show that the expected number of iterations of the while-loop is $O(1)$. Let $f \in \mathbb{Z}$ maximal such that $E''[2^f] \subseteq \ker(\psi)$, and let $\psi' = \psi/2^f$. If $\deg(\psi')$ is odd, then $\alpha$ is non-scalar (its degree is divisible by 2 but not by 4) and the loop terminates at this iteration. Now, suppose $\deg(\psi')$ is even and write $\ker(\psi') \cap E''[2] = G_\psi$, a group of order 2. The loop in the reduction terminates in the event that $\ker \hat{\nu} \neq G_\psi$. In the rest of the proof, we bound the probability of this event at each iteration.

Let $P$ be the probability distribution of the pair $(E'', \hat{\nu})$, and $Q$ the probability distribution of the pair $(E'', \eta)$ where $\eta$ is uniformly random (among the three 2-isogenies from $E''$). Note that by construction, the value $Q(E'', \eta)$ does not depend on $\eta$, and we also write it $\tilde{Q}(E'')$. Consider the function $\tau$ defined in [BCC$^+$23, Lemma 14]. We have

$$ \tau(p, 2, 3, k) = \frac{1}{4}(p-1)^{1/2} \left(1 + \sqrt{3}\right) \left(k + \frac{1}{2}\right) 3^{-k/2} \le p^{1/2} 3^{-k/4}. $$

From [BCC$^+$23, Lemma 14], if $\tau(p, 2, 3, k) \le \varepsilon$, then the statistical distance $\|P - Q\|_1/2$ is at most $\varepsilon$. This condition is satisfied if the 3-walk $\varphi$ has length at least

$$ \begin{aligned} n(p, 2, 3, \varepsilon) &= \min\{k \mid \tau(p, 2, 3, k) \le \varepsilon\} \\ &\le \min\{k \mid p^{1/2} 3^{-k/4} \le \varepsilon\} = 2 \log_3(p) - 4 \log_3(\varepsilon). \end{aligned} $$

We deduce that indeed $\|P - Q\|_1 < \varepsilon$, since $\varphi$ has length $\lceil 2 \log_3(p) - 4 \log_3(\varepsilon) \rceil$. We now obtain the following bound:

$$ \begin{aligned} \Pr[\ker \hat{\nu} = G_{\psi}] &= \sum_{(E'', \hat{\nu})} P(E'', \hat{\nu}) \Pr[\ker \hat{\nu} = G_{\psi} \mid (E'', \hat{\nu})] \\ &\le \sum_{(E'', \hat{\nu})} (Q(E'', \hat{\nu}) + \max_{\eta} |P(E'', \eta) - Q(E'', \eta)|) \Pr[\ker \hat{\nu} = G_{\psi} \mid E''] \\ &\le \sum_{E''} \tilde{Q}(E'') + \sum_{E''} \max_{\eta} |P(E'', \eta) - Q(E'', \eta)| \le \frac{1}{3} + \varepsilon. \end{aligned} $$

The second line uses that for any fixed $E''$, the distribution of $\psi$ is independent of $\nu$. In conclusion, at each iteration, the event $\ker \hat{\nu} \neq G_\psi$ (leading to termination) happens with probability at least $2/3 - \varepsilon$. With $\varepsilon < 1/3$, the expected number of iterations is at most $(2/3 - \varepsilon)^{-1} \le 3 = O(1)$. $\square$

## 8.4 An unconditional algorithm for ENDRING in time $\tilde{O}(p^{1/2})$

As the foundational problem of isogeny-based cryptography, understanding the hardness of ENDRING is critical. The fastest known algorithms have complexity
in $\tilde{O}(p^{1/2})$, but rely on unproven assumptions such as the generalised Riemann hypothesis. With our new results, we can now prove that `ENDRING` can be solved in time $\tilde{O}(p^{1/2})$ unconditionally. In contrast, the previous fastest unconditional algorithm had complexity $\tilde{O}(p)$ and only returned a full-rank subring of the endomorphism ring [Koh96, Theorem 75].

The first method to reach complexity $\tilde{O}(p^{1/2})$ under the generalised Riemann hypothesis consists in reducing `ENDRING` to $\ell$-ISOGENYPATH (via [Wes22b]), and solving $\ell$-ISOGENYPATH by a generic graph path-finding algorithm. Unconditionally, we can follow the same strategy, but using our new reduction from `ENDRING` to $\ell$-ISOGENYPATH (Theorem 8.5). Let us start by recalling the following folklore solution to $\ell$-ISOGENYPATH.

**Proposition 8.6.** *Algorithm 7 solves the $\ell$-ISOGENYPATH problem in expected time poly($\ell, \log p)p^{1/2}$ and returns paths of length $O(\log p)$.*

<caption>**Algorithm 7** Solving $\ell$-ISOGENYPATH.</caption>

**Require:** Two supersingular elliptic curves $E_0/\mathbb{F}_{p^2}$ and $E_1/\mathbb{F}_{p^2}$, a parameter $n$.
**Ensure:** An $\ell$-isogeny path $E_0 \to E_1$.
1: $T \leftarrow \emptyset$ an empty hash table
2: **while** $\#T < p^{1/2}$ **do**
3: &nbsp;&nbsp;&nbsp;&nbsp; $\varphi \leftarrow$ a random walk $\varphi: E_0 \to E$ of length $n$ in the $\ell$-isogeny graph
4: &nbsp;&nbsp;&nbsp;&nbsp; **if** $j(E)$ is not the key of any entry in $T$ **then**
5: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; Record $\varphi$ in $T$, with key $j(E)$
6: &nbsp;&nbsp;&nbsp;&nbsp; **end if**
7: **end while**
8: **while** true **do**
9: &nbsp;&nbsp;&nbsp;&nbsp; $\psi \leftarrow$ a random walk $\psi: E_1 \to E$ of length $n$ in the $\ell$-isogeny graph
10: &nbsp;&nbsp;&nbsp;&nbsp; **if** $j(E)$ is the key of a recorded entry $\varphi$ in $T$ **then**
11: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; **return** $\hat{\varphi} \circ \psi: E_0 \to E_1$
12: &nbsp;&nbsp;&nbsp;&nbsp; **end if**
13: **end while**

*Proof.* Algorithm 7 is a standard bi-directional pathfinding algorithm. Choose the parameter $n$ as in Proposition 2.7, so that random isogeny paths of length $O(\log p)$ reach a target at statistical distance $O(1/p)$ from uniform. The $\ell$-isogeny graph has $O(p)$ vertices, and each sampled curve is close to uniform, so the table is complete after $O(p^{1/2})$ iterations of the first loop. By the same token, thanks to the birthday paradox, the second loop finds a matching entry after an expected $O(p^{1/2})$ number of attempts. The factor $\text{poly}(\ell, \log p)$ accounts for the cost of sampling an isogeny path and checking that a candidate is in the table. $\square$

**Theorem 8.7.** *There is an algorithm solving `ENDRING` in expected time $\tilde{O}(p^{1/2})$.*

*Proof.* This follows from the fact that there is an algorithm of complexity $\tilde{O}(p^{1/2})$ for the 2-isogeny path problem (Proposition 8.6), and `ENDRING` reduces to polynomially many instances of the $\ell$-isogeny path problem (Theorem 8.5). $\square$
References

Arp23. Sarah Arpin. Adding level structure to supersingular elliptic curve isogeny graphs. Preprint arXiv:2203.03531, 2023. https://arxiv.org/abs/2203.03531.

BCC$^{+}$23. Andrea Basso, Giulio Codogni, Deirdre Connolly, Luca De Feo, Tako Boris Fouotsa, Guido Maria Lido, Travis Morrison, Lorenz Panny, Sikhar Patranabis, and Benjamin Wesolowski. Supersingular curves you can trust. In Carmit Hazay and Martijn Stam, editors, *Advances in Cryptology - EUROCRYPT 2023*, volume 14005 of *Lecture Notes in Computer Science*, pages 405-437. Springer, 2023.

CD23. Wouter Castryck and Thomas Decru. An efficient key recovery attack on SIDH. In *Advances in cryptology—EUROCRYPT 2023. Part V*, volume 14008 of *Lecture Notes in Comput. Sci.*, pages 423–447. Springer, Cham, [2023] ©2023.

CL23. Giulio Codogni and Guido Lido. Spectral theory of isogeny graphs. Preprint arXiv:2308.13913, 2023. https://arxiv.org/abs/2308.13913.

CLG09. Denis X. Charles, Kristin E. Lauter, and Eyal Z. Goren. Cryptographic hash functions from expander graphs. *Journal of Cryptology*, 22(1):93–113, Jan 2009.

Del73. Pierre Deligne. La conjecture de Weil. I. *Publ. Math., Inst. Hautes Étud. Sci.*, 43:273–307, 1973.

Deu41. Max Deuring. Die typen der multiplikatorenringe elliptischer funktionalenkörper. *Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg*, 14(1):197–272, 1941.

DKL$^{+}$20. Luca De Feo, David Kohel, Antonin Leroux, Christophe Petit, and Benjamin Wesolowski. Sqisign: Compact post-quantum signatures from quaternions and isogenies. In Shiho Moriai and Huaxiong Wang, editors, *Advances in Cryptology - ASIACRYPT 2020 - 26th International Conference on the Theory and Application of Cryptology and Information Security*, volume 12491 of *Lecture Notes in Computer Science*, pages 64–93. Springer, 2020.

DLRW23. Pierrick Dartois, Antonin Leroux, Damien Robert, and Benjamin Wesolowski. SQISignHD: New dimensions in cryptography. IACR Cryptology ePrint Archive, Report 2023/436, 2023. https://eprint.iacr.org/2023/436.

DV13. Lassina Dembélé and John Voight. Explicit methods for Hilbert modular forms. In *Elliptic curves, Hilbert modular forms and Galois deformations*, pages 135–198. Basel: Birkhäuser/Springer, 2013.

EHL$^{+}$18. Kirsten Eisenträger, Sean Hallgren, Kristin Lauter, Travis Morrison, and Christophe Petit. Supersingular isogeny graphs and endomorphism rings: Reductions and solutions. In Jesper Buus Nielsen and Vincent Rijmen, editors, *Advances in Cryptology - EUROCRYPT 2018*, pages 329–368, Cham, 2018. Springer International Publishing.

FIK$^{+}$23. Jenny Fuselier, Annamaria Iezzi, Mark Kozek, Travis Morrison, and Changningphaabi Namoijam. Computing supersingular endomorphism rings using inseparable endomorphisms. Preprint arXiv:2306.03051, 2023. https://arxiv.org/abs/2306.03051.

HLMW23. Arthur Herlédan Le Merdy and Benjamin Wesolowski. The supersingular endomorphism ring problem given one endomorphism. Preprint arXiv:2309.11912, 2023. https://arxiv.org/abs/2309.11912.
IR93. Gábor Ivanyos and Lajos Rónyai. Finding maximal orders in semisimple algebras over $\mathbb{Q}$. *Comput. Complexity*, 3(3):245-261, 1993.

JL70. H. Jacquet and R. P. Langlands. *Automorphic forms on GL(2)*, volume 114 of *Lect. Notes Math*. Springer, Cham, 1970.

KLPT14. David Kohel, Kristin Lauter, Christophe Petit, and Jean-Pierre Tignol. On the quaternion $\ell$-isogeny path problem. *LMS Journal of Computation and Mathematics*, 17(A):418-432, 2014.

Koh96. David Kohel. *Endomorphism rings of elliptic curves over finite fields*. PhD thesis, University of California, Berkeley, 1996.

LM23. Antonio Lei and Katharina Müller. On towers of isogeny graphs with full level structure. Preprint arXiv:2309.00524, 2023. https://arxiv.org/abs/2309.00524.

Mes86. Jean-François Mestre. La méthode des graphes. exemples et applications. In *Proceedings of the international conference on class numbers and fundamental units of algebraic number fields (Katata)*, pages 217-242, 1986.

ML98. Saunders Mac Lane. *Categories for the working mathematician*, volume 5 of *Graduate Texts in Mathematics*. Springer-Verlag, New York, second edition, 1998.

MMP$^{+}$23. Luciano Maino, Chloe Martindale, Lorenz Panny, Giacomo Pope, and Benjamin Wesolowski. A direct key recovery attack on SIDH. In Carmit Hazay and Martijn Stam, editors, *Advances in Cryptology - EUROCRYPT 2023. Part V*, volume 14008 of *Lecture Notes in Computer Science*, pages 448-471. Springer, 2023.

Piz90. Arnold K Pizer. Ramanujan graphs and Hecke operators. *Bulletin of the American Mathematical Society*, 23(1):127-137, 1990.

Rob22. Damien Robert. Some applications of higher dimensional isogenies to elliptic curves (overview of results). Cryptology ePrint Archive, Paper 2022/1704, 2022. https://eprint.iacr.org/2022/1704.

Rob23. Damien Robert. Breaking SIDH in polynomial time. In *Advances in cryptology-EUROCRYPT 2023. Part V*, volume 14008 of *Lecture Notes in Comput. Sci.*, pages 472-503. Springer, Cham, [2023] ©2023.

Sil86. Joseph H. Silverman. *The Arithmetic of Elliptic Curves*, volume 106 of *Graduate Texts in Mathematics*. Springer-Verlag, 1986.

Voi13. John Voight. Identifying the matrix ring: algorithms for quaternion algebras and quadratic forms. In *Quadratic and higher degree forms*, pages 255-298. New York, NY: Springer, 2013.

Voi21. John Voight. *Quaternion Algebras*. Springer International Publishing, 2021. Graduate Texts in Mathematics, No. 288.

Wes22a. Benjamin Wesolowski. Orientations and the supersingular endomorphism ring problem. In Orr Dunkelman and Stefan Dziembowski, editors, *Advances in Cryptology - EUROCRYPT 2022*, volume 13277 of *Lecture Notes in Computer Science*, pages 345-371. Springer, 2022.

Wes22b. Benjamin Wesolowski. The supersingular isogeny path and endomorphism ring problems are equivalent. In *FOCS 2021-62nd Annual IEEE Symposium on Foundations of Computer Science*, 2022.
# A Illustration of our equidistribution theorem

In this appendix, we give some more examples and comments on the use of Theorem 3.10 and Proposition 3.11.

## A.1 Distributions and functions

Recall the definition of our adjacency operator on $L^2(G_F)$:

$$A_{\ell}F(x) = \sum_{x \to y} F(y),$$

where the sum runs over edges of degree $\ell$ leaving $x$. This sum always has $\ell + 1$ terms. In some situations it is more natural to use a different operator $B_{\ell}$:

$$B_{\ell}F(x) = \sum_{x \leftarrow y} F(y)$$

where the sum runs over edges of degree $\ell$ arriving at $x$. This sum may have fewer than $\ell + 1$ terms, due to automorphisms.

In order to relate the two operators, it is convenient to compute the adjoint of $A_{\ell}$. Let $\mu$ be the measure on $G_F$ (recall $\mu(x) = \frac{1}{\# \mathrm{Aut}(x)}$). We have

$$\begin{aligned}
\langle A_{\ell}F, G \rangle &= \sum_{x} A_{\ell}F(x) \overline{G(x)}\mu(x) \\
&= \sum_{x} \sum_{x \to y} F(y) \overline{G(x)}\mu(x) \\
&= \sum_{y} \sum_{x \leftarrow y} F(y) \overline{G(x)}\mu(x) \\
&= \sum_{y} F(y) \left( \frac{1}{\mu(y)} \sum_{x \leftarrow y} \overline{G(x)}\mu(x) \right) \mu(y) \\
&= \langle F, A_{\ell}^*G \rangle,
\end{aligned}$$

where

$$A_{\ell}^{*}G(x) = \frac{1}{\mu(x)} \sum_{x \leftarrow y} G(y)\mu(y).$$

We therefore introduce the “diagonal” operator $M$ on $L^2(G_F)$ defined by

$$MF(x) = F(x)\mu(x),$$

so that we have

$$A_{\ell}^{*} = M^{-1}B_{\ell}M \text{ i.e. } B_{\ell} = MA_{\ell}^{*}M^{-1}.$$

Since $A_{\ell}^{*}$ has the same orthogonal eigenvectors as $A_{\ell}$, with complex conjugate eigenvalues, this gives the spectral decomposition of $B_{\ell}$.
For instance, the action of one step of a degree $\ell$ random walk on a distribution on $\mathcal{G}_F$ is given by $\frac{B_\ell}{\ell+1}$. Therefore, in the case where $\mathcal{G}_F^1$ is connected, $L_{\deg}^2(\mathcal{G}_F)$ is one-dimensional generated by the constant function $1$ equal to $1$ everywhere, so we obtain that for every $F$, the sequence $(\frac{A_\ell}{\ell+1})^k F$ quickly converges to a constant function, and therefore for every distribution $f$, the distribution $(\frac{B_\ell}{\ell+1})^k f$ obtained after $k$ steps of the random walk converges to the distribution $M1 = \mu$, i.e. to the stationary distribution.

## A.2 Explicit orthogonal projection onto $L_{\deg}^2$

Another useful tool is the explicit decomposition of functions according to $L^2(\mathcal{G}_F) = L_{\deg}^2(\mathcal{G}_F) \oplus L_0^2(\mathcal{G}_F)$. We first introduce some notation: for two vertices $x, y$ of $\mathcal{G}_F$, write $x \sim y$ if they are in the same connected component of $\mathcal{G}_F^1$ (this is an equivalence relation). Moreover, for every vertex $x$, let

$$W(x) = \sum_{y \sim x} \mu(y).$$

If $x \sim y$, then $W(x) = W(y)$. We now define an operator $P$ on $L^2(\mathcal{G}_F)$:

$$PF(x) = \frac{1}{W(x)} \sum_{y \sim x} F(y)\mu(y).$$

The function $PF$ is clearly in $L_{\deg}^2(\mathcal{G}_F)$, and if $F \in L_{\deg}^2(\mathcal{G}_F)$ then $PF = F$; therefore $P$ is a projector onto $L_{\deg}^2(\mathcal{G}_F)$. In order to prove that $P$ is the desired orthogonal projector, it is enough to show that it is self-adjoint. Let $F, G \in L^2(\mathcal{G}_F)$, then

$$ \begin{aligned} \langle PF, G \rangle &= \sum_x PF(x) \overline{G(x)} \mu(x) \\ &= \sum_x \frac{1}{W(x)} \sum_{y \sim x} F(y) \mu(y) \overline{G(x)} \mu(x) \\ &= \sum_y \sum_{x \sim y} \frac{1}{W(x)} F(y) \mu(y) \overline{G(x)} \mu(x) \\ &= \sum_y \sum_{x \sim y} \frac{1}{W(y)} F(y) \mu(y) \overline{G(x)} \mu(x) \\ &= \sum_y F(y) \left( \frac{1}{W(y)} \sum_{x \sim y} \overline{G(x)} \mu(x) \right) \mu(y) \\ &= \langle F, PG \rangle. \end{aligned} $$

So $P$, being self-adjoint, is the orthogonal projection onto $L_{\deg}^2(\mathcal{G}_F)$. Note that one can also see this formula as the sum of the orthogonal projections onto the indicator functions of the connected components of $\mathcal{G}_F^1$.
### A.3 Equidistribution over an entire connected component of $\mathcal{G}_F$

Assume that $\mathcal{G}_F$ is connected (one can always reduce to this case by considering connected components). The existence of the map $\text{Deg}$ and the resulting action of $A_\ell$ on $L_{\text{deg}}^2(\mathcal{G}_F)$ often force the $\ell$-part of $\mathcal{G}_F$ to be disconnected and/or multipartite, preventing degree $\ell$ random walks from properly equidistributing. One may be tempted to think that there is a fundamental obstruction to the equidistribution of random walks on the whole of $\mathcal{G}_F$. We will see here that this is not the case: one can easily obtain full equidistribution, simply by using several primes for the random walk (in other words, in general the disconnectedness of $\mathcal{G}_F$ is the only fundamental obstruction to equidistribution).

Pick a bound $X$, and assume that $\Sigma$ contains every prime $\ell < X$ that does not divide $pN$. Let $\mathcal{N}(X)$ denote the number of such primes, so that we have $\mathcal{N}(X) \approx \frac{X}{\log X}$. Define the operator $\Delta$ on $L^2(\mathcal{G}_F)$ by

$$ \Delta = \frac{1}{\mathcal{N}(X)} \sum_{\ell < X} \frac{A_\ell}{\ell + 1}. $$

The interpretation of $\Delta$ is that one step of the corresponding random walk consists in choosing a prime $\ell < X$ uniformly at random, and then using one step of the degree $\ell$ random walk.

Since the $A_\ell$ are normal operators that pairwise commute, $\Delta$ is also a normal operator, stabilises $L_{\text{deg}}^2(\mathcal{G}_F)$ and $L_0^2(\mathcal{G}_F)$, and is diagonalisable in the same orthogonal basis as the $A_\ell$. We bound its eigenvalues and operator norm.

- On $L_0^2(\mathcal{G}_F)$, the operator norm of $\Delta$ is bounded by

$$ \frac{1}{\mathcal{N}(X)} \sum_{\ell < X} \frac{2\sqrt{\ell}}{\ell + 1} \approx \frac{1}{\sqrt{X}}. $$

- On $L_{\text{deg}}^2(\mathcal{G}_F)$, there is one eigenvector for each character $\chi$ of $(\mathbb{Z}/N\mathbb{Z})^\times$ that vanishes on $\text{deg}(H)$ (with the notations of Proposition 3.11), with eigenvalue 1 if $\chi$ is the trivial character, and otherwise

$$ \frac{1}{\mathcal{N}(X)} \sum_{\ell < X} \chi(\ell) \approx \frac{1}{\sqrt{X}}. $$

For $X$ large enough, all the eigenvalues are therefore small, except for the eigenvalue 1 corresponding to the constant function. Moreover, these approximation can be turned into good bounds under the generalised Riemann hypothesis. Therefore, for a moderate value of $X$, the random walk corresponding to $\Delta$ will quickly equidistribute over the whole of $\mathcal{G}_F$.

### A.4 Example: graphs attached to endomorphisms modulo $\ell$

It is often convenient to use a functor slightly different from $\text{End}/N$, namely the functor $\mathcal{F}$ (for $\Sigma$ the set of all primes not dividing $N$) defined by
- $\mathcal{F}(E) = \text{End}(E)/N \text{End}(E);$

- $\mathcal{F}(\varphi): \alpha \mapsto (\deg \varphi)^{-1}\varphi\alpha\hat{\varphi}$ (which makes sense: $\deg \varphi$ is invertible mod $N$).

The main reason to prefer this functor is that for every isogeny $\varphi: E \to E'$, the map $\mathcal{F}(\varphi): \text{End}(E)/N \text{End}(E) \to \text{End}(E')/N \text{End}(E')$ is a ring homomorphism, and therefore preserves the trace, degree, dual, minimal polynomial and level. This functor clearly satisfies the (mod $N$)-congruence property. We will describe the connected components of the graphs $\mathcal{G}_{\mathcal{F}}$, and $\mathcal{G}_{\mathcal{F}}^1$, and the graph $\mathcal{G}_{\text{deg}}$.

For simplicity, we will assume $N = \ell$ is an odd prime different from $p$, but the other cases can be treated similarly. We recall the classification of conjugacy classes in $M_2(\mathbf{F}_\ell)$ and their centraliser in $\text{GL}_2(\mathbf{F}_\ell)$:

(1) Homotheties

$$ \begin{pmatrix} a & 0 \\ 0 & a \end{pmatrix} \text{ for } a \in \mathbf{F}_\ell. $$

The centraliser $H$ of such a matrix is $\text{GL}_2(\mathbf{F}_\ell)$, and $\det(H) = \mathbf{F}_\ell^\times$.

(2) Diagonalisable matrices, with representatives

$$ \begin{pmatrix} a & 0 \\ 0 & b \end{pmatrix} \text{ for } a \neq b \in \mathbf{F}_\ell. $$

The centraliser $H$ of such a matrix is

$$ \begin{pmatrix} * & 0 \\ 0 & * \end{pmatrix} \cong \mathbf{F}_\ell^\times \times \mathbf{F}_\ell^\times, $$

and $\det(H) = \mathbf{F}_\ell^\times$. Two matrices in such a conjugacy class are also $\text{SL}_2(\mathbf{F}_\ell)$-conjugate.

(3) Semisimple, non-diagonalisable matrices, with representatives

$$ \Psi(\lambda) \text{ for } \lambda \in \mathbf{F}_{\ell^2}, $$

where $\Psi: \mathbf{F}_{\ell^2} \to M_2(\mathbf{F}_\ell)$ is the ring homomorphism given by the action on an $\mathbf{F}_\ell$-basis of $\mathbf{F}_{\ell^2}$. The centraliser of such a matrix is $H = \Psi(\mathbf{F}_{\ell^2}^\times) \cong \mathbf{F}_{\ell^2}^\times$ and $\det(H) = \mathbf{F}_\ell^\times$. Two matrices in such a conjugacy class are also $\text{SL}_2(\mathbf{F}_\ell)$-conjugate.

(4) Non-semisimple matrices, with representatives

$$ \begin{pmatrix} a & 1 \\ 0 & a \end{pmatrix} \text{ for } a \in \mathbf{F}_\ell. $$

The centraliser of such a matrix is

$$ H = \left\{ \begin{pmatrix} c & d \\ 0 & c \end{pmatrix} \mid c \in \mathbf{F}_{\ell}^{\times}, d \in \mathbf{F}_{\ell} \right\}, $$

and $\det(H) = (\mathbf{F}_\ell^\times)^2$. Each such conjugacy class splits into two $\text{SL}_2(\mathbf{F}_\ell)$-conjugacy class, with representatives

$$ \begin{pmatrix} a & \varepsilon \\ 0 & a \end{pmatrix} \text{ for } a \in \mathbf{F}_\ell \text{ and } \varepsilon \in \mathbf{F}_\ell^\times / (\mathbf{F}_\ell^\times)^2; $$
under conjugacy by an element $g \in GL_2(\mathbf{F}_\ell)$, the entry $\varepsilon$ of the representative gets multiplied by $\det(g)$ modulo $(\mathbf{F}_\ell^\times)^2$.

In particular, conjugacy classes are completely characterised by the pair (characteristic polynomial, minimal polynomial).

For every $E \in SS(p)$, choose an isomorphism $\psi_E: \mathrm{End}(E)/\ell \mathrm{End}(E) \cong M_2(\mathbf{F}_\ell)$. By Proposition 3.11 (3), two vertices $(E, \alpha)$ and $(E, \beta)$ above the same curve $E$ are connected if and only if $\alpha$ and $\beta$ are conjugate in $\mathrm{End}(E)/\ell \mathrm{End}(E)$, if and only if $\psi_E(\alpha)$ and $\psi_E(\beta)$ are conjugate. Moreover, since any two curves are connected and the $\mathcal{F}(\varphi)$ are ring isomorphisms, the connected components of $\mathcal{G}_\mathcal{F}$ are exactly the

$$ \{(E, \alpha) : \psi_E(\alpha) \in C\} $$

where $C$ is a conjugacy class in $M_2(\mathbf{F}_\ell)$. Fix $\eta \in \mathbf{F}_\ell^\times \setminus (\mathbf{F}_\ell^\times)^2$. We have $\deg(H) = \mathbf{F}_\ell^\times$ for all types, except (4) where $\deg(H) = (\mathbf{F}_\ell^\times)^2$. So the graph $\mathcal{G}_{\deg}$ consists in one isolated vertex for each $C$, except for type (4) which gives a connected component with two vertices $\{1, \eta\}$, connected by edges labelled by the elements of $\mathbf{F}_\ell^\times \setminus (\mathbf{F}_\ell^\times)^2$.

We now consider $\mathcal{G}_\mathcal{F}^1$. By Proposition 3.11 (3), two vertices $(E, \alpha)$ and $(E, \beta)$ above the same curve $E$ are connected in $\mathcal{G}_\mathcal{F}^1$ if and only if $\alpha$ and $\beta$ are conjugate in $\mathrm{End}(E)/\ell \mathrm{End}(E)$ by an element of degree 1 mod $\ell$, if and only if $\psi_E(\alpha)$ and $\psi_E(\beta)$ are $\mathrm{SL}_2(\mathbf{F}_\ell)$-conjugate.

For any ring $R$ and $g \in R^\times$, let $\mathrm{Ad}(g)$ denote the endomorphism of $R$ given by $r \mapsto grg^{-1}$. Let $E \in SS(p)$. By Proposition 3.11 (2), there exists $\varphi: E_0 \to E$ of degree 1 mod $\ell$. The composition $\psi_E \circ \mathcal{F}(\varphi) \circ \psi_{E_0}^{-1}$ is an automorphism of $M_2(\mathbf{F}_\ell)$, hence of the form $\mathrm{Ad}(g)$ for some $g \in GL_2(\mathbf{F}_\ell)$. Changing $\psi_E$ if necessary (by an interior automorphism), we may assume that $\det g \in (\mathbf{F}_\ell^\times)^2$. In this case, this property holds for all $\varphi': E_0 \to E$ of degree 1 mod $\ell$:

$$ \begin{align*} \psi_E \circ \mathcal{F}(\varphi') \circ \psi_{E_0}^{-1} &= \psi_E \circ \mathcal{F}(\varphi) \circ \mathcal{F}(\varphi^{-1}\varphi') \circ \psi_{E_0}^{-1} \\ &= \psi_E \circ \mathcal{F}(\varphi) \circ \mathrm{Ad}(\varphi^{-1}\varphi') \circ \psi_{E_0}^{-1} \\ &= \psi_E \circ \mathcal{F}(\varphi) \circ \psi_{E_0}^{-1} \circ \mathrm{Ad}(\psi_{E_0}(\varphi^{-1}\varphi')) \\ &= \mathrm{Ad}(g) \circ \mathrm{Ad}(\psi_{E_0}(\varphi^{-1}\varphi')) \\ &= \mathrm{Ad}(g\psi_{E_0}(\varphi^{-1}\varphi')), \end{align*} $$

and $\det \psi_{E_0}(\varphi^{-1}\varphi') = \deg(\varphi^{-1}\varphi') = 1 \mod \ell$.

Now let $(E_0, \alpha)$ and $(E, \beta)$ be vertices. Since $E$ and $E_0$ are connected by an isogeny $\varphi$ of degree 1 mod $\ell$, the vertices $(E_0, \alpha)$ and $(E, \beta)$ are connected if and only if $(E, \mathcal{F}(\varphi)(\alpha))$ and $(E, \beta)$ are connected, if and only if $\psi_E(\mathcal{F}(\varphi)(\alpha))$ and $\psi_E(\beta)$ are $\mathrm{SL}_2(\mathbf{F}_\ell)$-conjugate, if and only if $\psi_{E_0}(\alpha)$ and $\psi_E(\beta)$ are $\mathrm{SL}_2(\mathbf{F}_\ell)$-conjugate by our assumption on $\psi_E$.

In other words, the connected components of $\mathcal{G}_\mathcal{F}^1$ are the

$$ \{(E, \alpha) : \psi_E(\alpha) \in C\} $$

for $C$ a conjugacy class in $M_2(\mathbf{F}_\ell)$ not of type (4), and the

$$ \{(E, \alpha) : \psi_E(\alpha) \in C_1\} \text{ and } \{(E, \alpha) : \psi_E(\alpha) \in C_\eta\} $$
for $C$ a conjugacy class in $M_2(\mathbf{F}_\ell)$ of type (4). (The point of our assumption was to make sure that components $C_1$ and $C_\eta$ are not swapped by an isogeny $\varphi$ of degree 1 mod $\ell$.)

## A.5 Example: endomorphism transported by a random walk

Let us examine the following situation: let $E_0 \in \mathrm{SS}(p)$ and $\alpha_0 \in \mathrm{End}(E_0)$, let $\varphi: E_0 \to E$ be the result of a $k$-steps random walk of 2-isogenies, and let $\alpha = \varphi\alpha_0\varphi$. What is the distribution of $(E, \alpha \bmod N)$ as $k \to \infty$? Again, for simplicity we treat the prime case $N = \ell \neq p$.

We first determine the behaviour of the random walk using the functor $\mathcal{F}$ from Section A.4. We choose $\psi_E: \mathrm{End}(E)/\ell \mathrm{End}(E) \cong M_2(\mathbf{F}_\ell)$ with the same compatibility condition as in that section. Let $C$ be the conjugacy class of the matrix $\psi_{E_0}(\alpha \bmod \ell)$.

Let $f$ be a distribution on the vertices of $\mathcal{G}_\mathcal{F}$. As in Section A.1, since the effect of one step of random walk is given by $f \mapsto \frac{B_2}{3}f$, it is convenient to encode $f$ into a function $F \in L^2(\mathcal{G}_\mathcal{F})$ by the formula $F(E, \beta) = f(E, \beta)\mu(E, \beta)$, so that the action is given by $F \mapsto \frac{A_2^*}{3}F$. The initial distribution $f_0$ is defined by

$$f_0(E_0, \alpha_0 \bmod \ell) = 1$$

and $f_0$ is 0 everywhere else, so the corresponding initial function $F_0$ is defined by

$$F_0(E_0, \alpha_0 \bmod \ell) = \mu(E_0, \alpha_0 \bmod \ell)^{-1}$$

and $F_0$ is 0 everywhere else. Using the projection formula from Section A.2, we see that $PF_0$ is the indicator function of the connected component of $(E_0, \alpha_0 \bmod \ell)$, scaled by $W(E_0, \alpha_0 \bmod \ell)$. We use the corresponding function on $\mathcal{G}_{\mathrm{deg}}$ to determine the action of $\frac{A_2^*}{3}$.

- $C$ is not of type (4): the vertex $\mathrm{Deg}(E_0, \alpha_0 \bmod \ell)$ is an isolated vertex in $\mathcal{G}_{\mathrm{deg}}$, and the action of $\frac{A_2^*}{3}$ is trivial.

- $C$ is of type (4): the connected component of $\mathrm{Deg}(E_0, \alpha_0 \bmod \ell)$ in $\mathcal{G}_{\mathrm{deg}}$ consists of two vertices. The action of $\frac{A_2^*}{3}$ is trivial if $2 \in (\mathbf{F}_\ell^\times)^2$, and swaps the two vertices otherwise.

Coming back to functions on $\mathcal{G}_\mathcal{F}$, we obtain the following.

- If $C$ is not of type (4), or if 2 is a square modulo $\ell$, or if $k$ is even, then we have $(\frac{A_2^*}{3})^k PF_0 = PF_0$, i.e. $(\frac{B_2}{3})^k f_0$ is close to the distribution supported on the connected component of $(E_0, \alpha_0 \bmod \ell)$ and where the probability of $(E, \beta)$ is proportional to $\mu(E, \beta)$.

- Otherwise, $(\frac{A_2^*}{3})^k PF_0$ is the scaled indicator function of the connected component of $\mathcal{G}_\mathcal{F}^1$ corresponding to $C_{\eta\varepsilon}$, where $\psi_{E_0}(\alpha_0 \bmod \ell) \in C_\varepsilon$, i.e. $(\frac{B_2}{3})^k f_0$ is close to the distribution supported on that connected component and where the probability of $(E, \beta)$ is proportional to $\mu(E, \beta)$.
Finally, the actual distribution of $\alpha \mod \ell$ is obtained by taking the distributions described above, and multiplying the corresponding random endomorphism mod $\ell$ by $2^k$ (which usually changes the conjugacy class). The statistical distance to the distribution obtained by projection onto $L_{\deg}(\mathcal{G}_{\mathcal{F}})$ can be estimated using the eigenvalue bounds of Theorem 3.10.

## A.6 Distribution of isogenies produced by random walks

Let $\ell$ be a prime and $E_0 \in \text{SS}(p)$. A natural question is: what is the distribution of the isogenies $\varphi: E_0 \to E$ produced by a long random $\ell$-isogeny walk starting from $E_0$? Our equidistribution theorem gives nontrivial information about this, in the following form. Let $N \ge 2$ be an integer not divisible by $\ell$. We are going to look at the distribution of $\varphi \mod N \in \text{Hom}(E_0, E)/N \text{Hom}(E_0, E)$.

Let $\Sigma$ be the set of all primes not dividing $N$. We introduce the functor $\mathcal{F} = (\text{Hom}(E_0, -)/N)^\times: \text{SS}_\Sigma(p) \to \text{Sets}$:

$$ - \mathcal{F}(E) = \{\varphi \in \text{Hom}(E_0, E)/N \text{Hom}(E_0, E) \mid \text{deg}(\varphi) \in (\mathbb{Z}/N\mathbb{Z})^\times\}; $$

$$ - \text{for } \psi \in \text{Hom}_{\Sigma}(E, E'), \text{ the map } \mathcal{F}(\psi): \mathcal{F}(E) \to \mathcal{F}(E') \text{ is } \varphi \mapsto \psi \circ \varphi. $$

The functor $\mathcal{F}$ clearly satisfies the $(\text{mod } N)$-congruence property.

The action of the group $G = (\text{End}(E_0)/N \text{End}(E_0))^\times$ on the set $\mathcal{F}(E_0) = (\text{End}(E_0)/N \text{End}(E_0))^\times$ is the left regular action, and therefore has a unique orbit with trivial stabiliser $H = 1$ (we choose $x = \text{id}$ as the base point). Therefore $\mathcal{G}_{\deg}$ is the Cayley graph of $(\mathbb{Z}/N\mathbb{Z})^\times$, and the map $\text{Deg}: \mathcal{G}_{\mathcal{F}} \to \mathcal{G}_{\deg}$ sends $(E, \varphi)$ to $\text{deg} \varphi \mod N$.

We obtain the following proposition.

**Proposition A.1.** Let $k \ge 0$. Let $\varphi: E_0 \to E_\varphi$ be the random isogeny obtained by a $k$-step $\ell$-isogeny random walk from $E_0$. Let $\nu$ be the distribution on pairs $(E, \psi)$ where $\psi \in \text{Hom}(E_0, E)/N \text{Hom}(E_0, E)$ has degree $\ell^k \mod N$, up to isomorphism, given by probability proportional to $\frac{1}{\#\text{Aut}(E, \psi)}$. Then the statistical distance between the distribution of $(E_\varphi, \varphi \mod N)$ and $\nu$ is at most

$$ \frac{1}{2\sqrt{6}} \left( \frac{2\sqrt{\ell}}{\ell+1} \right)^k N^2 \sqrt{p}. $$

*Proof.* Let $f \in L^2(\mathcal{G}_{\mathcal{F}})$ be such that $f(E_0, \text{id}) = \#\text{Aut}(E_0, \text{id})$ and $f(E, \psi) = 0$ for all other vertices $(E, \psi)$. Then for all $(E, \psi) \in \mathcal{G}_{\mathcal{F}}$ we have

$$ \frac{1}{\# \text{Aut}(E, \psi)} \left( \frac{A_{\ell}^{*}}{\ell + 1} \right)^k f(E, \psi) = \text{Pr}[(E_{\varphi}, \varphi \mod N) = (E, \psi)] $$

(see Section A.1). Let $f = f_0 + f_1$ with $f \in L_0^2(\mathcal{G}_{\mathcal{F}})$ and $f_1 \in L_{\deg}^2(\mathcal{G}_{\mathcal{F}})$ be the orthogonal decomposition of $f$. Then $f_1$ is proportional to the function that takes the value 1 on all $(E, \psi)$ with $\text{deg} \psi = 1 \in (\mathbb{Z}/N\mathbb{Z})^\times$ and 0 elsewhere, and

$$ \frac{1}{\# \text{Aut}(E, \psi)} \left( \frac{A_{\ell}^{*}}{\ell + 1} \right)^k f_1(E, \psi) = \text{Pr}_{\nu}[(E, \psi)]. $$
The statistical distance in the statement is therefore

$$ \begin{align*} & \sum_{(E, \psi)} \frac{1}{\# \mathrm{Aut}(E, \psi)} \left| \left( \frac{A_{\ell}^*}{\ell+1} \right)^k f_0(E, \psi) \right| \\ & \le \left( \sum_{(E, \psi)} \frac{1}{\# \mathrm{Aut}(E, \psi)} \right)^{1/2} \left\| \left( \frac{A_{\ell}^*}{\ell+1} \right)^k f_0 \right\| \quad (\text{Cauchy-Schwarz}) \\ & \le \left( N^4 \frac{p-1}{24} \right)^{1/2} \left( \frac{2\sqrt{\ell}}{\ell+1} \right)^k \|f\| \\ & \le N^2 \sqrt{\frac{p}{24}} \left( \frac{2\sqrt{\ell}}{\ell+1} \right)^k, \end{align*} $$

as claimed.

□

**Corollary A.2.** Keep the notations of Proposition A.1. There exists a bound $n = O(\log_{\ell}(pN) - \log_{\ell}(\varepsilon))$ such that for all $E$ and all $k \ge n$, conditional on $E_{\varphi} = E$, the distribution of $\varphi \bmod N$ is $\varepsilon$-close to uniform among isogenies of degree $\ell^k \bmod N$.

## A.7 Computation of End(E): the obvious $\tilde{O}(p^{1/2})$ algorithm works

Theorem 8.7 states that one can compute End(E) in expected time $\tilde{O}(p^{1/2})$ unconditionally. However, if we unravel the reductions leading to this theorem, the resulting algorithm seems needlessly complicated. Here, we unconditionally show that the obvious collision-based algorithm to compute endomorphisms also yields End(E) in expected time $\tilde{O}(p^{1/2})$.

**Algorithm 8 Finding an endomorphism by collisions**

**Require:** A supersingular elliptic curve $E_0/F_{p^2}$, a parameter $k$.

**Ensure:** An endomorphism of $E_0$.

1: $T \leftarrow \emptyset$ an empty hash table

2: **while** true **do**

3: &nbsp;&nbsp;&nbsp;&nbsp; $\psi \leftarrow$ a random walk $\psi: E_0 \to E$ of length $k$ in the $\ell$-isogeny graph

4: &nbsp;&nbsp;&nbsp;&nbsp; **if** $j(E)$ is the key of a recorded entry $\varphi$ in $T$ **then**

5: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; **return** $\hat{\varphi} \circ \psi \in \mathrm{End}(E_0)$

6: &nbsp;&nbsp;&nbsp;&nbsp; **else**

7: &nbsp;&nbsp;&nbsp;&nbsp; Record $\varphi$ in $T$, with key $j(E)$

8: &nbsp;&nbsp;&nbsp;&nbsp; **end if**

9: **end while**

An easy consequence of Corollary A.2 is the following.
**Proposition A.3.** There exists a bound $n = O(\log_{\ell}(pN))$ such that for all choices of parameter $k \ge n$, Algorithm 8 runs in expected time poly($\ell, \log p, k)p^{1/2}$, and the endomorphisms produced are $O(1/p)$-close to uniform modulo $N$ among endomorphisms of degree $\ell^{2k} \in (\mathbb{Z}/N\mathbb{Z})^\times$.

From Proposition A.3, it is easy to see (by an analysis similar to Section 5 and Section 7 but easier) that for polynomial choices of $k$ with $\ell \in \{2, 3\}$, the endomorphisms output by Algorithm 8 generate $\text{End}(E_0)$ after polynomially many calls. A variant also provides a reduction from $\text{ENDRING}$ to $\text{ISOGENY}$ alternative to the proof of Theorem 8.5.