# Calculating the modulus for a large value

I'm building a calculator for International Bank Account Numbers (IBAN) but I'm having trouble calculating the modulus for a big number. That is to say, my results are not the same as that of the examples I have.

To calculate the IBAN checksum I have to follow these steps (taken from WikiPedia):

1. Replace the two check digits by 00 (e.g., GB00 for the UK).
2. Move the four initial characters to the end of the string.
3. Replace the letters in the string with digits, expanding the string as necessary, such that A or a=10, B or b=11 and Z or z=35. Each alphabetic character is therefore replaced by 2 digits.
4. Convert the string to an integer (i.e., ignore leading zeroes).
5. Calculate Mod-97 of the new number.
6. Subtract the remainder from 98 and, if necessary, pad with a leading 0 to make a two digit number.

For example NL20INGB0001234567

1. NL00INGB0001234567
2. INGB0001234567NL00
3. 182316110001234567232100
4. 182316110001234567232100
5. 182316110001234567232100 % 97 = 67
6. 98 - 67 = 31

Since 31 does not equal 20 I conclude that something went wrong. According to an example 182316110001234567232100 % 97 should yield 78 but I don't see how.

What am I doing wrong in my modulus calculation?

Cheers

-
It turns out this had to do with the size of the integer, hence the language couldn't handle. –  Marijn Huizendveld May 31 '12 at 16:40

Indeed 182316110001234567232100 mod 97 = 78. Perhaps you're using too small an integer type. 182316110001234567232100 requires at least 78 (unsigned) bits.

-
Oh - that's a good thought. A small integer type. +1 –  mixedmath May 31 '12 at 16:37
That was it. I'm very disappointed in R and JavaScript for the lack of error messages :-( –  Marijn Huizendveld May 31 '12 at 16:41

I'm not entirely sure what you're doing wrong. As you showed no work as to how you calculated the mod, I can't really say anything about it. But your source is correct, as

$$\frac{182316110001234567232100}{97} = 1879547525785923373526 + \frac{78}{97}$$

Or, as W|A would say:

-

One method is to calculate it iteratively.

Here is a recursive Matlab function that can calculate the required modulo. I'm sure you could work this in Java. Crucially, the big IBAN number must be stored as an array, and the function only works with IBAN formats (or other numbers that have 4*n digits)

So, C and B are regular numbers, but A must be input as an array.

function C = bigmod(A,B)
A = A(:)';

% Convert array to number
d14 = A(1:4) * [1e3 1e2 1e1 1e0]';  % The first four digits
d34 = A(3:4) * [1e1 1e0]';          % The 3rd and 4th digits

remainder = mod(d14,B);

if (length(A)==4)
C = remainder;
else
d4 = mod(remainder,10);
d3 = (remainder-d4)/10;
C = bigmod([d3 d4 A(5:end)], B);
end
end


Test by

A = [1 8 2 3 1 6 1 1 0 0 0 1 2 3 4 5 6 7 2 3 2 1 0 0]
C = bigmod(A,97)


gives C = 78

-

python can handle (essentially) arbitrarily large integers.

Scroll down in http://www.artofproblemsolving.com/Wiki/index.php/Getting_Started_With_Python_Programming for an example.

For a list of other languages see

http://en.wikipedia.org/wiki/Arbitrary-precision_arithmetic

-
One could use several tricks to avoid large computations, using e.g. $100 \equiv 3 \pmod{97}$. For example, since the last two digits are always $00$, we know that $$1823161100012345672321(00) \equiv 3 \cdot (1823161100012345672321) \pmod{97}.$$ But essentially, you end up with a $24$-digit number, and instead of calculating this big number modulo $97$, you can also treat each digit seperately. This is very similar to checking divisibility by $3$: You simply add up all digits (since $10 \equiv 1 \mod 3$), and the resulting number is divisible by $3$ if and only if the original number was.
In other words, to calculate $182316110001234567232100$ modulo $97$, try instead taking the "inner product" with numbers $\{10^k \mod 97: k = 0, 1, \ldots, 23\}$ such as these given below: $$1, 10, 3, 30, 9, -7, 27, -21, -16, 34, -48, 5, -47, 15, -44, 45, -35, 38, -8, 17, -24, -46, 25, -41.$$ For instance, in your example, you can put the $24$-digit number $182\ldots100$ above and these $24$ numbers (in reversed order) below to get $$\begin{array}{cccccccccccc} 1 & 8 & 2 & 3 & 1 & 6 & 1 & 1 & 0 & 0 & 0 & 1 \ldots \\ -41 & 25 & -46 & -24 & 17 & -8 & 38 & -35 & 45 & -44 & 15 & -47 \ldots \\ \\ \ldots 2 & 3 & 4 & 5 & 6 & 7 & 2 & 3 & 2 & 1 & 0 & 0 \\ \ldots 5 & -48 & 34 & -16 & -21 & 27 & -7 & 9 & 30 & 3 & 10 & 1\end{array}$$ Calculating the product of those pairs of numbers above and below, you get $$\begin{array}{cccccccccccc} 1 & 8 & 2 & 3 & 1 & 6 & 1 & 1 & 0 & 0 & 0 & 1 \ldots \\ -41 & 25 & -46 & -24 & 17 & -8 & 38 & -35 & 45 & -44 & 15 & -47 \ldots \\ \hline -41 & 200 & -92 & -72 & 17 & -48 & 38 & -35 & 0 & 0 & 0 & -47 \ldots \\ \\ \ldots 2 & 3 & 4 & 5 & 6 & 7 & 2 & 3 & 2 & 1 & 0 & 0 \\ \ldots 5 & -48 & 34 & -16 & -21 & 27 & -7 & 9 & 30 & 3 & 10 & 1 \\ \hline \ldots 10 & -144 & 136 & -80 & -126 & 189 & -14 & 27 & 60 & 3 & 0 & 0 \end{array}$$ Adding up the numbers below the line, we end up with $-19$, which modulo $97$ equals $78$, as expected.
An advantage of this method is that, once you have those $24$ numbers, the computations are really simple and require only really small numbers. You can even do this method by hand, as I actually did for the example above.