average number of calls of REDC

[Torbjorn Granlund]

"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