Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
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?
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.
