In the multiplicative group Zp*, the discrete logarithm problem is: given elements r and q of the group, and a prime p, find a number k such that r = qk mod p. If the elliptic curve groups is described using multiplicative notation, then the elliptic curve discrete logarithm problem is: given points P and Q in the group, find a number that Pk = Q; k is called the discrete logarithm of Q to the base P. When the elliptic curve group is described using additive notation, the elliptic curve discrete logarithm problem is: given points P and Q in the group, find a number k such that Pk = Q
In the elliptic curve group defined by
y2 = x3 + 9x + 17 over F23,
What is the discrete logarithm k of Q = (4,5) to the base P = (16,5)?
One (naïve) way to find k is to compute multiples of P until Q is found. The first few multiples of P are:
P = (16,5) 2P = (20,20) 3P = (14,14) 4P = (19,20) 5P = (13,10) 6P = (7,3) 7P = (8,7) 8P = (12,17) 9P = (4,5)
Since 9P = (4,5) = Q, the discrete logarithm of Q to the base P is k = 9.
In a real application, k would be large enough such that it would be infeasible to determine k in this manner.