Score:2

Why is the set of r-torsion points isomorphic to $\mathbb{Z}_r \times \mathbb{Z}_r$

fr flag

I'm reading "On the implementation of pairing-based cryptosystems".

It states that $E(\mathbb{F}_{k^q})[r]$ is isomorphic to the product of $\mathbb{Z}_r$ with itself. $E(\mathbb{F}_{k^q})[r]$ is the set of $r$-torsion points, which means all points, $P$ where $rP = O$ (I think).

Ok. Let's test this with $r = 2$. We know, the 4 solutions are: $\{O, (a_0, 0), (a_1, 0), (a_2, 0)\}$ where $a_n$ is the $n$-th root to the cubic $x^3 + ax + b = 0$.

But $\mathbb{Z}_2 \times \mathbb{Z}_2$ is $\{(0, 0), (0, 1), (1, 0), (1, 1)\}$.

I guess this is isomorphic since there are 4 elements in each set. But... I'm not sure how stating there is an isomorphism adds any value?

For example: We could instead just say $E(\mathbb{F}_{k^q})[r]$ has $r^2$ elements (which is the size of $\mathbb{Z}_r \times \mathbb{Z}_r$).

Score:1
gb flag

$E(\mathbb{F}_{k^q})[r]$ is the set of $r$-torsion points, which means all points, $P$ where $rP = O$ (I think).

Correct.

I guess this is isomorphic since there are 4 elements in each set. But... I'm not sure how stating there is an isomorphism adds any value?

For example: We could instead just say $E(\mathbb{F}_{k^q})[r]$ has $r^2$ elements (which is the size of $Z_r \times Z_r$).

Understanding this structure is quite important for a lot of applications in cryptography. For example, it is very fundamental in isogeny-based cryptography. The reason for this, is because as a product of two cyclic groups, it is generated by two (independent) points $P, Q$ of order $r$. That is, every point in the torsion can be written as $[a]P + [b]Q$ for some coefficients $a,b$. Compare this, say, to classical elliptic curve cryptography, where we work in a cyclic group and every point can be written as $[x]G$ for a single generator $G$. There are no points of order $r^2$ in $E(\mathbb{F}_{k^q})[r]$, even if the group itself has order $r^2$.

Because of this structure, there are $r+1$ subgroups of order $r$ in the torsion subgroup. This is important in isogeny-based cryptography because each of those subgroups form the kernel of a different isogeny from the curve $E$.

Studying the structure of the $p$-torsion subgroups when $p$ is the characteristic of the field (what it seems like you have called $k$ - I suspect you wrote $q$ and $k$ the wrong way around) also classifies elliptic curves into "ordinary" and "supersingular" curves.

For more information, see Silverman's "The Arithmetic of Elliptic Curves", section III, Corollary 6.4.

In pairing-based crytography, this structure is also extremely important. A good reference for more info in this area is Craig Costello's "Pairings for beginners". (See chapter 4 especially).

Foobar avatar
fr flag
Thanks for the explanation. I'm looking at Craig Costello's "Pairings for beginners" and he uses the symbol "|" a decent amount. For example: $r\, |\, 105$. Do you know what this means?
Morrolan avatar
ng flag
That will likely denote the "divides" relation. That is $x | y \Leftrightarrow y = kx, k \in \mathbb{Z}$.
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.