5.2 The Elliptic Curve Discrete Logarithm Problem In the multiplicative group Zp*, the discrete logarithm problem is: given elements p and q of the group, 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 P = kQ
	Example 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.
	Certicom is a trademark of the Certicom Corp. © Copyright Certicom Corp. 1997. All rights reserved. Comments or Questions about this site? Please contact info@certicom.ca