Large Integer Arithmetic - how to implement modulo?

Question

I want to implement my own (simple) large/arbitrary integer precision arithmetic, first in Java (cause I am more familiar with the syntax), then rewrite it to C.

I have addition, subtraction and multiplication for numbers of infinite length and now I need modulo for cryptographic applications.

I store the digits of my arbitrary numbers in an array, I followed the following guide on how to store the numbers: How to handle very large numbers in Java without using java.math.BigInteger

So for example I want to calculate

849465603662254214335539562 % 578907659710377778063722

when I have two arrays:

int[] a = [8, 4, 9, 4, 6, 5, 6, 0, 3, 6, 6, 2, 2, 5, 4, 2, 1, 4, 3, 3, 5, 5, 3, 9, 5, 6, 2]
int[] b = [5, 7, 8, 9, 0, 7, 6, 5, 9, 7, 1, 0, 3, 7, 7, 7, 7, 8, 0, 6, 3, 7, 2, 2]

representing those numbers.

What would be a simple as possible solution to get

int[] c = modFunction(a, b)

Any help is appreciated.

Answer 1

Method 1

I came up with this method; it's not necessarily efficient, but it works.

Notice that you can use the length of the input (in digits) to compute its logarithm.
You can use this to perform division, and therefore modulus.

Specifically, first notice that

849465603662254214335539562 / (578907659710377778063722 * 1000) = 1.4...

Therefore

849465603662254214335539562 - 578907659710377778063722 * 1000 = 270557943951876436271817562

Now notice that

270557943951876436271817562 / (578907659710377778063722 * 100) = 4.6...

Therefore

270557943951876436271817562 - (578907659710377778063722 * 400) = 38994880067725325046328762

Now notice that

38994880067725325046328762 / (578907659710377778063722 * 10) = 6.7...

Therefore

38994880067725325046328762 - (578907659710377778063722 * 60) = 4260420485102658362505442

And finally, notice that

4260420485102658362505442 / (578907659710377778063722 * 1) = 7.3...

Therefore

4260420485102658362505442 - (578907659710377778063722 * 7) = 208066867130013916059388

So the answer is 208066867130013916059388.

The powers of 10 are easy to obtain just by examining the length, and you can figure out which multiple of them you need to subtract by just trying out all 10 possibilities with multiplication and figuring out which is the highest that gives a nonnegative result.

Method 2

Just binary search for the quotient using multiplication! Then find the remainder using the quotient.

Answer 2

When computing D mod M, you can subtract from D any integer multiple of M without changing the result. If you subtract with an approximation of the quotient D/M, you get closer to the desired modulo. Repeating until the quotient 0 will give you the answer.

while D >= M
  Q= some integer approximation of D / M
  D= D - Q.M

To get such a quotient approximation, take the K most significant digits of D and M and compute the integer part of Q=10^K.D/M. This is conveniently done using double precision arithmetic and gives you K digits (you can use up to K=15). Add len(D)-len(M)-K zeroes to realign before the subtraction.

Note that truncating after K digits can result in a small error on the quotient as you divide approximations of D and M (to the first K digits). (My guess is that the maximum error on Q is by one unit.) This error does not really matter, because as long as you subtract an integer multiple of M, D remains an exact value. Only in the end do you need to check that 0<=D<M.

In the given example, 849465603662254214335539562 mod 578907659710377778063722, the approximate quotient is 10^15.849465603662254 / 578907659710377 = 1467359412876373. and you need to add -12 zeroes (!) for realignment, i.e. shift the decimal point to the left and use 1467.

Then 849465603662254214335539562 - 1467 * 578907659710377778063722 = 208066867130013916059388 is the requested modulo.

Answer 3

Why you do not want to use BigDecimal class? It has remainder method which does exactly what you want. You may check source code of BigDecimal class to check how it is implemented.

Answer 4

Modulo is pretty simple:

a % b = a - floor((a / b)) * b

All you need is integer division (or a floor() and a division), multiplication, subtraction. I suppose you already have these operations.

If you have integers only, there is no need for the floor() function:

a % b = a - (a / b) * b

Example:

849465603662254214335539562 % 578907659710377778063722 =
849465603662254214335539562 - (849465603662254214335539562  / 578907659710377778063722) *  578907659710377778063722 =
849465603662254214335539562 - 1467 * 578907659710377778063722 =
849465603662254214335539562 - 849257536795124200419480174 =
208066867130013916059388