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

Правка en1, от 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?

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский Bellala 2022-04-07 18:23:44 399 Initial revision (published)