V. Bunimov and M. Schimmler (Germany)
modular exponentiation, modular multiplication, carry save adder, computer arithmetic, logarithmic complexity
A new algorithm for modular multiplication suitable for an optimal modular exponentiation is given. It is optimised with respect to time complexity. Each modular multiplication is computed with time complexity of O(log n). The time complexity of modular exponentiation is O(n*log n). Before executing the first modular multiplication a lookup table is generated containing values that allow for an efficient reduction with respect to the modulus. These values can be used for all modular multiplications. The multiplication is calculated by parallel additions. It is shown how the new algorithm can be efficiently implemented in hardware using carry save adders and one carry lookahead adder.
Important Links:
Go Back
