By duckladydinh, history, 18 months ago,

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

• +6

 » 18 months ago, # |   0 Auto comment: topic has been updated by duckladydinh (previous revision, new revision, compare).
 » 18 months ago, # |   0 Auto comment: topic has been updated by duckladydinh (previous revision, new revision, compare).
 » 18 months ago, # |   0 Auto comment: topic has been updated by duckladydinh (previous revision, new revision, compare).
 » 18 months ago, # |   0 Auto comment: topic has been updated by duckladydinh (previous revision, new revision, compare).
 » 18 months ago, # |   -14 I'm not an expert on the subject, but this is my template to calculate the modular inverse of a number using binary exponentiaton.  int binpow(int b){ // binary exponentiation long long n = MOD-2; // fermat's little theorem long long ans = 1; long long place = b; while(n){ // decompose n into binary representation if(n&1) ans = (ans * place)%MOD; place = (place*place)%MOD; n >>= 1; } return ans; } 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.
 » 18 months ago, # |   +12 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 int inv_mod(int a, int m) { assert(0
 » 18 months ago, # |   +10