I'm looking to construct a set of elliptic curve parameters for the Tate pairing. I'm working with an elliptic curve over the field $F_{q^{12}}$ where $q$ is a prime number of magnitude around $~2^{256}$. The curve has an equation on the form:

$y^2 = x^3 + k$

I've also found a point $P$ of order $p$ when the curve is over $F_q$ (where $p$ is also a prime of magnitude around $2^{256}$, and where $p |(q^{12} - 1)$).

Now all that is left is to find another point $Q$ on this curve over the extension field $F_{q^{12}}$ (and which must be linearly independent from $P$). How do I do that? I found an explanation that I could use the algorithm:

1) Generate random point $R$ on the curve

2) Calculate $Z := (n/p) R$ where $n$ is the number of points on the curve

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

Now my question is: What is the running time of this algorithm in terms of iterations? I.e. what is the expected probability of success in step 3? I've tried let it run for hundreds of iterations and it still hasn't found a point; I keep getting $O$! Is there any other method I can use? Basically what I want is to find a member of the $p$-torsion group of the curve which has size exactly $p^2$ (by the way, I've verified that $p^2$ divides the number of points on the curve). However $p^2$ is an extremely small number compared to the order of the curve - $2^{512}$ vs $2^{3072}$, so the probability of a random point being in the torsion group is very small.


The correct answer was provided by Mike Scott:


The solution is to multiply by $n/(p^2)$ rather than $n/p$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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