Modulus of Very large Number

https://cs.stackexchange.com, obviously this is a better site for such a question.

Why is GMP "out of the question"? There may be alternatives that satisfy your requirements, if only we knew what they were.

Otherwise, you might look to create an equivalent of the well-known methods for mentally calculating modulus of large numbers with small numbers (e.g. for % 7, we repeatedly multiply most-significant digit by 10-7=3 and add it to the next one, mod 7, until there's only a single digit left).

The first step would be to figure out how to compute (a+b) mod c when both a and b are less than c but (a+b) may overflow. The rest should easily follow.