mpz_powm and squaring modulo an integer

[Paul Zimmermann]

>   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 ev=
> en
>   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.
>   =
> 
> I suspect you'll gain just a percent or two by avoiding those shifts.

I agree. A significant speedup could be obtained for large operands as follows:

- using the fact that the divisor is invariant (precomputing its inverse)

- using a subquadratic implementation of Montgomery's REDC, which can
  perform a modular reduction in 1.5 M(log m). See page 6 of
  <http://www.loria.fr/~zimmerma/papers/ecm-submitted.pdf>.

Paul Zimmermann