average number of calls of REDC

[Andreas Vetter]

Hello!
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).

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!

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.

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?

I hope there are people out there who can help me
thanks 
Andreas Vetter

-- 
Supergünstige DSL-Tarife + WLAN-Router für 0,- EUR*
Jetzt zu GMX wechseln und sparen http://www.gmx.net/de/go/dsl