[curves] Twist security and induced distributions

[David Gil]

On Thursday, November 13, 2014 1:56 AM, Steven Galbraith <s.galbraith at math.auckland.ac.nz> wrote:

> Let E : y^2 = x^3 + a*x + b be an elliptic curve and E' : Y^2 = X^3 + d^2*a*x + d^3*b be its quadratic twist.  The primality of E( F_q ) and E'( F_q ) are not independent events!!  Indeed, far from it.  

This is exactly what I was looking for! I had an initial argument that
    p(is_prime(|E(F_q)|) && is_prime(|E'(F_q)))
is closer to
    p(is_prime(|E(F_q)|))
than it is to
    p(is_prime(|E(F_q)|))*p(is_prime(|E'(F_q)|)
from a sort of symmetry argument; but that was pure hand-waving. 

> Some sort of vague explanation is given in the paper:
> S. D. Galbraith, J. F. McKee, The probability that the number of
points on an elliptic curve over a finite field is prime, Journal of
the London Mathematical Society, 62, no. 3, p. 671-684 (2000) 

This is terrific! Thank you for the reference. (Based on a quick scan through it, my hand-waving was entirely wrong...)

I'll run a numerical experiment or two this weekend: E.g., draw from the distribution of Tf and look for the probability of a prime "pair" for some of the primes currently being considered.

(And perhaps cross-check via point-counting that this also makes sense for Edwards curves with small cofactor drawn via the djb or NUMS methods.)


-dlg