Patent ID: 6546104
Filing Date: 2003-04-08
Classification: G06F

Abstract:
A Montgomery reduction apparatus for receiving positive integers C and p and calculating D=CÂ·Râˆ’1 mod p by using R defined as R=2n using an integer n falling within a range n&gE;L with a bit length being represented by L when p is expressed in binary notation, comprising:an (&agr;, &bgr;) extraction section for calculating an integer pair (&agr;, &bgr;) satisfying C=&agr;R+&bgr; on the basis of C and R; a multiplication section for obtaining &egr;&bgr; by multiplying &egr; satisfying Râˆ’1=&egr;(mod p) and &bgr; calculated by said (&agr;, &bgr;) extraction section; an addition section for obtaining &agr;+&egr;&bgr; by adding &agr; calculated by said (&agr;, &bgr;) extraction section and &egr;&bgr; calculated by said multiplication section; and a calculation section for obtaining a remainder D=&agr;+&bgr;Â·&egr;(mod p) which is congruent to &agr;+&egr;&bgr; obtained by said addition section with respect to p as a modulus and is not more than p.