Recently I read a paper in which it use Pohlig-hellman algrithm to solve the follow formular:
$$N \equiv 65537^c \pmod M $$
The target is to get c when N is given.The interesting thing is that the modulus is not a prime,but a primorial number(the product of the frst n successive primes,i.e., M = 2 ∗ 3 ∗ 5 * ··· ∗ 167) .
I'm confused! I know that the Pohlig-Hellman algorithm applies to groups whose order is a prime power.For example, in that paper, the order of G generated by 65537 is :$|G| = 2^4 * 3^4 * 5^2 * 7 * 11 * 13 * 17 * 23 * 29 * 37 * 41 * 53 * 83$
But when we use Chinese reminder theory(CRT) to findthe simultaneous congruences:
$$c \equiv c_1 \pmod {2^4}$$
$$c \equiv c_2 \pmod {3^4}$$
$$c \equiv c_1 \pmod {5^2}$$
$$...$$
$$c \equiv c_1 \pmod {83^1}$$
According to CRT, We can only get the result: $c \equiv x \pmod {|G|}$ rather than $c \equiv x \pmod {M}$
$\mathbf Questions:$
- Am I wrong?
- Can pohlig-hellman solve such discrete log problem when M is a primorial number?
Since $x^{\phi(M)}\pmod M$due to Fermat's little theorem, you have to find $c\pmod {\phi(M)}$, and one can easily see that $\phi(M)=(p_1-1)\ldots(p_{39}-1)=|G|$.