squring modulo an integer and squaring in general
Paul Zimmermann
Paul.Zimmermann at loria.fr
Wed Feb 1 10:44:27 CET 2006
> 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
More information about the gmp-discuss
mailing list