squring modulo an integer and squaring in general

"Jürgen Bullinger" juergen.bullinger at gmx.net
Wed Feb 1 01:29:17 CET 2006

Hello all,

thank you Paul and Torbjorn for your replies to my last mails.
I looked at the docu. I guess the following expression in the gmp doc:

                \         b
     w[n] =     /     (-1) * x[i] * y[j]

mean the same as:
                ---                     ---
                \                       \
     w[n] =     /      x[i] * y[j]   -  /     x[i] * y[j]
                ---                     ---
               i+j=n                    i+j=2^k+n

Is this right?

>From what I read in the gmp docu so far I guess that a special purpose fft
implemenation for squaring integers would also need half of the limb
multiplications (similar to the discription of the baseline multiplication
algorithm about squaring). Is this right?
What do you think, is it worth the effort to do such an implementation? or
is the overall runtime of this limb-multiplications related to other
operations needed to do the fft multiplication too low?

Kind regards

DSL-Aktion wegen großer Nachfrage bis 28.2.2006 verlängert:
GMX DSL-Flatrate 1 Jahr kostenlos* http://www.gmx.net/de/go/dsl

More information about the gmp-discuss mailing list