New Residue Arithmetic Based Barrett Algorithms: Modular Integer Computations
| Autor: | Hanshen Xiao, Hari Krishna Garg |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2016 |
| Předmět: |
General Computer Science
Computational complexity theory Computer science Computation Polynomial remainder theorem Cryptography 02 engineering and technology chinese remainder theorem (CRT) Integer Barrett algorithm (BA) 0202 electrical engineering electronic engineering information engineering General Materials Science Hardware_ARITHMETICANDLOGICSTRUCTURES Chinese remainder theorem Residue (complex analysis) Modular arithmetic business.industry modular multiplication (MoM) 020208 electrical & electronic engineering General Engineering Barrett modular multiplication (BMM) Modular design 020202 computer hardware & architecture lcsh:Electrical engineering. Electronics. Nuclear engineering business montgomery multiplication (MM) Algorithm residue number systems (RNS) lcsh:TK1-9971 |
| Zdroj: | IEEE Access, Vol 4, Pp 4882-4890 (2016) |
| ISSN: | 2169-3536 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|