I am new to multipilcative inverse stuff.

Let say we need to calculate **multipilcative inverse** of (a^n) under modulo m.

Meaning, `(a^n)^-1 % m`

What I was thinking

we can use fermet little theorem such that now equation will become, (a^n)^(m-2) under modaulo m.

`(a^n)^-1 % m = (a^n)^m-2 under modulo m`

.

` = ( a^(n(m-2)) ) under modulo m`

.

But the problem is n and m are very big numbers, if I calculate n(m-2) this will surpass long . How can one solve this?

You can take the inverse and raise it to n, or do a^n mod m then find the inverse of that.

Assuming all necessary conditions for applying Fermatâ€™s Little Theorem hold, the given expression (a^{n})^{-1} \bmod m can be computed easily by first computing a^{n} \bmod m in \log_{2}{m} time, and then computing the inverse (again by exponentiation in \log_{2}{m} time), or as nicely mentioned by @everule1, it can be done in any order (first compute a^{-1} \bmod m and then raise it to power n).

Also, if m is not a *prime* (which is a condition for Fermatâ€™s Little Theorem), then also we can compute the modular multiplicative inverse using Extended Euclid Algorithm.

Hope that helps.

1 Like

compute (a)^n%m by binary exponentiation then find out mmi by fermat or whatever u want.