[prev in list] [next in list] [prev in thread] [next in thread] 

List:       gmp-discuss
Subject:    development of the runtime for powm-functions
From:       tege () swox ! com (Torbjorn Granlund)
Date:       2005-11-28 22:20:02
Message-ID: 86oe44xvn1.fsf () king ! swox ! se
[Download RAW message or body]

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

[prev in list] [next in list] [prev in thread] [next in thread]