Another look at some fast modular arithmetic methods

Abstract

In this work we re-examine a modular multiplication and a modular exponentiation method. The multiplication method, proposed by Hayashi in 1998, uses knowledge of the factorization of both N + 1 and N + 2 to compute a multiplication modulo N. If both N + 1 and N + 2 can be factored into k equally sized relatively prime factors then the computations are done modulo each of the factors and then combined using the Chinese Remainder Theorem. It was suggested that the (asymptotic) computational costs of the method is 1/k of simply multiplying and reducing modulo N. We show, however, that the computational costs of the method is (asymptotically) at least as costly as simply multiplying and reducing modulo N for both squarings and general multiplications when efficient arithmetic is used. The exponentiation method, proposed by Hwang, Su, Yeh and Chen in 2005, is based on Hayashi's method and uses knowledge of the factorization of P + 1 and P – 1 to compute an exponentiation modulo an odd prime P. We begin by showing that the method cannot be used as a general purpose exponentiation method and then modify the method so that it can work as a general purpose modular multiplication method. Like Hayashi's method, however, this method is at best (asymptotically) only as efficient as simply multiplying and reducing modulo P.

Keywords

• fast modular arithmetic
• modular exponentiation