# average number of calls of REDC

Paul Zimmermann Paul.Zimmermann at loria.fr
Tue Aug 31 18:28:53 CEST 2004

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

I'll try...

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.

It is indeed O(n^(k/(k-1))), but since k varies with n, this gives
O(n log(n)loglog(n)).

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.

What you describe is known as Barrett's division. If the inverse of the
divisor is known, you can indeed perform a division (with remainder) in
2*M(n) [in fact two short products]. But computing q=1/d costs about 3*M(n),
so this will be interesting only when the same divisor d is used many times,
and currently gmp does not enable the user to cache 1/d.

Paul Zimmermann
```