Completely Redundant Modular Exponentiation by Operand Changing

摘要

A new algorithm for modular exponentiation of long integers is presented. It is based on a modular multiplication method where the operands are kept in redundant representation during the whole exponentiation process. In contrast to the algorithms previously known, the multiplication is performed by modification of one of the operands in each multiply-add-step. This allows to speedup the individual operations within the loop of the multiplication by access to a small lookup table whose entries are not depending on the operands of the multiplication.