1
$\begingroup$

I'm working through Pairings for Beginners by Craig Costello, and am trying to understand the preamble to the Tate pairing. (See p. 70 ff., section 5.2 of of the PDF.). I'm having trouble following a few arguments and would really like some help please.

The setting is curves of embedding degree $k > 1$, $r∥\#E(F_q)$ (where $∥$ means divides, but just once).

Since there are $r^2$ points in the the $r$-torsion subgroup $E(F_{q^k})[r]$ we usually have $r^2∥\#E(F_{q^k})$.

Ok so far.

Thus, let $h = \frac{\#E(F_{q^k})}{r^2}$ be the cofactor that sends points in $E(F_{q^k})$ to points in $E(F_{q^k})[r]$.

I don't follow this part. Presumably he's asserting that with this $h$, we can take any point $P ∈ E(F_{q^k})$, and we will get $hP ∈ E(F_{q^k})[r]$? I don't see how $hP$ would necessarily be a point of order $r$?

Let $rE(F_{q^k})$ be the coset of points in $E(F_{q^k})$ defined by $rE(F_{q^k}) = \{[r]P : P ∈ E(F_{q^k})\}$.

The number of elements in $rE(F_{q^k})$ is $h$

I don't see why the order of this 'coset' is $h$?

and it contains the point at infinity; from here we will simply denote this coset as $rE$. Following [Sco04], we can obtain another distinct coset of $E(F_{q^k})$ by adding a random element $R$ (not in $E[r]$) to each element of $rE$. In this way we can obtain precisely $r^2$ distinct, order $h$ cosets.

Without knowing the answer to my previous question ("why does $rE$ have order $h$") I can't yet accept this step. I believe it will follow from Lagrange's Theorem directly, if I can be convinced that the order of $rE$ is $h$.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

Try doing some examples. Sage (free and open source software) is very helpful here.

I think the simplest example is $E : y^2 = x^3 + 1$ over $\mathbf{F}_5$. This curve has embedding degree $k=2$.

sage: q = 5
sage: k = 2
sage: F.<z> = GF(5^2, modulus = x^2 + 2)
sage: E0 = EllipticCurve(GF(5), [0,1])
sage: E = EllipticCurve(F, [0,1])
sage: E0
Elliptic Curve defined by y^2 = x^3 + 1 over Finite Field of size 5
sage: E
Elliptic Curve defined by y^2 = x^3 + 1 over Finite Field in x of size 5^2
sage: E0.order()
6
sage: E.order()
36

Here $E_0$ denotes the curve over $\mathbf{F}_5$, and $E$ denotes the curve over $\mathbf{F}_{25}$. (Sage distinguishes between these two objects, so you need different symbols for them.) We can take $r=3$; note that $r$ divides the order of $E_0(\mathbf{F}_5)$ exactly once, so the requirements are satisfied.

Let's list the points in $E(\mathbf{F}_{25})$:

sage: E.points()
[(0 : 1 : 0), (0 : 1 : 1), (0 : 4 : 1), (1 : 2*z : 1), (1 : 3*z : 1), (2 : 2 : 1), (2 : 3 : 1), (3 : z : 1), (3 : 4*z : 1), (4 : 0 : 1), (z : 2*z + 2 : 1), (z : 3*z + 3 : 1), (z + 2 : 2*z : 1), (z + 2 : 3*z : 1), (z + 3 : 0 : 1), (2*z + 1 : z : 1), (2*z + 1 : 4*z : 1), (2*z + 2 : 2*z + 2 : 1), (2*z + 2 : 3*z + 3 : 1), (2*z + 3 : 2*z + 2 : 1), (2*z + 3 : 3*z + 3 : 1), (2*z + 4 : 2 : 1), (2*z + 4 : 3 : 1), (3*z + 1 : z : 1), (3*z + 1 : 4*z : 1), (3*z + 2 : 2*z + 3 : 1), (3*z + 2 : 3*z + 2 : 1), (3*z + 3 : 2*z + 3 : 1), (3*z + 3 : 3*z + 2 : 1), (3*z + 4 : 2 : 1), (3*z + 4 : 3 : 1), (4*z : 2*z + 3 : 1), (4*z : 3*z + 2 : 1), (4*z + 2 : 2*z : 1), (4*z + 2 : 3*z : 1), (4*z + 3 : 0 : 1)]

Let's find their orders:

sage: max([P.order() for P in E.points()])
6

This last computation indicates that the maximum order of any single point in $E(\mathbf{F}_{25})$ is 6, even though the order of $E(\mathbf{F}_{25})$ itself is 36. Hopefully you know enough group theory to understand how this is possible; if not, you should review your group theory.

Let's pick a point in $E(\mathbf{F}_{25})$ of order 6. By trial and error, I find:

sage: P = E(3,z)
sage: P
(3 : z : 1)
sage: P.order()
6

Let's multiply $P$ by $h$ and see what happens (note that I have to convert $h$ from a rational number to an integer in order to do the multiplication):

sage: r = 3
sage: h = Integer(E.order()/r^2)
sage: h
4
sage: h*P
(1 : 2*z : 1)
sage: (h*P).order()
3
sage: (h*P).order() == r
True

We see that the order of $hP$ equals $r$, as expected.

Let's compute the "coset" $rE(\mathbf{F}_{25})$. Note that we convert the list of points to a dictionary and back to a list to remove duplicates:

sage: list(dict.fromkeys([r*P for P in E.points()]))
[(4 : 0 : 1), (0 : 1 : 0), (z + 3 : 0 : 1), (4*z + 3 : 0 : 1)]

Note this coset contains the point at infinity $(0:1:0)$, as claimed. Of course, this coset has $h=4$ elements, as expected:

sage: len(list(dict.fromkeys([r*P for P in E.points()]))) == h
True

I haven't answered any of your theoretical questions in your post. This is very much intentional. If you understand enough examples, the theory is obvious. If you don't understand examples, then no amount of theory knowledge will help you. Do not focus overly on the theory. Please, work with lots and lots of examples. Understand those examples and understand them well. Then, if you still have questions, ask your questions using examples to illustrate your questions. There is no shortcut to enlightenment. You MUST work with examples.

Improve this answer
$\endgroup$
5
  • $\begingroup$ It's worth mentioning that another way to remove duplicates from a list in python (and things built from python, like sage) is via the set built-in type, which are used for unordered collections of distinct hashable types. The code set(r*P for P in E.points()) should have the same functionality that your code relying on dictionaries does, while being more "Pythonic". You can wrap that expression in list( ) if you care about the return type being a list vs a set. $\endgroup$
    – Mark
    Aug 31, 2019 at 6:34
  • $\begingroup$ Oh, thanks! Yeah I should have done that. Actually I like the command {r*P for P in E.points()} better and I think it does the same thing. $\endgroup$
    – djao
    Aug 31, 2019 at 15:11
  • $\begingroup$ Thanks very much for your generously detailed example. Seeing an example certainly does help, and your clear demonstration of Sage is really helpful - what's really nice is that it's given me a lot of tools to start playing with examples as you suggest (I've not used Sage before, but the syntax looks very intuitive). $\endgroup$
    – Michael Connor
    Sep 1, 2019 at 17:15
  • $\begingroup$ To settle my curiosity, I'm still hopeful for someone to be able to offer a theoretical justification for the author's assertions. Whilst examples help (and indeed your example and the author's examples are invaluable), I do still like to be persuaded by a theoretical argument - an example could be a one-off 'fluke' (although of course won't be in this case), whereas an algebraic argument covers off all cases, and gives me more confidence going forward. $\endgroup$
    – Michael Connor
    Sep 1, 2019 at 17:16
  • $\begingroup$ Theoretical justifications of course exist, but aren't really useful until and unless you've internalized the surrounding theory of elliptic curves. At a minimum, read up to Corollary III.6.4 in Silverman's "The Arithmetic of Elliptic Curves" which is necessary in order to justify the claims at hand. If you still have a specific question after understanding this Corollary, please ask the specific question. $\endgroup$
    – djao
    Sep 2, 2019 at 6:19

Your Answer

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

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