[curves] Twist security and induced distributions

[Steven Galbraith]

Interesting question.

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.

Look at this magma run:

 > p := NextPrime( Random(500)); for X := 1 to 20 do print IsPrime( p + 
1 + X), "  ", IsPrime( p + 1 - X ); end for;
false    true
false    false
false    false
false    false
true    true
false    false
false    true
false    false
false    false
false    false
true    true
false    false
true    false
false    false
false    false
false    false
false    true
false    false
true    true
false    false

Try it yourself.  Use sage if you prefer.   Be amazed at the magic of 
mathematics.

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)

pdf is on my webpage.

This does not fully answer your question.  But somehow the answer should 
vaguely be that the distribution for "nearly prime order of E" and 
"nearly prime order of both E and its twist" are not so different.

   Steven



On 13/11/14 06:22, David Leon Gil wrote:
> Question:
>
> What is the distribution induced on the trace of Frobenius by choosing 
> a curve such that its twist has nearly prime order?
>
> (I.e., is it any different from the distribution induced by choosing a 
> curve parameter at random, which -- as I understand it -- is the 
> Sato-Tate distribution?)
>
>
> _______________________________________________
> Curves mailing list
> Curves at moderncrypto.org
> https://moderncrypto.org/mailman/listinfo/curves

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://moderncrypto.org/mail-archive/curves/attachments/20141113/1137f850/attachment.html>