Libraion's blog

[HELP] Explanation for calculate modular inverse of all number from 1 to N in O(n)
By Libraion, history, 5 years ago, In English

I suddenly came across these lines of code when looking at others' submissions: (M is a prime)

    inv[1]=1;
    for(i=2;i<N;i++)
        inv[i]=(M-M/i)*inv[M%i]%M;

I tried to google it to understand the formula but ended up finding nothing. So could anyone give me the proof for this?

Thanks a lot <3 <3.

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

»
5 years ago, # |
← Rev. 3   Vote: I like it +20 Vote: I do not like it

I wasn't aware of this until your post. Fyi the precedence of % and * is equal. So you can read it as ((M-M/i)*inv[M%i])%M)

The inverse $$$\mod M$$$ of $$$i$$$ is the number $$$j$$$ such that $$$ij=1 \mod M$$$. It is unique if we insist that it be in $$$[0,M)$$$. Denote it $$$i^{-1}$$$.

Suppose we know all the inverses $$$1^{-1},2^{-1},\ldots,(i-1)^{-1}$$$. The division algorithm gives $$$M = qi+r$$$ with $$$0\leq r < i$$$ which means in particular that we know $$$r^{-1}$$$. Then to prove that $$$i^{-1}=(M-q)r^{-1}$$$, just multiply $$$i$$$ with it:

$$$i(M-q)r^{-1}=-iqr^{-1}=(r-M)r^{-1}=rr^{-1}=1$$$ (all equalities are modulo $$$M$$$).

→ Reply
»
5 years ago, # |
  Vote: I like it +8 Vote: I do not like it

From
M % i = M — (M / i) * i
We have
M % i = -(M / i) * i
Multiply 2 sides by (i^-1) * (M % i)^-1
(M % i) * (i^-1) * (M % i)^-1 = -(M / i) * i * (i^-1) * (M % i)^-1
Result
i^-1 = -(M / i) * (M % i)^-1

→ Reply
»
5 years ago, # |
← Rev. 3   Vote: I like it +5 Vote: I do not like it

If you assume M = i*p+r, The above equation reduces to, inv[i] = (M-p)*inv[r] = -p*inv[r].

You can see easily that this (-p*inv[r]) is indeed inv[i] as i*(-p*inv[r]) = (-i*p)*inv[r] = (r-M)*inv[r] = 1!

→ Reply
»
5 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Thank you guys very much <3 <3.

→ Reply
»
5 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

I had a related thought that is more understandable but a clunkier. For $$$a$$$ coprime to prime $$$p$$$, $$$a^1, a^2, \dots, a^{k-1} \pmod p$$$ is a sequence of all distinct numbers between 1 and $$$p-1$$$ (exercise: prove this).

Assume $$$p$$$ is an odd prime so we can let $$$a=2$$$. Then we can compute $$$a^1, a^2, \dots, a^{p-1} \pmod p$$$ and store in two arrays, one mapping $$$k \to a^k$$$ and the other $$$a^k \to k$$$ (all values are $$$<p$$$). Then the inverse of $$$a^k$$$ is then $$$a^{p-1-k}$$$. To find $$$x^{-1}$$$, we lookup its exponent $$$k$$$, compute new exponent $$$p-1-k$$$, then lookup $$$a^{p-1-k}$$$.

→ Reply