Encryption devices and encryption key generation method, as well as the prime generator and prime number generating method

摘要

PROBLEM TO BE SOLVED: To reduce a necessary memory capacity by sequentially generating larger prime numbers based on a prime number not exceeding 2n bits and generating a second prime number having a specified bit length. ;SOLUTION: A random number generation part 5 generates an odd number having double bit length of a word size, and an arithmetic operation part 4 performs division for trial by using a prime number not larger than word size of the prime number table. When a generated odd number cannot be divided by all the prime numbers in the prime number table, this odd number is judged as a prime number. A parameter (i) of the following processing loop is set to zero (0). Based on a prime number F_i, a random number generation part 5 generates a random number R_i satisfying R_iF_i to create a prime number candidate N_i expressed as N_i=2R_iF_i+1. If this can be divided by prime numbers in the prime number table, N_i is judged as a composite number, and R_i is re-generated by leaving F_i value at it is for generating a new prime candidate N_i, and it is calculated whether or not a fixed (a_i) satisfies a fixed equation. R_i is increased in the bit length and adjusted, and the prime number N_i is obtained when the prime number candidate N_i has reached a fixed bit length.;COPYRIGHT: (C)1998,JPO