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.