METHOD FOR GENERATING PRIME NUMBERS PROVEN SUITABLE FOR CHIP CARDS

摘要

The invention relates to a method for generating prime numbers which is implemented in an electronic device (DV) wherein the method includes steps of: calculating a candidate prime number (Pr) having a number of bits (L) using the formula Pr = 2P × R + 1 wherein P is a prime number and R is an integer; using the Pocklington primality test on the candidate prime number; rejecting the candidate prime number if it fails the Pocklington test; and generating the integer (R) from a multiplicative inverse (X) belonging to a set of multiplicative inverse elements modulo the product (Pv) of numbers (Qj) belonging to a group of small prime numbers greater than 2 so that the candidate prime number (Pr) is not divisible by any of the numbers from the group. The prime number P has a number of bits equal to a bit near one half or one third the number of bits of the candidate prime number.