0

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 :(

Quora93
  • 1
  • 1
    I don't know what a DLP instance is but if you are asking about a cyclic subgroup generated by $5^2$ (mod 18) and $5^3$ (mod 18) then what you wrote is correct. By the way, you should put your mathematical expressions between a pair of "$" so that the website understand it in mathematical format. – Quang Dũng Đinh May 03 '23 at 05:53
  • 1
    Hi @QuangDũngĐinh Thank you so much for your kind response, yes I am exploring cyclic subgroup. Also I am very grateful to you for the tip regarding math expression, since this is my first post I was not aware. Thanks a lot once again! – Quora93 May 03 '23 at 06:18
  • $5^{3 }$ % $18 = 17$ – Lozenges May 03 '23 at 06:49
  • Hi @Lozenges the question has the below details as well: Let the DLP instance in Z∗18 be 7 ≡ 5^x(mod 18). Since n = 6 = 2 × 3, let p = 2, and q = 3. – Quora93 May 03 '23 at 07:19
  • the elements generated by $5^3$ mod $18$ are ${17,1}$ and not ${11,1}$. That was my comment. I don't know what a DLP instance is, can you explain? – Lozenges May 03 '23 at 07:35
  • Hi @Lozenges

    Original DLP instance:

    h ≡ g^x(mod N), where g is the generator of Z∗N .

     – Quora93 May 03 '23 at 09:36

1 Answers1

0

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]}.

Quora93
  • 1