# 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$. Feb 3, 2014 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! Feb 4, 2014 at 6:21
• sorry i thought you return $R$ in step 3. However, see my answer for clarification. Feb 4, 2014 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=2;
t=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. Feb 5, 2014 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? Feb 4, 2014 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. Feb 4, 2014 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. Feb 4, 2014 at 21:56