squaring modulo an integer

Torbjorn Granlund tege at swox.com
Mon Jan 30 14:29:37 CET 2006

"Jürgen Bullinger" <juergen.bullinger at gmx.net> writes:

  I have another question.
  Are there special routines in gmp to do squaring modulo an integer?


  If not, what do you think, are there any performance improvements possible
  squaring numbers with a special purpose function (in comparison to mpz_powm
  or a multiplication algorithm modulo an integer ?mpz_mulm?)?

At the low level, special squaring code will be used for mpz(r,a,a).
See mpn_mul and mpn_mul_n.

  Is there a good introduction to fft-multiplication algorithms as used in
  gmp on the web?

I don't know.  Hopefully smoebody else can answer.


More information about the gmp-discuss mailing list