development of the runtime for powm-functions
Torbjorn Granlund
tege at swox.com
Mon Nov 28 23:20:02 CET 2005
Juergen Bullinger <juergen.bullinger at gmx.net> writes:
In other words, is it possible to say how long a powm with a numbers of
length 2n bits (for the exponent as well as the module with a fixed
base) takes if the runtime for the same operation with numbers of n bit
length is known?
The complexity of the mpz_powm implementation in GMP 4.1 is
2
O(m n log n)
where m is the size of the exponent and n is the size of the mod
argument.
(If a degenerate case where the base is very much larger than the
mod argument, its size will also affect the complexity.)
--
Torbjörn
More information about the gmp-discuss
mailing list