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.
> 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)