In prime characteristic p > 0, raising a sum a+b to the p-th power is more quickly done by simply computing ap and bp and adding them. The basic strategy 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 1.06369 seconds |
i4 : time fastExponentiation(321,f); -- used 0.00326535 seconds |
If an element in a ring of characteristic 0 is passed, fastExponentiation(n,f) simply computes fn in the usual way.