Science Forums 2

[CraigD]

I wouldn’t worry about the computer security implication of an algorithm to generate consecutive prime numbers.

The major thread to most popular public-key encryption systems, such as RSA, is the invention of a much more efficient solution to the factoring problem. The output of a prime number generator, regardless of how efficient it is, doesn’t solve the factoring problem. Since, per the prime number theorem the number of prime numbers from 2 to x is known to be near , for a prime number generator to be any better for brute-force factoring of a typical cryptographic composite number (eg: for RSA-4096) than counting by odd numbers, it must require no more that about 710 () times the computing effort incrementing by 2. Even if a prime number generator were this efficient, the brute-force factoring approach with which it would help would only be slightly helped. For common cryptographic composite number sizes, such approaches are impractical for any classical (ie: not a quantum computer) computer.

Only if a prime number generator also implements or suggests a dramatically more efficient solution to the factoring problem is there a need to worry about its computer security implications.