[curves] Twist security and induced distributions
David Gil
dgil at yahoo-inc.com
Thu Nov 13 08:15:34 PST 2014
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
More information about the Curves
mailing list