faster powm

Jason Moxham J.L.Moxham@maths.soton.ac.uk
Wed, 12 Mar 2003 04:07:46 +0000


At

http://217.35.81.229/gmp/gmp_plus.html

is a faster powm function eg at 750,000 decimal digits it's about 60% fas=
ter=20
than mpz_powm and if you have the time even faster for larger ones.

Note: It's a large download 1.7M , as it includes some other things=20

Basically its a mpn based sliding base 2^k with barrett reduction .

For small values it is slower than the existing mpz_powm , all I need to =
do is=20
add a basecase redc to sort this out , which is very easy.

I chose barrett reduction over redc reduction , because I have other uses=
 for=20
this for which redc is no good (ie I need to test divisibility and/or siz=
e of=20
residues), and powm is a good test case.

Jason