METHOD OF GENERATING PROVEN PRIME NUMBERS SUITABLE FOR BEING IMPLEMENTED IN A SMART CARD

摘要

The invention relates to a method for generating a prime number, implemented in an electronic device, the method including steps of generating a prime number from another prime number using the formula Pr=2P·R+1, where P is a prime number having a number of bits lower than that of the candidate prime number, and R is an integer, and applying the Pocklington primality test to the candidate prime number, the candidate prime number being proven if it passes the Pocklington test. According to the invention, the size in number of bits of the candidate prime number is equal to three times the size of the prime number, to within one unit, the generated candidate prime number being retained as candidate prime number only if the quotient of the integer division of the integer by the prime number is odd.

主权项

1. An encryption method implemented in an electronic device, the method comprising steps of:
generating a candidate prime number from another prime number using the following formula:
Pr=2P·R+1where Pr is the candidate prime number, P is a prime number having a number of bits lower than a desired number of bits of the candidate prime number, and R is an integer,
applying the Pocklington primality test to the candidate prime number, and supplying the candidate prime number as proven prime number if it passes the Pocklington test, wherein the size in number of bits of the candidate prime number is equal to three times the size of the prime number, to within one unit, the method comprising steps of calculating a quotient of an integer division of the integer by the prime number, and of rejecting the generated candidate prime number if the quotient of the integer division of the integer by the prime number is even.