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.net/blog/entry/101672