I've always believed that getting the inverse of some integer n this way takes O(log(p)) time:
long long inv(long long n, long long p) {
if (n == 1) return 1;
return inv(p%n, p) * (p - p/n) % p;
}
But recently someone told me that it might be O(sqrt(p)).
So what is the correct time complexity?