# Splitting the mod value

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.

• If time complexity is not an issue, you can always add $a$ by itself $a$-times and take mod at every step. – EuxhenH Jan 8 at 18:30
• @EuxhenH You are right but time complexity is crucial for me, I will edit my question to reflect that. – eXPRESS Jan 8 at 18:34
• 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. – EuxhenH Jan 8 at 18:43
• @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). – eXPRESS Jan 8 at 20:29