Computer-implemented method for fast generation and testing of probable prime numbers for cryptographic applications

• US 20030235299A1
• Filed: 06/21/2002
• Published: 12/25/2003
• Est. Priority Date: 06/21/2002
• Status: Active Grant

• Current Assignee: Rambus Inc.
• Original Assignee: Atmel Corporation (Microchip Technology Incorporated)
• Inventors: Dupaquis, Vincent
• Granted Patent: US 6,718,536 B2
• Time in Patent Office: Days
• US Class Current: 380/30
• CPC Class Codes: G06F 2207/7204 Prime number generation or prime number testing
• CPC Class Codes: G06F 7/72 using residue arithmetic
• CPC Class Codes: H04L 9/3033 details relating to pseudo-prime or prime number generation, e.g. primality test

Abstract

A computer program provides fast generation and testing of probable prime numbers for cryptographic applications. The program instructions executed on computer hardware execute steps that include a smart increment program function that finds successive candidates using a table of congruent values that are relatively prime to a selected set of very small primes do identify an increment to the next candidate, thereby sieving out about ¾ths of the really obvious components that don'"'"'t need to be subjected to trial division. The program instructions also include a small primes testing program function that speeds trial division against a list of small primes by carrying out the division on modular reduced values rather than the very large candidates themselves. Only the about 10% of the candidates that pass the small primes test will then be subjected to more rigorous, but time consuming, probable primality tests.

Claims

1. A computer-implemented cryptography program stored on a hardware-readable medium, said cryptography program including instructions for generating one or more probable prime candidates for cryptographic use, said program causing processing hardware executing said program to carry out at least the following program steps:

providing a pseudo-random number having a specified first bit size;

generating a first candidate from said pseudo-random number by summing with a first increment, said first increment chosen such that said first candidate is relatively prime to a set of very small primes;

repeatedly testing successive candidates beginning with said first candidate by means of trial division against a list of small primes other than said very small primes until a candidate is found that is relatively prime to all of said small primes in said list, successive candidates being tested by

(i) calculating a set of modular reductions of the first candidate, the elements of this set of modular reductions being remainders congruent to the first candidate modulus each of a corresponding set of products of distinct groups of primes in said list of small primes, said products having a specified maximum second bit size that is smaller than said first bit size by at least a factor of four;

(ii) maintaining a main increment value that is updated for each successive candidate, each successive update of the main increment value when added to the value of said first candidate providing the next successive candidate that is relatively prime to the set of very small primes;

(iii) for each element of the set of modular reductions incremented by the current update of the main increment value, unless and until a candidate has been found to be composite, testing the incremented element by trial division against each of the primes in the corresponding group of primes in to determine whether the remainder is zero and if so designating the current candidate as composite;

after finding a candidate that is relatively prime to all of said small primes in said list, subjecting said candidate, equal to the first candidate plus the current main increment, to at least one known rigorous probable primality test, and if a candidate is found to be composite according to any one said rigorous test, then continuing testing of successive candidates by trial division against the list of small primes as before until a candidate is found that passes both small primes trial division and said rigorous test, such candidate being considered to be a probable prime value; and

using the probable prime value in said cryptographic program.

2. The program of claim 1 wherein the processing hardware comprises a general purpose programmable computer system and the program is in the form of software readable by said computer system.

3. The program of claim 1 wherein the processing hardware comprises an integrated circuit chip and the program is in the form of firmware accessible by said chip.

4. The program of claim 1 wherein the processing hardware comprises a configurable logic chip, such as a field programmable logic array, configured to implement said program.

5. The program of claim 1 in the form of an application specific integrated circuit specially designed to execute the program steps.

6. The program of claim 1 wherein the first bit size is at least 256 bits.

7. The program of claim 1 wherein the second bit size is 32 bits.

8. The program of claim 1 wherein said set of very small primes comprises 2, 3, 5 and 7.

9. The program of claim 8 wherein said list of small primes comprises all successive primes between 11 and 241.

10. The program of claim 8 wherein said first increment is found by comparing a remainder congruent to the pseudo-random number modulus 210 with a table of 210 elements representing values from zero to 209, wherein elements of the table corresponding to values relatively prime to all of 2, 3, 5 and 7 are distinguished in the table from elements corresponding to values divisible by any of 2, 3, 5 or 7, and the comparing is carried out to identify an increment that will bring said remainder to a value that is relatively prime to all of 2, 3, 5 and 7.

11. The program of claim 10 wherein said main increment is found by comparison with said table of 210 elements, each successive main increment value bringing said remainder to the next relatively prime value in the table.

12. The program of claim 1 wherein said known rigorous probable primality test comprises the Miller-Rabin test.

13. The program of claim 1 wherein said known rigorous probable primality test comprises the Fermat test.

14. The program of claim 1 wherein the probable prime value is used to generate at least one cryptographic key.