Exponentiation arithmetic unit, exponentiation remainder arithmetic unit, elliptic power multiple arithmetic unit, arrangement of those methods, and recording medium

摘要

PROBLEM TO BE SOLVED: To reduce the size of a power holding area by shifting positions of bits which are to be read out next from a bit string storage means from an upper bit side to a lower bit side except a sign bit. ;SOLUTION: An exponent value holding register 201 has a width in which 2 is added to the number (n) of bits of an exponent value. At the input 202 of an initial vale, an input (k) is inputted and an exponent value judging part 203 classifies bit patterns of upper 4 bits of the exponent value holding register 201 into four kinds of types and an exponent value transforming part 204 performs tranformations of bit patterns of the upper 4 bits of the register 201. An exponent value shifter 205 shifts bits other than the most significant bit of the register 201 to the left by one bit. In this case, a corresponding bit string in a bit string storage means is updated with the generated bit sting data by specifying the calculating method of a number A which is to be exponentiated on the basis of bit string data to be read out and next respective means are made repeatingly operate by (n+1) times while sifting positions of bits which are to be read out next from the upper bit side to the lower bit side except the sign bit.;COPYRIGHT: (C)2000,JPO