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