# Generating bilinear pairing parameters - running time of finding member of p-torsion group

Update: Question completely rephrased.

I want to create the parameters for a bilinear pairing (the Tate pairing in this case).

In case you're interested I'm following this thesis, specifically the type $F$ curves (page 61) which has embedding degree $k = 12$. But it's probably not necessary to refer to the thesis to answer this question, since my question is likely elementary.

Using the method I've so far generated a finite field of size q where q is prime, an elliptic curve over $F_q, E(F_q)$, a prime of size $p$ so that $p | (q^{12} - 1)$ and a point $P$ on $E(F_q)$ of order $p$. Now the last step is to generate a point $Q$ which must also have order $p$ over the curve $E(F_{q^k})$ which must not be on $E(F_q)$. I've searched around and found the following suggested algorithm (where n is the number of points on $E(F_{q^k})$):

1) Generate a random point $R$ on $E(F_{q^k})$

2) Calculate $Z :=(n/p) R$

3) If $Z != O$, return $Z$ - otherwise, go to 1.

I.e. keep generating random points, scaling them by $(n/p)$ and repeating this until one gets a point different from the point-in-infinity, in which case the result should be a point of order $p$.

My question is - what is the running time of this algorithm? I.e. what is the per-iteration probability of getting $Z != O$ in step 3? I've tried to let it run but it doesn't find any points, it just keeps getting $O$ in step 2. Now, since calculation over $E(F_{q^k})$ are quite slow, I've only tried a few hundred iterations.

In this case $p$ and $q$ are primes of size 256 bits and $k = 12$. This means that $n$ is of the order of $2^{3072}$ (since n is the number of points on $E(F_{q^k})$). The p-torsion group has size $p^2$ meaning that such points are extremely rare and would be impossible to find by "random checking". But in this case, the algorithm doesn't operate by just generating a random point and checking if $p R$ is O. Rather, it generates a random point and multiplies by $(n/p)$. So it could be this increases the probability of finding a point.

But still, it seems to take forever! So it would be nice to know what the expected number of iterations is. Thanks!

-
Are you really looking for order $p$ points? Your Algorithm will give you points of order is divided by $p^s$ with $n = p^sm$. –  gmoktop Feb 3 at 22:22
gmoktop: Actually what I'm looking for is a point in the p-torsion group, i.e. a point that satisfies p*P = O so it must have either order p, or the order must be a divisor in p. But since p is prime, this should mean the point must have order p. I'm not sure I understand what you mean that the algorithm gives points of order is divided by p^s? What is this algorithm (the one in my post!) called and is there a reference where I could read more about it? I only saw it mentioned for use for this specific problem but I don't know how it works! –  Morty Feb 4 at 6:21
sorry i thought you return $R$ in step 3. However, see my answer for clarification. –  gmoktop Feb 4 at 8:47

Given the number of points #E on the curve over the base field $p$, then the number of points (np) over the k-th extension is given by the iteration (due to Weil)

trace=p+1-#E;
t[0]=2;
t[1]=trace;
for (int i=1;i<k;i++)
t[i+1]=trace*t[i] - p*t[i-1];

np= pow(p,k)+1-t[k];

-
Thanks just the answer I was looking for :-) I already know the number of points on the curve over the base field so it is easy to calculate the number of points over the extended field. –  Morty Feb 5 at 14:19

In your step 2 replace $p$ by $p^2$. That should do it.

But you should really be looking for points Q on the sextic twist. See the original Barreto-Naehrig paper.

-
Yes, replacing p by p^2 immediately solved the problem (it found a point on the first iteration). Yes I read I can use twist curves but wanted to keep it as simple as possible in the beginning. By the way can you recommend a way to calculate the number of points on the curve (over the q^12 field)? Right now I use Sage and it's very fast but I need to implement my own point counting. I was wondering if this type of curve, due to its construction, has characteristics that makes it easier than in the general case? –  Morty Feb 4 at 20:45

a point in a $p$-torsion group doesn't have necessarily order $p$. It is of order $p^s$ for some $s \geq 1$.

If you know that the $p$-torsion of your (abelian) group has $p^2$ elements. It is either the cyclic group of order $p^2$ or the product of two copies of the cyclic group of order $p$. In the latter case it has $p-1$ points of order $p$ and $p^2-p$ points of order $p^2$, in the former all points but $O$ are of order $p$.

Now consider your algorithm: Say $p^2$ divides $n$, but $p^3$ does not, i.e. $n = p^2m$.

Lets assume you pick a point $R$ with order $p$. You will get $\frac{n}{p}R=pmR=O$. So in step 3, you will discard $R$. The same holds for all points $R$ with an order which divides $pm$. However assume $R$ has order $p^2$ (or $p^2$ divides the order), then $Z := \frac{n}{p} R\neq O$. You know $Z$ has order $p$ as desired. But it may be that you will never find a point which order is divided by $p^2$.

You can extend the algorithm to:

1. Choose $R$ at random
2. Calculate $Z = pR$
3. If $Z = O$ return $R$
4. Calculate $Z = \frac{n}{p} R$
5. If $Z \neq O$ return $Z$
-
Thanks, but does this algorithm perform (much) better than the original? Because it seems improbable to get a success in step 1-3 (probability ~2^512 / 2^3072)? And steps 4-5 are the original. –  Morty Feb 4 at 20:48
Well, my point is that the unmodified algorithm never terminates if there are no points of order $p^2$. And this may happen. –  gmoktop Feb 4 at 21:56
gmoktop: Thanks! –  Morty Feb 5 at 14:18