development of the runtime for powm-functions

Juergen Bullinger juergen.bullinger at
Sat Nov 26 08:46:17 CET 2005


are there any estimations about the "development" of the runtime for
powm-functions depending on the Size of numbers.

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?

>From a logical point of view I think the time should multiply by c*2^3
(with c about 1) every time the size of the numbers is doubled. Because
I think for plain squaring it should multiply by 2^2.
On the outher hand I think that the modulo divisions develop slower.

Are my assumptions right? 
Are there maybe more accurate estimations?

Thank you in advance

Juergen Bullinger <juergen.bullinger at>

More information about the gmp-discuss mailing list