pranay2063's blog

By pranay2063, 4 years ago, In English,

Hi all,

While searching about inverse modulo, i got to know about a concise algorithm to find inverse modulo of numbers in range[1...n) under modulo m.

Time complexity of this approach is O(n).

Implementation of the algorithm:

r[1] = 1; for (int i=2; i<n; ++i) r[i] = (m — (m/i) * r[m%i] % m) % m;

Here is the link: http://e-maxx.ru/algo/reverse_element

I am unable to understand the proof of the algorithm. It would be very helpful if anyone explains the same in a simple way.

 
 
 
 
  • Vote: I like it  
  • +3
  • Vote: I do not like it  

»
4 years ago, # |
Rev. 3   Vote: I like it +1 Vote: I do not like it

m mod i = m — m/i*i
m mod i = — m/i*i (mod m)
// multiply by r[i]
r[i] * (m mod i) = — m/i*i *r[i] (mod m)
r[i] * (m mod i) = — m/i (mod m)
// multiply by r[m % i] — reverse to (m mod i) (reverse modulo m)
r[i] = — m/i * r[m % i] (mod m)

»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

This is the simplest I can think of:

We want to prove that .

Now multiply both sides by . We assume that already.

And note that is the largest multiple of i that is not greater than m. In other words, .

Thus , and so . That is, r[i] is the modular inverse of i modulo m.

There are some massive holes (mathematically) there, but should be easily patched up; but you want a simple explanation, not a completely correct one.

»
7 months ago, # |
  Vote: I like it +11 Vote: I do not like it

I was discussing with mgold earlier about another way to find the modular inverse of the first N numbers mod a prime number P.

Find the factorial of the first N numbers, let's say fak[n] = n!,

fak[0] = 1
for k=1...N:
    fak[k] = fak[k-1] * k % P

Find the modular inverse of N!. This is a result of Fermat Little Theorem and it can be computed in O(logP)

ifak[N] = modpow(fak[N], P - 2)

Now we can calculate the inverse of each factorial backwards in O(N).

for k=N-1...0:
  ifak[k] = ifak[k+1] * (k+1) % P

Most of the times I need to pre calculate the inverse of each of the first N numbers just to calculate the inverse of the factorial. So I can get C(n,k) in O(1). In that case we are done.

But If you actually need the inverse of the first N numbers you can compute them:

for k=1...N:
    inv[k] = ifak[k] * fak[k-1] % P

Here is my code using this method: 35525761