# Use pohlig-hellam algorithm to solve discrete log whose modulus is a primorial number

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

1. Am I wrong?
2. 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|$.
• But you don't need $c\pmod {M}$ (I've just corrected a typo), you need the exponent $c\pmod {\phi(M)}$ to calculate the power $\pmod M$.