By raising $7 ≡ 5^x(mod 18)$ to the powers 2 and 3, we get: $13 ≡ 7^x(mod 18)$ and $1 ≡ 17^x(mod 18)$, respectively. Solving DLP in the first subgroup gives us $x ≡ 2 (mod 3)$. What is x in the second subgroup? How to use the Chinese Remainder Theorem (using PARI) to find x in the original DLP (Cyclic subgroup)instance? I have tried it but need to validate my proof!
My proof is as follows: For $1 ≡ 17^x (mod 18)$
Since 17 is the inverse of 1 modulo 18 ($17 * 1 ≡ 1 (mod 18)$), any power of 17 modulo 18 is also 1. This implies that x can be any integer multiple of the order of the second subgroup. In this case, the order of the second subgroup is 2, so x can take values that are multiples of 2. Thus, we have:
$x ≡ 0 (mod 2)$
Now, we have two congruences:
$x ≡ 2 (mod 3)$ $x ≡ 0 (mod 2)$ We can use the Chinese Remainder Theorem to find x in the original DLP instance.
In PARI/GP, you can use the "chinese" command to find the solution:
chinese(Mod(2, 3), Mod(0, 2))
This command will return a solution for x: $%1 = Mod(2, 6)$ So, $x ≡ 2 (mod 6)$ is the solution for the original DLP instance $7 ≡ 5^x (mod 18)$. Since the smallest non-negative integer that satisfies this congruence is 2, the value of x is 2.