1

I need to find the smallest number k for which (2n - 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 108.

phuclv
  • 37,963
  • 15
  • 156
  • 475
Shiven Sinha
  • 656
  • 5
  • 14
  • It is the fact that M is around 10\**8 that makes this easy. Brute force is doable, but the "baby steps - giant steps" algorithm will make quick work of this. – President James K. Polk Mar 14 '20 at 12:29
  • @PresidentJamesMoveonPolk Is there a way to minimise the value returned from BSGS? I'm sorry if that's a dumb question, but the implementations I tried don't always return the minimum value. The Euler's totient function does sometimes reduce it, but in many cases the period of cyclicity is actually smaller than the value of the totient function. – Shiven Sinha Mar 14 '20 at 12:53
  • Just compute all the solutions and take the minimum. There shouldn't be very many, depending on the factorization of M. Also, just replace n with n mod lambda(M). – President James K. Polk Mar 14 '20 at 13:08

1 Answers1

1

First you can't store the value in string because 210000 digits is far more than the total number of particles in the universe (1080 ≈ 2265.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

You don't need to loop (2n - 1)k times. It's actually impossible because assuming you can loop 232 times a second then you'll need 232 seconds ≈ 136 years to loop 264 times. Imagine how many centuries it need to count up to 210000. 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

phuclv
  • 37,963
  • 15
  • 156
  • 475
  • Definitely, no crazy plans about storing the number :) As for deducing from the cycle, some numbers can result in pretty large ones. I had tried that earlier, but say for `n = 10**10000` and `m = 10**9 - 23`, the cycle extends to 11107338 items. I'm trying to fit it in one second. – Shiven Sinha Mar 14 '20 at 13:34
  • 1
    It is probably noticeable faster to first reduce n' = n mod λ(M), and then compute 2\**n' mod M. Your method takes 10,000 squarings mod M versus 30 squarings + 30 multiplies mod M if n' is used instead. You do have to factor M to compute the lambda function, so if that isn't one-time work then it has to be included in the cost. – President James K. Polk Mar 14 '20 at 15:40
  • @PresidentJamesMoveonPolk Thanks for the suggestion, but again M isn't a constant in the queries. And the Carmichael function, although straightforward, is often pretty slow to compute. I'll try it out though, and see if it does reasonably well. – Shiven Sinha Mar 15 '20 at 08:48
  • Slow and fast are relative. But if M is changing a lot, then having to factor M each time means that using the Carmichael function is not going to buy you much if any improvementl – President James K. Polk Mar 15 '20 at 14:22