tg at gmplib.org
Tue Feb 4 20:26:59 UTC 2014
nisse at lysator.liu.se (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