Let the DLP instance in Z∗18 be 7 ≡ 5^x(mod 18). Since n = 6 = 2 × 3, let p = 2, and q = 3. What are the elements generated by 5^2 modulo 18 and 5^3 modulo 18?
My answer is:
For 5^2 modulo 18:
(5^2) % 18 = 25 % 18 = 7
(5^4) % 18 = (7^2) % 18 = 49 % 18 = 13
(5^6) % 18 = (13^2) % 18 = 169 % 18 = 1
So, the elements generated by 5^2 modulo 18 are {7, 13, 1}.
For 5^3 modulo 18:
(5^3) % 18 = 125 % 18 = 11
(5^6) % 18 = (11^2) % 18 = 121 % 18 = 1
So, the elements generated by 5^3 modulo 18 are {11, 1}.
But I somehow feel I am understanding the question wrong :(
5² = 25 is congruent to 7 (mod 18) as
18|(25–7). As GCD(7, 18) = 1, [7] belongs to the group U(18) of reduced residue classes of integers modulo 18 under the operation of multiplication of residue classes of integers modulo 18.
U(18) = {[1], [5], [7], [11], [13], [17]}, which is
isomorphic to U(2)×U(3²) ~ U(3²) as
U(2) = {[1]}. Note that [r] denotes the residue class of the integer r modulo 18.
The cyclic subgroup of U(18) generated by [5]
is <[5]> = {[5], [5]²=[25]=[7], [5]³=[35]=[17], [5]⁴=
[85]=[13], [5]⁵=[65]=[11], [5]⁶=[55]=[1]} = U(18)
This U(18) is a cyclic group of order 6, with [5] as one of the generators. The other generators of U(18) are of the form [5]^t, where GCD(t, 6) = 1 ==> the set of all the generators of U(18) is {[5], [5]⁵} = {[5], [11]}.
On the other hand [5]³ = [17] and [17]²=[289] = [1] in U(18).
Thus <[5²]> = <[7]> = {[7], [13], [1]} = <[13]> and
<[5³]> = <[17]> = {[17], [1]}.