proposal for optimized exponent reduction function

["Jürgen Bullinger"]

Hello,

in mpz/powm.c I saw, that euler-phi is used to reduce the exponent for small
modules if "REDUCE_EXPONENT" is defined.
I modified this function to take into account that for composite modules the
actual multiplicative order is a real divisor of euler-phi.

This modification makes use of the fact, that for a composite number of
the form m=p1^a1*p2^a2*.....pn^an
(ord_m b) is a divisor of lcm ((ord_{p1^a1} b), (ord_{p2^a2} b), ...,
(ord_{pn^an} b))

for all bases b 

ord_m b is the multiplicative order of b (mod m) and lcm the least common
multiple.

because (ord_{pi^ai} b) divides eulerPhi(pi^ai) for each 1<=i<=n and each
base b with gcd(b,m)=1

it follows that 

lcm ((ord_{p1^a1} b), (ord_{p2^a2} b), ..., (ord_{pn^an} b)) divides
lcm (eulerPhi(p1^a1), eulerPhi(p2^a2), ..., eulerPhi(pn^an))

So this reduction is applicable in all cases where also the eulerPhi
reduction is applicable.

I think it is not worth calling a least common multiple (lcm) to reduce the
exponent, so I just reduce some of the common factors 2 and 3 (but also not
all of them). For integers with x distinct prime factors this can reduce the
the exponent by a factor 6^(x-1).

I am not sure if this additional reduction saves a lot of time, but the
calculation is also about 20-30% faster, because I only use d = +/-1 (mod 6)
as for trial divisons.

I called the function pseudo_phi and created a little test program which
prints out timings and checks the results.
Basically for the checks it makes use of the theorem:

b^(ord_m b)=1 (mod m)

I append the file to this mail. If you are interested you can compile it
using

gcc -O3 -o phitest phitest.c -lgmp

please note that the actual function is called pseudo_phi. It doesn't need
anything else in the source file. All the other functions and defines
besides pseudo_phi are just needed to test it.

kind 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
-------------- next part --------------
A non-text attachment was scrubbed...
Name: phitest.c
Type: text/x-csrc
Size: 7914 bytes
Desc: not available
Url : http://gmplib.org/list-archives/gmp-discuss/attachments/20060212/63d89448/phitest.bin