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()
:
IdealToIsogenyCoprime()
to translate and evaluate -isogenies (where is coprime to )IdealToIsogenySmallFromKLPT()
to translate -isogenies using the output ofIdealToIsogenyCoprime()
.
Corresponding isogeny of ideal with coprime norm
We first describe IdealToIsogenyCoprime()
, which takes as input two equivalent left
As the two ideals are equivalent, we expect the domains and codomains of IdealToIsogenyCoprime()
.
The algorithm can be broken down into the following steps:
Consider the function:
as defined in Lemma 1 in the SQISign paper. For the first step, we need to find such that , which is achieved using the functionchi_inverse()
.We compute two ideals
Ensure that the ideals are cyclic and that their norm divides .Compute the isogenies whose kernels correspond to the
, say .Compute an isogeny
i.e., is the pushforward of through . The codomain of should be isomorphic to , but may not be equal. To fix this we use techniques described in Correct up to Isomorphism.Compute the dual isogeny
. Throughout, we can ensure the computation of the dual isogenies is efficient by exploiting the fact we already know the kernel of . For an isogeny of degree , we find for some point linearly independent to . By the previous step, the codomain of and the domain of should be the same.Return
Corresponding isogeny of ideal with norm
Next, we describe the subroutine IdealToIsogenySmallFromKLPT()
in more detail. This algorithm takes the following input: left
of degree , such that , of norm dividing- The corresponding isogeny
.

Figure 1: We compute
Following the diagram above, we compute
.
We will do this as follows:
Compute
: we first compute the kernel corresponding to of norm dividing . Let be the generator of this kernel. As is a left -ideal, . As has domain , we map to using . Then,Compute ideal
: we now use KLPT to compute the ideal equivalent to with norm dividing by runningEquivalentSmoothIdealHeuristic()
.Compute
: we compute such that , and such that usingchi_inverse()
. Set Be careful: when ,chi_inverse()
will return . This means that when we compute kernels from , it may be twisted by the automorphism . To avoid this, we manually set .Compute
: as the domain of is not , we need to instead consider a related ideal with left order . The ideal we consider is which will correspond to the isogeny of degree . Note that the -power part of corresponds entirely to as and . Therefore, we only need to compute the part of coprime to , namely . From this, which we obtain by runningideal_to_kernel()
on to obtain kernel generator . As has left order , . Therefore, the kernel of is generated by .Compute
and : we now consider the ideal Then, has left order and will correspond to the isogeny of degree dividing . How can this be used to compute and ?- This isogeny can be decomposed as
where is of degree dividing and is of degree dividing . - Compute
by runningideal_to_kernel()
on . - Then,
is the subgroup of order (dividing) within , i.e., where is the -valuation of . From this kernel we obtain . - Similarly, we compute the subgroup of
of order and push it through to obtain , and therefore .
- This isogeny can be decomposed as
Meet-in-the-middle step to find
: we now brute force the isogeny of (small) degree 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:
To compute

Figure 2: We compute
Compute
: from the diagram we can see that so once we compute the dual of , we can compute , and therefore .Compute
: ideally, we would compute the kernel of by observing that it is equal to . However, we do not actually know the kernel of , so we work around this by computing and as . We do this, using the diagram above, as follows:- We first compute
and from this we get . - To compute
, we first need , whose kernel is given by . Then, by pre-composing with an isomorphism if necessary to make its codomain , we obtain . - Finally, we compute the kernel of
as to obtain the isogeny .
- We first compute
We can now output
Edge cases
Small step size
When the step size is small enough, i.e., smaller than
- Set
and to have the same codomain as above. - Derive
as above. - Find
, an ideal equivalent to with norm dividing .
We then return IdealToIsogenySmallFromKLPT()
is called as the last step of the parent IdealToIsogenyFromKLPT()
.
Backtracking: when has non-trivial GCD
There is a caveat with the procedure depicted above. Before computing IdealToIsogenySmallFromKLPT()
the coefficients of
Let