Fast exponentiation methodby folding exponent in half
Der‐Chyuan Lou, Chia‐Chen Chang · Electronics Letters · 1996
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.