Cryptography Reference
In-Depth Information
F p is greater than both
the number of supersingular curves and the number of curves with trace 2 (these
primes are not very abundant). Find also the prime p
first prime such that the number of anomalous curves over
<
1000 for which the number
of anomalous curves is largest.
A consequence of Hasse's theorem which is important for some cryptographic
applications is that there is an efficient PPT algorithm to pick a point in E
( F p )
uniformly at random. The algorithm simply picks a random element x 0
∈ F
and
checks whether x 0 is the x -coordinate of a point in E
( F p )
. This can be accomplished
by computing the Legendre symbol x 0 + ax + b
p
which, as we have seen in Chap. 2
2
can be done in time O
by means of quadratic reciprocity. If the element
thus obtained is a quadratic residue then a square root can be computed by using,
e.g., Tonelli's Algorithm 2.8, in time O
(
len
(
p
)
)
4
. We choose one of the two square
roots y 0 and this gives a point on the curve, with coordinates
(
len
(
p
)
)
. Since for
each nonzero x -coordinate of a point there are two points on the curve and the
minimum nu mber of points is, by Hasse's theorem,
(
x 0 ,
y 0 )
2 p , we see that at least
>
p
2 p
1
F p are coordinates of points on the curve. Then, using
Proposition 2.2, we obtain that the number of expected trials in order to find an
x -coordinate of the curve is
2 (
p
)
elements of
O p 1 / 2 . Observe that this reasoning
2 p
=
2
+
2 p
p
p m
can also be applied to an elliptic curve over
F q where q
=
for some m
>
1 and,
also in this case, there exist PPT algorithms to extract square roots in
F q .Notealso
that the probability of picking a given point of order 2 (in case it exists) with this
algorithm is twice the probability of picking any other given point of order
2but
this is not a serious deviation from uniformity because there are at most three points
of order 2 and hence the probability of picking such a point is negligible in the size
of p .
The next Maple function chooses a pseudo-random point on an elliptic curve
given in the format output by EllipticCurve . The generator should be initial-
ized first with a call to RandomTools:-MersenneTwister:-SetState()
but we do not include this call inside the function because it could make the
procedure repeatedly choose the same point if many points are chosen in quick
succession:
=
> PseudoRandomEllipticPoint := proc(E::list(integer))
uses RandomTools:-MersenneTwister;
local a, b, p, ls, x, z, y, sign;
a := E[1];
b := E[2];
p := E[3];
ls := -1;
while ls = -1 do
x := GenerateInteger(':-range' = 0 .. p-1);
z := (xˆ3+a*x+b) mod p;
ls := numtheory:-legendre(z, p)
end do;
y := numtheory:-msqrt(z, p);
sign := 2*GenerateInteger('range' = 0 .. 1)-1;
y := sign*y mod p;
[x, y]
end proc:
 
Search WWH ::




Custom Search