squring modulo an integer and squaring in general

[Paul Zimmermann]

> 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]
>                 ---
>             i+j=b*2^k+n
>                b=0,1
> 
> 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?

Yes.

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

There is already a special fft code for squaring. There is no public
squaring function in GMP, however squaring is recognized internally
by the different multiplication functions, by a simple pointer comparison.

Paul