average number of calls of REDC
Andreas Vetter
AVetter at gmx.de
Wed Sep 1 16:48:50 CEST 2004
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
More information about the gmp-discuss
mailing list