average number of calls of REDC
Paul Zimmermann
Paul.Zimmermann at loria.fr
Wed Sep 1 13:56:57 CEST 2004
From: Torbjorn Granlund <tege at swox.com>
Date: 30 Aug 2004 20:10:17 +0200
"Andreas Vetter" <AVetter at gmx.de> writes:
There is a little table in powm.c where the average number of calls of REDC
is listed, depending on the bitlength of the exponent and the width of the
sliding windows used. I wonder how how you got this table (only the testing
or is ther some math behind this?) an if it is possible to enlarge it
(perhaps somebody has a bigger one?!), because I want to determine the time
doing RSA en- and decryption with modulus > FFT_THRESHOLD (~9000) and
exponent almost of the same size. Therefore I need the time for
multiplication, the time for reduction and the number of reductions, which
is the same as the numbers of multiplications (somebody correct me if I'm
wrong).
I hope Paul can answer you here.
Here is that table:
/* average number of calls to redc for an exponent of n bits
with the sliding window algorithm of base 2^k: the optimal is
obtained for the value of k which minimizes 2^(k-1)+n/(k+1):
n\k 4 5 6 7 8
128 156* 159 171 200 261
256 309 307* 316 343 403
512 617 607* 610 632 688
1024 1231 1204 1195* 1207 1256
2048 2461 2399 2366 2360* 2396
4096 4918 4787 4707 4665* 4670
*/
The explanation is as follows: the sliding window algorithm needs to compute
all odd powers of at most k bits, which requires 2^(k-1) products.
The number of sliding blocks is about n/(k+1), which gives n/(k+1)-1
multiplications, and the number of squarings is n minus the width of the
largest block, i.e. about n - (k+1).
This gives a total of n - (k+1) + n/(k+1) - 1 + 2^(k-1).
Paul
More information about the gmp-discuss
mailing list