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

Auto comment: topic has been updated by duckladydinh (previous revision, new revision, compare).Auto comment: topic has been updated by duckladydinh (previous revision, new revision, compare).Auto comment: topic has been updated by duckladydinh (previous revision, new revision, compare).Auto comment: topic has been updated by duckladydinh (previous revision, new revision, compare).I'm not an expert on the subject, but this is my template to calculate the modular inverse of a number using binary exponentiaton.

I claim the time complexity is O(log n) because we bitshift n by >>= 1 for every iteration. For a 32 bit number, we shift n a maximum of 32 times and for a 64 bit number, we shift it by a maximum of 64 times.

`Euclidean algorithm is popular for finding the modular inverse but I find it a bit hard to implement.`

well, you can shrink it to following

it looks similar to method you described; work for every valid pair (your bad at mod=8 i=3); and run obviously in $$$O(logm)$$$.

https://codeforces.com/blog/entry/101672