development of the runtime for powm-functions
juergen.bullinger at gmx.net
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 gmx.net>
More information about the gmp-discuss