duckladydinh's blog

What's the time complexity of this modular inverse algorithm?
By duckladydinh, history, 16 months ago, In English

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

  • Vote: I like it
  • +6
  • Vote: I do not like it

»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by duckladydinh (previous revision, new revision, compare).

→ Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by duckladydinh (previous revision, new revision, compare).

→ Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by duckladydinh (previous revision, new revision, compare).

→ Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by duckladydinh (previous revision, new revision, compare).

→ Reply
»
16 months ago, # |
  Vote: I like it -14 Vote: I do not like it

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.

→ Reply
»
16 months ago, # |
  Vote: I like it +12 Vote: I do not like it

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<a); assert(a<m);
	return a==1 ? 1 : m - (int64_t)m * inv_mod(m%a, a) / a;
}

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)$$$.

→ Reply
»
16 months ago, # |
  Vote: I like it +10 Vote: I do not like it

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

→ Reply