Example of
a difficult underlying problem:

Discrete Logarithm on (Z/pZ)*, p prime.

Discrete Logarithm on (Z/pZ)*, p prime.

Difficult because the values of gx are
very scattered (mod p) as x varies.

Very important that p-1 have a large prime
factor

(otherwise can use Chinese remainder
theorem to bootstrap from easier cases).

Methods exist which are much faster than
simply guessing. Some use the structure of **Z**.

Possibly harder for more abstract
incarnations of the same group.
Different representations *do
not necessarily* have equivalent DLOG problems.

Example: (**Z**/p**Z**)* is
abstractly isomorphic to **Z**/(p-1)**Z**.

DLOG is very easy on the cyclic groups **Z**/m**Z** :

can easily solve ax=b (mod m), if
a and m are relatively prime.

especially when the generator a is 1
(tautological).

Given p,
y, and a generator g of (Z/pZ)*, solve gx = y
for x.

(In other
words, explicitly invert the previous isomorphism.)