Semiconductor device and IC card

A semiconductor device comprising:

• a random number generator;
• a modulus generator;
• an exponent generator;
• a power residue calculating unit;
• and a determination unit, and determining primality of an input prime number candidate,
• wherein the random number generator generates a random number as a randomizing number,
• wherein the modulus generator generates a product of the prime number candidate and the randomizing number as a first integer,
• wherein the exponent generator generates a product of a number obtained by subtracting one from the prime number candidate and a number obtained by subtracting one from the randomizing number, as a second integer,
• wherein the power residue calculating unit carries out power residue calculation, with the first integer as a modulus and the second integer as an exponent, and
• wherein the determination unit determines primality of the prime number candidate based on an output of the power residue calculating unit.

A semiconductor device comprising:

• a random number generator;
• a randomizing number generator;
• a modulus generator;
• an exponent generator;
• a power residue calculating unit;
• and a determination unit, and determining primality of an input prime number candidate,
• wherein the random number generator generates a random number sequence,
• wherein the randomizing number generator generates a randomizing number by prime factor calculation, with an integer calculated based on the random number sequence as an exponent,
• wherein the modulus generator generates a first integer that is a product of the prime number candidate and the randomizing number,
• wherein the exponent generator generates a second integer,
• wherein the power residue calculating unit carries out power residue calculation, with the first integer as a modulus and the second integer as an exponent, and
• wherein the determination unit determines primality of the prime number candidate based on an output of the power residue calculating unit.

A semiconductor device comprising:

• a random number generator;
• a modulus generator;
• an exponent generator;
• a power residue calculating unit;
• and a determination unit, and determining primality of an input prime number candidate,
• wherein the random number generator generates a first random number as a randomizing number,
• wherein the modulus generator generates a product of the prime number candidate and the randomizing number as a first integer,
• wherein the exponent generator factorizes a product of a number obtained by subtracting one from the randomizing number and a number obtained by subtracting one from the prime number candidate into prime factors, calculates the maximum integer “s” and integer P′ satisfying an expression (r−1) (P−1)=2s P′, and generates the integer P′ as a second integer,
• wherein the power residue calculating unit carries out power residue calculation, with the first integer as a modulus and the second integer as an exponent, and
• wherein the determination unit determines primality of the prime number candidate based on an output of the power residue calculating unit.

A semiconductor device for carrying out primality determination including power residue calculation, said device comprising:

• a power residue calculating unit;
• and a determination unit, and determining primality of an input prime number candidate,
• wherein the power calculating unit carries out power residue calculation, with a product of the prime number candidate and a random number as a modulus of the power residue calculation, and
• wherein the device determines primality of the prime number candidate based on an output of the power residue calculating unit.