3
$\begingroup$

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})$.

Improve this question
$\endgroup$
3
  • $\begingroup$ I'm voting to close this question as off-topic because it is about general mathematics. $\endgroup$
    – fkraiem
    Commented Oct 11, 2017 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
    Commented Oct 11, 2017 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
    Commented Oct 11, 2017 at 15:49

1 Answer 1

Reset to default
1
$\begingroup$

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$.

Improve this answer
$\endgroup$
2
  • $\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$
    – NNN
    Commented Oct 22, 2017 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
    Commented Oct 23, 2017 at 5:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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