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 :)?
↵
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 :)?
