|
Computing discrete logarithms on elliptic curves over finite fields
is considered to be a very difficult problem. The best algorithms
for general elliptic curves take exponential time, and do not take
much advantage of properties of the curve. Solving such problems
can thus be computationally infeasible for large curves. Indeed, elliptic
curves are becoming increasingly appealing for applications in
cryptography.
Although hard instances of the elliptic curve discrete logarithm
may be impossible to solve, Magma is able to efficiently solve
reasonable sized instances, or instances where the large prime factor
of the order of the base point is not too big. Magma does
this as follows:
The first step is to compute the factorisation of the order of the
base point, which may require calling SEA if the order of the curve is not
already known to Magma.
Then it checks that the order of the base point is a multiple of
the order of the other point.
If this is not true then there is no solution.
It next breaks the problem down to solving the discrete logarithm
modulo the prime power factors of the order using the Pohlig--Hellman
algorithm.
For very small primes it will try to solve this by exhaustive search.
If a solution does not exist then Magma might determine this during
the exhaustive search and abort the remaining computations.
For the larger prime power factors, Magma uses the parallel collision
search version of Pollard's rho algorithm.
The implementation includes Edlyn Teske's idea of r-adding walks
and Michael Wiener's and Robert Zuccherato's idea of treating
the point P the same as -P (for curves of the form
y2 = x3 + a x + b) so as to reduce the search space by a factor of
1/Sqrt(2) (this idea was independently discovered by other
researchers). It should be noted that Magma is not always able to
determine the nonexistence of a solution and therefore may run
forever if given very bad parameters.
For this reason, the user has the option of setting a time limit
on the calculation.
The discrete log of P to the base Q (an integer n satisfying
n * Q = P where 0 ≤n < Order(Q)).
The arguments Q and P must be points on the same elliptic curve,
which must be defined over a finite field.
The function returns -1 if it is determined that no solution exists.
The discrete log of P to the base Q (an integer n satisfying
n * Q = P where 0 ≤n < Order(Q)).
The arguments Q and P must be points on the same elliptic curve,
which must be defined over a finite field.
The argument t is a time limit in seconds on the calculation; if this
limit is exceeded then the calculation is aborted.
The time limit t must be a small positive integer.
This function returns -1 if it is determined that no solution exists;
if the calculation is aborted due to the time limit being exceeded then
-2 is returned.
In the example below we create a random elliptic curve over a
randomly chosen 40-bit prime field.
Our base point Q is chosen randomly on the curve, and
the other point P is selected as a random multiple of Q.
Using the Log function, we recover that multiplier (m)
and finally we verify that the solution is correct.
> K := GF(RandomPrime(40));
> E := EllipticCurve([Random(K), Random(K)]);
> E;
Elliptic Curve defined by y^2 = x^3 + 456271502613*x + 504334195864
over GF(742033232201)
> Q := Random(E);
> Q;
(174050269867 : 191768822966 : 1)
> FactoredOrder(Q);
[ <31, 1>, <7789, 1>, <3073121, 1> ]
> P := Random(Order(Q))*Q;
> P;
(495359429535 : 455525174166 : 1)
> m := Log(Q, P);
> m*Q - P;
(0 : 1 : 0)
[Next][Prev] [Right] [Left] [Up] [Index] [Root]
|