Approximate Factoring
Suppose you want to compute (a*x) mod m where a and x are positive and less than the modulus m. If integer overflow is not an issue, you can do this by computing k1 = a*x/m*m where, a*x/m signifies the largest integer less than or equal to a*x/m, and then computing the result k1*m, called the residue. Suppose, however, that the intermediate value a*x would overflow. The modulus m can always be approximately factored into m = a*q + r with q = m/a. Now calculate k=ax/aq. Note that k is x/q, thereby avoiding this overflow of a*x. Using the fact that m = a*q+r, you can see that the residue is:
a*x- k1*mor
a*(x - k*q) - k*r + (k-k1)*mIf a*a is less than m, k-k1 is either zero or one, and x is positive and less than m, the following code fragment using signed integers computes the residue correctly without overflow:
k = x / q; residue = a* (x - k * q) - k * r; if (residue < 0) residue += m;The check against only negative values can be used in computing the residue if zero values are impossible, as they are if m is prime.
