Perform a modulus in a huge number?

Question

I need to do a modulus operation on very large integers. The biggest integer supported by my platform (edit: .NET 2.0) is a 64 bit integer, which aren't big enough for the numbers I'm working with.

How can I do a modulus on really big integers, like 12654875632126424875387321657498462167853687516876876?

I have a solution that treats the number as a string and works it in pieces one by one, but I wanted to know if there's a better way.

Here's my function treating the number as a string. It basically does long division the way you'd do it by hand.

    Public Function MyMod(ByVal numberString As String, ByVal modby As Integer) As Integer
        Dim position As Integer = -1
        Dim curSubtraction As Integer = 0

        While position < numberString.Length - 1
            position += 1
            curSubtraction = curSubtraction * 10 + CInt(numberString.Substring(position, 1))

            If (curSubtraction / modby) < 1 And position = numberString.Length - 1 Then
                Return curSubtraction
            ElseIf (curSubtraction / modby) < 1 Then
                Continue While
            Else
                curSubtraction = curSubtraction Mod modby
            End If
        End While
        Return curSubtraction
    End Function

Is there a cleaner, more efficient way?

EDIT: To clarify, the integers are coming from IBAN bank account numbers. According to the specification, you have to convert the IBAN account number (containing letters) into one integer. Then, you do a modulus on the integer. So, I guess you could say that the real source of the integer to perform the modulus on is a string of digits.

Answer 1

You haven't specified where the numbers are coming from, but you might be able to make some simplifications. If the numbers are originally smaller, then consider things like:

(a + b) MOD n = ((a MOD n) + (b MOD n)) MOD n

or

ab MOD n = (a MOD n)(b MOD n) MOD n