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