摘要 |
PROBLEM TO BE SOLVED: To provide a prime number generation device, a program and a method, in which a second prime number having a form of polynomial of a first prime number, which is not limited to the prime number of a safe prime, is generated at high speed. SOLUTION: The first prime number p and the second prime number f(p) having the form of the polynomial f(p)(=a<SB>n</SB>×p<SP>n</SP>+a<SB>n-1</SB>×p<SP>n-1</SP>+...+a<SB>2</SB>×p<SP>2</SP>+a<SB>1</SB>×p+a<SB>0</SB>), where a constant term (a<SB>0</SB>) is not 0, which is calculated from the first prime number, are generated, and thereby, the second prime number f(p) having the form of the polynomial of the first prime number is generated without being limited by the prime number (2p+1) of the safe prime form. In addition to that, a percentage of performing a full-scale prime number judgment method which takes time is decreased by performing the full-scale prime number judgment including Fermats small theorem, after performing trial division which is calculated at high speed beforehand, and thereby, the first and the second prime numbers p and f(p) are generated at high speed. COPYRIGHT: (C)2007,JPO&INPIT
|