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

摘要

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.