Patent ID: 6317769
Filing Date: 2001-11-13
Classification: G06F

Abstract:
An apparatus for calculating B.sup.c (mod n), comprising:a first circuit for executing a process of calculating B (mod n) and holding the calculation result B1 and for repeating 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 said B1 as an initial value;a second circuit for cumulating the calculation result of said first circuit when a value of a bit at a predetermined position of said first register is equal to 1;a second register for storing 1 as an initial value;a C output circuit for outputting C;a third circuit for cumulating the calculation result of said 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 said second register is equal to 1;wherein the bit at the predetermined position of the first register and the second register shifts from LSB to MSB of their stored values; andwherein, when a process for MSB of a value stored by the first register ends,(a) a value congruent to the cumulated result in the second circuit modulo n is set as said holding value and stored into the first register,(b) the output of the C output circuit changes to a value shifted from LSB to MSB of the C, and(c) 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.