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

  • $\begingroup$ thanks, I agree that to get ϕ(M) is easy. I want to find c (mod M), but I can only find c (mod |G|) .This is why i'm confused. $\endgroup$
    – John
    Jan 7 '18 at 8:50
  • $\begingroup$ 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$. $\endgroup$
    – user436658
    Jan 7 '18 at 8:58
  • $\begingroup$ I got it ! Did you mean that if I find c(mod|G|) with pohlig-hellman algrithm ,it proves that the c(mod M) is exist but uncertain(so don't need to focus on it)? thank you ,professor Vector, sincerely! $\endgroup$
    – John
    Jan 7 '18 at 11:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.