development of the runtime for powm-functions

[Torbjorn Granlund]

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