Modulo Operation Properties

Question

I calculated the sum S = (a * x + b * y + c)% N. Yes, it looks like a quadratic equation, but this is not because x and y have some properties and must be calculated using some recurrence relations. Since the sum exceeds even the limits of the unsigned long long, I want to know how I can calculate this sum using the properties of the modulo operation, properties that let me write something like this (I say something because I don’t remember exactly how these properties): (a * x)% N + (b * y)% N + c% N, which avoids exceeding the limits of an unsigned long long.

Thank you in advance for your concern! :)

Answer 1

a % N = x means that for some integers 0 <= x < N and m : m * N + x = a .

You can simply deduce that if a % N = x and b % N = y , then

 (a + b) % N = = (m * N + x + l * N + y) % N = = ((m + l) * N + x + y) % N = = (x + y) % N = = (a % N + b % N) % N. 

We know that 0 < x + y < 2N , so you need to save the remainder calculation. This shows that you can separate the summation and calculate the balances separately, and then add them, but do not forget to get the balance for the sum.

For multiplication:

 (a * b) % N = = ((m * N + x) * (l * N + y)) % N = = ((m * l + x * l + m * y) * N + x * y) % N = = (x * y) % N = = ((a % N) * (b % N)) % N. 

That way you can also do the same with the products.

These properties can simply be deduced in a more general form using some abstract algebra (the remainders form the factor ring Z/nZ ).

Answer 2

You can accept the idea even more if necessary:

 S = ( (a%N)*(x%N)+(b%N)*(y%N)+c%N )%N 

Answer 3

You can apply a module to each member of the amount as you suggested; but even after summing them up, you must apply the module again to get the final result.

Answer 4

How about this:

  int x = (7 + 7 + 7) % 10; int y = (7 % 10 + 7 % 10 + 7 % 10) % 10; 

Answer 5

You remember correctly. The equation that you indicated is where you% N each of the terms is correct. And that will be exactly what I use. You also owe% N ​​for each partial amount (and amount) again, since the addition results can be even larger than N. BUT be careful, this only works if your size is limited to half that of your N. If it isn’t so, it can become really unpleasant.

Btw for the following% N partial sum operations, you don’t need to do a complete division, check> N and if a simple subtraction of N is enough.

Answer 6

Not only can you reduce the entire mod n variable before starting the calculation, you can write your own mod-mul to calculate a * x mod n using the shift-and-add method and reduce the result of mod n at each step, so your intermediate calculations will require only one bit than n. Once these products are calculated, you can add them in pairs and reduce mod n after each addition, which will also not require more than 1 bit outside the range of n.

In my answer there is a question about implementing modular multiplication in python. The conversion to C should be trivial.