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: