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!
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.