average number of calls of REDC

[Paul Zimmermann]

   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