mpz_powm and squaring modulo an integer
Paul Zimmermann
Paul.Zimmermann at loria.fr
Mon Jan 30 14:42:17 CET 2006
> 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
More information about the gmp-discuss
mailing list