Calculating the modulus for a large value

Question

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

Answer 1

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

Answer 2

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:

Answer 3

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

Answer 4

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