mpz_powm and squaring modulo an integer

["Jürgen Bullinger"]

Hello all,

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.

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?

regards Juergen


-- 
Lust, ein paar Euro nebenbei zu verdienen? Ohne Kosten, ohne Risiko!
Satte Provisionen für GMX Partner: http://www.gmx.net/de/go/partner