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

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?


More information about the gmp-discuss mailing list