mpz_powm and squaring modulo an integer

[Torbjorn Granlund]

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

  I looked at the code of mpz_powm and recognized that it calles one of hte
  tdiv_rq-functions (mpz or mpn I can not remember right now). 
  I saw that this function does a shift left on the divisor to move the most
  significant bit to fill the most significant bit in the limb with the
  highest value.
  This is done every time tdiv_rq is called, which also makes one additional
  copy of the divisor necessary. My idea is to do this shift left already in
  the powm function right before the actual calculation and do a shift left
  after the calculation is finished to avoid the overhead. Maybe this is even
  possible without changeing the tdiv-code.
  
  Do you think this could improve the performance significantly? I can't
  judge, because I don't know how many percent of the runtime this copy
  operations in tdiv_rq take.
  
You may want to build a profiled libgmp.  See --enable-profiling.

I suspect you'll gain just a percent or two by avoiding those shifts.

  BTW: if I understood the code correctly it looks if this shift left is
  necessary at all. If not it doesn't create a copy of the divisor. What is 
  the copy of the other number needed for? is it just to preserve the
  numerator? If so, would it be possible to drop this numerator, or is the
  copy also needed for technical reasons?

You need to multiply both the dividend and divisor by the same factor
in order to preserve the quotient.

-- 
Torbjörn