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.
compute (a)^n%m by binary exponentiation then find out mmi by fermat or whatever u want.