# [curves] Twist security and induced distributions

Steven Galbraith s.galbraith at math.auckland.ac.nz
Thu Nov 13 01:55:16 PST 2014

```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>
```