Cryptography Reference
In-Depth Information
one is found that is prime. Because of the near uniform distribution of orders in
the Hasse interval, the probability that
|
(
F
p
)
|
is prime or has a prime factor of
minimum specified length should be close to the probability of a random integer in
the interval having this property. Although not much is proved about the occurrence
of primes in short intervals, it has been conjectured by Galbraith and McKee [82]
that the probability that a randomly chosen elliptic curve over
E
F
p
has prime order can
be approximated by
c
p
/
ln
p
as
p
→∞
, where
c
p
depends on
p
and lies between
0
62. Thus the probability of choosing a curve of prime order this way is
expected to be about one half the probability that a randomly chosen integer
x
of
thesamesizeas
p
turns out to be prime, which is asymptotic to 1
.
44 and 0
.
/
ln
x
by the PNT
(Theorem 6.2).
11.3.2 The Current State of the ECDLP
The rho method has a parallelized version which is more efficient because it yields
a factor
m
speedup when
m
processors are used. This is because all processors use
the same iterating function to compute the sequence of points and there is a strategy
that enables efficient finding of a collision in the sequences generated by different
processors (see, for example, [97] for details).
The parallelized version of the rho method holds the current record for an ECDLP.
We give an account of this record in the next example.
Example 11.20
Consider the following parameters, where
p112
is prime:
> a := 4451685225093714772084598273548424:
b := 2061118396808653202902996166388514:
p112 := (2ˆ128-3)/(11*6949):
isprime(p112);
true
and the elliptic curve defined by the equation
y
2
x
3
=
+
ax
+
b
over
F
p
112
:
> E112 := EllipticCurve(a, b, p112):
This curve was standardized as curve
secp112r1
in a standard issued in 2000
which is now obsolete (currently, the minimum recommended size of the prime
p
for elliptic curves defined over
F
p
is 192 bits). The order of the group of rational
points of this curve can be easily computed using, for example, Schoof's algorithm
and it turns out to be the following 112-bit prime:
> o112 := 4451685225093714776491891542548933:
isprime(o112);
true
Thus each point on the curve, with the sole exception of the point at infinity, is a
generator of the group. In particular the point:
> P := [188281465057972534892223778713752, 3419875491033170827167861896082688];
IsEllipticPoint(P, E112);
true
