Patent ID: 7171437

Claim:
A power-residue calculating unit comprising: a first register group holding a first kind of data; a second register group holding a kind of data to be referred to concurrently with the data held in said first register group; a first internal bus connected to said first register group; a second internal bus connected to said second register group; a Montgomery multiplication residue calculation executing portion connected to said first and second internal buses for concurrently referring to values held in said first and second register groups and executing a Montgomery multiplication residue calculation; a power-residue calculation executing portion connected to said first and second internal buses and said Montgomery multiplication residue calculation executing portion for concurrently referring to values held in said first and second register groups, communicating data with said Montgomery multiplication residue calculation executing portion, and executing a power-residue calculation; and a pseudo calculation executing portion for executing in a pseudo manner an intermediate calculation process that can be omitted to obtain each calculation result of said Montgomery multiplication residue calculation and said power-residue calculation.