3

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.

Community
  • 1
  • 1
luuksen
  • 1,357
  • 2
  • 12
  • 38
  • Here's a solution in C++: https://github.com/wkaras/C-plus-plus-intrusive-container-templates/blob/master/modulus_hash.h – WaltK Mar 05 '19 at 04:59

4 Answers4

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.

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.

Community
  • 1
  • 1
user541686
  • 205,094
  • 128
  • 528
  • 886
  • That first method looks really interesting! I'll try to implement it. – luuksen Nov 21 '14 at 09:56
  • @YvesDaoust: How is he supposed to find the quotient directly? That's begging the problem basically. – user541686 Nov 21 '14 at 10:10
  • That's right, sorry. I am undoing my harsh comments. –  Nov 21 '14 at 10:19
  • @YvesDaoust: Double precision only works for up to ~308 digits, which is not exactly a lot when you're talking about bignums. Also, it completely misses the point of the question. – user541686 Nov 21 '14 at 10:25
  • If you convert your numbers to double precision, ordinary division gives you good approximations of the quotient that you can use to reduce the dividend. In the given case, the quotient is 1467.359... so that you can compute D - 1467 N. –  Nov 21 '14 at 10:28
  • @YvesDaoust: Sigh, here we go again. I don't have the energy to go for a second round of arguments only to delete them afterwards all over again. Just post your own answer explaining whatever your better method is. – user541686 Nov 21 '14 at 10:28
  • Yes, there is this 10^308 limit that needs to be worked around, by renormalizing the exponent and keeping your own accounting. –  Nov 21 '14 at 10:42
  • 1
    I mark this as an answer, because I tried to implement it and it seems to work correctly, is pretty simple and fast enough for my needs. If someone needs a superfast and optimized solution, don't implement this or use a real library. :) – luuksen Nov 21 '14 at 15:34
0

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
gaborsch
  • 15,408
  • 6
  • 37
  • 48
  • 1
    I don't have division yet as I said, but I'll think about implementing it if I need to. – luuksen Nov 21 '14 at 10:24
  • Division and modulo are like twins. If you have one, soon you'll need the other one. And I think it's easier to implement a simple division. – gaborsch Nov 21 '14 at 10:35
-2

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.

Bartosz Bilicki
  • 12,599
  • 13
  • 71
  • 113