1
$\begingroup$

This question is related to this one. Specifically, assume that we have $p$ = 2048, $m$ = 13 and $c$ = 357.

In this case, $c\ =m^e\ \bmod \ p$.

I know that many algorithms rely on the difficulty of computing the discrete logarithm. I have read however that discrete log across powers of 2 is weak. Could someone explain to me why and how you would compute it in my example?

$\endgroup$
3
  • $\begingroup$ So, basically, you're asking for a step-by-step example of how the Pohlig–Hellman algorithm works? $\endgroup$ Commented Apr 24, 2019 at 15:00
  • $\begingroup$ Basically, yes. I read the article and tried to follow / implement as I read but I feel I am missing something. I'd really like to understand it. $\endgroup$
    – S. L.
    Commented Apr 24, 2019 at 15:14
  • 1
    $\begingroup$ notice the multiplictive group mod 2048 does not have order 2048. We only have those co prime with n, i.e which don't have 2 as a factor. $\endgroup$
    – Meir Maor
    Commented Apr 24, 2019 at 17:21

1 Answer 1

2
$\begingroup$

There are a couple reasons that the discrete log is weak across powers of two, the most basic reason is because it is only considered strong when the modulus is some large prime, p.

This is a good link about how to find the mod inverse, and in it you will find their function for computing it. https://www.geeksforgeeks.org/multiplicative-inverse-under-modulo-m/

Basically, for your example, the program would solve the mod inverse problem in a very short amount of time (which is bad!). That is why if you use larger values of m and p, the calculations done in the pow function will take much longer than it did with the previous numbers.

As for why powers of 2 specifically are weak, I would recommend looking at the Chinese Remainder Theorem, just know that this requires a lot of math and is just based on the fact that any power of two is comprised solely of factors of 2. https://en.wikipedia.org/wiki/Chinese_remainder_theorem.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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