Exponentiation using division chains

Exponentiation may be performed faster than the traditional square-and-multiply method by iteratively reducing the exponent modulo numbers which themselves require few multiplications, such as those with few non-zero bits. For a suitable choice of such divisors, this reduces the expected number of non-squaring multiplications by over half at the cost of a single extra register. The method is applicable to exponentiation in any multiplicative group where squaring is as expensive as multiplication and not cheaper than integer division. In particular, both hardware and software implementations of the RSA crypto-system can benefit