$\#\mathcal{A}[d] = d^{2g}$ and $\#\ker(\tilde{F}) = \#\ker(F) = d^g$. Hence, $\#F(\mathcal{A}[d]) = d^g = \#\ker(\tilde{F})$ and $\ker(\tilde{F}) = F(\mathcal{A}[d])$. Point (iii) follows.

(iv) Suppose $\ker(F)$ has rank $g$. Let $(x_1, \dots, x_g)$ be a basis of generators of $\ker(F)$. Then, the $x_i$ all have order $d$ and are linearly independent over $\mathbb{Z}/d\mathbb{Z}$. Then, $\ker(F) \cap \mathcal{A}[d_1] = ([d_2]x_1, \dots, [d_2]x_g)$ and the $[d_2]x_i$ all have order $d_1$ and are linearly independent over $\mathbb{Z}/d_1\mathbb{Z}$, so that $\#\ker(F) \cap \mathcal{A}[d_1] = d_1^g = \#\ker(F_1)$. The equality $\ker(F_1) = \ker(F) \cap \mathcal{A}[d_1]$ follows by (ii).

To prove that $\ker(\tilde{F}_2) = F(\mathcal{A}[d]) \cap \mathcal{B}[d_2]$, it suffices to prove that $F(\mathcal{A}[d]) = \ker(\tilde{F})$ has rank $g$ and the preceding reasoning will apply. We have $F(\mathcal{A}[d]) \cong \mathcal{A}[d]/\ker(F)$, so it suffices to prove that there is a subgroup $G \subset \mathcal{A}[d]$ of rank $g$ such that $\ker(F) \oplus G = \mathcal{A}[d]$, because, we will have $F(\mathcal{A}[d]) \cong G$. We consider the $d$-th Weil pairing $e_d^{\lambda_A} : \mathcal{A}[d]^2 \to \mu_d(\mathbb{F}_p)$, where $\mu_d(\mathbb{F}_p)$ is the group of $d$-th roots of unity in $\mathbb{F}_p$, and the group homomorphism

$$ \Phi : \mathcal{A}[d] \to \mu_d(\mathbb{F}_p)^g \\ y \mapsto (e_d^{\lambda_A}(x_i, y))_{1 \le i \le g}. $$

Since $\ker(F)$ is maximal isotropic, we have $\ker(\Phi) = \ker(F)$. It follows that $\#\mathrm{im}(\Phi) = \#\mathcal{A}[d]/\#\ker(\Phi) = d^{2g}/d^g = d^g$, so that $\mathrm{im}(\Phi) = \mu_d(\mathbb{F}_p)^g$ i.e. $\Phi$ is surjective. Let $\zeta \in \mu_d(\mathbb{F}_p)$ be a primitive $d$-th root of unity. Then, for all $j \in [1; g]$ there exists $y_j \in \mathcal{A}[d]$ such that $e_d^{\lambda_A}(x_i, y_j) = \zeta^{\delta_{i,j}}$ for all $i \in [1; g]$, where $\delta_{i,j}$ is the Kronecker delta. It follows that the $y_i$ all have order $d$ (since $e_d^{\lambda_A}(x_i, y_i) = \zeta$ has order $d$), are linearly independent over $\mathbb{Z}/d\mathbb{Z}$ and linearly independent of the $x_i$. We can then take $G := (y_1, \dots, y_g)$. This completes the proof. $\square$

## E.4 Correctness of RepresentIsogeny$_{g, \ell_e, \ell_f}$ (Proposition 14)

**Proposition 14.** Algorithms 4 and 15 are correct. Namely, Algorithm 4 returns $F_1, \tilde{F}_2$ such that $F_2 \circ F_1 = F(\sigma, a_1, a_2)$ on entry $a_1, a_2, P_1, P_2, \sigma(P_2), \sigma(P_2)$, where $\sigma : E_1 \to E_2$ is a $q$-isogeny with $a_1^2 + a_2^2 + q = \ell^e$ (and similarly for Algorithm 15).

*Proof.* We assume that Algorithm 4 received $a_1, a_2, P_1, P_2, \sigma(P_2), \sigma(P_2)$ on entry. Let us write $F^* := F(\sigma, a_1, a_2)$ and decompose $F^* := F_2^* \circ F_1^*$, where $F_1^*$ is an $\ell^{e_1}$-isogeny of kernel $\ker(F^*)[\ell^{e_1}]$ and $\tilde{F}_2^*$ is an $\ell^{e_2}$-isogeny of kernel $F^*(E_1^2 \times E_2^2[\ell^{e_2}])$. Then, by construction the outputs $F_1$ and $\tilde{F}_2$ of Algorithm 4 satisfy $\ker(F_1) = \ker(F_1^*)$, $\ker(\tilde{F}_2) = \ker(\tilde{F}_2^*)$, $\mathrm{deg}(F_1) = \mathrm{deg}(F_1^*)$ and $\mathrm{deg}(\tilde{F}_2) = \mathrm{deg}(\tilde{F}_2^*)$. Hence, by [Mum74, Theorem 4, p.73] if we denote $(\mathcal{C}, \lambda_C)$ the common codomain of $F_1$ and $\tilde{F}_2$ and $(\mathcal{C}^*, \lambda_{\mathcal{C}^*})$ the common codomain of $F_1^*$ and $\tilde{F}_2^*$, then we get that $F_1 = \lambda \circ F_1^*$ and $\tilde{F}_2 = \mu \circ \tilde{F}_2^*$, where $\lambda$ and $\mu$ are isomorphisms $(\mathcal{C}^*, \lambda_{\mathcal{C}^*}) \xrightarrow{\sim} (\mathcal{C}, \lambda_C)$.

To conclude, we need to be more specific about the way $F_1$ and $\tilde{F}_2$ are computed explicitly with the theta-model of level 2 (see Appendix F.3). To ensure $F_1$
and $\tilde{F}_2$ define the same level-structure on $C[4]$, we use Algorithm 20 outputting two symplectic basis of $E_1^2 \times E_2^2[4^{\max(e_1,e_2)}]$ satisfying the compatibility equation of Corollary 58. The output of this algorithm only depends on the input $a_1, a_2, P_1, P_2, \sigma(P_2), \sigma(P_2)$, so it would be the same if we applied it for $F_1^*$ and $\tilde{F}_2^*$. It follows that $(C, \lambda_C) = (C^*, \lambda_{C^*})$ and that $F_1$ and $F_1^*$ coincide on $F_1^{-1}(C[4])$, so that $\lambda$ and $\text{id}_C$ coincide on $C[4]$, so that $\lambda = \text{id}_C$ by [Mil86, Proposition 17.5.(b)]. Similarly, $\tilde{F}_2$ and $\tilde{F}_2^*$ coincide on $\tilde{F}_2^{-1}(C[4])$, so that $\mu = \text{id}_C$. It follows that $F_2 \circ F_1 = F^* = F(\sigma, a_1, a_2)$, so Algorithm 4 is correct. The same proof applies to Algorithm 15. $\square$

## E.5 Verification (Proposition 15 and Corollary 16)

**Proposition 15.** Algorithms 5 and 16 are correct. Namely, when given $E_1, E_2, a_1, a_2, F_1, \tilde{F}_2$, if Algorithm 5 returns True, then $F_2 \circ F_1$ is an efficient representation of an isogeny $\sigma : E_1 \to E_2$ of degree $q = \ell^e - a_1^2 - a_2^2$ (and similarly for Algorithm 16).

*Proof.* Assume that Algorithm 5 returns True on input $E_1, E_2, a_1, a_2, F_1, \tilde{F}_2$. Then, $F := F_2 \circ F_1$ is well defined and is an $\ell^e$-isogeny. We may write $F := (f_{i,j})_{1 \le i,j \le 4} \in \text{End}(E_1^2 \times E_2^2)$. Then, since $\tilde{F} \circ F = [\ell^e]$, we get that

$$ \forall 1 \le j \le 4, \quad \sum_{i=1}^{4} \deg(f_{i,j}) = \ell^e, \qquad (4) $$

so the $f_{i,j}$ have degree $\le \ell^e$. By assumption, there exists $Q \in E_1$ of order $\ell^f \ell^{f'}$ such that $f_{1,1}(Q) = [a_1]Q, f_{2,1}(Q) = -[a_2]Q$ and $f_{4,1}(Q) = 0$. Besides, by Cauchy Schwarz inequality

$$ \deg(f_{1,1} - [a_1]) \le \left( \sqrt{\deg(f_{1,1})} + \sqrt{\deg([a_1])} \right)^2 \le 4\ell^e < \ell^f \ell^{f'}. $$

It follows that $f_{1,1} = [a_1]$. We similarly obtain that $f_{2,1} = -[a_2]$ and $f_{4,1} = 0$. Hence, by 4, we get $\deg(f_{3,1}) = \ell^e - a_1^2 - a_2^2 = q$. But $\sigma := f_{3,1}$ is an isogeny $E_1 \to E_2$. This proves the correctness of Algorithm 5.

We use a similar argument to prove the correctness of Algorithm 16. We write $F := (f_{i,j})_{1 \le i,j \le 8}$. Then, the evaluation of the T-torsion points ensures that $f_{i,1} = [a_i]$ for all $i \in [1; 4]$ and $f_{i,1}$ for all $i \in \{6, 7, 8\}$ since $T > 4\ell^e$ ($T \simeq p^3$ and $\ell^e \simeq p^2$). Using an analogue of 4, we conclude that $\sigma := f_{5,1} : E_1 \to E_2$ has degree $q = \ell^e - a_1^2 - a_2^2 - a_3^2 - a_4^2$. This completes the proof. $\square$

**Corollary 16.** The verification procedures FastVerify and RigorousVerify (Algorithms 3 and 14) are correct. Namely, on input $(R_1, R_2, q)$, FastVerify (respectively RigorousVerify) returns True if and only if $(R_1, R_2, q)$ defines an efficient representation of an isogeny $\sigma : E_1 \to E_2$ of degree $q$, where $q$ is $\ell^e$-good and prime to $\ell'$ (respectively $q < \ell^e$).
and $\tilde{F}_2$ define the same level-structure on $C[4]$, we use Algorithm 20 outputting two symplectic basis of $E_1^2 \times E_2^2[4^{\max(e_1,e_2)}]$ satisfying the compatibility equation of Corollary 58. The output of this algorithm only depends on the input $a_1, a_2, P_1, P_2, \sigma(P_2), \sigma(P_2)$, so it would be the same if we applied it for $F_1^*$ and $\tilde{F}_2^*$. It follows that $(C, \lambda_C) = (C^*, \lambda_{C^*})$ and that $F_1$ and $F_1^*$ coincide on $F_1^{-1}(C[4])$, so that $\lambda$ and $\text{id}_C$ coincide on $C[4]$, so that $\lambda = \text{id}_C$ by [Mil86, Proposition 17.5.(b)]. Similarly, $\tilde{F}_2$ and $\tilde{F}_2^*$ coincide on $\tilde{F}_2^{-1}(C[4])$, so that $\mu = \text{id}_C$. It follows that $F_2 \circ F_1 = F^* = F(\sigma, a_1, a_2)$, so Algorithm 4 is correct. The same proof applies to Algorithm 15. $\square$

## E.5 Verification (Proposition 15 and Corollary 16)

**Proposition 15.** Algorithms 5 and 16 are correct. Namely, when given $E_1, E_2, a_1, a_2, F_1, \tilde{F}_2$, if Algorithm 5 returns True, then $F_2 \circ F_1$ is an efficient representation of an isogeny $\sigma : E_1 \to E_2$ of degree $q = \ell^e - a_1^2 - a_2^2$ (and similarly for Algorithm 16).

*Proof.* Assume that Algorithm 5 returns True on input $E_1, E_2, a_1, a_2, F_1, \tilde{F}_2$. Then, $F := F_2 \circ F_1$ is well defined and is an $\ell^e$-isogeny. We may write $F := (f_{i,j})_{1 \le i,j \le 4} \in \text{End}(E_1^2 \times E_2^2)$. Then, since $\tilde{F} \circ F = [\ell^e]$, we get that

$$ \forall 1 \le j \le 4, \quad \sum_{i=1}^{4} \deg(f_{i,j}) = \ell^e, \qquad (4) $$

so the $f_{i,j}$ have degree $\le \ell^e$. By assumption, there exists $Q \in E_1$ of order $\ell^f \ell^{f'}$ such that $f_{1,1}(Q) = [a_1]Q, f_{2,1}(Q) = -[a_2]Q$ and $f_{4,1}(Q) = 0$. Besides, by Cauchy Schwarz inequality

$$ \deg(f_{1,1} - [a_1]) \le \left( \sqrt{\deg(f_{1,1})} + \sqrt{\deg([a_1])} \right)^2 \le 4\ell^e < \ell^f \ell^{f'}. $$

It follows that $f_{1,1} = [a_1]$. We similarly obtain that $f_{2,1} = -[a_2]$ and $f_{4,1} = 0$. Hence, by 4, we get $\deg(f_{3,1}) = \ell^e - a_1^2 - a_2^2 = q$. But $\sigma := f_{3,1}$ is an isogeny $E_1 \to E_2$. This proves the correctness of Algorithm 5.

We use a similar argument to prove the correctness of Algorithm 16. We write $F := (f_{i,j})_{1 \le i,j \le 8}$. Then, the evaluation of the T-torsion points ensures that $f_{i,1} = [a_i]$ for all $i \in [1; 4]$ and $f_{i,1}$ for all $i \in \{6, 7, 8\}$ since $T > 4\ell^e$ ($T \simeq p^3$ and $\ell^e \simeq p^2$). Using an analogue of 4, we conclude that $\sigma := f_{5,1} : E_1 \to E_2$ has degree $q = \ell^e - a_1^2 - a_2^2 - a_3^2 - a_4^2$. This completes the proof. $\square$

**Corollary 16.** The verification procedures FastVerify and RigorousVerify (Algorithms 3 and 14) are correct. Namely, on input $(R_1, R_2, q)$, FastVerify (respectively RigorousVerify) returns True if and only if $(R_1, R_2, q)$ defines an efficient representation of an isogeny $\sigma : E_1 \to E_2$ of degree $q$, where $q$ is $\ell^e$-good and prime to $\ell'$ (respectively $q < \ell^e$).
*Proof.* If FastVerify($R_1, R_2, q$) returns True, it means that $q$ is $\ell^e$-good and prime to $\ell$, that FastVerify found $a_1, a_2 \in \mathbb{Z}$ such that $a_1^2 + a_2^2 + q = \ell^e$ and that $\text{IsValid}_{4, \ell^e, \ell^f, \ell^{f'}}(E_1, E_2, a_1, a_2, *)$ returned True. In particular, by Proposition 15, it means that $\text{RepresentIsogeny}_{4, \ell^e, \ell^f}(E_1, E_2, a_1, a_2, P_1, P_2, R_1, R_2)$ returned an efficient representation of a $q$-isogeny $\sigma : E_1 \to E_2$. Hence, the knowledge of $(R_1, R_2, q)$, Cornacchia's algorithm to find $a_1, a_2$ and $\text{RepresentIsogeny}_{4, \ell^e, \ell^f}$ (running in polynomial time in $\log(p)$) define an efficient representation of $\sigma$.

Conversely, if $(R_1, R_2, q)$ defines an efficient representation of a $q$-isogeny $\sigma : E_1 \to E_2$, where $q$ is $\ell^e$-good and prime to $\ell'$, then we can evaluate $\sigma$ on the canonical basis $(P_1, P_2)$ of $E_1[\ell^f]$ in polynomial time in $\log(p)$ and obtain $(R_1, R_2) := (\sigma(P_1), \sigma(P_2))$. On input $(R_1, R_2, q)$, FastVerify will find $a_1, a_2 \in \mathbb{Z}$ such that $a_1^2 + a_2^2 + q = \ell^e$ and apply $\text{RepresentIsogeny}_{4, \ell^e, \ell^f}(E_1, E_2, a_1, a_2, P_1, P_2, R_1, R_2)$, which will return $F_1, \tilde{F}_2$ such that $F_2 \circ F_1 = F(\sigma, a_1, a_2)$ by Proposition 14. Hence, $\text{IsValid}_{4, \ell^e, \ell^f, \ell^{f'}}$ will return True by construction, and so will FastVerify.

The same proof applies to RigorousVerify. $\square$

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

## E.6 On the codomain distribution of random isogenies with bounded degree (Theorem 42)

The goal of this section is to prove a bound on the statistical distance between codomains of random isogenies with bounded degrees and the uniform distribution on the supersingular isogeny graph. Similar results have been proved on fixed degree smooth isogeny walks [GPS20, Theorem 1] and non-bactracking $\ell$-isogeny walks [BCC+23, Theorem 11]. We generalize these results to the case of non-fixed degree. Heuristically, we should expect to be as close to the uniform distribution lower degree bounds than in the fixed degree case, but this is not the case. In particular, as for non-bactracking $\ell$-isogeny walks, we need to allow isogenies of degree $p^{1+\varepsilon}$ to reach a statistical distance of $O(p^{-\varepsilon/2})$ to the uniform distribution. However, we provide an elementary proof that does not require to study adjacency matrices of the supersingular isogeny graph and modular forms (unlike [BCC+23]). The main ingredients are the Deuring correspondence and a count of small quaternion ideal vectors (Corollary 50). We start by proving a classical bound on the last minimum of quaternion ideals claimed in [KLPT14, § 3.1] but never proved so far.

**Lemma 48.** Let $O \subset B_{p,\infty}$ be a quaternion order and $I$ be a left ideal of $O$. Let $(\alpha_1, \dots, \alpha_4)$ be a Minkowski reduced basis of $I$ for the quadratic form $q_I : \alpha \in I \mapsto \text{nrd}(\alpha)/\text{nrd}(I)$, so that $q_I(\alpha_i) \le q_I(\alpha_{i+1})$ for all $i \in \{1, 2, 3\}$. Then

$$q_I(\alpha_4) \le \frac{8p}{\pi^2}.$$

*Proof.* As we saw in the proof of Lemma 12, we have by Minkowski's second theorem (Equation 3):

$$\prod_{i=1}^{4} q_I(\alpha_i) \le \frac{64p^2}{\pi^4}.$$
*Proof.* If FastVerify($R_1, R_2, q$) returns True, it means that $q$ is $\ell^e$-good and prime to $\ell$, that FastVerify found $a_1, a_2 \in \mathbb{Z}$ such that $a_1^2 + a_2^2 + q = \ell^e$ and that $\text{IsValid}_{4, \ell^e, \ell^f, \ell^{f'}}(E_1, E_2, a_1, a_2, *)$ returned True. In particular, by Proposition 15, it means that $\text{RepresentIsogeny}_{4, \ell^e, \ell^f}(E_1, E_2, a_1, a_2, P_1, P_2, R_1, R_2)$ returned an efficient representation of a $q$-isogeny $\sigma : E_1 \to E_2$. Hence, the knowledge of $(R_1, R_2, q)$, Cornacchia's algorithm to find $a_1, a_2$ and $\text{RepresentIsogeny}_{4, \ell^e, \ell^f}$ (running in polynomial time in $\log(p)$) define an efficient representation of $\sigma$.

Conversely, if $(R_1, R_2, q)$ defines an efficient representation of a $q$-isogeny $\sigma : E_1 \to E_2$, where $q$ is $\ell^e$-good and prime to $\ell'$, then we can evaluate $\sigma$ on the canonical basis $(P_1, P_2)$ of $E_1[\ell^f]$ in polynomial time in $\log(p)$ and obtain $(R_1, R_2) := (\sigma(P_1), \sigma(P_2))$. On input $(R_1, R_2, q)$, FastVerify will find $a_1, a_2 \in \mathbb{Z}$ such that $a_1^2 + a_2^2 + q = \ell^e$ and apply $\text{RepresentIsogeny}_{4, \ell^e, \ell^f}(E_1, E_2, a_1, a_2, P_1, P_2, R_1, R_2)$, which will return $F_1, \tilde{F}_2$ such that $F_2 \circ F_1 = F(\sigma, a_1, a_2)$ by Proposition 14. Hence, $\text{IsValid}_{4, \ell^e, \ell^f, \ell^{f'}}$ will return True by construction, and so will FastVerify.

The same proof applies to RigorousVerify. $\square$

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

## E.6 On the codomain distribution of random isogenies with bounded degree (Theorem 42)

The goal of this section is to prove a bound on the statistical distance between codomains of random isogenies with bounded degrees and the uniform distribution on the supersingular isogeny graph. Similar results have been proved on fixed degree smooth isogeny walks [GPS20, Theorem 1] and non-bactracking $\ell$-isogeny walks [BCC+23, Theorem 11]. We generalize these results to the case of non-fixed degree. Heuristically, we should expect to be as close to the uniform distribution lower degree bounds than in the fixed degree case, but this is not the case. In particular, as for non-bactracking $\ell$-isogeny walks, we need to allow isogenies of degree $p^{1+\varepsilon}$ to reach a statistical distance of $O(p^{-\varepsilon/2})$ to the uniform distribution. However, we provide an elementary proof that does not require to study adjacency matrices of the supersingular isogeny graph and modular forms (unlike [BCC+23]). The main ingredients are the Deuring correspondence and a count of small quaternion ideal vectors (Corollary 50). We start by proving a classical bound on the last minimum of quaternion ideals claimed in [KLPT14, § 3.1] but never proved so far.

**Lemma 48.** Let $O \subset B_{p,\infty}$ be a quaternion order and $I$ be a left ideal of $O$. Let $(\alpha_1, \dots, \alpha_4)$ be a Minkowski reduced basis of $I$ for the quadratic form $q_I : \alpha \in I \mapsto \text{nrd}(\alpha)/\text{nrd}(I)$, so that $q_I(\alpha_i) \le q_I(\alpha_{i+1})$ for all $i \in \{1, 2, 3\}$. Then

$$q_I(\alpha_4) \le \frac{8p}{\pi^2}.$$

*Proof.* As we saw in the proof of Lemma 12, we have by Minkowski's second theorem (Equation 3):

$$\prod_{i=1}^{4} q_I(\alpha_i) \le \frac{64p^2}{\pi^4}.$$
This inequality is not sufficient to conclude (we only get $q_I(\alpha_4) = O(p^2)$ instead of $O(p)$). To complete the proof, we follow [BST+17, Theorem 3.1].

Let $(\beta_1, \dots, \beta_4)$ be a Minkowski reduced basis of $\mathcal{O}$. As the $\alpha_i$, the $\beta_i$ satisfy

$$ \prod_{i=1}^{4} \mathrm{nrd}(\beta_i) \leq \frac{64p^2}{\pi^4}. $$

Let $A := (a_{i,j})_{1 \leq i,j \leq 4} \in M_3(\mathbb{Z})$, where for all $1 \leq i, j \leq 4$, $a_{i,j}$ is the coefficient of $\alpha_4$ in the decomposition of $\beta_i \alpha_j$ in the basis $(\alpha_1, \dots, \alpha_4)$ (this is an integer since $\mathcal{O}I \subseteq I$). Then $A$ is invertible. Indeed, if $x \in \mathbb{Z}^4$ satisfy $Ax = 0$ i.e. $\sum_{j=1}^3 a_{i,j}x_j = 0$ for all $i \in [1; 4]$, then $\alpha := \sum_{j=1}^4 x_j \alpha_j$ satisfies $\mathcal{O}\alpha \subseteq \langle \alpha_1, \alpha_2, \alpha_3 \rangle$. But $\mathcal{O}\alpha$ has rank 4 whenever $\alpha \neq 0$, so $\alpha = 0$ and $x = 0$.

$A$ being invertible, there exists a permutation $\sigma \in \mathfrak{S}_4$ such that $a_{i,\sigma(i)} \neq 0$ for all $i \in [1; 4]$. It follows that for all $i \in [1; 4]$, $\beta_i \alpha_{\sigma(i)}$ completes $\langle \alpha_1, \alpha_2, \alpha_3 \rangle$ as a full-rank sublattice of $I$, so that $\mathrm{nrd}(\alpha_4) \leq \mathrm{nrd}(\beta_i \alpha_{\sigma(i)})$ i.e. $q_I(\alpha_4) \leq \mathrm{nrd}(\beta_i)q_I(\alpha_{\sigma(i)})$, since $(\alpha_1, \dots, \alpha_4)$ is Minkowski reduced. It follows that

$$ q_I(\alpha_4)^4 \leq \prod_{i=1}^{4} (\mathrm{nrd}(\beta_i)q_I(\alpha_{\sigma(i)})) = \prod_{i=1}^{4} \mathrm{nrd}(\beta_i) \prod_{i=1}^{4} q_I(\alpha_i) \leq \left(\frac{64p^2}{\pi^4}\right)^2. $$

The result follows.

□

Now, we introduce a generalization of [Wes22, Lemma 3.2] in every dimension, counting the elements of bounded norm in a lattice.

**Lemma 49.** Let $\Lambda \subseteq \mathbb{Z}^k$ be a full-rank lattice of last minimum $\lambda_k$ and $\rho > \sqrt{k}/2\lambda_k$. Then

$$ \frac{\pi^{k/2} \left( \rho - \frac{\sqrt{k} \lambda_k}{2} \right)^k}{\Gamma\left(\frac{k}{2} + 1\right) \mathrm{Covol}(\Lambda)} \leq \#\Lambda \cap B(0, \rho) \leq \frac{\pi^{k/2} \left( \rho + \frac{\sqrt{k} \lambda_k}{2} \right)^k}{\Gamma\left(\frac{k}{2} + 1\right) \mathrm{Covol}(\Lambda)}, $$

where $B(0, \rho)$ is the ball of center 0 and radius $\rho$ for the Euclidean norm and $\Gamma$ is Euler's gamma function.

*Proof.* Let $\mathcal{V} := \{v \in \mathbb{R}^k \mid \|v\| = \min_{\lambda \in \Lambda} \|v + \lambda\|\}$ be the Voronoi cell at the origin of $\Lambda$ and $\mu := \sup_{v \in \mathcal{V}} \|v\|$ be the covering radius of $\Lambda$. Then, we have

$$ B(0, \rho - \mu) \subseteq \bigsqcup_{\lambda \in \Lambda \cap B(0, \rho)} (\lambda + \mathcal{V}) \subseteq B(0, \rho + \mu), $$

so that

$$ \mathrm{Vol}(B(0, \rho - \mu)) \leq (\#\Lambda \cap B(0, \rho)) \cdot \mathrm{Vol}(\mathcal{V}) \leq \mathrm{Vol}(B(0, \rho + \mu)). $$

Since $\mathrm{Vol}(\mathcal{V}) = \mathrm{Covol}(\Lambda)$, $\mathrm{Vol}(B(0, \rho \pm \mu)) = \pi^{k/2}(\rho \pm \mu)^k/\Gamma(k/2 + 1)$ and $\mu \leq \sqrt{k}\lambda_k/2$, the result follows. □
This inequality is not sufficient to conclude (we only get $q_I(\alpha_4) = O(p^2)$ instead of $O(p)$). To complete the proof, we follow [BST+17, Theorem 3.1].

Let $(\beta_1, \dots, \beta_4)$ be a Minkowski reduced basis of $\mathcal{O}$. As the $\alpha_i$, the $\beta_i$ satisfy

$$ \prod_{i=1}^{4} \mathrm{nrd}(\beta_i) \leq \frac{64p^2}{\pi^4}. $$

Let $A := (a_{i,j})_{1 \leq i,j \leq 4} \in M_3(\mathbb{Z})$, where for all $1 \leq i, j \leq 4$, $a_{i,j}$ is the coefficient of $\alpha_4$ in the decomposition of $\beta_i \alpha_j$ in the basis $(\alpha_1, \dots, \alpha_4)$ (this is an integer since $\mathcal{O}I \subseteq I$). Then $A$ is invertible. Indeed, if $x \in \mathbb{Z}^4$ satisfy $Ax = 0$ i.e. $\sum_{j=1}^3 a_{i,j}x_j = 0$ for all $i \in [1; 4]$, then $\alpha := \sum_{j=1}^4 x_j \alpha_j$ satisfies $\mathcal{O}\alpha \subseteq \langle \alpha_1, \alpha_2, \alpha_3 \rangle$. But $\mathcal{O}\alpha$ has rank 4 whenever $\alpha \neq 0$, so $\alpha = 0$ and $x = 0$.

$A$ being invertible, there exists a permutation $\sigma \in \mathfrak{S}_4$ such that $a_{i,\sigma(i)} \neq 0$ for all $i \in [1; 4]$. It follows that for all $i \in [1; 4]$, $\beta_i \alpha_{\sigma(i)}$ completes $\langle \alpha_1, \alpha_2, \alpha_3 \rangle$ as a full-rank sublattice of $I$, so that $\mathrm{nrd}(\alpha_4) \leq \mathrm{nrd}(\beta_i \alpha_{\sigma(i)})$ i.e. $q_I(\alpha_4) \leq \mathrm{nrd}(\beta_i)q_I(\alpha_{\sigma(i)})$, since $(\alpha_1, \dots, \alpha_4)$ is Minkowski reduced. It follows that

$$ q_I(\alpha_4)^4 \leq \prod_{i=1}^{4} (\mathrm{nrd}(\beta_i)q_I(\alpha_{\sigma(i)})) = \prod_{i=1}^{4} \mathrm{nrd}(\beta_i) \prod_{i=1}^{4} q_I(\alpha_i) \leq \left( \frac{64p^2}{\pi^4} \right)^2. $$

The result follows.

□

Now, we introduce a generalization of [Wes22, Lemma 3.2] in every dimension, counting the elements of bounded norm in a lattice.

**Lemma 49.** Let $\Lambda \subseteq \mathbb{Z}^k$ be a full-rank lattice of last minimum $\lambda_k$ and $\rho > \sqrt{k}/2\lambda_k$. Then

$$ \frac{\pi^{k/2} \left( \rho - \frac{\sqrt{k} \lambda_k}{2} \right)^k}{\Gamma\left(\frac{k}{2} + 1\right) \mathrm{Covol}(\Lambda)} \leq \#\Lambda \cap B(0, \rho) \leq \frac{\pi^{k/2} \left( \rho + \frac{\sqrt{k} \lambda_k}{2} \right)^k}{\Gamma\left(\frac{k}{2} + 1\right) \mathrm{Covol}(\Lambda)}, $$

where $B(0, \rho)$ is the ball of center 0 and radius $\rho$ for the Euclidean norm and $\Gamma$ is Euler's gamma function.

*Proof.* Let $\mathcal{V} := \{v \in \mathbb{R}^k \mid \|v\| = \min_{\lambda \in \Lambda} \|v + \lambda\|\}$ be the Voronoi cell at the origin of $\Lambda$ and $\mu := \sup_{v \in \mathcal{V}} \|v\|$ be the covering radius of $\Lambda$. Then, we have

$$ B(0, \rho - \mu) \subseteq \bigsqcup_{\lambda \in \Lambda \cap B(0, \rho)} (\lambda + \mathcal{V}) \subseteq B(0, \rho + \mu), $$

so that

$$ \mathrm{Vol}(B(0, \rho - \mu)) \leq (\#\Lambda \cap B(0, \rho)) \cdot \mathrm{Vol}(\mathcal{V}) \leq \mathrm{Vol}(B(0, \rho + \mu)). $$

Since $\mathrm{Vol}(\mathcal{V}) = \mathrm{Covol}(\Lambda)$, $\mathrm{Vol}(B(0, \rho \pm \mu)) = \pi^{k/2}(\rho \pm \mu)^k / \Gamma(k/2 + 1)$ and $\mu \leq \sqrt{k}\lambda_k/2$, the result follows. □
**Corollary 50.** Let $\mathcal{O} \subset \mathcal{B}_{p,\infty}$ be a maximal order and $I$ be an integral left $\mathcal{O}$-ideal. Then, for all $\varepsilon > 0$ the number of ideals of norm $\le p^{1+\varepsilon}$ that are right-equivalent to $I$ is

$$N_{p^{1+\varepsilon}}([I]) := \#\{J \sim I \mid \text{nrd}(J) \le p^{1+\varepsilon}\} = \frac{2\pi^2}{\#\mathcal{O}_R(I)^\times} p^{1+2\varepsilon} (1 + O(p^{-\varepsilon/2})).$$

*Proof.* By [DKLPW20, Lemma 1], an ideal $J$ is right-equivalent to $I$ if and only if it is of the form $J := I\bar{\alpha}/\text{nrd}(I)$ for some $\alpha \in I$. Besides, $\alpha$ is uniquely determined by $J$ up to multiplication on the right by an element of $\mathcal{O}_R(I)^\times$ and we have $\text{nrd}(J) = \text{nrd}(\alpha)/\text{nrd}(I) = q_I(\alpha)$. It follows that

$$N_{p^{1+\varepsilon}}([I]) := \#\{J \sim I \mid \text{nrd}(J) \le p^{1+\varepsilon}\} = \frac{1}{\#\mathcal{O}_R(I)^\times} \#\{\alpha \in I \mid q_I(\alpha) \le p^{1+\varepsilon}\}.$$

As in the proof of Lemma 12, let $\iota : \mathcal{B}_{p,\infty} \to \mathbb{R}^4$ be the canonical embedding, such that $\|\iota(\alpha)\|^2 = \text{nrd}(\alpha)$ for all $\alpha \in \mathcal{B}_{p,\infty}$, where $\|\cdot\|$ is the Euclidean norm on $\mathbb{R}^4$. Consider the lattice $\Lambda := \iota(I)$. We then have

$$N_{p^{1+\varepsilon}}([I]) = \frac{1}{\#\mathcal{O}_R(I)^\times} \#\Lambda \cap B \left(0, p^{(1+\varepsilon)/2} \sqrt{\text{nrd}(I)}\right)$$

By Lemmas 48 and 49, we get

$$\#\Lambda \cap B \left(0, p^{(1+\varepsilon)/2} \sqrt{\text{nrd}(I)}\right) \le \frac{\pi^2 \left( p^{(1+\varepsilon)/2} \sqrt{\text{nrd}(I)} + \frac{2\sqrt{2p \text{nrd}(I)}}{\pi} \right)^4}{2 \text{Covol}(\Lambda)}$$

with $\text{Covol}(\Lambda) = p/4 \text{nrd}(I)^2$, as we saw in the proof of Lemma 12. It follows, that the right term of the inequality is $2\pi^2 p^{1+2\varepsilon}(1 + O(p^{-\varepsilon/2}))$. Applying the lower bound of Lemma 49, we also get that

$$\#\Lambda \cap B \left(0, p^{(1+\varepsilon)/2} \sqrt{\text{nrd}(I)}\right) \ge 2\pi^2 p^{1+2\varepsilon} (1 + O(p^{-\varepsilon/2})).$$

The result follows. $\square$

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

We denote by $\text{SS}(p)$ the set of supersingular elliptic curves over $\mathbb{F}_{p^2}$ (up to $\overline{\mathbb{F}}_p$-isomorphism) and $S$ the probability distribution on $\text{SS}(p)$ given by $S(E) := 1/(K\#\text{Aut}(E))$ for all $E \in \text{SS}(p)$, with $K := \sum_{E \in \text{SS}(p)} 1/(\#\text{Aut}(E)) = (p-1)/24$ by Eichler mass formula [Voi20, Theorem 25.1.1]. Let $U$ be the uniform distribution on $\text{SS}(p)$. Recall that by Lemma 30, the statistical distance between $S$ and $U$ is $d_{TV}(S, U) = O(p^{-1})$. We can now finally prove our main result.

**Theorem 42.** Let $\varepsilon \in ]0, 2]$. Let $E/\overline{\mathbb{F}}_{p^2}$ be a supersingular elliptic curve and $\pi$ be the probability distribution of codomains $E'$ (up to $\overline{\mathbb{F}}_p$-isomorphism) of isogenies $\sigma : E \to E'$ chosen uniformly at random among isogenies of degree $\deg(\sigma) \le p^{1+\varepsilon}$. Then $d_{TV}(U, \pi) = O(p^{-\varepsilon/2})$.
**Corollary 50.** Let $\mathcal{O} \subset \mathcal{B}_{p,\infty}$ be a maximal order and $I$ be an integral left $\mathcal{O}$-ideal. Then, for all $\varepsilon > 0$ the number of ideals of norm $\le p^{1+\varepsilon}$ that are right-equivalent to $I$ is

$$N_{p^{1+\varepsilon}}([I]) := \#\{J \sim I \mid \text{nrd}(J) \le p^{1+\varepsilon}\} = \frac{2\pi^2}{\#\mathcal{O}_R(I)^\times} p^{1+2\varepsilon} (1 + O(p^{-\varepsilon/2})).$$

*Proof.* By [DKLPW20, Lemma 1], an ideal $J$ is right-equivalent to $I$ if and only if it is of the form $J := I\bar{\alpha}/\text{nrd}(I)$ for some $\alpha \in I$. Besides, $\alpha$ is uniquely determined by $J$ up to multiplication on the right by an element of $\mathcal{O}_R(I)^\times$ and we have $\text{nrd}(J) = \text{nrd}(\alpha)/\text{nrd}(I) = q_I(\alpha)$. It follows that

$$N_{p^{1+\varepsilon}}([I]) := \#\{J \sim I \mid \text{nrd}(J) \le p^{1+\varepsilon}\} = \frac{1}{\#\mathcal{O}_R(I)^\times} \#\{\alpha \in I \mid q_I(\alpha) \le p^{1+\varepsilon}\}.$$

As in the proof of Lemma 12, let $\iota : \mathcal{B}_{p,\infty} \to \mathbb{R}^4$ be the canonical embedding, such that $\|\iota(\alpha)\|^2 = \text{nrd}(\alpha)$ for all $\alpha \in \mathcal{B}_{p,\infty}$, where $\|\cdot\|$ is the Euclidean norm on $\mathbb{R}^4$. Consider the lattice $\Lambda := \iota(I)$. We then have

$$N_{p^{1+\varepsilon}}([I]) = \frac{1}{\#\mathcal{O}_R(I)^\times} \#\Lambda \cap B\left(0, p^{(1+\varepsilon)/2} \sqrt{\text{nrd}(I)}\right)$$

By Lemmas 48 and 49, we get

$$\#\Lambda \cap B\left(0, p^{(1+\varepsilon)/2} \sqrt{\text{nrd}(I)}\right) \le \frac{\pi^2 \left( p^{(1+\varepsilon)/2} \sqrt{\text{nrd}(I)} + \frac{2\sqrt{2p \text{nrd}(I)}}{\pi} \right)^4}{2 \text{Covol}(\Lambda)}$$

with $\text{Covol}(\Lambda) = p/4 \text{nrd}(I)^2$, as we saw in the proof of Lemma 12. It follows, that the right term of the inequality is $2\pi^2 p^{1+2\varepsilon}(1 + O(p^{-\varepsilon/2}))$. Applying the lower bound of Lemma 49, we also get that

$$\#\Lambda \cap B\left(0, p^{(1+\varepsilon)/2} \sqrt{\text{nrd}(I)}\right) \ge 2\pi^2 p^{1+2\varepsilon} (1 + O(p^{-\varepsilon/2})).$$

The result follows.

□

We denote by $\text{SS}(p)$ the set of supersingular elliptic curves over $\mathbb{F}_{p^2}$ (up to $\overline{\mathbb{F}}_p$-isomorphism) and $S$ the probability distribution on $\text{SS}(p)$ given by $S(E) := 1/(K\#\text{Aut}(E))$ for all $E \in \text{SS}(p)$, with $K := \sum_{E \in \text{SS}(p)} 1/(\#\text{Aut}(E)) = (p-1)/24$ by Eichler mass formula [Voi20, Theorem 25.1.1]. Let $U$ be the uniform distribution on $\text{SS}(p)$. Recall that by Lemma 30, the statistical distance between $S$ and $U$ is $d_{TV}(S, U) = O(p^{-1})$. We can now finally prove our main result.

**Theorem 42.** Let $\varepsilon \in ]0, 2]$. Let $E/\overline{\mathbb{F}}_{p^2}$ be a supersingular elliptic curve and $\pi$ be the probability distribution of codomains $E'$ (up to $\overline{\mathbb{F}}_p$-isomorphism) of isogenies $\sigma : E \to E'$ chosen uniformly at random among isogenies of degree $\deg(\sigma) \le p^{1+\varepsilon}$. Then $d_{TV}(U, \pi) = O(p^{-\varepsilon/2})$.
Proof. By the Deuring correspondence, it suffices to prove that given a maximal order $\mathcal{O} \subset \mathcal{B}_{p,\infty}$ and $\mathrm{Cl}(\mathcal{O})$ the set of right-equivalence classes of left-ideals of $\mathcal{O}$, the distribution $\pi'$ of the ideal classes $[I] \in \mathrm{Cl}(\mathcal{O})$ when $I$ is sampled uniformly at random among ideals of norm $\le p^{1+\varepsilon}$ (which is the quaternion analogue of $\pi$) is at statistical distance $O(p^{-\varepsilon/2})$ from the uniform distribution $U'$ on $\mathrm{Cl}(\mathcal{O})$. We also denote by $S'$ the quaternion analogue of $S$, namely the distribution on $\mathrm{Cl}(\mathcal{O})$ given by $S([I]) := 1/(K\#O_R(I)^\times)$ for all $[I] \in \mathrm{Cl}(\mathcal{O})$, where $K := \sum_{[I] \in \mathrm{Cl}(\mathcal{O})} 1/(\#O_R(I)^\times) = (p-1)/24$ is the Eichler mass. By Lemma 30, $d_{TV}(U', S') = O(p^{-1})$, so it suffices to prove that $d_{TV}(S', \pi') = O(p^{-\varepsilon/2})$.

By Corollary 50, the number of left $\mathcal{O}$-ideals of norm $\le p^{1+\varepsilon}$ is

$$N_{p^{1+\varepsilon}} = \sum_{[I] \in \mathrm{Cl}(\mathcal{O})} N_{p^{1+\varepsilon}}([I]) = 2\pi^2 K p^{1+2\varepsilon} (1 + O(p^{-\varepsilon/2})),$$

so the distribution $\pi'$ is given by

$$\forall [I] \in \mathrm{Cl}(\mathcal{O}), \quad \pi'([I]) = \frac{N_{p^{1+\varepsilon}}([I])}{N_{p^{1+\varepsilon}}} = \frac{1}{K}(1 + O(p^{-\varepsilon/2})).$$

It follows immediately that

$$d_{TV}(S', \pi') = \frac{1}{2} \sum_{[I] \in \mathrm{Cl}(\mathcal{O})} |S'([I]) - \pi'([I])| = \frac{\#\mathrm{Cl}(\mathcal{O})}{K} O(p^{-\varepsilon/2}) = O(p^{-\varepsilon/2}).$$

The result follows. $\square$

# F Higher dimensional isogenies and the theta model

In this section, we explain how to compute an $\ell^e$-isogeny between abelian varieties in plain generality and then apply it to our specific problem. In subsection F.1, we give a high level description of an $\ell^e$-isogeny computation as a chain of $\ell$-isogenies. In the remaining subsections, we introduce the $\Theta$-model to compute $\ell$-isogenies when $\ell = 2$.

Indeed, unlike in dimension 2 or 3, we cannot use Jacobians to compute isogenies in dimension 4 or 8. However, there already exist algorithms to compute $\ell$-isogenies in any dimension $g$ with the $\Theta$-model [LR12; LR15; LR23] in time $O(\ell^g)$. To minimize the complexity, the best strategy, would be to take $\ell = 2$ and to use $\Theta$-coordinates of level $n = 2$. However, existing algorithms only work when $\ell$ and $n$ are coprime. We propose an algorithm to compute 2-isogenies in level $n = 2$ in Appendix F.4 and how we can use it in our specific problem (computing two 2-isogeny chains $F_1$ and $\widetilde{F}_2$ with the same codomain).

## F.1 Computing an $\ell$-isogeny chain.

Let $F : (\mathcal{A}, \lambda_A) \to (\mathcal{B}, \lambda_B)$ be an $\ell^e$-isogeny between principally polarized abelian varieties and let $K$ be its kernel. Assume that $K$ has rank $g$. Then, we can decompose $F$ as an $\ell$-isogeny chain as in dimension 1.
Proof. By the Deuring correspondence, it suffices to prove that given a maximal order $\mathcal{O} \subset \mathcal{B}_{p,\infty}$ and $\mathrm{Cl}(\mathcal{O})$ the set of right-equivalence classes of left-ideals of $\mathcal{O}$, the distribution $\pi'$ of the ideal classes $[I] \in \mathrm{Cl}(\mathcal{O})$ when $I$ is sampled uniformly at random among ideals of norm $\le p^{1+\epsilon}$ (which is the quaternion analogue of $\pi$) is at statistical distance $O(p^{-\epsilon/2})$ from the uniform distribution $U'$ on $\mathrm{Cl}(\mathcal{O})$. We also denote by $S'$ the quaternion analogue of $S$, namely the distribution on $\mathrm{Cl}(\mathcal{O})$ given by $S([I]) := 1/(K\#O_R(I)^\times)$ for all $[I] \in \mathrm{Cl}(\mathcal{O})$, where $K := \sum_{[I] \in \mathrm{Cl}(\mathcal{O})} 1/(K\#O_R(I)^\times) = (p-1)/24$ is the Eichler mass. By Lemma 30, $d_{TV}(U', S') = O(p^{-1})$, so it suffices to prove that $d_{TV}(S', \pi') = O(p^{-\epsilon/2})$.

By Corollary 50, the number of left $\mathcal{O}$-ideals of norm $\le p^{1+\epsilon}$ is

$$N_{p^{1+\epsilon}} = \sum_{[I] \in \mathrm{Cl}(\mathcal{O})} N_{p^{1+\epsilon}}([I]) = 2\pi^2 K p^{1+2\epsilon} (1 + O(p^{-\epsilon/2})),$$

so the distribution $\pi'$ is given by

$$\forall [I] \in \mathrm{Cl}(\mathcal{O}), \quad \pi'([I]) = \frac{N_{p^{1+\epsilon}}([I])}{N_{p^{1+\epsilon}}} = \frac{1}{K}(1 + O(p^{-\epsilon/2})).$$

It follows immediately that

$$d_{TV}(S', \pi') = \frac{1}{2} \sum_{[I] \in \mathrm{Cl}(\mathcal{O})} |S'([I]) - \pi'([I])| = \frac{\#\mathrm{Cl}(\mathcal{O})}{K} O(p^{-\epsilon/2}) = O(p^{-\epsilon/2}).$$

The result follows. $\square$

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

# F Higher dimensional isogenies and the theta model

In this section, we explain how to compute an $\ell^e$-isogeny between abelian varieties in plain generality and then apply it to our specific problem. In subsection F.1, we give a high level description of an $\ell^e$-isogeny computation as a chain of $\ell$-isogenies. In the remaining subsections, we introduce the $\Theta$-model to compute $\ell$-isogenies when $\ell = 2$.

Indeed, unlike in dimension 2 or 3, we cannot use Jacobians to compute isogenies in dimension 4 or 8. However, there already exist algorithms to compute $\ell$-isogenies in any dimension $g$ with the $\Theta$-model [LR12; LR15; LR23] in time $O(\ell^g)$. To minimize the complexity, the best strategy, would be to take $\ell = 2$ and to use $\Theta$-coordinates of level $n = 2$. However, existing algorithms only work when $\ell$ and $n$ are coprime. We propose an algorithm to compute 2-isogenies in level $n = 2$ in Appendix F.4 and how we can use it in our specific problem (computing two 2-isogeny chains $F_1$ and $\widetilde{F}_2$ with the same codomain).

## F.1 Computing an $\ell$-isogeny chain.

Let $F : (\mathcal{A}, \lambda_A) \to (\mathcal{B}, \lambda_B)$ be an $\ell^e$-isogeny between principally polarized abelian varieties and let $K$ be its kernel. Assume that $K$ has rank $g$. Then, we can decompose $F$ as an $\ell$-isogeny chain as in dimension 1.
**Lemma 51.** We can write $F$ as a product of $\ell$-isogenies $F = F_e \circ \dots \circ F_1$ between principally polarized abelian varieties $F_i : \mathcal{A}_{i-1} \to \mathcal{A}_i$ (for $i \in [1; e]$, with $\mathcal{A}_0 := \mathcal{A}$ and $\mathcal{A}_e := \mathcal{B}$).

Let $K_0 := K = \ker(F)$ and $K_i := F_i(K_{i-1})$ for all $i \in [1; e]$. Then, we have $\ker(F_i) = [\ell^{e-i}]K_{i-1}$ for all $i \in [1; e]$.

*Proof.* We prove by induction on $i \in [0; e]$ that we can write $F = G_i \circ F_i \circ \dots \circ F_1$ where the $F_j : \mathcal{A}_{j-1} \to \mathcal{A}_j$ for $j \in [1; i]$ are $\ell$-isogenies between principally polarized abelian varieties (PPAV) of kernel $\ker(F_j) = [\ell^{e-j}]K_{j-1}$ and $G_i$ is an $\ell^{e-i}$-isogeny between PPAV of kernel $\ker(G_i) = K_i$. For $i = 0$, the result is trivial. Let us assume the result at rank $i \in [0; e-1]$. Then we simply apply point (i) of Proposition 13 to $G_i$ to write $G_i := G_{i+1} \circ F_{i+1}$, where $F_{i+1}$ and $G_{i+1}$ are respectively $\ell$ and $\ell^{e-(i+1)}$-isogenies between PPAV. By point (iv) of Proposition 13, we also have $\ker(F_{i+1}) = K_i \cap \mathcal{A}_i[\ell]$ since $K_i$ has rank $g$ (K also having rank $g$). Since $K_i \subset \mathcal{A}_i[\ell^{e-i}]$ is maximal isotropic of rank $g$, we may write $K_i = \langle x_1, \dots, x_g \rangle$ where all the $x_i \in \mathcal{A}_i[\ell^{e-i}]$ have order $\ell^{e-i}$, so that

$$ \ker(F_{i+1}) = K_i \cap \mathcal{A}_i[\ell] = \langle [\ell^{e-(i+1)}]x_1, \dots, [\ell^{e-(i+1)}]x_g \rangle = [\ell^{e-(i+1)}]K_i. $$

We also have $\ker(G_{i+1}) = F_{i+1}(\ker(G_i)) = K_{i+1}$. This completes the proof. $\square$

The above lemma leads to similar isogeny computation algorithms to the dimension 1 case. Assume that we know a basis $\mathcal{B}_0$ of $K = \ker(F)$ and let $\mathcal{B}_i := F_i(\mathcal{B}_{i-1})$, which is a basis of $K_i$ for all $i \in [1; e]$. Consider the graph whose vertices are the $[\ell^j]\mathcal{B}_i$ for $0 \le i \le e-1$, $0 \le j \le e-1-i$ and edges are of two kind:

- multiplication by $\ell [\ell^j]\mathcal{B}_i \to [\ell^{j+1}]\mathcal{B}_i$ (left edges);

- $\ell$-isogeny computation $[\ell^j]\mathcal{B}_i \to [\ell^j]\mathcal{B}_{i+1}$ (right edges).

<figure><img src="image_10.png" /><figcaption>**Fig. 2.** Computational structure of the $\ell^e$ isogeny $F$ with $e = 5$.</figcaption></figure>
**Lemma 51.** We can write $F$ as a product of $\ell$-isogenies $F = F_e \circ \dots \circ F_1$ between principally polarized abelian varieties $F_i : \mathcal{A}_{i-1} \to \mathcal{A}_i$ (for $i \in \llbracket 1 ; e \rrbracket$, with $\mathcal{A}_0 := \mathcal{A}$ and $\mathcal{A}_e := \mathcal{B}$).

Let $K_0 := K = \ker(F)$ and $K_i := F_i(K_{i-1})$ for all $i \in \llbracket 1 ; e \rrbracket$. Then, we have $\ker(F_i) = [\ell^{e-i}]K_{i-1}$ for all $i \in \llbracket 1 ; e \rrbracket$.

*Proof.* We prove by induction on $i \in \llbracket 0 ; e \rrbracket$ that we can write $F = G_i \circ F_i \circ \dots \circ F_1$ where the $F_j : \mathcal{A}_{j-1} \to \mathcal{A}_j$ for $j \in \llbracket 1 ; i \rrbracket$ are $\ell$-isogenies between principally polarized abelian varieties (PPAV) of kernel $\ker(F_j) = [\ell^{e-j}]K_{j-1}$ and $G_i$ is an $\ell^{e-i}$-isogeny between PPAV of kernel $\ker(G_i) = K_i$. For $i = 0$, the result is trivial. Let us assume the result at rank $i \in \llbracket 0 ; e-1 \rrbracket$. Then we simply apply point (i) of Proposition 13 to $G_i$ to write $G_i := G_{i+1} \circ F_{i+1}$, where $F_{i+1}$ and $G_{i+1}$ are respectively $\ell$ and $\ell^{e-(i+1)}$-isogenies between PPAV. By point (iv) of Proposition 13, we also have $\ker(F_{i+1}) = K_i \cap \mathcal{A}_i[\ell]$ since $K_i$ has rank $g$ (K also having rank $g$). Since $K_i \subset \mathcal{A}_i[\ell^{e-i}]$ is maximal isotropic of rank $g$, we may write $K_i = \langle x_1, \dots, x_g \rangle$ where all the $x_i \in \mathcal{A}_i[\ell^{e-i}]$ have order $\ell^{e-i}$, so that

$$ \ker(F_{i+1}) = K_i \cap \mathcal{A}_i[\ell] = \langle [\ell^{e-(i+1)}]x_1, \dots, [\ell^{e-(i+1)}]x_g \rangle = [\ell^{e-(i+1)}]K_i. $$

We also have $\ker(G_{i+1}) = F_{i+1}(\ker(G_i)) = K_{i+1}$. This completes the proof. $\square$

The above lemma leads to similar isogeny computation algorithms to the dimension 1 case. Assume that we know a basis $\mathcal{B}_0$ of $K = \ker(F)$ and let $\mathcal{B}_i := F_i(\mathcal{B}_{i-1})$, which is a basis of $K_i$ for all $i \in \llbracket 1 ; e \rrbracket$. Consider the graph whose vertices are the $[\ell^j]\mathcal{B}_i$ for $0 \le i \le e-1$, $0 \le j \le e-1-i$ and edges are of two kind:

- multiplication by $\ell [\ell^j]\mathcal{B}_i \to [\ell^{j+1}]\mathcal{B}_i$ (left edges);

- $\ell$-isogeny computation $[\ell^j]\mathcal{B}_i \to [\ell^j]\mathcal{B}_{i+1}$ (right edges).

<figure><img src="image_10.png" /><figcaption>**Fig. 2.** Computational structure of the $\ell^e$ isogeny $F$ with $e = 5$.</figcaption></figure>
This graph represents the computational structure of $F$. To compute $F$, we need to compute the kernel basis $[\ell^{e-1}]\mathcal{B}_0, [\ell^{e-2}]\mathcal{B}_1, \dots, \mathcal{B}_{e-1}$ representing the $\ell$-isogenies in the chain, i.e. the bottom line in Figure 2. This graph is computed as follows: to go down right $[\ell^j]\mathcal{B}_i \to [\ell^j]\mathcal{B}_{i+1}$, we need to have reached the bottom vertex $[\ell^{e-1-i}]\mathcal{B}_i$ beforehand. Of course there are naive algorithms where we compute every point of the graph but they are quadratic in $e$ and far from optimal. There also exist divide and conquer strategies that require only $O(e \log(e))$ multiplications by $\ell$ and $\ell$-isogeny evaluations (see [JD11, § 4.2.2] for details). We can even optimize such a strategy to minimize the global cost depending on the relative cost of scalar multiplications by $\ell$ and $\ell$-isogeny evaluations.

## F.2 Theta coordinates

For simplicity, even through we work over a finite field, we will describe our algorithm using analytic theta functions. The algebraic theory of Mumford [Mum66b] can be used to show that our algorithms are still valid over an arbitrary field of odd characteristic.

Let $A = \mathbb{C}^g/(\mathbb{Z}^g + \Omega_A\mathbb{Z}^g)$ be an abelian variety with $\Omega = \Omega_A$ in the Siegel space corresponding to a principal polarisation $\mathcal{L} = \mathcal{L}_A$ on $A$. Let $\pi_A: \mathbb{C}^g \to A$ be the projection.

Recall that the analytic theta functions with characteristic $a, b \in \mathbb{Q}^g$ are given by

$$ \theta[\frac{a}{b}](z, \Omega) = \sum_{n \in \mathbb{Z}^g} e^{\pi i^t(n+a)\Omega(n+a) + 2\pi i^t(n+a)(z+b)}. $$

A basis of level 2 theta functions is given by $\theta_i^A(P) = \theta[\frac{0}{i/2}](z_P, \Omega/2)$, $i \in (\mathbb{Z}/2\mathbb{Z})^g$ where $z_P \in \mathbb{C}^g$ represents $P \in A$: $P = \pi_A(z_P)$. Here we use the following abuse of notations: if $i \in (\mathbb{Z}/2\mathbb{Z})^g$, we denote by $i$ any lift to $\mathbb{Z}^g$. Reciprocally if $i \in \mathbb{Z}^g$, we also denote by $i$ its reduction to $(\mathbb{Z}/2\mathbb{Z})^g$.

The analytic theta functions depend on the period matrix $\Omega_A$. Algebraically they are defined by a symmetric theta structure $\Theta_A$ of level 2. We will denote our theta functions by $\theta_i^{\Theta_A}$ when we want to make this dependence explicit.

We will also make use of the “dual” basis $\theta_{\chi}^{\prime A}(P) = \theta[\frac{\chi/2}{0}](2z_P, 2\Omega)$, $\chi \in (\hat{\mathbb{Z}}/2\hat{\mathbb{Z}})^g$, where we identify $(\hat{\mathbb{Z}}/2\hat{\mathbb{Z}})^g$ with $(\mathbb{Z}/2\mathbb{Z})^g$ via the inner product. Going to the dual level 2 coordinates corresponds analytically to the action of the symplectic matrix $S = (\begin{smallmatrix} 0 & 1 \\ -1 & 0 \end{smallmatrix})$ on the period matrix $\Omega_A$. Explicitly on theta coordinates the modular transform is given via the Hadamard transformation $\theta_{\chi}^{\prime} = \sum_i \chi(i)\theta_i$, and reciprocally $2^g\theta_i = \sum_{\chi} \chi(i)\theta_{\chi}^{\prime}$. We let $H$ be the Hadamard matrix in dimension $2^g$, by the formula above it allows to pass back and forth between the theta coordinates of level 2 and their duals.

## F.3 Matching theta structures

Let us recapitulate the isogeny we need to compute in the verification step of SQIsignHD: we have a $d$-isogeny $F: A \to B$ where $(A, \mathcal{L})$ and $(B, \mathcal{M})$ are
This graph represents the computational structure of $F$. To compute $F$, we need to compute the kernel basis $[\ell^{e-1}]\mathcal{B}_0, [\ell^{e-2}]\mathcal{B}_1, \dots, \mathcal{B}_{e-1}$ representing the $\ell$-isogenies in the chain, i.e. the bottom line in Figure 2. This graph is computed as follows: to go down right $[\ell^j]\mathcal{B}_i \to [\ell^j]\mathcal{B}_{i+1}$, we need to have reached the bottom vertex $[\ell^{e-1-i}]\mathcal{B}_i$ beforehand. Of course there are naive algorithms where we compute every point of the graph but they are quadratic in $e$ and far from optimal. There also exist divide and conquer strategies that require only $O(e \log(e))$ multiplications by $\ell$ and $\ell$-isogeny evaluations (see [JD11, § 4.2.2] for details). We can even optimize such a strategy to minimize the global cost depending on the relative cost of scalar multiplications by $\ell$ and $\ell$-isogeny evaluations.

## F.2 Theta coordinates

For simplicity, even through we work over a finite field, we will describe our algorithm using analytic theta functions. The algebraic theory of Mumford [Mum66b] can be used to show that our algorithms are still valid over an arbitrary field of odd characteristic.

Let $A = \mathbb{C}^g/(\mathbb{Z}^g + \Omega_A\mathbb{Z}^g)$ be an abelian variety with $\Omega = \Omega_A$ in the Siegel space corresponding to a principal polarisation $\mathcal{L} = \mathcal{L}_A$ on $A$. Let $\pi_A: \mathbb{C}^g \to A$ be the projection.

Recall that the analytic theta functions with characteristic $a, b \in \mathbb{Q}^g$ are given by

$$ \theta[\frac{a}{b}](z, \Omega) = \sum_{n \in \mathbb{Z}^g} e^{\pi i^t (n+a)\Omega(n+a) + 2\pi i^t (n+a)(z+b)}. $$

A basis of level 2 theta functions is given by $\theta_i^A(P) = \theta[\frac{0}{i/2}](z_P, \Omega/2)$, $i \in (\mathbb{Z}/2\mathbb{Z})^g$ where $z_P \in \mathbb{C}^g$ represents $P \in A$: $P = \pi_A(z_P)$. Here we use the following abuse of notations: if $i \in (\mathbb{Z}/2\mathbb{Z})^g$, we denote by $i$ any lift to $\mathbb{Z}^g$. Reciprocally if $i \in \mathbb{Z}^g$, we also denote by $i$ its reduction to $(\mathbb{Z}/2\mathbb{Z})^g$.

The analytic theta functions depend on the period matrix $\Omega_A$. Algebraically they are defined by a symmetric theta structure $\Theta_A$ of level 2. We will denote our theta functions by $\theta_i^{\Theta_A}$ when we want to make this dependence explicit.

We will also make use of the “dual” basis $\theta_{\chi}^{A}(P) = \theta[\frac{\chi/2}{0}](2z_P, 2\Omega)$, $\chi \in (\hat{\mathbb{Z}}/2\hat{\mathbb{Z}})^g$, where we identify $(\hat{\mathbb{Z}}/2\hat{\mathbb{Z}})^g$ with $(\mathbb{Z}/2\mathbb{Z})^g$ via the inner product. Going to the dual level 2 coordinates corresponds analytically to the action of the symplectic matrix $S = (\begin{smallmatrix} 0 & 1 \\ -1 & 0 \end{smallmatrix})$ on the period matrix $\Omega_A$. Explicitly on theta coordinates the modular transform is given via the Hadamard transformation $\theta'_{\chi} = \sum_i \chi(i)\theta_i$, and reciprocally $2^g\theta_i = \sum_{\chi} \chi(i)\theta'_{\chi}$. We let $H$ be the Hadamard matrix in dimension $2^g$, by the formula above it allows to pass back and forth between the theta coordinates of level 2 and their duals.

## F.3 Matching theta structures

Let us recapitulate the isogeny we need to compute in the verification step of SQIsignHD: we have a $d$-isogeny $F: A \to B$ where $(A, \mathcal{L})$ and $(B, \mathcal{M})$ are
given by products of elliptic curves with their product polarisations. We split
the isogeny in two as in Section 4.3: $F = F_2 \circ F_1$ with $F_1 : A \to C$ a $d_1$-isogeny
and $F_2 : C \to B$ an $d_2$-isogeny, and we assume that we are given the kernel of
$F_1$ in $A[d_1]$ and $\tilde{F}_2$ in $B[d_2]$.

The theta isogeny algorithm to compute $F_1$ requires (if $d_1$ is odd):

- A symmetric level 2 theta structure $\Theta_A$ on $(A, \mathcal{L})$. This level structure determines a symplectic basis of $A[2]$ and is in turn determined by a symplectic basis of $A[4]$. This symmetric level structure will be represented (up to twists) by the theta constant $(\theta_i^{\Theta_A}(0))_{i \in (\mathbb{Z}/2\mathbb{Z})^g}$ and gives a basis of sections $(\theta_i^{\Theta_A})_{i \in (\mathbb{Z}/2\mathbb{Z})^g}$ of $\mathcal{L}^2$. In particular if the 4-torsion is rational, the level 2 theta model will be rational (this is a sufficient but not necessary condition).

- Generators $P_1, \dots, P_g$ of the kernel $K = \text{Ker} F_1$ in theta coordinates $\theta_i^{\Theta_A}(P_j)$, with the basis of theta coordinates induced by the symmetric theta structure fixed above.

In SQIsignHD, $A$ will be equal to a product of $g$ elliptic curves $A = E_1 \times \dots \times E_g$ and the points of the kernel $K$ is described in terms of tuples of Weierstrass coordinates. We first need to explain how to convert these points to theta coordinates. We fix a symplectic basis $(e_i, f_i)$ on each $E_i$[4], this induces a product symplectic basis on $A$[4], hence a product theta structure. There are well known formula to convert from Weierstrass coordinates on $E_i$ to theta coordinates [Mum84]. We can then compute the theta coordinates on $A$ as follows:

**Lemma 52.** Let $\mathcal{L} = \mathcal{L}_1 \star \mathcal{L}_2 \cdots \star \mathcal{L}_g$ be a product polarisation on $A = E_1 \times \cdots \times E_g$. Endow $(A, \mathcal{L})$ with a product theta structure $\Theta_A$ of each theta structure $\Theta_{E_i}$ on $E_i$. If $P = (P_1, \dots, P_g) \in A$, then for $i = (i_1, \dots, i_g) \in (\mathbb{Z}/2\mathbb{Z})^g$, $\theta_i^{\Theta_A}(P) = \prod_{j=1}^g \theta_{i_j}^{\Theta_{E_j}}(P_j)$.

*Proof.* This follows from

$$
\theta \begin{bmatrix} a_1 & a_2 \\ b_1 & b_2 \end{bmatrix} ((z_1, z_2), \begin{pmatrix} \Omega_1 & 0 \\ 0 & \Omega_2 \end{pmatrix}) = \theta \begin{bmatrix} a_1 \\ b_1 \end{bmatrix} (z_1, \Omega_1) \theta \begin{bmatrix} a_2 \\ b_2 \end{bmatrix} (z_2, \Omega_2).
$$

□

Hence if we have a point $R \in A$ given in product Weierstrass coordinates
$R = (R_j) = ((x_j, y_j))$, we can convert each $R_i$ from Weierstrass coordinates
to level 2 theta coordinates $\theta_i^{\Theta_{E_j}}(R_j)$ then apply Lemma 52 to get the theta
coordinates of $R$ with respect to the product theta structure.

We can now apply the isogeny theorem from [CR15; LR23] with $N = d_1, d_2$:

**Theorem 53.** Let $(A, \mathcal{L})$ be a principally polarised abelian variety with a sym-
metric theta structure $\Theta_A$ of level 2, induced by a symplectic basis $\mathcal{B}_A =$
$(x_1, \dots, x_g, y_1, \dots, y_g)$ of $A[4]$ with respect to $\zeta$, a primitive fourth root of unity.

Let $(P_1, \dots, P_g)$ be a basis of the kernel of a maximal isotropic subgroup of $A[N]$ of rank $g$, given in theta coordinates, where $N$ is an odd integer.
given by products of elliptic curves with their product polarisations. We split
the isogeny in two as in Section 4.3: $F = F_2 \circ F_1$ with $F_1 : A \to C$ a $d_1$-isogeny
and $F_2 : C \to B$ an $d_2$-isogeny, and we assume that we are given the kernel of
$F_1$ in $A[d_1]$ and $\tilde{F}_2$ in $B[d_2]$.

The theta isogeny algorithm to compute $F_1$ requires (if $d_1$ is odd):

- A symmetric level 2 theta structure $\Theta_A$ on $(A, \mathcal{L})$. This level structure determines a symplectic basis of $A[2]$ and is in turn determined by a symplectic basis of $A[4]$. This symmetric level structure will be represented (up to twists) by the theta constant $(\theta_i^{\Theta_A}(0))_{i \in (\mathbb{Z}/2\mathbb{Z})^g}$ and gives a basis of sections $(\theta_i^{\Theta_A})_{i \in (\mathbb{Z}/2\mathbb{Z})^g}$ of $\mathcal{L}^2$. In particular if the 4-torsion is rational, the level 2 theta model will be rational (this is a sufficient but not necessary condition).

- Generators $P_1, \dots, P_g$ of the kernel $K = \text{Ker} F_1$ in theta coordinates $\theta_i^{\Theta_A}(P_j)$, with the basis of theta coordinates induced by the symmetric theta structure fixed above.

In SQIsignHD, $A$ will be equal to a product of $g$ elliptic curves $A = E_1 \times \dots \times E_g$ and the points of the kernel $K$ is described in terms of tuples of Weierstrass coordinates. We first need to explain how to convert these points to theta coordinates. We fix a symplectic basis $(e_i, f_i)$ on each $E_i$[4], this induces a product symplectic basis on $A$[4], hence a product theta structure. There are well known formula to convert from Weierstrass coordinates on $E_i$ to theta coordinates [Mum84]. We can then compute the theta coordinates on $A$ as follows:

**Lemma 52.** Let $\mathcal{L} = \mathcal{L}_1 \star \mathcal{L}_2 \cdots \star \mathcal{L}_g$ be a product polarisation on $A = E_1 \times \cdots \times E_g$. Endow $(A, \mathcal{L})$ with a product theta structure $\Theta_A$ of each theta structure $\Theta_{E_i}$ on $E_i$. If $P = (P_1, \dots, P_g) \in A$, then for $i = (i_1, \dots, i_g) \in (\mathbb{Z}/2\mathbb{Z})^g$, $\theta_i^{\Theta_A}(P) = \prod_{j=1}^g \theta_{i_j}^{\Theta_{E_j}}(P_j)$.

*Proof.* This follows from

$$
\theta \begin{bmatrix} a_1 & a_2 \\ b_1 & b_2 \end{bmatrix} ((z_1, z_2), \begin{pmatrix} \Omega_1 & 0 \\ 0 & \Omega_2 \end{pmatrix}) = \theta \begin{bmatrix} a_1 \\ b_1 \end{bmatrix} (z_1, \Omega_1) \theta \begin{bmatrix} a_2 \\ b_2 \end{bmatrix} (z_2, \Omega_2).
$$

□

Hence if we have a point $R \in A$ given in product Weierstrass coordinates
$R = (R_j) = ((x_j, y_j))$, we can convert each $R_i$ from Weierstrass coordinates
to level 2 theta coordinates $\theta_i^{\Theta_{E_j}}(R_j)$ then apply Lemma 52 to get the theta
coordinates of $R$ with respect to the product theta structure.

We can now apply the isogeny theorem from [CR15; LR23] with $N = d_1, d_2$:

**Theorem 53.** Let $(A, \mathcal{L})$ be a principally polarised abelian variety with a sym-
metric theta structure $\Theta_A$ of level 2, induced by a symplectic basis $\mathcal{B}_A =$
$(x_1, \dots, x_g, y_1, \dots, y_g)$ of $A[4]$ with respect to $\zeta$, a primitive fourth root of unity.

Let $(P_1, \dots, P_g)$ be a basis of the kernel of a maximal isotropic subgroup of $A[N]$ of rank $g$, given in theta coordinates, where $N$ is an odd integer.
Let $P$ be a point of $A$ given in theta coordinates. Let $F: A \to B = A/K$ be the induced isogeny. Then there is a unique descent of $\mathcal{L}^N$ to a polarisation $\mathcal{M}$ on $B$, and a symmetric theta structure $\Theta_B$ on $\mathcal{M}$ induced by the symplectic basis $F(\mathcal{B}_A) = (\frac{1}{N}F(x_1), \dots, \frac{1}{N}F(x_g), F(y_1), \dots, F(y_g))$ with respect to $\zeta$ of $B[4]$.

Furthermore, the theta null point of $B$ and the theta coordinates of $F(P)$ can be computed in $O(N^g)$ arithmetic operations over the base field.

*Proof.* This is a special case of Theorem 56 proved below. □

We can use Theorem 53 to compute an $l^e$-isogeny by splitting it into a product of $l$-isogenies. In SQIsignHD we specifically want to handle the case $l=2$. We will give an algorithm in Appendix F.4.

We have another difficulty to solve first. In SQIsignHD we glue two isogenies together $F_1: A \to C$ and $\tilde{F}_2: B \to C$. These isogenies are compatible with the product polarisation on $A$ and $B$, so the codomain $C$ is endowed with the same polarisation in both cases. However, when using Theorem 53 to compute $C$ and its polarisation, it needs not be endowed with the same level 2 symmetric theta structure $\Theta_C$ for the two isogenies.

Let $\mathcal{B}_1$ be a symplectic basis of $C[4]$ giving the symmetric theta structure on $C$ induced by $F_1$, and $\mathcal{B}_2$ be the one induced by $\tilde{F}_2$. Then there is a symplectic matrix $M \in \text{Sp}_{2g}(\mathbb{Z}/4\mathbb{Z})$ such that $M\mathcal{B}_1 = \mathcal{B}_2$. We can use the theta transformation formula [BL04, §8.6] for $M$ to convert the theta null point expressed in terms of $\mathcal{B}_1$ to the one expressed in terms of $\mathcal{B}_2$: $\theta_i^{\mathcal{B}_2}(0) = \theta_i^{M\mathcal{B}_1}(0)$. Once we have endowed $C$ with the same theta structures, checking that they are indeed the same simply amounts to testing for equality of the theta null points seen as projective coordinates.

So one way to test that $F_1$ and $\tilde{F}_2$ indeed have the same polarised codomain $C$ is to apply Theorem 53 twice and then to act by all matrices in $M \in \text{Sp}_{2g}(\mathbb{Z}/4\mathbb{Z})$ on the theta null point induced by $F_1$ until we find an equality of projective theta null points with the theta null point induced by $\tilde{F}_2$. This costs $O(1)$ but in practice is too expensive. We will instead explain how to compute the correct correcting matrix $M$ directly.

**Remark 54.** Many symplectic basis $\mathcal{B}_C$ of $C[4]$ will give the same symmetric theta structure $\Theta_C$ of level 2 on $C$ (hence the same theta null point), indeed the theta null point only determines a symplectic basis of $C[2]$. Rather than working with the 4-torsion we could work only with the 2-torsion and take $M \in \text{Sp}_{2g}(\mathbb{Z}/2\mathbb{Z})$; this does not completely determines all the symmetric theta structures of level 2 but it is easy to test all $2^{2g}$ possibilities.

**Proposition 55.** Let $F_1: A \to C$ be a $d_1$-isogeny, $\tilde{F}_2: B \to C$ be a $d_2$-isogeny, $F = F_2 \circ F_1: A \to B$, with $d_1$ and $d_2$ prime to 2. Let $\mathcal{B}_A$ a symplectic basis of $A[4]$, $\mathcal{B}_B$ a symplectic basis of $B[4]$. Let $\mathcal{B}'_B$ be the symplectic basis on $B$ induced by $F$. Let $M' = \begin{pmatrix} \alpha' & \beta' \\ \gamma' & \delta' \end{pmatrix}$ be the symplectic matrix such that $M'\mathcal{B}'_B = \mathcal{B}_B$. Let $\mathcal{B}_1$ be the symplectic basis of $C[4]$ induced by $F_1$ and $\mathcal{B}_2$ be the symplectic basis of $C[4]$ induced by $\tilde{F}_2$. Then $\mathcal{B}_2 = M\mathcal{B}_1$, with $M = \begin{pmatrix} \alpha'/d_2 & \beta' \\ \gamma' & d_2\gamma' \end{pmatrix}$.
Let $P$ be a point of $A$ given in theta coordinates. Let $F: A \to B = A/K$ be the induced isogeny. Then there is a unique descent of $\mathcal{L}^N$ to a polarisation $\mathcal{M}$ on $B$, and a symmetric theta structure $\Theta_B$ on $\mathcal{M}$ induced by the symplectic basis $F(\mathcal{B}_A) = (\frac{1}{N}F(x_1), \dots, \frac{1}{N}F(x_g), F(y_1), \dots, F(y_g))$ with respect to $\zeta$ of $B[4]$.

Furthermore, the theta null point of $B$ and the theta coordinates of $F(P)$ can be computed in $O(N^g)$ arithmetic operations over the base field.

*Proof.* This is a special case of Theorem 56 proved below. $\square$

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

We can use Theorem 53 to compute an $l^e$-isogeny by splitting it into a product of $l$-isogenies. In SQIsignHD we specifically want to handle the case $l=2$. We will give an algorithm in Appendix F.4.

We have another difficulty to solve first. In SQIsignHD we glue two isogenies together $F_1: A \to C$ and $\tilde{F}_2: B \to C$. These isogenies are compatible with the product polarisation on $A$ and $B$, so the codomain $C$ is endowed with the same polarisation in both cases. However, when using Theorem 53 to compute $C$ and its polarisation, it needs not be endowed with the same level 2 symmetric theta structure $\Theta_C$ for the two isogenies.

Let $\mathcal{B}_1$ be a symplectic basis of $C[4]$ giving the symmetric theta structure on $C$ induced by $F_1$, and $\mathcal{B}_2$ be the one induced by $\tilde{F}_2$. Then there is a symplectic matrix $M \in \text{Sp}_{2g}(\mathbb{Z}/4\mathbb{Z})$ such that $M\mathcal{B}_1 = \mathcal{B}_2$. We can use the theta transformation formula [BL04, §8.6] for $M$ to convert the theta null point expressed in terms of $\mathcal{B}_1$ to the one expressed in terms of $\mathcal{B}_2$: $\theta_i^{\mathcal{B}_2}(0) = \theta_i^{MB_1}(0)$. Once we have endowed $C$ with the same theta structures, checking that they are indeed the same simply amounts to testing for equality of the theta null points seen as projective coordinates.

So one way to test that $F_1$ and $\tilde{F}_2$ indeed have the same polarised codomain $C$ is to apply Theorem 53 twice and then to act by all matrices in $M \in \text{Sp}_{2g}(\mathbb{Z}/4\mathbb{Z})$ on the theta null point induced by $F_1$ until we find an equality of projective theta null points with the theta null point induced by $\tilde{F}_2$. This costs $O(1)$ but in practice is too expensive. We will instead explain how to compute the correct correcting matrix $M$ directly.

**Remark 54.** Many symplectic basis $\mathcal{B}_C$ of $C[4]$ will give the same symmetric theta structure $\Theta_C$ of level 2 on $C$ (hence the same theta null point), indeed the theta null point only determines a symplectic basis of $C[2]$. Rather than working with the 4-torsion we could work only with the 2-torsion and take $M \in \text{Sp}_{2g}(\mathbb{Z}/2\mathbb{Z})$; this does not completely determines all the symmetric theta structures of level 2 but it is easy to test all $2^{2g}$ possibilities.

**Proposition 55.** Let $F_1: A \to C$ be a $d_1$-isogeny, $\tilde{F}_2: B \to C$ be a $d_2$-isogeny, $F = F_2 \circ F_1: A \to B$, with $d_1$ and $d_2$ prime to 2. Let $\mathcal{B}_A$ a symplectic basis of $A[4]$, $\mathcal{B}_B$ a symplectic basis of $B[4]$. Let $\mathcal{B}'_B$ be the symplectic basis on $B$ induced by $F$. Let $M' = \begin{pmatrix} \alpha' & \beta' \\ \gamma' & \delta' \end{pmatrix}$ be the symplectic matrix such that $M'\mathcal{B}'_B = \mathcal{B}_B$. Let $\mathcal{B}_1$ be the symplectic basis of $C[4]$ induced by $F_1$ and $\mathcal{B}_2$ be the symplectic basis of $C[4]$ induced by $\tilde{F}_2$. Then $\mathcal{B}_2 = M\mathcal{B}_1$, with $M = \begin{pmatrix} \alpha'/d_2 & \beta' \\ \gamma' & d_2\gamma' \end{pmatrix}$.
Proof. Define $\gamma_x = \begin{pmatrix} x & 0 \\ 0 & 1 \end{pmatrix}$. By Theorem 53, we have $B_1 = \gamma_{1/d_1} \cdot F_1 B_A$, $B_2 = \gamma_{1/d_2} \cdot \tilde{F}_2 B_B$, $B'_B = \gamma_{1/d} \cdot F B_A$. If $MB_1 = B_2$, we get that $M = d_2\gamma_{1/d_2} M' \gamma_{1/d} \gamma_{1/d_1}^{-1}$. $\square$

So if we compute the image of $F$ on $A[4]$, we can recover the correct matrix $M$. In SQIsignHD, $F$ is built from $\sigma: E_1 \to E_2$ and scalars, so for the verification it suffices to give the action of $\sigma$ on the 4-torsion. If it is not provided, we can just guess it and try the corresponding symplectic matrix, this greatly reduces the number of symplectic matrices to try to only a few choices.

We now explain how to handle the case of a $d$-isogeny $F$ where $d$ is not prime to 2. A difficulty is that if we only start with a symplectic basis $B_A$ of $A[4]$, then since the kernel of $F_1$ may contain points of 4-torsion, $F_1$ does not induce a canonical symplectic basis of $C[4]$ anymore. So the algorithm needs to start with more data.

**Theorem 56.** Let $(A, \mathcal{L})$ be a principally polarised abelian variety, with $\mathcal{L}$ a symmetric ample line bundle. Let $N$ be an integer, $B'_A = (x'_1, \dots, x'_g, y'_1, \dots, y'_g)$ be a symplectic basis of $A[4N]$ with respect to a primitive $4N$-root of unity $\zeta$, and $B_A = N B'_A$ the induced symplectic basis of $A[4]$. It induces a symmetric level 2 theta structure $\Theta_A$ on $A$.

Let $K$ be the maximal isotropic kernel generated by the points $P_j = 4x'_j$. Assume that we are given the theta coordinates of level 2 of the $x'_j$, and the theta coordinates of a point $P$ in $A$.

Let $F: A \to B = A/K$ the induced isogeny. Then there is a unique descent of $\mathcal{L}^N$ to a symmetric line bundle $M$ on $B$, and a symmetric theta structure on $M$ induced by the symplectic basis

$$ (F(x'_1), \dots, F(x'_g), NF(y'_1), \dots, NF(y'_g)) $$

with respect to $\zeta^N$ of $B[4]$.

Furthermore, the theta null points of $B$ and the theta coordinates of $F(P)$ can be computed in $O(N^g)$ arithmetic operations over the base field.

Proof. Since we are given the points $(x'_i, y'_i)$ in level 2 theta coordinates, we can use the algorithms of [LR12; CR15; LR23] to construct a symmetric theta structure of level $2N$ on the theta group $G(\mathcal{L}^{2N})$. However, the references above assume for simplicity that the degree of the isogenies is prime to the level $m$ of the symmetric theta structure we start with. Here $m = 2$ and $N$ is no longer assumed to be odd. So we need the general case, which is described in [Rob10, Chapters 6 and 7], [Rob21, § 2.10, Remarks 2.10.3 and 2.10.7]. Once we are in level $2N$, we can apply Mumford's isogeny theorem [Mum66a, Theorem 4 p.302–303] to obtain a symmetric theta structure $\Theta_B$ of level 2 on $B$ and the equations of the isogeny. The algorithm takes time $O(N^g)$. It remains to show that the theta structure we obtain on $B$ is the one induced by the points $(F(x'_1), \dots, F(x'_g), NF(y'_1), \dots, NF(y'_g))$.
Proof. Define $\gamma_x = \begin{pmatrix} x & 0 \\ 0 & 1 \end{pmatrix}$. By Theorem 53, we have $\mathcal{B}_1 = \gamma_{1/d_1} \cdot F_1 \mathcal{B}_A$, $\mathcal{B}_2 = \gamma_{1/d_2} \cdot \tilde{F}_2 \mathcal{B}_B$, $\mathcal{B}'_B = \gamma_{1/d} \cdot F \mathcal{B}_A$. If $M \mathcal{B}_1 = \mathcal{B}_2$, we get that $M = d_2 \gamma_{1/d_2} M' \gamma_{1/d} \gamma_{1/d_1}^{-1}$. $\square$

So if we compute the image of $F$ on $A[4]$, we can recover the correct matrix $M$. In SQIsignHD, $F$ is built from $\sigma: E_1 \to E_2$ and scalars, so for the verification it suffices to give the action of $\sigma$ on the 4-torsion. If it is not provided, we can just guess it and try the corresponding symplectic matrix, this greatly reduces the number of symplectic matrices to try to only a few choices.

We now explain how to handle the case of a $d$-isogeny $F$ where $d$ is not prime to 2. A difficulty is that if we only start with a symplectic basis $\mathcal{B}_A$ of $A[4]$, then since the kernel of $F_1$ may contain points of 4-torsion, $F_1$ does not induce a canonical symplectic basis of $C[4]$ anymore. So the algorithm needs to start with more data.

**Theorem 56.** Let $(A, \mathcal{L})$ be a principally polarised abelian variety, with $\mathcal{L}$ a symmetric ample line bundle. Let $N$ be an integer, $\mathcal{B}'_A = (x'_1, \dots, x'_g, y'_1, \dots, y'_g)$ be a symplectic basis of $A[4N]$ with respect to a primitive $4N$-root of unity $\zeta$, and $\mathcal{B}_A = N \mathcal{B}'_A$ the induced symplectic basis of $A[4]$. It induces a symmetric level 2 theta structure $\Theta_A$ on $A$.

Let $K$ be the maximal isotropic kernel generated by the points $P_j = 4x'_j$. Assume that we are given the theta coordinates of level 2 of the $x'_j$, and the theta coordinates of a point $P$ in $A$.

Let $F: A \to B = A/K$ the induced isogeny. Then there is a unique descent of $\mathcal{L}^N$ to a symmetric line bundle $M$ on $B$, and a symmetric theta structure on $M$ induced by the symplectic basis

$$ (F(x'_1), \dots, F(x'_g), NF(y'_1), \dots, NF(y'_g)) $$

with respect to $\zeta^N$ of $B[4]$.

Furthermore, the theta null points of $B$ and the theta coordinates of $F(P)$ can be computed in $O(N^g)$ arithmetic operations over the base field.

Proof. Since we are given the points $(x'_i, y'_i)$ in level 2 theta coordinates, we can use the algorithms of [LR12; CR15; LR23] to construct a symmetric theta structure of level $2N$ on the theta group $G(\mathcal{L}^{2N})$. However, the references above assume for simplicity that the degree of the isogenies is prime to the level $m$ of the symmetric theta structure we start with. Here $m = 2$ and $N$ is no longer assumed to be odd. So we need the general case, which is described in [Rob10, Chapters 6 and 7], [Rob21, § 2.10, Remarks 2.10.3 and 2.10.7]. Once we are in level $2N$, we can apply Mumford's isogeny theorem [Mum66a, Theorem 4 p.302–303] to obtain a symmetric theta structure $\Theta_B$ of level 2 on $B$ and the equations of the isogeny. The algorithm takes time $O(N^g)$. It remains to show that the theta structure we obtain on $B$ is the one induced by the points $(F(x'_1), \dots, F(x'_g), NF(y'_1), \dots, NF(y'_g))$.
Let $Z(K)$ be the centralizer of $K$ in the theta group $G(\mathcal{L}^{2N})$. The theta structure $\Theta_B$ is induced by the canonical map $\alpha_f : Z(K)/\tilde{K} \to G(\mathcal{M}^2)$ from [Mum66a, Equation (2) p.302], where $\tilde{K}$ is the canonical lift of $K$ into the theta group $G(\mathcal{L}^{2N})$ induced by our theta structure of level $2N$. The points

$$ (2F(x'_1), \dots, 2F(x'_g), 2NF(y'_1), \dots, 2NF(y'_g)) $$

form a symplectic basis of $B[2]$. The theta structure $\Theta_B$ on $G(\mathcal{M}^2)$ is determined by the symmetric lifts of this basis into $G(\mathcal{M}^2)$. By definition of the induced theta structure, if $T$ is in this basis, the symmetric lift $g_T \in G(\mathcal{M}^2)$ above $T$ induced by $\Theta_B$ is given by the image by $\alpha_f$ of the symmetric lift $g_{T'} \in G(\mathcal{L}^{2N})$ induced by the theta structure of level $2N$ on $A$ for any point $T'$ such that $F(T') = T$. For $T = 2F(x'_j)$, we can take $T' = 2x'_j$. Since the theta structure on $G(\mathcal{L}^{2N})$ is determined by the basis $(x'_j, y'_j)$, the lift $g_{T'}$ is determined as follow: let $g_{x'_j} \in G(\mathcal{L}^{4N})$ be any of the two symmetric lift of $x'_j$, and define $g_{T'} = \eta_2(g_{x'_j})$ where $\eta_2$ is defined in [Mum66a, § 2, p.310]; this does not depend on the choice of $g_{x'_j}$. Since $\alpha_f$ sends symmetric elements into symmetric elements and commutes with $\eta_2$, we get that $g_T = \eta_2(g_{F(x'_j)})$ where $g_{F(x'_j)}$ is any of the two symmetric element above $F(x'_j)$ in $G(\mathcal{M}^4)$. Likewise, when $T = 2NF(y'_j)$, we check that $g_T = \eta_2(g_{NF(y'_j)})$, for $g_{NF(y'_j)} \in G(\mathcal{M}^4)$ one of the two symmetric elements above $NF(y'_j)$. Hence the descent of the symmetric theta structure of level $2N$ on $G(\mathcal{L}^{2N})$ induced by the basis $(x'_1, \dots, x'_g, y'_1, \dots, y'_g)$ to a symmetric theta structure of level 2 on $G(\mathcal{M}^2)$ is indeed the one induced by $(F(x'_1), \dots, F(x'_g), NF(y'_1), \dots, NF(y'_g))$. $\square$

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

Notice that $NF(y'_j) = F(y_j)$, so Theorem 56 only needs the points $(x'_j, y_j)$ as input. If $N$ is odd, Theorem 53 is a special case of Theorem 56: by the CRT, from a symplectic basis $(x_j, y_j)$ of $A[4]$ and a basis $P_j$ of $K$, there is a unique $x'_j \in A[4N]$ which induces both $x_j$ and $P_j$: $x_j = Nx'_j$, $P_j = 4x'_j$.

However when $N$ is not prime to 2, we cannot start with any symplectic basis $(x_j, y_j)$ of $A[4]$, it has to be compatible with our kernel $K$, in the sense that there should exists $x'_j$ a basis of a maximal isotropic subgroup of $A[4N]$ which induces both $x_j$ and $P_j$. In the situation of SQIsignHD, where we convert our points given by tuple of Weierstrass coordinates into theta coordinates given by a product theta structure, the resulting product symplectic basis of $A[4]$ will not be compatible with our kernels in general. So to get an input suitable for Theorem 56, we first start with the basis $(P_j)$ of $K$ (in tuple of Weierstrass coordinates), fix points $x'_j$ above each $P_j$ such that $P_j = 4x'_j$ and the $x'_j$ generate an isotropic subgroup of $A[4N]$. Then we let $x_j = Nx'_j$, and fix a symplectic complement $y_j$ of the $x_j$. We compute the symplectic matrix $M$ that changes the product symplectic basis into the $(x_j, y_j)$ and act by this matrix to get the theta coordinates in terms of our new basis $(x_j, y_j)$.

We can adapt Proposition 55 to the general case:

**Proposition 57.** Let $F_1 : A \to C$ be a $d_1$-isogeny, $\tilde{F}_2 : B \to C$ a $d_2$-isogeny and $F = F_2 \circ F_1$ an $d$-isogeny, where $d = d_1d_2$. Let $d'$ be a common multiple of $d_1$ and $d_2$, and write $d' = c_1d_1 = c_2d_2$.
Let $Z(K)$ be the centralizer of $K$ in the theta group $G(\mathcal{L}^{2N})$. The theta structure $\Theta_B$ is induced by the canonical map $\alpha_f : Z(K)/\tilde{K} \to G(\mathcal{M}^2)$ from [Mum66a, Equation (2) p.302], where $\tilde{K}$ is the canonical lift of $K$ into the theta group $G(\mathcal{L}^{2N})$ induced by our theta structure of level $2N$. The points

$$ (2F(x'_1), \dots, 2F(x'_g), 2NF(y'_1), \dots, 2NF(y'_g)) $$

form a symplectic basis of $B[2]$. The theta structure $\Theta_B$ on $G(\mathcal{M}^2)$ is determined by the symmetric lifts of this basis into $G(\mathcal{M}^2)$. By definition of the induced theta structure, if $T$ is in this basis, the symmetric lift $g_T \in G(\mathcal{M}^2)$ above $T$ induced by $\Theta_B$ is given by the image by $\alpha_f$ of the symmetric lift $g_{T'} \in G(\mathcal{L}^{2N})$ induced by the theta structure of level $2N$ on $A$ for any point $T'$ such that $F(T') = T$. For $T = 2F(x'_j)$, we can take $T' = 2x'_j$. Since the theta structure on $G(\mathcal{L}^{2N})$ is determined by the basis $(x'_j, y'_j)$, the lift $g_{T'}$ is determined as follow: let $g_{x'_j} \in G(\mathcal{L}^{4N})$ be any of the two symmetric lift of $x'_j$, and define $g_{T'} = \eta_2(g_{x'_j})$ where $\eta_2$ is defined in [Mum66a, § 2, p.310]; this does not depend on the choice of $g_{x'_j}$. Since $\alpha_f$ sends symmetric elements into symmetric elements and commutes with $\eta_2$, we get that $g_T = \eta_2(g_{F(x'_j)})$ where $g_{F(x'_j)}$ is any of the two symmetric element above $F(x'_j)$ in $G(\mathcal{M}^4)$. Likewise, when $T = 2NF(y'_j)$, we check that $g_T = \eta_2(g_{NF(y'_j)})$, for $g_{NF(y'_j)} \in G(\mathcal{M}^4)$ one of the two symmetric elements above $NF(y'_j)$. Hence the descent of the symmetric theta structure of level $2N$ on $G(\mathcal{L}^{2N})$ induced by the basis $(x'_1, \dots, x'_g, y'_1, \dots, y'_g)$ to a symmetric theta structure of level 2 on $G(\mathcal{M}^2)$ is indeed the one induced by $(F(x'_1), \dots, F(x'_g), NF(y'_1), \dots, NF(y'_g))$. $\square$

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

Notice that $NF(y'_j) = F(y_j)$, so Theorem 56 only needs the points $(x'_j, y_j)$ as input. If $N$ is odd, Theorem 53 is a special case of Theorem 56: by the CRT, from a symplectic basis $(x_j, y_j)$ of $A[4]$ and a basis $P_j$ of $K$, there is a unique $x'_j \in A[4N]$ which induces both $x_j$ and $P_j$: $x_j = Nx'_j$, $P_j = 4x'_j$.

However when $N$ is not prime to 2, we cannot start with any symplectic basis $(x_j, y_j)$ of $A[4]$, it has to be compatible with our kernel $K$, in the sense that there should exists $x'_j$ a basis of a maximal isotropic subgroup of $A[4N]$ which induces both $x_j$ and $P_j$. In the situation of SQIsignHD, where we convert our points given by tuple of Weierstrass coordinates into theta coordinates given by a product theta structure, the resulting product symplectic basis of $A[4]$ will not be compatible with our kernels in general. So to get an input suitable for Theorem 56, we first start with the basis $(P_j)$ of $K$ (in tuple of Weierstrass coordinates), fix points $x'_j$ above each $P_j$ such that $P_j = 4x'_j$ and the $x'_j$ generate an isotropic subgroup of $A[4N]$. Then we let $x_j = Nx'_j$, and fix a symplectic complement $y_j$ of the $x_j$. We compute the symplectic matrix $M$ that changes the product symplectic basis into the $(x_j, y_j)$ and act by this matrix to get the theta coordinates in terms of our new basis $(x_j, y_j)$.

We can adapt Proposition 55 to the general case:

**Proposition 57.** Let $F_1 : A \to C$ be a $d_1$-isogeny, $\tilde{F}_2 : B \to C$ a $d_2$-isogeny and $F = F_2 \circ F_1$ an $d$-isogeny, where $d = d_1d_2$. Let $d'$ be a common multiple of $d_1$ and $d_2$, and write $d' = c_1d_1 = c_2d_2$.
Let $(P_1, \dots, P_g)$ be a basis of the kernel of $F_1$, and $(x'_1, \dots, x'_g, y'_1, \dots, y'_g)$ a symplectic basis of $A[4d']$ with respect to $\zeta$, a primitive $4d'$-root of unity, and such that $P_i = 4c_1x'_i$.

Let $(Q_1, \dots, Q_g)$ be a basis of the kernel of $\tilde{F}_2$, and $(u'_1, \dots, u'_g, v'_1, \dots, v'_g)$ a symplectic basis of $B[4d']$ with respect to $\zeta$, such that $Q_i = 4c_2v'_i$.

Then the induced theta structure on $C$ induced by $F_1$ and $\tilde{F}_2$ via Theorem 56 is the same if

$$ \tilde{F}_2(c_2v'_i) = F_1(d'y'_i) \text{ and } F_1(c_1x'_i) = \tilde{F}_2(d'u'_i) \qquad (5) $$

*Proof.* The symplectic theta structure on $C$ induced by $F_1$ is given by $(F_1(c_1x'_i), F_1(d'y'_i))$, and the one induced by $\tilde{F}_2$ is given by $(\tilde{F}_2(d'u'_i), \tilde{F}_2(c_2v'_i))$. $\square$

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

We note that in the isogeny algorithm for $F_1$ we only need the points $c_1x'_i, d'y'_i$ and for $\tilde{F}_2$ we only need the points $d'u'_i, c_2v'_i$.

**Corollary 58.** Let $F = F_2 \circ F_1$. To get the same theta structure on $C$, it suffices to choose $x'_i, y'_i, u'_i, v'_i$ such that $F(c_2y'_i) = c_2v'_i$ and $\tilde{F}(c_1u'_i) = c_1x'_i$.

An algorithm to construct suitable $x'_i, y'_i, u'_i, v'_i$ is as follows. Take $y''_i$ a basis of a symplectic complement of $\text{Ker } F_1$ in $A[d_1], y'_i \in A[d']$ isotropic such that $4c_1y'_i = y''_i$, and let $v'_i = F(y'_i)$. Then $Q_i = 4c_2v'_i$ is a basis of $\text{Ker } \tilde{F}_2$. We let $u'_i$ be a symplectic complement of $v'_i$ in $B[d']$, and we let $x'_i = \tilde{F}(u'_i)$. Let $P_i = 4c_1x'_i$, they form a basis of $\text{Ker } F_1$.

Corollary 58 explain why we need $f \ge e_2 + 2$ in Remark 4.2 when $\ell = 2$ (an alternative if we are only given the action of $\sigma$ on $E_1[\ell^{e_2}]$ would be to just guess it on $E_1[\ell^{e_2+2}]$).

<table><caption>**Algorithm 20:** Finding two compatible basis.</caption><thead><tr><th></th><th></th></tr></thead><tbody><tr><td><b>Data:</b></td><td>ker($\tilde{F}_2$), an algorithm to evaluate $F = F_1 \circ F_2$ on $A[d']$ and an algorithm to evaluate $\tilde{F}$ on $B[d']$.</td></tr><tr><td><b>Result:</b></td><td>Two symplectic basis $(x'_1, \dots, x'_g, y'_1, \dots, y'_g)$ of $A[4d']$ and $(u'_1, \dots, u'_g, v'_1, \dots, v'_g)$ of $B[4d']$ such that $\text{ker}(F_1) = \langle 4c_1x'_i \rangle_i$, $\text{ker}(\tilde{F}_2) = \langle 4c_2v'_i \rangle_i$, $F(c_2y'_i) = c_2v'_i$ and $\tilde{F}(c_1u'_i) = c_1x'_i$ for all $i \in [1; g]$.</td></tr><tr><td>1</td><td>Find $(y''_1, \dots, y''_g)$ a basis of a symplectic complement of $\text{Ker}(F_1)$ in $A[d_1]$;</td></tr><tr><td>2</td><td>Find $(y'_1, \dots, y'_g)$ forming an isotropic subgroup of $A[d']$ such that $4c_1y'_i = y''_i$ for all $i \in [1; g]$;</td></tr><tr><td>3</td><td>$v'_i \leftarrow \tilde{F}(y'_i)$ for all $i \in [1; g]$;</td></tr><tr><td>4</td><td>Let $(u'_1, \dots, u'_g)$ be a symplectic complement of the $v'_i$ in $B[d']$;</td></tr><tr><td>5</td><td>$x'_i \leftarrow \tilde{F}(u'_i)$ for all $i \in [1; g]$;</td></tr><tr><td>6</td><td>Return $(x'_1, \dots, x'_g, y'_1, \dots, y'_g)$ and $(u'_1, \dots, u'_g, v'_1, \dots, v'_g)$;</td></tr></tbody></table>
Let $(P_1, \dots, P_g)$ be a basis of the kernel of $F_1$, and $(x'_1, \dots, x'_g, y'_1, \dots, y'_g)$ a symplectic basis of $A[4d']$ with respect to $\zeta$, a primitive $4d'$-root of unity, and such that $P_i = 4c_1x'_i$.

Let $(Q_1, \dots, Q_g)$ be a basis of the kernel of $\tilde{F}_2$, and $(u'_1, \dots, u'_g, v'_1, \dots, v'_g)$ a symplectic basis of $B[4d']$ with respect to $\zeta$, such that $Q_i = 4c_2v'_i$.

Then the induced theta structure on $C$ induced by $F_1$ and $\tilde{F}_2$ via Theorem 56 is the same if

$$ \tilde{F}_2(c_2v'_i) = F_1(d'y'_i) \text{ and } F_1(c_1x'_i) = \tilde{F}_2(d'u'_i) \qquad (5) $$

*Proof.* The symplectic theta structure on $C$ induced by $F_1$ is given by $(F_1(c_1x'_i), F_1(d'y'_i))$, and the one induced by $\tilde{F}_2$ is given by $(\tilde{F}_2(d'u'_i), \tilde{F}_2(c_2v'_i))$. $\square$

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

We note that in the isogeny algorithm for $F_1$ we only need the points $c_1x'_i, d'y'_i$ and for $\tilde{F}_2$ we only need the points $d'u'_i, c_2v'_i$.

**Corollary 58.** Let $F = F_2 \circ F_1$. To get the same theta structure on $C$, it suffices to choose $x'_i, y'_i, u'_i, v'_i$ such that $F(c_2y'_i) = c_2v'_i$ and $\tilde{F}(c_1u'_i) = c_1x'_i$.

An algorithm to construct suitable $x'_i, y'_i, u'_i, v'_i$ is as follows. Take $y''_i$ a basis of a symplectic complement of $\text{Ker } F_1$ in $A[d_1], y'_i \in A[d']$ isotropic such that $4c_1y'_i = y''_i$, and let $v'_i = F(y'_i)$. Then $Q_i = 4c_2v'_i$ is a basis of $\text{Ker } \tilde{F}_2$. We let $u'_i$ be a symplectic complement of $v'_i$ in $B[d']$, and we let $x'_i = \tilde{F}(u'_i)$. Let $P_i = 4c_1x'_i$, they form a basis of $\text{Ker } F_1$.

Corollary 58 explain why we need $f \ge e_2 + 2$ in Remark 4.2 when $\ell = 2$ (an alternative if we are only given the action of $\sigma$ on $E_1[\ell^{e_2}]$ would be to just guess it on $E_1[\ell^{e_2+2}]$).

<table><caption>**Algorithm 20:** Finding two compatible basis.</caption>
  <tbody>
    <tr>
      <td>**Data:** ker($\tilde{F}_1$), ker($\tilde{F}_2$), an algorithm to evaluate $F = F_1 \circ F_2$ on $A[d']$ and an algorithm to evaluate $\tilde{F}$ on $B[d']$.</td>
    </tr>
    <tr>
      <td>**Result:** Two symplectic basis $(x'_1, \dots, x'_g, y'_1, \dots, y'_g)$ of $A[4d']$ and $(u'_1, \dots, u'_g, v'_1, \dots, v'_g)$ of $B[4d']$ such that $\text{ker}(F_1) = \langle 4c_1x'_i \rangle_i$, $\text{ker}(\tilde{F}_2) = \langle 4c_2v'_i \rangle_i$, $F(c_2y'_i) = c_2v'_i$ and $\tilde{F}(c_1u'_i) = c_1x'_i$ for all $i \in [1; g]$.</td>
    </tr>
    <tr>
      <td>1 Find $(y''_1, \dots, y''_g)$ a basis of a symplectic complement of $\text{Ker}(F_1)$ in $A[d_1]$;</td>
    </tr>
    <tr>
      <td>2 Find $(y'_1, \dots, y'_g)$ forming an isotropic subgroup of $A[d']$ such that $4c_1y'_i = y''_i$ for all $i \in [1; g]$;</td>
    </tr>
    <tr>
      <td>3 $v'_i \leftarrow \tilde{F}(y'_i)$ for all $i \in [1; g]$;</td>
    </tr>
    <tr>
      <td>4 Let $(u'_1, \dots, u'_g)$ be a symplectic complement of the $v'_i$ in $B[d']$;</td>
    </tr>
    <tr>
      <td>5 $x'_i \leftarrow \tilde{F}(u'_i)$ for all $i \in [1; g]$;</td>
    </tr>
    <tr>
      <td>6 Return $(x'_1, \dots, x'_g, y'_1, \dots, y'_g)$ and $(u'_1, \dots, u'_g, v'_1, \dots, v'_g)$;</td>
    </tr>
  </tbody>
</table>
## F.4 Computing 2$^e$-isogenies

We need to compute an $N$-isogeny, with $N = d_1$ or $N = d_2$ with the notations from Appendix F.3. The isogeny algorithms described in [CR15; LR23] assume that the degree is prime to 2 for simplicity. For SQIsignHD, we want to take $\ell = 2$ (so that $N = 2^e$) for efficiency. The general case of $N$ even is described in [Rob10; Rob21]. In this section we focus on the case $N = 2^e$ and detail how the general algorithm can be used to compute 2-isogenies. Handling 2-isogenies is actually easier because we can use the duplication formulae directly.

With the notations of Theorem 56, we assume that we are given the $4N$-torsion points $(x'_1, \dots, x'_g)$ given in theta coordinates by the symmetric theta structure of level 2 induced by a symplectic basis $(x_1, \dots, x_g, y_1, \dots, y_g)$ of $A[4]$ with $x_j = Nx'_j$. Let $P_j = 4x'_j$, $K$ the subgroup generated by the $P_j$, $F: A \to B = A/K$ the corresponding isogeny.

We then write $N = 2N'$, and let $T_j = N'P_j$, the kernel of a 2-isogeny $f$ through which $F$ factorizes. We remark also that $T_j'' = N'x'_j$ is a point of 8-torsion such that $x_j = 2T_j''$. We will explain how to compute the isogenous theta null point of the codomain of $f$, and how to push points through $f$. The points $f(x'_j)$ will then be points of $4N'$ torsion, and we iterate.

So from now on we let $f$ be a 2-isogeny $A \to B$, $K = \langle T_1, \dots, T_g \rangle$ be the kernel of $f$, $(T_1'', \dots, T_g'')$ be points in $A[8]$ such that $T_j = 4T_j''$, $j = 1, \dots, g$. We assume that the symmetric theta structure $\Theta_A$ on $A$ is induced by a symplectic basis $(T_1', \dots, T_g', U_1', \dots, U_g')$ where $T_j' = 2T_j''$ and that we are given the coordinates of the $T_j''$, $j \in \{1, \dots, g\}$. If $i \in (\mathbb{Z}/2\mathbb{Z})^g$, we let $T_i'' = \sum_{j=1}^g i_j T_j''$. For simplicity, we will even assume that we are given the theta coordinates of all $T_i''$, $i \in (\mathbb{Z}/2\mathbb{Z})^g$, in particular the points $T_i$, $i \in (\mathbb{Z}/2\mathbb{Z})^g$ span the full kernel $K$.

The 2-isogeny formula will be derived from the duplication formula [Igu72, Theorem 2 p. 139, p. 141]:

$$ \theta \begin{bmatrix} a_1 \\ b_1 \end{bmatrix} (z_1, \Omega) \theta \begin{bmatrix} a_2 \\ b_2 \end{bmatrix} (z_2, \Omega) = \sum_{t \in \frac{1}{2}\mathbb{Z}^g/\mathbb{Z}^g} \theta \begin{bmatrix} \frac{a_1+a_2}{2} + t \\ b_1 + b_2 \end{bmatrix} (z_1 + z_2, 2\Omega) \cdot \theta \begin{bmatrix} \frac{a_1-a_2}{2} + t \\ b_1 - b_2 \end{bmatrix} (z_1 - z_2, 2\Omega) \quad (6) $$

$$ 2^g \theta \begin{bmatrix} a_1 \\ b_1 \end{bmatrix} (z_1, \Omega) \theta \begin{bmatrix} a_2 \\ b_2 \end{bmatrix} (z_2, \Omega) = \sum_{t \in \frac{1}{2}\mathbb{Z}^g/\mathbb{Z}^g} e^{-2\pi i(a_1|2t)} \theta \begin{bmatrix} \frac{a_1+a_2}{2} + t \\ \frac{b_1+b_2}{2} \end{bmatrix} \left(\frac{z_1+z_2}{2}, \frac{\Omega}{2}\right) \cdot \theta \begin{bmatrix} \frac{a_1-a_2}{2} + t \\ \frac{b_1-b_2}{2} \end{bmatrix} \left(\frac{z_1-z_2}{2}, \frac{\Omega}{2}\right). \quad (7) $$

We will derive algebraic formula for the analytic isogeny $\phi: A = \mathbb{C}^g/(\Omega_A \mathbb{Z}^g + \mathbb{Z}^g) \to B = \mathbb{C}^g/(\Omega_B \mathbb{Z}^g + \mathbb{Z}^g)$, $z \mapsto 2z$ where $\Omega_B = 2\Omega_A$. We will then explain how to use these formula to compute our algebraic isogeny $f$.

Recall from Appendix F.2 that the Hadamard matrix $H$ allows to convert from the theta coordinates $\theta_i^A$ to the dual theta coordinates $\theta_i^{A'}$. Given two points $P_1, P_2$ given by theta coordinates $\theta_i(P_j)$, we also let $(\theta_i(P_1)) \star (\theta_i(P_2)) = (\theta_i(P_1) \cdot \theta_i(P_2))_{i \in (\mathbb{Z}/2\mathbb{Z})^g}$.
## F.4 Computing 2$^e$-isogenies

We need to compute an $N$-isogeny, with $N = d_1$ or $N = d_2$ with the notations from Appendix F.3. The isogeny algorithms described in [CR15; LR23] assume that the degree is prime to 2 for simplicity. For SQIsignHD, we want to take $\ell = 2$ (so that $N = 2^e$) for efficiency. The general case of $N$ even is described in [Rob10; Rob21]. In this section we focus on the case $N = 2^e$ and detail how the general algorithm can be used to compute 2-isogenies. Handling 2-isogenies is actually easier because we can use the duplication formulae directly.

With the notations of Theorem 56, we assume that we are given the $4N$-torsion points $(x'_1, \dots, x'_g)$ given in theta coordinates by the symmetric theta structure of level 2 induced by a symplectic basis $(x_1, \dots, x_g, y_1, \dots, y_g)$ of $A[4]$ with $x_j = Nx'_j$. Let $P_j = 4x'_j$, $K$ the subgroup generated by the $P_j$, $F: A \to B = A/K$ the corresponding isogeny.

We then write $N = 2N'$, and let $T_j = N'P_j$, the kernel of a 2-isogeny $f$ through which $F$ factorizes. We remark also that $T_j'' = N'x'_j$ is a point of 8-torsion such that $x_j = 2T_j''$. We will explain how to compute the isogenous theta null point of the codomain of $f$, and how to push points through $f$. The points $f(x'_j)$ will then be points of $4N'$ torsion, and we iterate.

So from now on we let $f$ be a 2-isogeny $A \to B$, $K = \langle T_1, \dots, T_g \rangle$ be the kernel of $f$, $(T_1'', \dots, T_g'')$ be points in $A[8]$ such that $T_j = 4T_j''$, $j = 1, \dots, g$. We assume that the symmetric theta structure $\Theta_A$ on $A$ is induced by a symplectic basis $(T_1', \dots, T_g', U_1', \dots, U_g')$ where $T_j' = 2T_j''$ and that we are given the coordinates of the $T_j''$, $j \in \{1, \dots, g\}$. If $i \in (\mathbb{Z}/2\mathbb{Z})^g$, we let $T_i'' = \sum_{j=1}^g i_j T_j''$. For simplicity, we will even assume that we are given the theta coordinates of all $T_i''$, $i \in (\mathbb{Z}/2\mathbb{Z})^g$, in particular the points $T_i$, $i \in (\mathbb{Z}/2\mathbb{Z})^g$ span the full kernel $K$.

The 2-isogeny formula will be derived from the duplication formula [Igu72, Theorem 2 p. 139, p. 141]:

$$ \theta \begin{bmatrix} a_1 \\ b_1 \end{bmatrix} (z_1, \Omega) \theta \begin{bmatrix} a_2 \\ b_2 \end{bmatrix} (z_2, \Omega) = \sum_{t \in \frac{1}{2}\mathbb{Z}^g/\mathbb{Z}^g} \theta \begin{bmatrix} \frac{a_1+a_2}{2} + t \\ b_1 + b_2 \end{bmatrix} (z_1 + z_2, 2\Omega) \cdot \theta \begin{bmatrix} \frac{a_1-a_2}{2} + t \\ b_1 - b_2 \end{bmatrix} (z_1 - z_2, 2\Omega) \quad (6) $$

$$ 2^g \theta \begin{bmatrix} a_1 \\ b_1 \end{bmatrix} (z_1, \Omega) \theta \begin{bmatrix} a_2 \\ b_2 \end{bmatrix} (z_2, \Omega) = \sum_{t \in \frac{1}{2}\mathbb{Z}^g/\mathbb{Z}^g} e^{-2\pi i(a_1|2t)} \theta \begin{bmatrix} \frac{a_1+a_2}{2} + t \\ \frac{b_1+b_2}{2} \end{bmatrix} \left( \frac{z_1+z_2}{2}, \frac{\Omega}{2} \right) \cdot \theta \begin{bmatrix} \frac{a_1-a_2}{2} + t \\ \frac{b_1-b_2}{2} \end{bmatrix} \left( \frac{z_1-z_2}{2}, \frac{\Omega}{2} \right). \quad (7) $$

We will derive algebraic formula for the analytic isogeny $\phi: A = \mathbb{C}^g/(\Omega_A \mathbb{Z}^g + \mathbb{Z}^g) \to B = \mathbb{C}^g/(\Omega_B \mathbb{Z}^g + \mathbb{Z}^g)$, $z \mapsto 2z$ where $\Omega_B = 2\Omega_A$. We will then explain how to use these formula to compute our algebraic isogeny $f$.

Recall from Appendix F.2 that the Hadamard matrix $H$ allows to convert from the theta coordinates $\theta_i^A$ to the dual theta coordinates $\theta_i^{A'}$. Given two points $P_1, P_2$ given by theta coordinates $\theta_i(P_j)$, we also let $(\theta_i(P_1)) \star (\theta_i(P_2)) = (\theta_i(P_1) \cdot \theta_i(P_2))_{i \in (\mathbb{Z}/2\mathbb{Z})^g}$.
**Proposition 59.** Let $P$ be a point on $A$. Then the theta coordinates of the points $\phi(P) \in B$, where $\phi: A \to B$ is the isogeny defined above, are given by:

$$ (\theta_i^B(\phi(P))) \star (\theta_i^B(0))_{i \in (\mathbb{Z}/2\mathbb{Z})^g} = H \cdot ((\theta'_\chi^A(P))_{\chi \in (\hat{\mathbb{Z}}/2\hat{\mathbb{Z}})^g} \star (\theta'_\chi^A(P))_{\chi \in (\hat{\mathbb{Z}}/2\hat{\mathbb{Z}})^g}). $$

*Proof.* Using the duplication formula, we obtain (with $\Omega = \Omega_A$):

$$ \theta^{[0]}_i(2z, \Omega)\theta^{[0]}_i(0, \Omega) = \sum_{t \in \frac{1}{2}\mathbb{Z}^g/\mathbb{Z}^g} \theta^{[t]}_{2i}(2z, 2\Omega)\theta^{[t]}_0(2z, 2\Omega) $$

This means that $(\theta_i^B(\phi(P))\theta_i^B(0))_{i \in (\mathbb{Z}/2\mathbb{Z})^g} = H \cdot (\theta'_\chi^A(P))^2_{\chi \in (\hat{\mathbb{Z}}/2\hat{\mathbb{Z}})^g}$. $\square$

So the image of a point $P$ by a 2-isogeny $\phi$ is simple to compute, provided we know the theta null point $\theta_i^B(0) = \theta^{[0]}_{i/2}(0, 2\Omega)$ of $B$: start with the theta coordinates $\theta_i^A(P)$ of $P$, apply the Hadamard transform to get the dual coordinates $\theta'_\chi(P)$, square these coordinates, and apply the Hadamard transform again to obtain $\theta_i^B(\phi(P))\theta_i^B(0)$. It now only remains to divide by the coordinates $\theta_i^B(0)$ given by the theta null point of $B$.

**Corollary 60.** Assume that we are given the theta coordinates $\theta_i^A(P)$ of $P \in A$ and of the theta null point $\theta_i^B(0)$ of $B$. After a precomputation of $2^g$ inversions to invert the coordinates of the theta null point of $B$, the theta coordinates of $\phi(P)$ can be computed in $2$ Hadamard transforms, $2^g$ squares and $2^g$ multiplications.

Furthermore, given the theta null points of $A$ and $B$ one can check (up to signs) that $A$ and $B$ are indeed 2-isogenous (with compatible theta structure) using $2^{g+1}$ squares and $2$ Hadamard transforms.

*Proof.* The first statement follows from the Proposition. For the second statement, if $A$ and $B$ are 2-isogenous, then $\theta_i^B(0)^2 = H \cdot \theta'_\chi^A(0)^2$, which determines the $\theta_i^B(0)$ up to a sign. $\square$

In particular the proof of Corollary 60 shows that we can easily compute the square of the coordinates of the theta null point of $B$. In practice in our complexity estimates, we will often neglect the Hadamard transforms since they just amount to some additions and subtractions. It remains to compute the correct square roots.

**Proposition 61.** Let $i \in \mathbb{Z}^g$ and $z'_i \in \mathbb{C}^g$ be the analytic theta point given by the affine coordinates $\theta'_i(z'_i) = \theta^{[0]}_{i/4+t/2}(0, \Omega_A/2)$. Then $T'_i = \pi_A(z'_i)$ is a point in $A[4]$. The points $T_i = 2T'_i$ generate the kernel corresponding to the kernel $\frac{1}{2}\mathbb{Z}^g/\mathbb{Z}^g$ of the isogeny $\phi$.

We have up to a constant (not depending on $i$):

$$ \theta_i^B(0) = \sum_t \theta_t^A(z'_i)^2. \qquad (8) $$
**Proposition 59.** Let $P$ be a point on $A$. Then the theta coordinates of the points $\phi(P) \in B$, where $\phi: A \to B$ is the isogeny defined above, are given by:

$$ (\theta_i^B(\phi(P))) \star (\theta_i^B(0))_{i \in (\mathbb{Z}/2\mathbb{Z})^g} = H \cdot ((\theta'_\chi^A(P))_{\chi \in (\hat{\mathbb{Z}}/2\hat{\mathbb{Z}})^g} \star (\theta'_\chi^A(P))_{\chi \in (\hat{\mathbb{Z}}/2\hat{\mathbb{Z}})^g}). $$

*Proof.* Using the duplication formula, we obtain (with $\Omega = \Omega_A$):

$$ \theta[0]_i(2z, \Omega)\theta[0]_i(0, \Omega) = \sum_{t \in \frac{1}{2}\mathbb{Z}^g/\mathbb{Z}^g} \theta[\frac{t}{2i}](2z, 2\Omega)\theta[\frac{t}{0}](2z, 2\Omega) $$

This means that $(\theta_i^B(\phi(P))\theta_i^B(0))_{i \in (\mathbb{Z}/2\mathbb{Z})^g} = H \cdot (\theta'_\chi^A(P))^2_{\chi \in (\hat{\mathbb{Z}}/2\hat{\mathbb{Z}})^g}$. $\square$

So the image of a point $P$ by a 2-isogeny $\phi$ is simple to compute, provided we know the theta null point $\theta_i^B(0) = \theta[0]_{i/2}](0, 2\Omega)$ of $B$: start with the theta coordinates $\theta_i^A(P)$ of $P$, apply the Hadamard transform to get the dual coordinates $\theta'_\chi(P)$, square these coordinates, and apply the Hadamard transform again to obtain $\theta_i^B(\phi(P))\theta_i^B(0)$. It now only remains to divide by the coordinates $\theta_i^B(0)$ given by the theta null point of $B$.

**Corollary 60.** Assume that we are given the theta coordinates $\theta_i^A(P)$ of $P \in A$ and of the theta null point $\theta_i^B(0)$ of $B$. After a precomputation of $2^g$ inversions to invert the coordinates of the theta null point of $B$, the theta coordinates of $\phi(P)$ can be computed in $2$ Hadamard transforms, $2^g$ squares and $2^g$ multiplications.

Furthermore, given the theta null points of $A$ and $B$ one can check (up to signs) that $A$ and $B$ are indeed 2-isogenous (with compatible theta structure) using $2^{g+1}$ squares and $2$ Hadamard transforms.

*Proof.* The first statement follows from the Proposition. For the second statement, if $A$ and $B$ are 2-isogenous, then $\theta_i^B(0)^2 = H \cdot \theta'_\chi^A(0)^2$, which determines the $\theta_i^B(0)$ up to a sign. $\square$

In particular the proof of Corollary 60 shows that we can easily compute the square of the coordinates of the theta null point of $B$. In practice in our complexity estimates, we will often neglect the Hadamard transforms since they just amount to some additions and subtractions. It remains to compute the correct square roots.

**Proposition 61.** Let $i \in \mathbb{Z}^g$ and $z'_i \in \mathbb{C}^g$ be the analytic theta point given by the affine coordinates $\theta'_i(z'_i) = \theta[0]_{i/4+t/2}](0, \Omega_A/2)$. Then $T'_i = \pi_A(z'_i)$ is a point in $A[4]$. The points $T_i = 2T'_i$ generate the kernel corresponding to the kernel $\frac{1}{2}\mathbb{Z}^g/\mathbb{Z}^g$ of the isogeny $\phi$.

We have up to a constant (not depending on $i$):

$$ \theta_i^B(0) = \sum_t \theta_t^A(z'_i)^2. \qquad (8) $$
Proof. Using the duplication formula again, we obtain for $i \in \mathbb{Z}^g$:

$$2^g \theta[\frac{0}{i/2}] (0, \Omega) \theta[\frac{0}{i}] (0, \Omega) = \sum_t \theta[\frac{0}{i/4+t/2}] (0, \Omega/2)^2.$$

Up to the projective factor $2^g \theta[\frac{0}{i}] (0, \Omega)$, we recover Eq. (8). We also check that although $z'_i$ depends on the choice of $i \in \mathbb{Z}^g$, the term on the left only depends on the reduction of $i$ in $(\mathbb{Z}/2\mathbb{Z})^g$. $\square$

In the analytic setting, when representing the points $z'_i$ and $T'_i$ by theta coordinates, they actually are represented by the same coordinates, but $z'_i$ is represented by affine coordinates while $T'_i$ is represented by projective coordinates. So the projection $\pi_A$ amount to sending the affine point $(\theta_i(z'_i)) \in \mathbb{A}^{2g}$ to the projective point in $\mathbb{P}^{2g-1}$.

We go back to the algebraic setting: we let $f: A \to B$ be a 2-isogeny with kernel generated by the points $(T_j)$, $j = 1, \dots, g$ and we assume that we are given isotropic points $T_j''$ such that $T_j = 4T_j''$, and the $T_j''$ are expressed as theta coordinates with respect to the theta structure induced by a symplectic basis $(T'_1, \dots, T'_g, U'_1, \dots, U'_g)$ where $T'_j = 2T_j''$. We need to compute the theta null point on $B$ for our algebraic isogeny $f$ like we did for our analytic isogeny $\phi$ above in Proposition 61. Then we can apply Proposition 59 to compute the image by $f$ of any point $P$.

Notice that Eq. (8), because of the sum, only makes sense for points in affine coordinates. So we cannot apply it directly in an algebraic algorithm, because we only have the 4-torsion points $T'_i$, $i \in (\mathbb{Z}/2\mathbb{Z})^g$ in projective coordinates. We need to lift the projective points $T'_i$ into an affine point $\tilde{T}'_i$ such that Eq. (8) make sense. We follow the terminology of [LR12, § 3] and speak about affine lifts. Riemann relations give a well defined doubling and differential addition law on affine lifts, hence a scalar multiplication.

Since we have the theta null point of level 2 on $A$, induced by the symplectic basis $(T'_1, \dots, T'_g, U'_1, \dots, U'_g)$ of $A$[4], the induced theta structure gives a canonical affine lift $\tilde{T}_i$ of the $T_i$, for all $i \in (\mathbb{Z}/2\mathbb{Z})^g$, and a canonical affine translation $\tilde{P} \mapsto \tilde{P} + \tilde{T}_i$ for all affine lifts $\tilde{P}$ of a point $P \in A$.

We take an arbitrary affine lift $\tilde{T}_i''$ of $T_i''$, which we then normalize via the equation

$$-3\tilde{T}_i'' = \tilde{T}_i'' + \tilde{T}_i, \qquad (9)$$

where the translation on the right is the canonical one induced by the theta structure. This rigidifies our choice of affine lift up to a root of unity $\mu$ of order $3^2 - 1^2 = 8$. Then $2\tilde{T}_i''$ is rigidified up to the action of $\mu^{2^2} = \pm 1$, and so if we let $\tilde{T}_i' = 2\tilde{T}_i''$, its coordinates are fully determined up to a sign. We can now apply Eq. (8), with $z'_i = \tilde{T}_i'$:

$$\theta_i^B(0) = \sum_{t \in (\mathbb{Z}/2\mathbb{Z})^g} \theta_t^A(\tilde{T}_i')^2 = \sum_{t \in (\mathbb{Z}/2\mathbb{Z})^g} \theta_t^A(2\tilde{T}_i'')^2. \qquad (10)$$

Because this equation only involves the squares of the coordinates of $\tilde{T}_i'$, our remaining sign ambiguity does not matter.
Proof. Using the duplication formula again, we obtain for $i \in \mathbb{Z}^g$:

$$2^g \theta [_{i/2}^0] (0, \Omega) \theta [_{0}^0] (0, \Omega) = \sum_t \theta [_{i/4+t/2}^0] (0, \Omega/2)^2.$$

Up to the projective factor $2^g \theta [_{0}^0] (0, \Omega)$, we recover Eq. (8). We also check that although $z'_i$ depends on the choice of $i \in \mathbb{Z}^g$, the term on the left only depends on the reduction of $i$ in $(\mathbb{Z}/2\mathbb{Z})^g$. $\square$

In the analytic setting, when representing the points $z'_i$ and $T'_i$ by theta coordinates, they actually are represented by the same coordinates, but $z'_i$ is represented by affine coordinates while $T'_i$ is represented by projective coordinates. So the projection $\pi_A$ amount to sending the affine point $(\theta_i(z'_i)) \in \mathbb{A}^{2g}$ to the projective point in $\mathbb{P}^{2g-1}$.

We go back to the algebraic setting: we let $f: A \to B$ be a 2-isogeny with kernel generated by the points $(T_j)$, $j = 1, \dots, g$ and we assume that we are given isotropic points $T_j''$ such that $T_j = 4T_j''$, and the $T_j''$ are expressed as theta coordinates with respect to the theta structure induced by a symplectic basis $(T'_1, \dots, T'_g, U'_1, \dots, U'_g)$ where $T'_j = 2T_j''$. We need to compute the theta null point on $B$ for our algebraic isogeny $f$ like we did for our analytic isogeny $\phi$ above in Proposition 61. Then we can apply Proposition 59 to compute the image by $f$ of any point $P$.

Notice that Eq. (8), because of the sum, only makes sense for points in affine coordinates. So we cannot apply it directly in an algebraic algorithm, because we only have the 4-torsion points $T'_i$, $i \in (\mathbb{Z}/2\mathbb{Z})^g$ in projective coordinates. We need to lift the projective points $T'_i$ into an affine point $\tilde{T}'_i$ such that Eq. (8) make sense. We follow the terminology of [LR12, § 3] and speak about affine lifts. Riemann relations give a well defined doubling and differential addition law on affine lifts, hence a scalar multiplication.

Since we have the theta null point of level 2 on $A$, induced by the symplectic basis $(T'_1, \dots, T'_g, U'_1, \dots, U'_g)$ of $A$[4], the induced theta structure gives a canonical affine lift $\tilde{T}_i$ of the $T_i$, for all $i \in (\mathbb{Z}/2\mathbb{Z})^g$, and a canonical affine translation $\tilde{P} \mapsto \tilde{P} + \tilde{T}_i$ for all affine lifts $\tilde{P}$ of a point $P \in A$.

We take an arbitrary affine lift $\tilde{T}_i''$ of $T_i''$, which we then normalize via the equation

$$-3\tilde{T}_i'' = \tilde{T}_i'' + \tilde{T}_i, \qquad (9)$$

where the translation on the right is the canonical one induced by the theta structure. This rigidifies our choice of affine lift up to a root of unity $\mu$ of order $3^2 - 1^2 = 8$. Then $2\tilde{T}_i''$ is rigidified up to the action of $\mu^{2^2} = \pm 1$, and so if we let $\tilde{T}_i' = 2\tilde{T}_i''$, its coordinates are fully determined up to a sign. We can now apply Eq. (8), with $z'_i = \tilde{T}_i'$:

$$\theta_i^B(0) = \sum_{t \in (\mathbb{Z}/2\mathbb{Z})^g} \theta_t^A(\tilde{T}_i')^2 = \sum_{t \in (\mathbb{Z}/2\mathbb{Z})^g} \theta_t^A(2\tilde{T}_i'')^2. \qquad (10)$$

Because this equation only involves the squares of the coordinates of $\tilde{T}_i'$, our remaining sign ambiguity does not matter.
**Remark 62.** If we only had the points $T'_i$ but not the $T''_i$, we could rigidify the choice of $\tilde{T}'_i$ via the equation $2\tilde{T}'_i = \tilde{T}_i$. This equation rigidifies the lift up to a root of unity $\mu$ of order $2^2 = 4$, so it remains a sign ambiguity in Eq. (10). However it is enough to do this rigidification for $i$ going through $e_1, \dots, e_g, e_1+e_2, \dots, e_j + e_k, \dots, e_{g-1} + e_g$ where $e_j$ is a a basis of $(\mathbb{Z}/2\mathbb{Z})^g$. The remaining choices of $\tilde{T}'_i$ are then fully determined from the Riemann relations, in particular from three way additions and differential additions. Thus we only have $g(g+1)/2$ signs ambiguity rather than $2^g$, and one can prove that all signs are actually valid [Rob10, Proposition 6.3.5]: they each correspond from a different choice of a 4-symplectic basis above our fixed 2-symplectic basis ($f(T'_j), f(U_j)$).

Nevertheless, when computing an $2^e$-isogeny, we need to be careful that this choice of 4-symplectic basis is compatible with our next kernel. Also in the end for the equality testing of Appendix F.3, we need to be sure to have chosen the correct theta structure. That's why we have to assume that we are given the $T''_i$, not only the $T'_i$, this allows us to fully rigidify the theta structure on B.

**Proposition 63.** Let $T''_j$, $j = 1, \dots, g$ be points of 8-torsion on A which generates an isotropic subgroup. Let $K$ be the kernel generate by the $4T''_j$. Assume that we are given the theta coordinates of the $T''_j$ via the theta structure induced by a symplectic basis $(2T'_j, U'_j)$. Let $(\theta_i^B(0))_{i \in (\mathbb{Z}/2\mathbb{Z})^g}$ be the projective theta null point of $B = A/K$ given by Theorem 56.

Then if $i \in (\mathbb{Z}/2\mathbb{Z})^g$, the value $\theta_i^B(0)$ (up to a constant which does not depend on $i$) can be computed using Eq. (10) where $\tilde{T}''_i$ is an affine lift of $T_i$ normalised using Eq. (9). This requires tripling an affine lift of $T''_i = \sum_{j=1}^g i_j T''_j$, a division and multiplication, and $2^g$ squares. If the tripling is computed via a doubling followed by a differential addition, it can be done in $2^{g+2}$ multiplications, $2^{g+1}$ doubling, and $2^g$ divisions.

The total cost to compute the theta null point of $B$ is then $(2^g - 1)(2^{g+2} + 1)$ multiplications, $2^g(2^{g+1} - 1)$ squares, $(2^g - 1)(2^g + 1)$ divisions, and $2^{g+1}$ inversions, that is $2^g(7 \cdot 2^g - 2) - 2$ arithmetic operations.

*Proof.* We use Eq. (10) to compute $\theta_i^B(0)$. We take an arbitrary lift $\tilde{T}''_i$ and compute $3\tilde{T}''_i$. We use Eq. (9) to compute the correct normalisation, this costs one division. We then plug in Eq. (10), this costs $2^g$ squares, and one multiplication by our normalisation factor.

But we remark that if $3\tilde{T}''_i$ is computed through a doubling $2\tilde{T}''_i$ followed by a differential addition $2\tilde{T}''_i + \tilde{T}''_i$, then the squares of the theta coordinates of $2\tilde{T}''_i$ are already computed.

The cost of the doubling and differential addition is described in [Rob10, Table 4.1]. The computation of $\theta_i^B(0)$ for $i \neq 0$ then costs $4 \cdot 2^g + 1$ multiplications, $2 \cdot 2^g$ squares and $2^g + 1$ divisions.

This costs assume the precomputation of some constants depending only on $A$ (more precisely its theta null point), which takes $2^g$ squares and $2^{g+1}$ inverses to compute once and for all. Taking this precomputation into account we get our final complexity. $\square$
**Remark 62.** If we only had the points $T'_i$ but not the $T''_i$, we could rigidify the choice of $\tilde{T}'_i$ via the equation $2\tilde{T}'_i = \tilde{T}_i$. This equation rigidifies the lift up to a root of unity $\mu$ of order $2^2 = 4$, so it remains a sign ambiguity in Eq. (10). However it is enough to do this rigidification for $i$ going through $e_1, \dots, e_g, e_1+e_2, \dots, e_j + e_k, \dots, e_{g-1} + e_g$ where $e_j$ is a a basis of $(\mathbb{Z}/2\mathbb{Z})^g$. The remaining choices of $\tilde{T}'_i$ are then fully determined from the Riemann relations, in particular from three way additions and differential additions. Thus we only have $g(g+1)/2$ signs ambiguity rather than $2^g$, and one can prove that all signs are actually valid [Rob10, Proposition 6.3.5]: they each correspond from a different choice of a 4-symplectic basis above our fixed 2-symplectic basis ($f(T'_j), f(U_j)$).

Nevertheless, when computing an $2^e$-isogeny, we need to be careful that this choice of 4-symplectic basis is compatible with our next kernel. Also in the end for the equality testing of Appendix F.3, we need to be sure to have chosen the correct theta structure. That's why we have to assume that we are given the $T''_i$, not only the $T'_i$, this allows us to fully rigidify the theta structure on B.

**Proposition 63.** Let $T''_j$, $j = 1, \dots, g$ be points of 8-torsion on A which generates an isotropic subgroup. Let $K$ be the kernel generate by the $4T''_j$. Assume that we are given the theta coordinates of the $T''_j$ via the theta structure induced by a symplectic basis ($2T'_j, U'_j$). Let $(\theta_i^B(0))_{i \in (\mathbb{Z}/2\mathbb{Z})^g}$ be the projective theta null point of $B = A/K$ given by Theorem 56.

Then if $i \in (\mathbb{Z}/2\mathbb{Z})^g$, the value $\theta_i^B(0)$ (up to a constant which does not depend on $i$) can be computed using Eq. (10) where $\tilde{T}''_i$ is an affine lift of $T_i$ normalised using Eq. (9). This requires tripling an affine lift of $T''_i = \sum_{j=1}^g i_j T''_j$, a division and multiplication, and $2^g$ squares. If the tripling is computed via a doubling followed by a differential addition, it can be done in $2^{g+2}$ multiplications, $2^{g+1}$ doubling, and $2^g$ divisions.

The total cost to compute the theta null point of $B$ is then $(2^g - 1)(2^{g+2} + 1)$ multiplications, $2^g(2^{g+1} - 1)$ squares, $(2^g - 1)(2^g + 1)$ divisions, and $2^{g+1}$ inversions, that is $2^g(7 \cdot 2^g - 2) - 2$ arithmetic operations.

*Proof.* We use Eq. (10) to compute $\theta_i^B(0)$. We take an arbitrary lift $\tilde{T}''_i$ and compute $3\tilde{T}''_i$. We use Eq. (9) to compute the correct normalisation, this costs one division. We then plug in Eq. (10), this costs $2^g$ squares, and one multiplication by our normalisation factor.

But we remark that if $3\tilde{T}''_i$ is computed through a doubling $2\tilde{T}''_i$ followed by a differential addition $2\tilde{T}''_i + \tilde{T}''_i$, then the squares of the theta coordinates of $2\tilde{T}''_i$ are already computed.

The cost of the doubling and differential addition is described in [Rob10, Table 4.1]. The computation of $\theta_i^B(0)$ for $i \neq 0$ then costs $4 \cdot 2^g + 1$ multiplications, $2 \cdot 2^g$ squares and $2^g + 1$ divisions.

This costs assume the precomputation of some constants depending only on $A$ (more precisely its theta null point), which takes $2^g$ squares and $2^{g+1}$ inverses to compute once and for all. Taking this precomputation into account we get our final complexity. $\square$
For computing $2^e$-isogenies decomposed as $e$ 2-isogenies, we start with $g$ points of $2^{e+2}$ torsions $x'_j$, and even with the $2^g$ points $x'_i$ for $i \in (\mathbb{Z}/2\mathbb{Z})^g$. We compute the $2^g$ points of each kernel using Fig. 2. For each 2-isogeny we need to apply Proposition 63 to compute the isogenous theta null point, and also apply Proposition 59 $2^g$ times to push the points through each isogeny, each image costing $2^{g+1}$ arithmetic operations by Corollary 60.

In this section we only described how the general isogeny formula adapt to the case $\ell = 2$, and omitted some specific optimisations available only for $2^n$-isogenies. Our implementation of the verification in dimension 4 use these further optimisations, which are described in [Rob23a]. Also to simplify the implementation of the verification, we require our response $\sigma$ to be of degree $q$ such that $\ell^e - q$ is a prime congruent to 5 modulo 8 (rather than just 1 modulo 4).

A profiling of the high level implementation of the FastSQIsignHD verification indicates that to compute a $2^{142}$-isogeny in dimension 4, costs around $2.7 \cdot 10^5$ multiplications, $1.3 \cdot 10^5$ squarings, 500 inversions and $6.5 \cdot 10^5$ additions. Using the estimates provided by [Lon23], this amounts to $70M$ CPU clock cycles. In comparison, the SQIsign NIST-I verification [The23b] costs $37M$ CPU clock cycles with the assembly optimizations of [Lon23]. Even though this is a rough estimate, such a comparison sounds promising for FastSQIsignHD: we expect a low level implementation of the current implementation to have a verification time roughly twice as slow as SQISign. Given that there are many optimisations we have yet to implement even in the high level version, we hope that we will be able to reach a similar verification time as in SQISign. Of course, only an actual implementation will give a concrete optimised verification time.

## F.5 A verification time vs compactness trade-off.

To speed up the verification time, the signer (or any verifier) can expand the compact signature by outputting all $e$ intermediates theta constants computed in the chain of $\ell$-isogenies computed during the verification. In dimension $g$, a theta constant over $\mathbb{F}_{p^2}$ takes $2^g \log(p^2)$ bits. The chain can be verified using Corollary 60.

When $g = 4$, $\lambda = 128$, $\ell = 2$, $e = 128$ and $p$ has 256 bits, storing each 128 theta constants then takes $128 \cdot 2^4 \cdot 512$ bits, that is 131kB. This is a much larger output than the $13/2\lambda \approx 832$ bits of the compressed signature, but by Corollary 60 the verification then takes only $e \cdot 2^{g+1} = 4096$ squares over $\mathbb{F}_{p^2}$ and $2e = 256$ Hadamard transforms (and a final linear change of variable to glue the theta structures at the end), so will be much faster than via the compact signature.

This allows for a verification time vs compactness trade-off. We remark that expanding the compact isogeny to allow for fast verification time can be done by anyone.
For computing $2^e$-isogenies decomposed as $e$ 2-isogenies, we start with $g$ points of $2^{e+2}$ torsions $x'_j$, and even with the $2^g$ points $x'_i$ for $i \in (\mathbb{Z}/2\mathbb{Z})^g$. We compute the $2^g$ points of each kernel using Fig. 2. For each 2-isogeny we need to apply Proposition 63 to compute the isogenous theta null point, and also apply Proposition 59 $2^g$ times to push the points through each isogeny, each image costing $2^{g+1}$ arithmetic operations by Corollary 60.

In this section we only described how the general isogeny formula adapt to the case $\ell = 2$, and omitted some specific optimisations available only for $2^n$-isogenies. Our implementation of the verification in dimension 4 use these further optimisations, which are described in [Rob23a]. Also to simplify the implementation of the verification, we require our response $\sigma$ to be of degree $q$ such that $\ell^e - q$ is a prime congruent to 5 modulo 8 (rather than just 1 modulo 4).

A profiling of the high level implementation of the FastSQIsignHD verification indicates that to compute a $2^{142}$-isogeny in dimension 4, costs around $2.7 \cdot 10^5$ multiplications, $1.3 \cdot 10^5$ squarings, 500 inversions and $6.5 \cdot 10^5$ additions. Using the estimates provided by [Lon23], this amounts to $70M$ CPU clock cycles. In comparison, the SQIsign NIST-I verification [The23b] costs $37M$ CPU clock cycles with the assembly optimizations of [Lon23]. Even though this is a rough estimate, such a comparison sounds promising for FastSQIsignHD: we expect a low level implementation of the current implementation to have a verification time roughly twice as slow as SQISign. Given that there are many optimisations we have yet to implement even in the high level version, we hope that we will be able to reach a similar verification time as in SQISign. Of course, only an actual implementation will give a concrete optimised verification time.

## F.5 A verification time vs compactness trade-off.

To speed up the verification time, the signer (or any verifier) can expand the compact signature by outputting all $e$ intermediates theta constants computed in the chain of $\ell$-isogenies computed during the verification. In dimension $g$, a theta constant over $\mathbb{F}_{p^2}$ takes $2^g \log(p^2)$ bits. The chain can be verified using Corollary 60.

When $g = 4$, $\lambda = 128$, $\ell = 2$, $e = 128$ and $p$ has 256 bits, storing each 128 theta constants then takes $128 \cdot 2^4 \cdot 512$ bits, that is 131kB. This is a much larger output than the $13/2\lambda \approx 832$ bits of the compressed signature, but by Corollary 60 the verification then takes only $e \cdot 2^{g+1} = 4096$ squares over $\mathbb{F}_{p^2}$ and $2e = 256$ Hadamard transforms (and a final linear change of variable to glue the theta structures at the end), so will be much faster than via the compact signature.

This allows for a verification time vs compactness trade-off. We remark that expanding the compact isogeny to allow for fast verification time can be done by anyone.