# 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

```