How to precompute modular inverse for given k for each k^i

Revision en3, by ricardogg, 2019-07-24 12:40:28

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.

Tags algebra, #math, modular arithmetic, modular inverse

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English ricardogg 2019-07-24 12:40:28 4 Corrected math formula
en2 English ricardogg 2019-07-24 12:39:46 142
en1 English ricardogg 2019-07-24 12:36:45 622 Initial revision (published)