Prime number generating device, prime number generating method, and computer readable storage medium

• US 20110142231A1
• Filed: 12/08/2010
• Published: 06/16/2011
• Est. Priority Date: 12/11/2009
• Status: Abandoned Application

• Current Assignee: Oki Semiconductor Company Limited (ROHM Co., Ltd.)
• Original Assignee: Oki Semiconductor Company Limited (ROHM Co., Ltd.)
• Inventors: Takeda, Koichi
• Application Number:
  US12/926,775
• Publication Number:
  US 20110142231A1
• Time in Patent Office: Days
• US Class Current: 380/30
• CPC Class Codes: G06F 2207/7204 Prime number generation or prime number testing
• CPC Class Codes: G06F 7/72 using residue arithmetic
• CPC Class Codes: H04L 2209/56 Financial cryptography, e.g. electronic payment or e-cash
• CPC Class Codes: H04L 9/3033 details relating to pseudo-prime or prime number generation, e.g. primality test

Abstract

A prime number generating device is provided that includes a computation unit capable of performing at least addition and division on data of a predetermined number of bits or less; a prime number candidate data generating unit that generates prime number candidate data with a larger number of bits than the predetermined number of bits; a partitioned prime number candidate data generating unit that generates a plurality of partitioned prime number candidate data elements by partitioning the prime number candidate data; and a determination data generating unit that generates determination data for determining whether or not the prime number candidate expressed by the prime number candidate data is a composite number by using the computation unit to add together the respective plurality of partitioned prime number candidate data elements.

Claims

1. A prime number generating device comprising:

a computation unit adapted to performing at least addition and division on data of a predetermined number of bits or less;

a prime number candidate data generating unit that generates prime number candidate data expressing a prime number candidate with a larger number of bits than the predetermined number of bits;

a partitioned prime number candidate data generating unit that generates a plurality of partitioned prime number candidate data elements by partitioning the prime number candidate data generated by the prime number candidate data generating unit to give data that is of the predetermined number of bits or less;

a determination data generating unit that generates determination data for determining whether or not the prime number candidate expressed by the prime number candidate data is a composite number, by using the computation unit to add together the respective plurality of partitioned prime number candidate data elements generated by the partitioned prime number candidate data generating unit;

a prime number testing unit that performs primality testing on the prime number candidate data, in cases in which it is determined for at least one prime number that the prime number candidate is not a multiple of the at least one prime number, by the computation unit dividing the at least one prime number into the determination data generated by the determination data generating unit; and

an output unit that outputs the prime number candidate data as a prime number when the prime number candidate is determined to be a prime number by the prime number testing unit.

2. The prime number generating device of claim 1, wherein:

the computation unit is further adapted to at least one operation of modulo operation, shift operation or sign change operation; and

the determination data generating unit generates the determination data by adding together respective data elements obtained by the computation unit using the at least one operation of modulo operation, shift operation, or sign change operation on the partitioned prime number candidate data elements.

3. A prime number generating method in a prime number generating device comprising a computation unit adapted to performing at least addition and division on data of a predetermined number of bits or less, the prime number generating method comprising:

generating prime number candidate data expressing a prime number candidate with a larger number of bits than the predetermined number of bits;

generating a plurality of partitioned prime number candidate data elements by partitioning the prime number candidate data to give data that is of the predetermined number of bits or less;

generating determination data for determining whether or not the prime number candidate expressed by the prime number candidate data is a composite number by the computation unit adding together the respective plurality of partitioned prime number candidate data elements;

performing primality testing on the prime number candidate data, in cases in which it is determined for at least one prime number that the prime number candidate is not a multiple of the at least one prime number, by the computation unit dividing the at least one prime number into the determination data; and

outputting the prime number candidate data as a prime number when the prime number candidate is determined to be a prime number.

4. The prime number generating method of claim 3, wherein the

computation unit is further adapted to at least one operation of modulo operation, shift operation or sign change operation;

and

determination data generating includes generating determination data by adding together respective data elements obtained by the computation unit using the at least one operation of modulo operation, shift operation, or sign change operation on the partitioned prime number candidate data elements.

5. A non-transitory computer readable storage medium storing a program for executing prime number generation processing in a prime number generating device comprising a computation unit capable of performing at least addition and division on data of a predetermined number of bits or less, the prime number generating method comprising:

generating prime number candidate data expressing a prime number candidate with a larger number of bits than the predetermined number of bits;

generating a plurality of partitioned prime number candidate data elements by partitioning the prime number candidate data to give data that is of the predetermined number of bits or less;

generating determination data for determining whether or not the prime number candidate expressed by the prime number candidate data is a composite number by the computation unit adding together the respective plurality of partitioned prime number candidate data elements;

performing primality testing on the prime number candidate data, in cases in which it is determined for at least one prime number that the prime number candidate is not a composite number having the at least one prime number as a factor, by the computation unit dividing the at least one prime number into the determination data; and

outputting the prime number candidate data as a prime number when the prime number candidate is determined to be a prime number.

6. The prime number generating method of claim 5, wherein the

computation unit is further capable of at least one operation of modulo operation, shift operation or sign change operation;

and

determination data generating in the prime number generating processing includes generating determination data by adding together respective data elements obtained by the computation unit using the at least one operation of modulo operation, shift operation, or sign change operation on the partitioned prime number candidate data elements.