0
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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$

$\endgroup$

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.