Subroutines when Computing Isogenies from Ideals

At a high level, the purpose of the algorithm IdealToIsogenyFromKLPT() is to compute the isogeny corresponding to a given ideal (via the Deuring Correspondence). We discuss how it is implemented in more depth in Computing Isogenies From Ideals.

In this blogpost, however, we discuss the two main subroutines in IdealToIsogenyFromKLPT():

1. IdealToIsogenyCoprime() to translate and evaluate $T$-isogenies (where $T$ is coprime to $\ell$)
2. IdealToIsogenySmallFromKLPT() to translate ${\ell }^f$-isogenies using the output of IdealToIsogenyCoprime().

Corresponding isogeny of ideal with coprime norm

We first describe IdealToIsogenyCoprime(), which takes as input two equivalent left ${\mathcal{O}}_0$-ideals $J,K$ where $J$ has norm dividing $T^2$ and $K$ has $\ell$-power norm, as well as the connecting isogeny corresponding to $K$, namely ${\phi }_K:E_0\to E_K$. The output is the isogeny ${\phi }_J:E_0\to E_J$ corresponding to $J$.

As the two ideals are equivalent, we expect the domains and codomains of ${\phi }_I$ and ${\phi }_J$ to be isomorphic. The importance of this function is to find isogenies with coprime degrees which is important for various pushforwards and pullbacks in the parent algorithms which call IdealToIsogenyCoprime().

The algorithm can be broken down into the following steps:

1. Consider the function: $${\chi }_I=I\frac{\overline{\alpha }}{n(I)},\alpha \in I\mathrm{\setminus }\{0\},$$ as defined in Lemma 1 in the SQISign paper. For the first step, we need to find $\alpha$ such that ${\chi }_K(\alpha )=J$, which is achieved using the function chi_inverse().

2. We compute two ideals $$H_1=J+{\mathcal{O}}_{0}T,\text{ and }{H}_2={\mathcal{O}}_0\alpha +{\mathcal{O}}_0\frac{n(J)}{n(H_1)}.$$ Ensure that the ideals are cyclic and that their norm divides $T$.

3. Compute the isogenies whose kernels correspond to the $H_i$, say ${\phi }_i:E_0\to E_i=E_0/⟨H_i⟩$.

4. Compute an isogeny $$\psi :E_K\to E_{\psi }=E_K/⟨{\phi }_K(\ker ({\phi }_2))⟩,$$ i.e., $\psi =[{\phi }_K{]}_{\star }{\phi }_2$ is the pushforward of ${\phi }_2$ through ${\phi }_K$. The codomain of $E_{\psi }$ should be isomorphic to $E_1$, but may not be equal. To fix this we use techniques described in Correct up to Isomorphism.

5. Compute the dual isogeny $\hat{\psi }$. Throughout, we can ensure the computation of the dual isogenies is efficient by exploiting the fact we already know the kernel of $\psi$. For an isogeny of degree $D$, we find $\ker (\hat{\psi })=\psi (R)$ for some point $R\in E[D]$ linearly independent to $\ker (\psi )$. By the previous step, the codomain of ${\phi }_1$ and the domain of $\hat{\psi }$ should be the same.

6. Return $${\phi }_J=\hat{\psi }\circ {\phi }_1:E_0\to E_1\to E_K\cong E_J=E_0/⟨J⟩.$$

Corresponding isogeny of ideal with norm ${\ell }^{2f_{\text{step}}+\mathrm{\Delta }}$

Next, we describe the subroutine IdealToIsogenySmallFromKLPT() in more detail. This algorithm takes the following input: left ${\mathcal{O}}_0$-ideals $I$ and $J$ of norm dividing $T^2{\ell }^{2f_{\text{step}}+\mathrm{\Delta }}$ and $T^2$ (respectively), an ideal $K\sim J$ of $\ell$-power norm, and the isogenies ${\phi }_J$, ${\phi }_K$ from $E_0$ to $E_1$ corresponding to $J$, $K$ respectively. It will output:

• $\phi :E_1\to E_2$ of degree ${\ell }^{2f_{\text{step}}+\mathrm{\Delta }}$, such that ${\phi }_I=\phi \circ {\phi }_J$,
• $L\sim I$ of norm dividing $T^2$
• The corresponding isogeny ${\phi }_L:E_0\to E_2$.

Following the diagram above, we compute $\phi :E_1\to E_2$ and ${\phi }_L:E_0\to E_2$ as:

• $\phi ={\psi }_1^{\prime }\circ {\rho }_2\circ \eta \circ {\psi }_1\circ {\phi }_1$.
• ${\phi }_L={\psi }_1^{\prime }\circ {\psi }_2$

We will do this as follows:

1. Compute ${\phi }_1:E_1\to E_3$: we first compute the kernel corresponding to $I_1=I+{\mathcal{O}}_0{\ell }^{\text{step}}$ of norm dividing ${\ell }^{\text{step}}$. Let $P$ be the generator of this kernel. As $I_1$ is a left ${\mathcal{O}}_0$-ideal, $P\in E_0$. As ${\phi }_1$ has domain $E_1$, we map $P$ to $E_1$ using ${\phi }_J:E_0\to E_1$. Then, ${\phi }_1:E_1\to E_1/⟨{\phi }_J(P)⟩.$

2. Compute ideal $L$: we now use KLPT to compute the ideal $L$ equivalent to $I$ with norm dividing $T^2$ by running EquivalentSmoothIdealHeuristic().

3. Compute $\gamma$: we compute $\alpha$ such that ${\chi }_K(\alpha )=J$, and $\beta$ such that ${\chi }_I(\beta )=L$ using chi_inverse(). Set $$\gamma =\frac{\beta \alpha }{n(J)}.$$ Be careful: when $n(K)=1$, chi_inverse() will return $\pm i$. This means that when we compute kernels from $\gamma$, it may be twisted by the automorphism $\iota$. To avoid this, we manually set $\alpha =1$.

4. Compute ${\psi }_1$: as the domain of ${\psi }_1$ is not $E_0$, we need to instead consider a related ideal with left order ${\mathcal{O}}_0$. The ideal we consider is $$H_1={\mathcal{O}}_0\gamma +{\mathcal{O}}_0(n(K){\ell }^{f_{\text{step}}}T),$$ which will correspond to the isogeny $${\phi }_{H_1}={\psi }_1\circ {\phi }_1\circ {\phi }_K:E_0\to E_5$$ of degree $n(K)l^{f_{\text{step}}}T$. Note that the $\ell$-power part of $H_1$ corresponds entirely to ${\phi }_1\circ {\phi }_K$ as $\mathrm{deg}({\phi }_1)={\ell }^{f_{\text{step}}}$ and $\mathrm{deg}({\phi }_K)=n(K)$. Therefore, we only need to compute the part of $H_1$ coprime to $\ell$, namely $H_1^{\prime }={\mathcal{O}}_0\gamma +{\mathcal{O}}_{0}T$. From this, which we obtain ${\psi }_1$ by running ideal_to_kernel() on $H_1^{\prime }$ to obtain kernel generator $P$. As $H_1^{\prime }$ has left order ${\mathcal{O}}_0$, $P\in E_0$. Therefore, the kernel of ${\psi }_1$ is generated by ${\phi }_1({\phi }_K(P))\in E_3$.

5. Compute ${\psi }_2$ and ${\hat{\rho }}_2$: we now consider the ideal $$H_2={\mathcal{O}}_0\overline{\gamma }+{\mathcal{O}}_0\frac{n(\gamma )}{n(H_1)}{\ell }^{-\mathrm{\Delta }}.$$ Then, $H_2$ has left order ${\mathcal{O}}_0$ and will correspond to the isogeny ${\phi }_{H_2}:E_0\to E_6$ of degree dividing ${\ell }^{f_{\text{step}}}T$. How can this be used to compute ${\psi }_2$ and ${\hat{\rho }}_2$?

   • This isogeny can be decomposed as ${\hat{\rho }}_2\circ {\psi }_2:E_0\to E_{\psi }\to E_6$ where ${\hat{\rho }}_2$ is of degree dividing ${\ell }^{f_{\text{step}}}$ and ${\psi }_2$ is of degree dividing $T$.
   • Compute $\ker ({\phi }_{H_2})$ by running ideal_to_kernel() on $H_2$.
   • Then, $\ker ({\psi }_2)$ is the subgroup of order (dividing) $T$ within $\ker ({\phi }_{H_2})$, i.e., $\ker ({\psi }_2)=l^h\cdot \ker ({\phi }_{H_2}),$ where $h$ is the $\ell$-valuation of $n(H_2)$. From this kernel we obtain ${\psi }_2:E_0\to E_{\psi }$.
   • Similarly, we compute the subgroup of $\ker ({\phi }_{H_2})$ of order ${\ell }^{f_{\text{step}}}$ and push it through ${\psi }_2$ to obtain $\ker ({\hat{\rho }}_2)$, and therefore ${\hat{\rho }}_2$.

6. Meet-in-the-middle step to find $\eta$: we now brute force the isogeny $\eta :E_5\to E_6$ of (small) degree $\mathrm{\Delta }$ by using meet-in-the-middle. For more details on this, see the page Meet in the Middle Isogenies.

Recall that the desired output of this function is: $\phi :E_1\to E_2$ such that ${\phi }_I=\phi \circ {\phi }_J$, an ideal $L\sim I$ and the corresponding isogeny ${\phi }_L$. We now have all the pieces we need, but to output everything correctly, we will need to perform some pushforwards and pullbacks.

To compute $\phi$, we exploit the fact that we know ${\phi }_1:E_1\to E_3$, and $\phi ={\phi }_2\circ \theta \circ {\phi }_1$. For the other outputs, we have already computed $L$ in Step 2, and the corresponding isogeny is given by ${\psi }_1^{\prime }\circ {\psi }_2:E_0\to E_2$, for which we computed ${\psi }_2$ in Step 5. We are left to compute ${\psi }_1^{\prime }$ and ${\phi }_2\circ \theta$.

7. Compute ${\psi }_1^{\prime }$: from the diagram we can see that $$\ker ({\psi }_1^{\prime })={\rho }_2(\eta (\ker ({\hat{\psi }}_1))),$$ so once we compute the dual of ${\psi }_1$, we can compute $\ker ({\psi }_1^{\prime })$, and therefore ${\psi }_1^{\prime }$.

8. Compute ${\phi }_2\circ \theta$: ideally, we would compute the kernel of ${\phi }_2\circ \theta$ by observing that it is equal to ${\hat{\psi }}_1(\ker ({\rho }_2\circ \eta ))$. However, we do not actually know the kernel of ${\rho }_2\circ \eta$, so we work around this by computing ${\lambda }_1$ and ${\lambda }_3$ as ${\phi }_2\circ \theta ={\lambda }_3\circ {\lambda }_1$. We do this, using the diagram above, as follows:

   • We first compute $\ker ({\lambda }_1)={\hat{\psi }}_1(\ker (\eta ))$ and from this we get ${\lambda }_1:E_3\to E_{\lambda }$.
   • To compute ${\lambda }_3$, we first need ${\lambda }_2$, whose kernel is given by $\eta (\ker ({\hat{\psi }}_1))$. Then, by pre-composing with an isomorphism if necessary to make its codomain $E_{\lambda }$, we obtain ${\lambda }_2:E_6\to E_{\lambda }$.
   • Finally, we compute the kernel of ${\lambda }_3$ as ${\lambda }_2(\ker ({\rho }_2))$ to obtain the isogeny ${\lambda }_3:E_{\lambda }\to E_2$.

We can now output $\phi$, $L$, and ${\phi }_L$ as required.

Edge cases

Small step size

When the step size is small enough, i.e., smaller than $f_{\text{step}}$, we can avoid going through the entire procedure above as the isogeny we wish to compute has degree dividing the available torsion, and we can skip many of the tricks used above and simply directly compute the kernel from the ideal. Concretely, we simply do the following:

1. Set ${\phi }_J$ and ${\phi }_K$ to have the same codomain as above.
2. Derive ${\phi }_1$ as above.
3. Find $L$, an ideal equivalent to $I$ with norm dividing $T^2$.

We then return ${\phi }_1$ and $L$. This will only happen when IdealToIsogenySmallFromKLPT() is called as the last step of the parent IdealToIsogenyFromKLPT().

Backtracking: when $\gamma$ has non-trivial GCD

There is a caveat with the procedure depicted above. Before computing $H_i$ in IdealToIsogenySmallFromKLPT() the coefficients of $\gamma$ (when written as a linear combination of the basis elements of ${\mathcal{O}}_0$) may have non-trivial GCD, which causes the isogenies to backtrack and the algorithm to fail. One solution is to regenerate $L$ and $\gamma$ until the coefficients of $\gamma$ have trivial GCD. However, we can relax the condition by fixing this backtracking when the GCD is a power of $\ell$. We detail this procedure below.

Let ${\alpha }_1,\dots ,{\alpha }_4$ be a basis of ${\mathcal{O}}_0$, and write $\gamma =c_1{\alpha }_1+\cdots +c_4{\alpha }_4$. Let $g=gcd(c_1,\dots ,c_4)$. If $g\ne {\ell }^{\times }$, we regenerate $L$ and $\gamma$. Otherwise, let us say $g={\ell }^d$. We replace $\gamma$ with $\gamma /g$. Note that now will have $g\cdot \gamma \in K$, $g\cdot \overline{\gamma }\in L$, and $$n(\gamma )=\frac{n(I)n(L)n(K)}{g^{2}n(J)}.$$ The ideals $H_1,H_2$ are computed in the same way, but in the meet-in-the-middle step we now expect to find an isogeny of degree ${\ell }^{\mathrm{\Delta }+d}$ between $E_5$ and $E_6$.

Back to Top