Fast exponentiation method obtained by folding the exponent in half

On average, the square-and-multiply method requires 1.5 k multiplications to evaluate χ^E, where k is the bit length of E. Recently, Wu and Chang (see ibid., vol. 31, no. 20, p. 1738-9, 1995) proposed an efficient method for computing χ^E, which needs 156 k/128 multiplications. By folding the exponent E in half and combining Wu and Chang´s method, we present a more efficient method for evaluating χ^E. On average, our new method needs only 149 k/128+3 multiplications