development of the runtime for powm-functions

Torbjorn Granlund tege at
Mon Nov 28 23:20:02 CET 2005

Juergen Bullinger <juergen.bullinger at> 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

O(m n log n)

where m is the size of the exponent and n is the size of the mod
(If a degenerate case where the base is very much larger than the
mod argument, its size will also affect the complexity.)


More information about the gmp-discuss mailing list