I have $a^x \bmod M$ and I am running algorithm based on $$ (a^2)\bmod M = (a\bmod M) * (a\bmod M) \bmod M.$$

The problem is that if $M$ is longer than half of digits of long long int (for example 14 digits long when long long int is max 19 digits), it can happen that $a\lt M$ but $a^2$ will overflow. $a$ is for example 13 digit number

Is there a way how to decompose/divide the $x$ to smaller numbers and do multiple runs with those instead so I will always avoid this? In other words is there some formula for splitting the mod value and compute it separately and then somehow get the result from these subresults?

Edit: Time complexity is an issue so I don't think I can change the algorithm.

  • $\begingroup$ If time complexity is not an issue, you can always add $a$ by itself $a$-times and take mod at every step. $\endgroup$ – EuxhenH Jan 8 at 18:30
  • $\begingroup$ @EuxhenH You are right but time complexity is crucial for me, I will edit my question to reflect that. $\endgroup$ – eXPRESS Jan 8 at 18:34
  • $\begingroup$ All I can think of is finding the factors of $a$ and then applying your algorithm to every factor (i.e., raise to power), and then multiplying them all together. But this is problematic when $a$ is a huge prime. $\endgroup$ – EuxhenH Jan 8 at 18:43
  • $\begingroup$ @EuxhenH Yeah that is definitely right way to go but way too slow if applied or even checked for every step. I actually do that when entering the algorithm and a is more than half digits of long long int but as algorithm progresses and M is bigger than half of digits I usually run into this problem pretty quickly and repeatedly. Thanks for suggestion though, if computational time is not the issue, it is definitely a solution (expect huge prime factors which would overflow anyway as you mentioned). $\endgroup$ – eXPRESS Jan 8 at 20:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.