sec_invert performance

Torbjorn Granlund tg at
Tue Feb 4 20:26:59 UTC 2014

nisse at (Niels Möller) writes:

  So if you know that the modulo is prime (or has some other type of known
  factorization), using powm actually beats sec_invert for sizes up to 6
Assuming CRT application is for free, at least.

  I still puzzled why the ratio between sec_invert and gcdext doesn't
  approach some constant (I'd expect the ratio to start growing again for
  sizes above the threshold for subquadratic gcdext).
I don't find the ratio strange, it seems constant within reasonable

All linear-time functions really take Bn+C time, and quadratic-time
functions take An²+Bn+C, of course.  If the sec_invert function has
small B and/or C while gcdext has larger B and/or C, then the observed
pattern seem even more reasonable.  Do you agree?

Please encrypt, key id 0xC8601622

More information about the gmp-devel mailing list