# average number of calls of REDC

Torbjorn Granlund tege at swox.com
Mon Aug 30 20:10:17 CEST 2004

```"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.

Another question: Why is complexity of GMP's FFT multiplication
O(n^(k/(k-1))) and not O(n log(n)loglog(n)) as written by Knuth?
I understood FFT as the same as Schoenhage-Strassen algorithm!

Another question for Paul.

Last one: To reduce big integers, division is used. So for the division: I
haven't read the Burnikel/Ziegler paper (but I'm going to), but I want to
know, why you can't get a O(2M(N)) division, where M(N) is the time for NxN
multiplication, by simply inverting the divisor "q" as in the single limb
division, getting a expression like
0,00 ..(N-1 Zeros)..00THEN_N_SIGNIFICANTBITS
and then multiplying the significant bits with the most significant half of
the divident? I think, with some more (neglegable) work (o.K. in O(M(N)))
you could get a correct division.

There is work in progress in this area.  But Burnikel/Ziegler division will
still be used for some operand sizes.

Really last one: Everytime I use the speed-tester to determine the computing
time of Toom3 multiplication there is a time-jump (not in real time ;-) )
somewhere between 11000 ans 13000 bits, but not always at hte same bitlength
(I run that one several times). Anybody any ideas why?

Poor clock function on your computer?

--
Torbjörn
```