1
$\begingroup$

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?
$\endgroup$

1 Answer 1

0
$\begingroup$

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

$\endgroup$
3
  • $\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, 2018 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, 2018 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, 2018 at 11:45

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .