Modulo of Division of Two Numbers

Question

we know that

(A + B) % P = (A % P + B % P) % P
(A * B) % P = (A % P * B % P) % P

where P is a prime .

I need to calculate (A / B) % P where A,B can be very large and can overflow .

Does such kind of formula for modular arithmetic holds for (A / B) % P and (A - B) % P.

If not then please explain what the correct answer is.

I.e is it true that (A / B) % P = ((A % P) / (B % P)) % P?

I WAS TRYING TO CALULATE (N*(N^2+5)/6)%P where N can be as large as 10^15

here A=n*(n^2+5) can surely overflow for n=10^15

I don't think there is such a think, but in any case, you will need stronger hypothesis on A and B : A/B must be an integer, otherwise what you are doing doesn't make any sense. — rks, Sep 02 '12 at 10:23
Another remark: A and B being integers, I don't see how A / B can overflow without either A or B overflowing themselves. — rks, Sep 02 '12 at 10:25
Not in modular arithmetic. 3/4 == 6 mod 7 because 6*4 == 3 model 7. — Sean Owen, Sep 02 '12 at 10:29
He is saying that they are individually large but not the quotient. — Sean Owen, Sep 02 '12 at 10:30
@Sean: Only if `3 / 4` means `3 * 4^(-1)`. Not sure if the OP really means that. — ypercubeᵀᴹ, Sep 02 '12 at 10:32
i know it is a little late but the following link might help future peers - https://www.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/modular-inverses — Varun, May 28 '18 at 06:06

score 56 · Accepted Answer · answered Sep 02 '12 at 10:39

56

Yes, but it's different:

(a - b) mod p = ((a mod p - b mod p) + p) mod p

(a / b) mod p = ((a mod p) * (b^(-1) mod p)) mod p

Where b^(-1) mod p is the modular inverse of b mod p. For p = prime, b^(-1) mod p = b^(p - 2) mod p.

Edit:

(N*(N^2+5)/6)%P

You don't need any modular inverses from this. Just simplify the fraction: N or N^2+5 will be divisible by 2 and 3. So divide them and then you have (a*b) mod P.

answered Sep 02 '12 at 10:39

IVlad

43,099
13
111
179

Regarding the edit, the problem is that `N^2 + 5` may overflow when `N` can be as large as 10^15 (assuming 64 bit integers, no problem with 128 bits). But if `N^2 + 5` is divisible by 2 or 3, the remainder `(N^2 + 5) % P` need not be. So you can only directly divide out what divides `N`. You can rewrite `N^2 + 5 = (N-1)*(N+1) + 6` and then switch on `N%6`, `0 -> ((N/6)*(N^2+5))%P`, `1 -> (N*(((N-1)/6)*(N+1)+1))%P`, `2 -> ((N/2)*((N-1)*((N+1)/3)+2))%P`, `3 -> ((N/3)*((N-1)*(N+1)/2+3))%P`, `4 -> ((N/2)*(((N-1)/3)*(N+1)+2))%P`, `5 -> (N*((N-1)*((N+1)/6)+1)%P`. But the modular inverse is easier. – Daniel Fischer Sep 02 '12 at 20:30
As an alternative, you could calculate `(N*(N^2+5)) % (6*P)` and divide the result by 6. Unless `6*P` overflows, of course, but if `P` is that large, a modular multiplication is quite messy anyway. – Daniel Fischer Sep 02 '12 at 20:34
@IVlad Thanks for the info. I'm using the exact same approach as stated by you while implementing Clifford cocks algo in gmp, but the problem is mod inverse does not exist for all pairs of (a,b). e.g., (40, 2018). Can you please suggest an alternative approach. – user3250183 Mar 03 '15 at 07:40
@user3250183 - not really, you can't do it then. Maybe look into the chinese remainder theorem and see if that helps. – IVlad Mar 03 '15 at 10:06
@IVIad shouldn't (a-b) mod p = (a mod p - b mod p) mod p. I referred this article at khanacademy - https://www.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/modular-addition-and-subtraction – Varun May 28 '18 at 06:03
@light it's the same thing really. My version just ensures that the result is positive in all programming languages. In some, with your version, it might be negative. While mathematically equivalent, it might not always be what you want. – IVlad May 28 '18 at 06:29
@IVlad The formula for `(a/b) mod p` holds only if `(a/b)` means `(a*b^{-1})`, right (where `b^{-1}` means the multiplicative inverse under modular arithmetic)? Or does it also apply for "integer division"? – Python_user Nov 18 '18 at 17:32
@Python_user it applies when `a` is divisible by `b`. The idea is to calculate the modulo of the result without doing the actual division, like you can do for addition and multiplication. You do that using the multiplicative inverse mod `p`, yes. – IVlad Nov 18 '18 at 21:48
@IVlad Thanks! I did derive the same, although the derivation seemed a little "non-trivial" (where I assumed divisibility and that `b^-1` exists w.r.t p). Is it necessarily "non-trivial" or is there an intuitive way of understanding it? – Python_user Nov 19 '18 at 02:17
@IVlad And isn't `b^{-1}` (w.r.t mod `p`) defined to be in the range [0,...,p-1]? i.e., it is not necessarily to explicitly apply the `mod` operation inside the bracket? – Python_user Nov 19 '18 at 03:03
@Python_user it's defined like that, yes. But I wrote it for clarity, since in practice it depends on how exactly you write the code that computes the inverse. – IVlad Nov 21 '18 at 22:11

score 6 · Answer 2 · answered Feb 23 '16 at 23:30

Vlad's answer is correct:

(a - b) mod p = ((a mod p - b mod p) + p) mod p
(a / b) mod p = ((a mod p) * (b^(-1) mod p)) mod p

These and some other operations are outlined here in the Equivalencies section.

Just want to let you know that this will work not only for prime number p. The first one will work for any p. The second one will work for any p, where b^(-1) or modular inverse is defined.

The modular inverse can be calculated with extended Euclidian algorithm

score 0 · Answer 3 · edited May 23 '17 at 10:31

0

Whatever your algorithm is, if the inputs are A and B and if they overflow, then you cannot start the algorithm. It's important to tell us where those numbers come from. Are they the sum or product of other numbers that you have ?

For big numbers you must use a special math library for large numbers. How to handle arbitrarily large integers With such library chances are that you could just do (A/B)%P.

edited May 23 '17 at 10:31

Community

1
1

answered Sep 02 '12 at 10:19

bokan

3,601
2
23
38

1

say I am calulating (n*(n^2+5)/6)%P n can be as large as 10^15 thwn what to do ??? – Rahul Kumar Dubey Sep 02 '12 at 10:37
Just use a bignum math library. Others have done the job for you. – bokan Sep 02 '12 at 12:36

score 0 · Answer 4 · answered Sep 08 '21 at 23:09

Following is another way for modular division of two numbers.

(A/B)%p = (A*modular_inverse(B))%p

Also , 
int modular_inverse(int n, int p){
    return power(n, p-2, p);
}

int power(ll x, ll i,ll p)
{
int ans = 1;
while(i > 0){
    if(i&1)ans = (ans*x)%p;
     i >>=1;
     x = (x*x)%p;
   }
return ans;
}

Modulo of Division of Two Numbers

4 Answers4

Linked