[comp.theory] Group Theory problem

ilan@Gang-of-Four.Stanford.EDU (Ilan Vardi) (11/18/89)

This problem is already intractable for k=1. Let G be the
multiplicative group of integers (mod p), p prime. Then G is known to
be a cyclic group. If g is a generator of G (primitive root), then for
a given a in G, finding x such that g^x = a (mod p) is called the
discrete logarithm problem. Finding x is hard, so that g^x is
considered a trap door function and is used for cryptography
(Diffie--Hellman).