# When using prime factorization for key gen, is there a limit on the size of the prime factors?

If there is a limit, does that leave a limited number of prime numbers that can be used for key gen? And, if that is the case is the encryption system vulnerable?

• Yes, if you can enumerate every 16kb (or whatever arbitrary bit size) large composite number's prime factors, then you can break 16kb RSA and similar cryptosystems that rely on the difficulty of prime factorization. Those are pretty huge numbers by the way.
– user
Jul 9, 2021 at 18:59

Some standards put a limit. For example FIPS 186-4 has an upper limits of $$1536$$ bit; more precisely, for this size, each of the two primes that form the composite modulus must be in the interval $$[2^{1535.5},2^{1536}]$$, so that the product is $$3072$$-bit. By the prime number theorem, there are about about $$2^{1524}$$ primes in this interval. That's about $$600\underbrace{\text{ million }\ldots\text{ million }}_{76\text{ times the word million}}$$. That's limited, but so large that it does not make the system vulnerable for any practical purpose.