average number of calls of REDC

[Andreas Vetter]

Thank you both for helping me with. I will read that sliding window stuff
again and I'm sure to understand your assumptions. Thats gonna get me
further. I've got another practical problem with the Thresholds of the
multiplication-algorithms. I changed them in gmp_mparam.h but I can't see
any difference in the compution time. I tried reconfigure with that new
thresholds but it doesn't work either :-(

Andreas


>    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
> 
> 
> 
> 

-- 
NEU: Bis zu 10 GB Speicher für e-mails & Dateien!
1 GB bereits bei GMX FreeMail http://www.gmx.net/de/go/mail