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.00119214 seconds |
i4 : time fastExponentiation(321, f); -- used 0.00155503 seconds |
If an element in a ring of characteristic 0 is passed, fastExponentiation(n, f) simply computes f n in the usual way.