I'm working through Pairings for Beginners by Craig Costello, and am trying to understand the Tate pairing.

He defines $rE = \{r*P | P \in E(\mathbb{F}_{q^k})\}$ and then forms the quotient group $E(\mathbb{F}_{q^k})/rE$. He then claims:

if $r^2 || \#E(\mathbb{F}_{q^k})$, then $E[r] \cap rE = \{\mathcal{O}\}$.

where $\cdot||\cdot$ means divides, but just once, and $E[r]$ is the r-torsion.

My question

Why is this true? I definitely agree that $\mathcal{O}$ is in this intersection, since $r[P] = \mathcal{O}$ for any $P$ in $E[r]$, but I don't see why this should be the only element in the intersection. Moreover, if there were some point $Q \neq \mathcal{O}$ in $E[r] \cap rE$, then $Q$ would have order $r^2$, which by Lagrange's Theorem, would be possible under the assumption that $r^2 || \#E(\mathbb{F}_{q^k})$.

  • $\begingroup$ I'm voting to close this question as off-topic because it is about general mathematics. $\endgroup$ – fkraiem Oct 11 '17 at 3:58
  • $\begingroup$ I will tell it again and again. There is no sharp boundary between mathematics and cryptography. Especially the text "Pairing for Beginners" is more targeted to cryptographers then to pure mathematicians, say in algebraic geometry. $\endgroup$ – user27950 Oct 11 '17 at 8:47
  • $\begingroup$ @fkraiem Since the cited book is clearly more of a cryptography-related thing, I have to disagree with your close-vote. $\endgroup$ – e-sushi Oct 11 '17 at 15:49

The group $E[r]$ is isomorphic to $\mathbb{Z}/r \mathbb{Z} \times \mathbb{Z}/r \mathbb{Z}$, which has $r^2$ elements, all of order $r$. Since your element $Q$ has order $r^2$, $E(\mathbb{F_{q^k}})$ has also a cyclic subgroup of order $r^2$. This group has $r (r-1)$ elements of order $r^2$ which cannot be elements from $E[r]$. This implies that $\#E(\mathbb{F_{q^k}})$ must be at least divisible by $r^3$.

  • $\begingroup$ Apologies for replying so late to this, but I fail to see: 1) How the group having $r(r-1)$ elements of order $r^2$ not from $E[r]$ implies that $\#E(\mathbb{F}_{q^k})$ must be divisible by $r^2$; and 2) Why this would even be a problem. The hypothesis is that $r^2 || \#E(\mathbb{F}_{q^k})$, which would not be violated. $\endgroup$ – Alex Oct 22 '17 at 21:08
  • $\begingroup$ This is proof by contraposition. If $E[r] \cap r E \neq \mathcal{O}$ then $\#E$ would be divisible by $r^k, k >2$ $\endgroup$ – user27950 Oct 23 '17 at 5:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.