Efficient exponentiation is a fundamental task in several areas, including computer algebra and cryptography. Fast algorithms for this problem are presented. One of them is faster than allowed by a lower bound on the complexity of general exponentiation; the trick is a clever choice of data structure in a special situation. These methods work very well in software, and we also mention a hardware implementation on an FPGA.