Join Log in
Score:7
honzaik avatar Crypto

CSIDH - l ideal generators

cn flag
honzaik

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.

95
1 + 2
Sam Jaques avatar
us flag
Sam Jaques
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?
0
Reply
ne flag
Luca De Feo
@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}$.
0
Reply
Score:4
avatar Crypto
ne flag
Luca De Feo

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.

0 + 1
honzaik avatar
cn flag
honzaik
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?
0
Reply
ne flag
Luca De Feo
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.
1
Reply
ne flag
Luca De Feo
But your argument works too, by observing that conjugate ideals have the same norm.
1
Reply
ธงชาติไทย
Elon Musk
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.