What is the time complexity of calculating the inverse of n recursively?

Revision en1, by Bellala, 2022-04-07 18:23:44

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?

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English Bellala 2022-04-07 18:23:44 399 Initial revision (published)