The patent badge is an abbreviated version of the USPTO patent document. The patent badge does contain a link to the full patent document.
The patent badge is an abbreviated version of the USPTO patent document. The patent badge covers the following: Patent number, Date patent was issued, Date patent was filed, Title of the patent, Applicant, Inventor, Assignee, Attorney firm, Primary examiner, Assistant examiner, CPCs, and Abstract. The patent badge does contain a link to the full patent document (in Adobe Acrobat format, aka pdf). To download or print any patent click here.
Patent No.:
Date of Patent:
Dec. 12, 2006
Filed:
Sep. 09, 2002
Marc Joye, Saint Zacharie, FR;
Pascal Paillier, Paris, FR;
Marc Joye, Saint Zacharie, FR;
Pascal Paillier, Paris, FR;
Gemplus, Gemenos Cedex, FR;
Abstract
A random prime number is generated within a predetermined interval by precalculating and storing a single value that functions as a universal parameter for generating prime numbers of any desired size. The value, π, is chosen as a product of k prime numbers. A number a is also chosen such that is co-prime with π. Once the values for π and a have been determined they can be stored and used for all subsequent iterations of the prime number generating algorithm. To generate a prime number, a random number x is chosen with uniform distribution, and a candidate prime number within the predetermined interval is calculated on the basis of the random number. This candidate is tested for primality, and returned as the result if it is prime. If the candidate is not prime, the random number x is multiplied by a, and used to generate a new candidate. This procedure is repeated, until the candidate is prime. Since a single value, namely π, needs to be precalculated, economies of storage are achieved. In addition, the interval of interest is approximated with a higher degree of resolution. Moreover, it is possible to utilize the same value of π for a number of different intervals.