Bitwise modulo with numbers bigger 2³²

Question

I have to calculate the remainder of two big numbers in C. One has the size of 938 or 256 Bit and the other has a size of 85 Bit. Both are no 2^n values!

My basic idea is to put every bit as one element of a short-array and calculate the remainder with basic bit operations. But I have no good idea how to do this. So I hope somebody here can help me.

For those who are interested I'm programming an ETCS - Encoder according to UNISIG-SUBSET 036 http://www.era.europa.eu/Document-Register/Documents/Set-2-Index009-SUBSET-036%20v300.pdf on page 36 - 39 and im trying to calculate the check bits.

Answer 1

Assuming you are working in decimal base, and you want to calculate X mod Y, you can do something like this:

1. mod = 0;
2. mod = ((mod * 10) + mostCignificantDigit)%Y;
3. remove the mostCignificantDigit from your number, and return to 2.

In other words, say you have the number in digit array A:

mod = 0;
for (int index = 0; index < A.size(); ++index)
        mod = ((mod*10)+A[index]) %Y