average number of calls of REDC

[Paul Zimmermann]

     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