# CSIDH - l ideal generators

I am trying to study the CSIDH algorithm. I have some beginner background in elliptic curves and I have been following Andrew Sutherland's lectures (https://math.mit.edu/classes/18.783/2019/lectures.html) to understand the endomorphism rings and the class group action and how we can apply the theory over complex curves to curves over a finite field. My background in number theory is not that good so this may be just a simple problem.

In CSIDH (page 13) it's mentioned that we the principal ideal $$(l)\mathcal{O}$$ (where $$\mathcal{O}$$ is an order in an imaginary quadratic field) splits into two ideals $$\mathbb{l}$$ and $$\mathbb{\overline{l}}$$ as in $$(l)\mathcal{O}= \mathbb{l}\mathbb{\overline{l}}$$ where also $$\mathbb{l}, \mathbb{\overline{l}}$$ are generated by $$(l, \pi \pm 1)$$.

Using ideal multiplication I get $$\mathbb{l}\mathbb{\overline{l}} =(l, \pi + 1)(l, \pi -1) = (l^2, l(\pi -1), l(\pi +1), \pi^2-1)$$ i.e. an element $$\alpha \in \mathbb{l}\mathbb{\overline{l}}$$ should have the form $$\alpha = al^2+bl(\pi-1)+cl(\pi+1)+d(\pi^2-1), \{a,b,c,d\} \subseteq \mathcal{O}$$ How do I get that $$\alpha = xl$$ for some $$x \in \mathcal{O}$$? Is it just simple simplification and usage of the assumption that $$\pi^2= 1 \mod l$$ (i.e. the characteristic equation) somehow or is there a more complicated reason?

My other question is where do we get that $$\mathbb{l}$$, $$\mathbb{\overline{l}}$$ are generated by those elements?

Thank you in advance. Also pointing to some good resources would help as well. I have been searching throught the cited papers but it's hard to find the right source.

• I'll add a follow-up question: The imaginary quadratic field is isomorphic to $\mathbb{Q}[\sqrt{-p}]$; what is the ideal in $\mathcal{O}_{\mathbb{Q}[\sqrt{-p}]}$ that $\pi$ (the Frobenius endomorphism) is isomorphic to? Commented Sep 5, 2021 at 20:53
• @SamJaques In the question, $π$ is a square root of $-p$, not the Frobenius endomorphism. By complex multiplication Frobenius is identified to one of the two square roots of $-p$. The associated ideal is simply the principal ideal $π\mathcal{O}$. Commented Sep 6, 2021 at 11:00

To answer your first question: it's as simple as that. Restating what you wrote, it's enough to check that $$l$$ divides all the four generators: $$l^2$$, $$l(π-1)$$, $$l(π+1)$$ and $$π^2-1$$. It's obvious for the first three, and for the last one just recall that by definition $$π^2 = -p$$, and that CSIDH expliciticly forces $$l|(p+1)$$. This proves that $$(l) ⊃ (l,π-1)(l,π+1)$$. To prove the other inclusion, see below.
Your second question is essentially asking to prove that $$l,\bar{l}$$ are prime ideals. An easy way to do so is by computing their norms. The norm of $$(l,π-1)$$ is the gcd of the norms of its elements. The norm of $$l$$ is $$l^2$$, and the norm of $$π-1$$ is $$(π-1)(-π-1) = p+1$$ (multiply by the conjugate). By construction $$\gcd(l^2,p+1)=l$$, so $$(l,π-1)$$ has norm $$l$$. But $$l$$ is a prime, so $$(l,π-1)$$ must be a prime ideal.
To conclude, you already knew that $$l\bar{l}⊂(l)$$, but now you also know that the norms on the LHS and RHS are the same, so necessarily $$l\bar{l}=(l)$$, up to units.
• thank you so much. the only thing im not sure about is where does the "norm is the gcd of the norms of its elements" come from. ive searched a bit and I've only found a theorem that the norm of an ideal in $\mathcal{O_K}$ is the gcd of the norms of all elements (not just generators). is this just because of a special case due to the order or does this apply for any order? Another way could be to use $(l)|(l,\pi -1)(l,\pi +1) \implies N((l))|N((l,\pi -1))N((l,\pi +1))$ and since $N((l))=l^2$ then either both are of norm $l$ or one of them is of norm $1$ which would be a contradiction right? Commented Sep 9, 2021 at 16:53
• That the norm of an ideal is the gcd of the norm of its elements is one of the possible definitions of the norm of an ideal. The reason I just took the gcd of the norms of the generators in my computation is that $n | N(a)$ and $n | N(b)$ imply $n | N(a+b)$. Thus it is enough to find the common factors of the generators to know the common factors of all elements. Commented Sep 9, 2021 at 21:01