[curves] Twist security and induced distributions

Steve Thomas steve at tobtu.com
Thu Nov 13 15:50:43 PST 2014


This email got bounced because "5.7.9 Message not accepted for policy reasons.
See http://postmaster.yahoo.com/errors/postmaster-28.html". It might just be me
because I relay email to a yahoo address.

In case anyone missed David Gil's email:

> On November 13, 2014 at 10:15 AM David Gil <dgil at yahoo-inc.com> wrote:
>
>
> 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
> _______________________________________________
> Curves mailing list
> Curves at moderncrypto.org
> https://moderncrypto.org/mailman/listinfo/curves


More information about the Curves mailing list