Explain the result of Pohlig-Hellman algorithm.

Question

At this discrete-logarithm calculator: https://www.alpertron.com.ar/DILOG.HTM. Let base = 2, pow = 2 and modulus = 1009 * 3643 = 3675787. (Note both 1009 and 3643 are prime numbers.). The solution obtained is:

Find exp such that $2^{exp}$ ≡ 2 (mod 3675787)

exp = 1 + 305928k

The calculator is using the Pohlig-Hellman algorithm. I cannot figure out how the 305928 term shows up in the result.

I followed all the steps shown in this answer: Use Pohlig-Hellman to solve discrete log. We get the result x = 1, but not the 305928k term.

Can someone explain how?

Answer 1

Hint: the multiplicative order of 2 modulo $n=3675787$ is $$\mathrm{ord}_{3675787}(2) = 305928$$ i.e. $305928\;$ is the smallest positive exponent $x$ with $2^x=1 \pmod n$