Working with Cyclic Ideals

In SQISign, we are most interested in a subset of integral ideals called cyclic ideals. This terminology is not standard, as they are usually called primitive, however we use this name in the context of SQISign to highlight their connection to cyclic isogenies (i.e., isogenies with cyclic kernel). They are defined as follows.

Definition. Let $I$ be an integral left $\OO$-ideal for some order $\OO$. We say that $I$ is cyclic if, for all prime $\ell$, we have that $I \nsubseteq \ell\OO$.

As we only want to work with cyclic isogenies, we require all our ideals to be cyclic throughout our algorithms. Luckily, if we start with cyclic ideals, usually the output ideals after some operation will also be cyclic. For example, if we have cyclic ideals $I$ and $J$ of coprime norm, their product $IJ$ will also be cyclic. However, there are a few exceptions to this:

• When multiplying two ideals $I$, $J$ whose norm is not coprime, the ideal $IJ$ may not be cyclic.
• Given input ideal $I$, the output of the KLPT algorithm (implemented as EquivalentSmoothIdealHeuristic()) may not be a cyclic ideal.

Due to these exceptions, we need a method which given an integral ideal, returns a cyclic ideal.

Making ideals cyclic

To make an integral ideal $I$ cyclic, we have written the function make_cyclic():

def make_cyclic(I, full=False):
    """
    Given an ideal I, returns a cyclic ideal by dividing
    out the scalar factor g = ideal_basis_gcd(I)
    """
    # Compute I as a linear combination of its left order basis
    I_basis = I.basis_matrix()
    O_basis = I.left_order().unit_ideal().basis_matrix()
    M = I_basis * O_basis.inverse()

    # Compute the gcd of the gcd of the matrix rows 
    g = gcd((gcd(M_row) for M_row in M))

    # Ideal is already cyclic
    if g == 1:
        return I, g
    
    # Scale the basis by the gcd
    J = O.left_ideal([b / g for b in I.basis()])
    if full:
        return remove_2_endo(J)
    return J, g

This algorithm works as follows.

1. Given input integral ideal $I$, let $\OO$ be its left order.
2. Determine coefficients $x_1, \dots, x_4 \in \BB$ such that $I = x_1\beta_1 + \dots + x_4\beta_4$, where the $\beta_i$ form a basis of $\OO$.
3. Writing each $x_m$ as $a_m + b_mi + c_mj + d_mij$, let $g_m = \gcd(a_m, b_m, c_m, d_m)$.
4. Compute $g = \gcd(g_1, g_2, g_3, g_4)$.
5. If $g = 1$, then the ideal is cyclic, and we return $I$. Otherwise, letting $\alpha_1, \dots, \alpha_4$ be a basis for $I$, we return the left $\OO$-ideal generated by the $\alpha_1/g, \dots, \alpha_4/g$.

We can optionally pass in full = True into make_cyclic(). In our current implementation of SQISign we do not use this, but we will exploit this in future when implementing the new full variants described in the second SQISign paper.

Back to Top