Large Integer Arithmetic - how to implement modulo?
I want to implement my own (simple) large / arbitrary integer precision arithmetic, first in Java (because I'm more familiar with the syntax) and then rewrite it in 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 tutorial on storing 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 these numbers.
What would be a simple, possible solution to obtain
int[] c = modFunction(a, b)
Any help is appreciated.
source to share
Method 1
I came up with this method; it's not necessarily effective, but it works.
Note that you can use the input length (in numbers) to calculate your logarithm.
You can use this to do division and therefore modulus.
In particular, please note first 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
Finally, notice that
4260420485102658362505442 / (578907659710377778063722 * 1) = 7.3...
therefore
4260420485102658362505442 - (578907659710377778063722 * 7) = 208066867130013916059388
So the answer 208066867130013916059388
.
Forces of 10 are easy to obtain just by examining the length, and you can figure out which one you need to subtract by simply trying all 10 possibilities with multiplication and figuring out which is the highest, which gives a non-negative result.
Method 2
Just binary search for quotient using multiplication! Then find the remainder using a factor.
source to share
When calculating, D mod M
you can subtract from D
any integer number from M
without changing the result. If you subtract the quotient approximation D/M
, you get closer to the desired modulus. Repeat until the value 0
gives you the answer.
while D >= M
Q= some integer approximation of D / M
D= D - Q.M
To get such a factorial approximation, take the K
most significant numbers D
and M
and calculate the whole part Q=10^K.D/M
. This is conveniently done using double precision arithmetic and gives you numbers K
(you can use up K=15
). Add len(D)-len(M)-K
zeros to align before subtracting.
Note that truncation after K
digits can result in a small error in the quotient when dividing the approximations D
and M
(by the first digits K
). (I am assuming the maximum error Q
is not one unit.) This error is not a big deal, because as long as you subtract an integer multiple of the value M
, the D
exact value remains. Only at the end you need to check that 0<=D<M
.
This example is an 849465603662254214335539562 mod 578907659710377778063722
approximate factor 10^15.849465603662254 / 578907659710377 = 1467359412876373.
and you need to add -12
zeroes (!) To rearrange, i.e. shift decimal point left and use 1467
.
Then 849465603662254214335539562 - 1467 * 578907659710377778063722 = 208066867130013916059388
is the requested module.
source to share
Modulo is pretty simple:
a % b = a - floor((a / b)) * b
All you need is integer division (or floor () and division), multiplication, subtraction. I assume you already have these operations.
If you only have integers, there is no need for a function floor()
:
a % b = a - (a / b) * b
Example:
849465603662254214335539562 % 578907659710377778063722 =
849465603662254214335539562 - (849465603662254214335539562 / 578907659710377778063722) * 578907659710377778063722 =
849465603662254214335539562 - 1467 * 578907659710377778063722 =
849465603662254214335539562 - 849257536795124200419480174 =
208066867130013916059388
source to share
Why don't you want to use the BigDecimal class? It has a remainder method that does exactly what you want. You can check the source code for the BigDecimal class to see how it is implemented.
source to share