mpz_invert function

[Torbjorn Granlund]

"Diego Sanchez Navarro" <diegosancheznavarro@hotmail.com> writes:

  Greetings everyone.

  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.

-- 
Torbjörn