Fast exponentiation method by folding exponent in half
On average, the square-and-multiply method requires 1.5k multiplications to evaluate xE, where k is the bit length of E. Recently, Wu and Chang proposed an efficient method for computing xE, which needs 156k/128 multiplications. By folding the exponent E in half and combining Wu and Chang's method, we present a more efficient method for evaluating xE. On average, our new method needs only 149k/128 + 3 multiplications.