4
$\begingroup$

What are examples of groups, where DLP (discrete logarithm problem) is hard?

Two obvious ones are: integers modulo $p$ ($p$ being prime) and elliptic curves over finite fields. What are the others?

  • 0
    Relevant: RSA Labs says "The best discrete logarithm algorithms [over finite fields] have expected running times similar to those of the best factoring algorithms." ([link](http://www.rsa.com/rsalabs/node.asp?id=2193))2011-09-11
  • 1
    As a point of clarification, you should distinguish between $\mathbb{Z}/p \mathbb{Z}$ and $(\mathbb{Z}/p \mathbb{Z})^ \times$. DLP is hard in the latter, and trivial in the former.2011-09-11
  • 3
    The difficulty of the discrete logarithm problem in a group is not a property of a group (that is, it is not invariant under isomorphism of groups); it is a property of a specific algorithm computing the group law using a specific algorithmic representation of the group's elements.2012-06-14

1 Answers 1