TABLE OF CONTENTS Another problem similar to factorization and widely used in cryptography is the discrete logarithm problem: in a multiplicative group G generated by some g, compute an integer x such that y = g x from y ? G. We summarize this by saying that we want to compute log g y in G. There are a few variants.
The order # G of the group can be available or not.
Since the logarithm is in unique modulo # G, we can ask for one possible logarithm if # G is not available.
The y elements may not necessarily be in G and in that case, the problem consists of distinguishing elements of G from other elements.
and so on.
Here are some formal problem specifications.
DLP (Discrete Logarithm Problem):
Parameters: a cyclic group G generated by an element g ? G
Input: an element y in G
Problem: compute the least integer x such that y = g x
DLKOP (Discrete Logarithm with Known Order Problem):
Parameters: a cyclic group G generated by an element g ? G, and the order # G
Input: an element y in G
Problem: compute x such that y = g x
Note that if the order of G is known, then computing the least discrete logarithm and computing...
