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

Автор ricardogg, история, 5 лет назад, По-английски

I was trying to find a solution to precompute for each $$$i, inv_i = (k^i)^{-1} \mod{p}$$$. I know the standard method using binary exponention, that is $$$inv_i = (k^i)^{p - 2}$$$ however this precomputation works in $$$O(N \log P)$$$. Is there any faster method to do this.

I know that if we instead precompute $$$inv_i = i^{-1} \mod{p}$$$ we can use this code to do this in $$$O(N)$$$, however I'm not sure how to modify this to work for any $$$k^i$$$.

Here is the code we can use for computing $$$inv_i = i^{-1} \mod{p}$$$

Edit: I just noticed that we can rewrite $$$inv_i = inv_{i-1} * k^{-1} \mod{p}$$$. So we just compute $$$k^{\mod - 2}$$$ and then use this relation.

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

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

Yes, we can do the precomputation in $$$O(N)$$$
Calculate $$$inverse = k^{~p-2} \mod p$$$ and initialize $$$inv_1 = inverse$$$.
And for each $$$i > 1$$$, assign $$$inv_i = (inv_{i-1} * inverse) \mod p$$$.