then an addition-subtraction chain may be used to obtain even fewer total multiplications+divisions (where subtraction corresponds to division). However, the slowness of division compared to multiplication makes this technique unattractive in general. For exponentiation to negative integer powers, on the other hand, since one division is required anyway, an addition-subtraction chain is often beneficial. One such example is a−31, where computing 1/a31 by a shortest addition chain for a31 requires 7 multiplications and one division, whereas the shortest addition-subtraction chain requires 5 multiplications and one division: (addition-subtraction chain, 5 mults + 1 div). For exponentiation on elliptic curves, the inverse of a point (x, y) is available at no cost, since it is simply (x, −y), and therefore addition-subtraction chains are optimal in this context even for positive integer exponents. References Donald E. Knuth, The Art of Computer Programming, Volume 2: Seminumerical Algorithms, 3rd edition, §4.6.3 (Addison-Wesley: San Francisco, 1998). Daniel J. Bernstein, "Pippenger's Algorithm", to be incorporated into author's High-speed cryptography book. (2002) Addition chains Computer arithmetic algorithms Exponentials