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

[HELP] Explanation for calculate modular inverse of all number from 1 to N in O(n)
Автор Libraion, история, 5 лет назад, По-английски

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.

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

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

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$$$).

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

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

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

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!

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

Thank you guys very much <3 <3.

→ Ответить
»
5 лет назад, # |
← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

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}$$$.

→ Ответить