Блог пользователя pranay2063

Inverse modulo of a range of numbers modulo m
Автор pranay2063, 9 лет назад, По-английски

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.

  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится

»
9 лет назад, # |
← Rev. 3   Проголосовать: нравится +1 Проголосовать: не нравится

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)

→ Ответить
»
9 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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.

→ Ответить
»
6 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

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

→ Ответить
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится

    Can you explain how the ifak[k] = ifak[k+1]*(k+1)%P works? More specifically, how modpow(fak[N],P-2) and ifak[k+1]*(k+1)%P produce the same result?

    → Ответить
    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      Can you explain how the ifak[k] = ifak[k+1]*(k+1)%P works?

      Notice that the inverse of factorials is computed in reverse order. You start by correctly computing the inverse factorial of $$$n$$$ which is $$$n!^{p - 2} mod(p)$$$: ifak[n] = modpow(fak[n], p - 2)

      Now that we now the inverse of $$$n!$$$ we can deduce smaller inverse in a similar fashion as we compute the factorials themselves

      $$$(k + 1)!^{-1} = (k! \cdot (k + 1))^{-1}$$$
      $$$(k + 1)!^{-1} = k!^{-1} \cdot (k + 1)^{-1}$$$
      $$$(k + 1)!^{-1} \cdot (k + 1) = k!^{-1}$$$

      So we deduce $$$k!^{-1}$$$ from $$$(k+1)!^{-1}$$$ easily using: ifak[k] = ifak[k + 1] * (k + 1) % p.

      More specifically, how modpow(fak[N],P-2) and ifak[k+1]*(k+1)%P produce the same result?

      Not sure what do you mean by this.

      • modpow(fak[N],P-2) is only used to compute the inverse of $$$N!$$$.
      • The recurrence ifak[k+1]*(k+1)%P is used to compute the remaining factorial inverses. $$$0 \le k \lt N$$$
      → Ответить
      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится +10 Проголосовать: не нравится

        What I meant earlier is that we could calculate inverse of each x! for x from 0 to N separately using modpow(fak[x],P-2) or we could do it faster with the iterative version, and I wanted to know how using both of them would give the same result.

        With the proof for the iterative step, it is very clear now, Thank you for this wonderful explanation!

        → Ответить