proposal for optimized exponent reduction function
"Jürgen Bullinger"
juergen.bullinger at gmx.net
Sun Feb 12 02:48:27 CET 2006
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
More information about the gmp-discuss
mailing list