Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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) –  anon Sep 11 '11 at 11:12
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. –  Brandon Carter Sep 11 '11 at 15:54
1  
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. –  Qiaochu Yuan Jun 14 '12 at 9:35
add comment

1 Answer 1

As you probably already know, you can take discrete logarithms for any cyclic group. However as you can see on the linked wiki page, no algorithm is known for computing general discrete logarithms.

However some other popular choices of groups that are used for discrete logarithm are the algebraic torus over finite fields and the divisor class group of a curve over a finite field.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.