What's the time complexity of this modular inverse algorithm?
Разница между en4 и en5, 39 символ(ов) изменены
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 :)?

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en5 Английский duckladydinh 2023-01-07 19:49:32 39
en4 Английский duckladydinh 2023-01-07 19:48:41 2
en3 Английский duckladydinh 2023-01-07 19:48:25 2
en2 Английский duckladydinh 2023-01-07 19:07:42 5
en1 Английский duckladydinh 2023-01-07 19:07:21 838 Initial revision (published)