average number of calls of REDC

Andreas Vetter AVetter at gmx.de
Mon Aug 30 19:57:31 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

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

More information about the gmp-discuss mailing list