New Residue Arithmetic Based Barrett Algorithms: Modular Integer Computations

Abstract

In this paper, we derive new computational techniques for residue number systems (RNSs)-based Barrett algorithm (BA). The focus of this paper is an algorithm that carries out the entire computation using only modular arithmetic without conversion to large integers via the Chinese remainder theorem. It also avoids the computationally expensive scaling-rounding operation required in the earlier work. There are two parts to this paper. First, we set up a new BA using two constants other than powers of two. Second, an RNS-based BA is described. A complete mathematical framework is described including proofs of the various steps in the computations and the validity of results. Third, we present a computational algorithm for RNS-based BA. Fourth, the RNS-based BA is used as a basis for new RNS-based algorithms for MoM and MoE. The applications we are dealing with are in the area of cryptography.

Keywords

• Barrett algorithm (BA)
• montgomery multiplication (MM)
• residue number systems (RNS)
• chinese remainder theorem (CRT)
• Barrett modular multiplication (BMM)
• modular multiplication (MoM)