next | previous | forward | backward | up | top | index | toc | Macaulay2 web site
TestIdeals :: fastExponentiation

fastExponentiation -- compute a power of an element in a ring of positive characteristic quickly

Synopsis

Description

In prime characteristic p > 0, raising a sum a + b to the pth power is more quickly done by simply computing ap and bp and adding them. The basic strategy behind fastExponentiation is to break up the exponent into its base p expansion, and then use the exponent rules. For example, (x + y)3p2 + 5p + 2 = ((x + y)3)p2((x + y)5)p(x + y)2.

i1 : R = ZZ/5[x];
i2 : f = sum(10, i -> x^i);
i3 : time f^321;
     -- used 0.00277022 seconds
i4 : time fastExponentiation(321, f);
     -- used 0.00352372 seconds

If an element in a ring of characteristic 0 is passed, fastExponentiation(n, f) simply computes f n in the usual way.

Ways to use fastExponentiation :