c code: prevent overflow in modular operation with huge modules (modules near the overflow treshold)

Question

In my c code I have to perform a series of recursive modular operations. In particular I have to perform operations like (A*B)modC, with C~2^126, and A,B that, in principle, could be very big numbers (from 0 to 2^128 - 1) ( I work with 128 bit unsigned __int128 variables).
The problem is how to perform the module during the multiplication process. I need this because if the module is performed after the multiplication, I could exceed 2^128 (if A and B are very big) during the multiplication and corrupt the successive modular operation.
So I'd like to perform a multiplication which restart from 0 every time that I pass C (during the multiplication process) instead of every time I pass 2^128 - 1.
How should I do this?

Answer 1

The naive solution is to implement multiplication as a loop over bits, shifting by one and adding each time. This way you can compute the modulus of the interim result each pass through the loop.

It requires 128 shifts, 128 additions and 128 modulo operations. If that is too slow for you then some boffin can probably tell you an optimization (but everyone knows you should only consider optimization once you are sure that the simplest solution isn't fast enough).