Discrete logarithm of number of form (2ⁿ - 1)

Question

I need to find the smallest number k for which (2ⁿ - 1)^k % M equals a given X.

The catch here is that n can be a very large number, with possibly 10,000 digits, and hence will be stored as a string. I know that this is a hard problem in general, but does the special form of the number imply any property that makes this easier in this case? M is not necessarily prime, but is within reasonable bounds of 10⁸.

Answer 1

First you can't store the value in string because 2¹⁰⁰⁰⁰ digits is far more than the total number of particles in the universe (10⁸⁰ ≈ 2^265.75). You don't even have enough memory if you store it as bits (in fact that's how bigint libraries store their numbers, no good libraries store values as characters)

So what you can do is to use modular exponentiation to get the modulo. Basically you use the (a * b) % M = ((a % M) * (b % M)) % M property to avoid calculating the real power value. Many languages already have built-in support for that, for example Python pow function has an optional third argument for this, resulting in pow(base, exp[, mod]). The implementation is exactly like the normal pow, just replace power *= base with modpow = (modpow * base) % M. There are a lot of examples on SO

• Calculating (a^b)%MOD
• Calculating pow(a,b) mod n
• Calculate (a^b)%c where 0<=a,b,c<=10^18

You don't need to loop (2ⁿ - 1)^k times. It's actually impossible because assuming you can loop 2³² times a second then you'll need 2³² seconds ≈ 136 years to loop 2⁶⁴ times. Imagine how many centuries it need to count up to 2¹⁰⁰⁰⁰. Luckily the result will repeat after a cycle, you just need to calculate the cycle length

Those are the hints needed. You can reference how to calculate a^(b^c) mod n? and finding a^b^c^... mod m which are closer to your problem