What's the time complexity of this modular inverse algorithm?

Revision en5, by duckladydinh, 2023-01-07 19:49:32

Hi

Euclidean algorithm is popular for finding the modular inverse but I find it a bit hard to implement. Instead, the following algorithm is much simpler. Let's call $$$f(i)$$$ the modular inverse of $$$i$$$ with respect to $$$m$$$

$$$ \begin{align*} m = ki + r & \implies 0 && \equiv && ki + r & \mod m \\ & \iff r && \equiv && -ki & \mod m \\ & \iff \frac{1}{i} && \equiv && -k(\frac{1}{r}) & \mod m \\ & \implies f(i) && = && (m-m/i)f(m \mod i) \mod m \end{align*} $$$

This method is often used in computing modular inverse for a range of numbers and much easier to implement to my taste BUT... what's the time complexity of this algorithm for computing a single modular inverse? I guess it's $$$O(logn)$$$ but my skill is too low to prove it :(.

Any math expert can help :)?

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en5 English duckladydinh 2023-01-07 19:49:32 39
en4 English duckladydinh 2023-01-07 19:48:41 2
en3 English duckladydinh 2023-01-07 19:48:25 2
en2 English duckladydinh 2023-01-07 19:07:42 5
en1 English duckladydinh 2023-01-07 19:07:21 838 Initial revision (published)