kingofnumbers's blog

Divide big numbers with modulo
By kingofnumbers, 12 years ago, In English

Hi, If i want to compute (1065*1001) mod 1000 , the best way to do this is computing (1065 modulo 1000) and (1001 modulo 1000) then Multiplying the two numbers so (1065 modulo 1000) = 65 and (1001 modulo 1000) = 1 then 65 * 1 = 65 so: (1065*1001) mod 1000 = 65 this way is much easier than computing 1065*1001 then modulo 1000

so my question is: is there a way resemble to the way above working with division like (6072/1012) mod 5 thanks.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

There is a way when modulo is a prime number.

Using Fermat's little theorem we have:

a ^ p ≡ a (mod p), p is prime

=>

a ^ ( p — 2 ) ≡ 1 / a (mod p)

So we have ( a / b ) % m = ( a % m ) * ( ( 1 / b ) % m ) = ( a % m ) * ( ( b ^ ( m — 2 ) ) % m )

→ Reply
  • »
    »
    12 years ago, # ^ |
    ← Rev. 2   Vote: I like it -8 Vote: I do not like it

    Thank you but this is not helping, because b ^ ( m — 2 ) is a huge number when m is big, and I want to make calculation easier not harder. any better ideas??

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Calculate it by modulo m.

      (a * b) mod m == ((a mod m) * (b mod m)) mod m

      → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        this is also useless when m is big for example m=10000000007 (10^9+7) so i have to multiply (b mod m)*(b mod m)*(b mod m) ......(b mod m)*(b mod m) (m times)

        → Reply
        • »
          »
          »
          »
          »
          12 years ago, # ^ |
            Vote: I like it +3 Vote: I do not like it 
          int res = 1;
for (int i = 0; i < n; i++) {
  res = res * b % m;
}
          → Reply
          • »
            »
            »
            »
            »
            »
            12 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            yes I know , the main problem is that the complexity of computing (a/b) mod m is O(m) and if I have n calculations to do so the total complexity is O(nm) which is slow.

            so I need way to calculate each ( (a/b) mod m ) in O(1) time

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              12 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it 

              int pow(int a,int b,int m)
{
  if(b==0) return 1;
  else if(b%2==0) return pow(a*a%m,b/2,m);
  else return pow(a,b-1,m)*a%m;
}
              → Reply
            • »
              »
              »
              »
              »
              »
              »
              12 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Only O(log(m)) is possible. And only if gcd(b,m)==1. Google 'fast exponentiation'

              → Reply