Calculation of the order of the cosets used in defining the Tate Pairing 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 &gt; 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 (&quot;why does $rE$ have order $h$&quot;) 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$.
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.&lt;z&gt; = 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.