Efficient modular arithmetics and architectures using residue number system

利用餘數系統的高效模運算及體系結構

Student thesis: Doctoral Thesis

View graph of relations

Author(s)

  • Xiaoxu YAO

Related Research Unit(s)

Detail(s)

Awarding Institution
Supervisors/Advisors
Award date14 Feb 2014

Abstract

Residue Number System (RNS) represents a large integer by a batch of small integers, an d the computation in RNS is distributed into several independent rings with small sizes. Due to this nature, RNS is proposed to perform modular arithmetics, and parallel architectures are available to accelerate the computation. However, one step in RNS modular multiplication, namely base extension, is of quadratic complexity, and therefore, the performance bottleneck of an RNS modular processor. In this thesis, we observe the importance of the RNS parameter selection to the modular arithmetics, especially to the base extension step. With the careful selection, the sizes of the intermediate operands are shrunk, and the complexity of the RNS modular multiplication is sub-quadratic. By theoretic analysis, we provide the optimal parameter set and the corresponding asymptotic complexity expression. However, the novel RNS computation may still encounter long carry propagation, which probably prevents higher computation speed. To overcome this carry problem, we first check the availability of redundant representations in the RNS arithmetics, and then propose the residue and redundant number system (R2NS). In an R2NS, the carry propagation is restricted within 1 bit or a machine word, and therefore, the speed/frequency performance of a system is guaranteed. The corresponding architectures are designed to realize the novel RNS and R2NS modular arithmetics without destroying the parallelism. Several configurations are proposed, so that the architecture can satisfy different application scenarios by adjusting the depth of pipeline, the degree of parallelism, and the constrains on time/area/power, etc. Modular arithmetics have numerous applications, and our major target is for public-key cryptography. We employ the proposed modular architectures to perform the public-key cryptographic algorithms, including Rivest-Shamir-Adleman, elliptic curve cryptography, and pairing-based cryptography. The implementation results confirm the advantages of the novel RNS and R2NS modular arithmetics.

    Research areas

  • Modular arithmetic