The patent badge is an abbreviated version of the USPTO patent document. The patent badge does contain a link to the full patent document.
The patent badge is an abbreviated version of the USPTO patent document. The patent badge covers the following: Patent number, Date patent was issued, Date patent was filed, Title of the patent, Applicant, Inventor, Assignee, Attorney firm, Primary examiner, Assistant examiner, CPCs, and Abstract. The patent badge does contain a link to the full patent document (in Adobe Acrobat format, aka pdf). To download or print any patent click here.
Patent No.:
Date of Patent:
Nov. 13, 2001
Filed:
Dec. 23, 1998
International Business Machines Corporation, Armonk, NY (US);
Abstract
An apparatus to calculate a remainder of B,modulo n at high speed with minimum hardware resources, while securing safety of a key comprises: a first circuit to execute a process of calculating B (mod n) and holding the calculation result B,and to repeat a process of shifting a holding value and calculating a value congruent to the shifted holding value modulo n and holding the calculation result; a first register for storing the B,as an initial value; a second circuit to cumulate the calculation result of the first circuit when a value of a bit at a predetermined position of the first register is equal to 1; a second register to store 1 as an initial value; a C output circuit to output C; a third circuit to cumulate the calculation result of the first circuit when an output value from said C output circuit is equal to 1 and a value of a bit at a predetermined position of the second register is equal to 1. The bit at the predetermined position of the first register and the second register shifts from LSB to MSB of their stored values. When a process for MSB of a value stored by the first register ends, a value congruent to the cumulated result in the second circuit modulo n is set as the holding value and stored into the first register, the output of the C output circuit changes to a value shifted from LSB to MSB of the C, and when the output of the C output circuit is 1, a value congruent to the cumulated result in the third circuit modulo n is stored in the second register.