A Parity Checker for a Large RNS Numbers Based on Montgomery Reduction Method

Taek-Won KWON  Jun-Rim CHOI  

IEICE TRANSACTIONS on Electronics   Vol.E88-C   No.9   pp.1880-1885
Publication Date: 2005/09/01
Online ISSN: 
DOI: 10.1093/ietele/e88-c.9.1880
Print ISSN: 0916-8516
Type of Manuscript: PAPER
Category: Electronic Circuits
residue number systems(RNS),  Chinese remainder theorem(CRT),  Montgomery reduction method,  parity checker,  

Full Text: PDF>>
Buy this Article

Fast and simple algorithm of a parity checker for a large residue numbers is presented. A new set of RNS moduli with 2r-(2l1) form for fast modular multiplication is proposed. The proposed RNS moduli has a large dynamic range for a large RNS number. The parity of a residue number can be checked by the Chinese remainder theorem (CRT). A CRT-based parity checker is simply organized by the Montgomery reduction method (MRM), implemented by using multipliers and the carry-save adder array. We present a fast parity checker with minimal hardware processed in three clock cycles for 32-bit RNS modulus set.