RSA Laboratories - 3.1.6 Could users of the RSA system run out of distinct primes?

As Euclid proved over two thousand years ago, there are infinitely many prime numbers. Because the RSA algorithm is generally implemented with a fixed key length, however, the number of primes available to a user of the algorithm is effectively finite. Although finite, this number is nonetheless very large. The Prime Number Theorem states that the number of primes less than or equal to n is asymptotic to n/lnn. Hence, the number of prime numbers of length 512 bits or less is roughly 10¹⁵⁰. This is greater than the number of atoms in the known universe.

Public-Key Cryptography Standards (PKCS) PKCS #1: RSA Cryptography Standard Section Index Foreword PKCS #3: Diffie-Hellman Key Agreement Standard PKCS #5: Password-Based Cryptography Standard Chapter 1 Introduction Chapter 2 Cryptography PKCS #6: Extended-Certificate Syntax Standard PKCS #7: Cryptographic Message Syntax Standard Chapter 3 Techniques in Cryptography Chapter 4 Applications of Cryptography PKCS #8: Private-Key Information Syntax Standard PKCS #9: Selected Attribute Types Chapter 5 Cryptography in the Real World Chapter 6 Laws Concerning Cryptography PKCS #10: Certification Request Syntax Standard PKCS #11: Cryptographic Token Interface Standard Chapter 7 Miscellaneous Topics Chapter 8 Further Reading PKCS #12: Personal Information Exchange Syntax Standard PKCS #13: Elliptic Curve Cryptography Standard Appendix A Mathematical concepts Appendix B Glossary PKCS #15: Cryptographic Token Information Format Standard PKCS Mailing Lists Appendix C References Workshops PKCS News Archives Guidelines for Contributions to the Public-Key Cryptography Standards (PKCS) One-Time Password Specifications (OTPS)	Home: Standards Initiatives: Public-Key Cryptography Standards (PKCS): PKCS #7: Cryptographic Message Syntax Standard: 3.1 RSA 3.1.6 Could users of the RSA system run out of distinct primes? As Euclid proved over two thousand years ago, there are infinitely many prime numbers. Because the RSA algorithm is generally implemented with a fixed key length, however, the number of primes available to a user of the algorithm is effectively finite. Although finite, this number is nonetheless very large. The Prime Number Theorem states that the number of primes less than or equal to n is asymptotic to n/lnn. Hence, the number of prime numbers of length 512 bits or less is roughly 10¹⁵⁰. This is greater than the number of atoms in the known universe. Top of Page
		Email to a friend Print