PlanetMath (more info)
 Math for the people, by the people.
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
Owner confidence rating: Very high Entry average rating: No information on entry rating
elliptic curve discrete logarithm problem (Definition)

The elliptic curve discrete logarithm problem is the cornerstone of much of present-day elliptic curve cryptography. It relies on the natural group law on a non-singular elliptic curve which allows one to add points on the curve together. Given an elliptic curve $ E$ over a finite field $ F$, a point on that curve, $ P$, and another point you know to be an integer multiple of that point, $ Q$, the “problem” is to find the integer $ n$ such that $ nP=Q$.

The problem is computationally difficult unless the curve has a “bad” number of points over the given field, where the term “bad” encompasses various collections of numbers of points which make the elliptic curve discrete logarithm problem breakable. For example, if the number of points on $ E$ over $ F$ is the same as the number of elements of $ F$, then the curve is vulnerable to attack. It is because of these issues that point-counting on elliptic curves is such a hot topic in elliptic curve cryptography.

For an introduction to point-counting, reference Schoof's algorithm.



"elliptic curve discrete logarithm problem" is owned by mathcam.
(view preamble)

View style:

See Also: Diffie-Hellman key exchange, the arithmetic of elliptic curves

Other names:  elliptic curve discrete log problem
Log in to rate this entry.
(view current ratings)

Cross-references: algorithm, reference, collections, term, field, number, multiple, integer, finite field, curve, points, elliptic curve, non-singular, group, elliptic curve cryptography
There are 4 references to this entry.

This is version 4 of elliptic curve discrete logarithm problem, born on 2003-07-17, modified 2005-03-18.
Object id is 4471, canonical name is EllipticCurveDiscreteLogarithmProblem.
Accessed 6673 times total.

Classification:
AMS MSC94A60 (Information and communication, circuits :: Communication, information :: Cryptography)

Pending Errata and Addenda
None.
[ View all 3 ]
Discussion
Style: Expand: Order:
forum policy

No messages.

Interact
post | correct | update request | add derivation | add example | add (any)