12 Nov 2002 09:39:55 +0100
"Diego Sanchez Navarro" <firstname.lastname@example.org> writes:
I am writing a paper investigating different alternatives of
calculating inverses of large numbers modulo a similarly large
number (several thousand bits long). I did not find details on the
GMP manual about the workings of the mpz_invert function. What
algorithm does it use? Is using it the same as using the mpz_gcdext
algorithm to calculate the inverse, or is it optimized in any way?
Thank you very much in advance for your help.
It uses Lehmer's algorithm just like mpz_gcdext.
The execution time is O(n^2).
It saves a little time compared to mpz_gcdext by not
computing both s and t in gcd(u,v) = u*s+v*t.