Path: utzoo!attcan!uunet!mailrus!cornell!uw-beaver!Teknowledge.COM!polya!Gang-of-Four.Stanford.EDU!ilan
From: ilan@Gang-of-Four.Stanford.EDU (Ilan Vardi)
Newsgroups: comp.theory
Subject: Re: Group Theory problem
Message-ID: <12848@polya.Stanford.EDU>
Date: 17 Nov 89 16:45:26 GMT
Sender: news@polya.Stanford.EDU
Reply-To: ilan@Gang-of-Four.Stanford.EDU (Ilan Vardi)
Organization: Computer Science Department, Stanford University
Lines: 9



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).