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

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.