This article analyzes the methods of prime number generation used in modern cryptographic systems and their mathematical foundations. The processes of generating large prime numbers, random number generators, and the operating principles of primality testing algorithms are examined. The efficiency and practical advantages of the Fermat and Miller–Rabin tests in prime number generation are evaluated. In addition, safe primes and their role in public-key cryptosystems such as RSA and Diffie–Hellman are analyzed. The research results demonstrate the significant importance of prime number generation algorithms in ensuring the security of cryptographic systems.
Methods Of Prime Number Generation In Cryptographic Systems And Their Analysis
DOI:
Keywords:
Prime number
prime number generation
primality test
Miller–Rabin algorithm
Abstract
References
Stallings W. Cryptography and Network Security. — Pearson, 2017.
Rivest R., Shamir A., Adleman L. “A Method for Obtaining Digital Signatures and Public-Key Cryptosystems”. Communications of the ACM, 1978.
Menezes A., van Oorschot P., Vanstone S. Handbook of Applied Cryptography. — CRC Press, 1996.
Rabin M. O. “Probabilistic Algorithm for Testing Primality”. Journal of Number Theory, 1980.
Bernstein D., Buchmann J., Dahmen E. Post-Quantum Cryptography. — Springer, 2009.
Hardy G. H., Wright E. M. An Introduction to the Theory of Numbers. — Oxford University Press, 2008.
Paar C., Pelzl J. Understanding Cryptography. — Springer, 2010.
Rosen K. H. Elementary Number Theory and Its Applications. — Pearson, 2010.
Carmichael R. D. “On Composite Numbers P Which Satisfy the Fermat Congruence”. American Mathematical Monthly, 1910.
Miller G. L. “Riemann’s Hypothesis and Tests for Primality”. Journal of Computer and System Sciences, 1976.
Rabin M. O. “Probabilistic Algorithm for Testing Primality”. Journal of Number Theory, 1980.
Schneier B. Applied Cryptography. — Wiley, 1996.
Rivest R., Shamir A., Adleman L. “A Method for Obtaining Digital Signatures and Public-Key Cryptosystems”. Communications of the ACM, 1978. Signatures and Public-Key Cryptosystems”. Communications of the ACM, 1978.
Kelsey J., Schneier B., Ferguson N. Yarrow-160: Notes on the Design and Analysis of the Yarrow Cryptographic Pseudorandom Number Generator. — Selected Areas in Cryptography, Springer, 1999.
Crandall R., Pomerance C. Prime Numbers: A Computational Perspective. — Springer, 2005.
Peter Shor “Algorithms for Quantum Computation: Discrete Logarithms and Factoring”. Proceedings of the 35th Annual Symposium on Foundations of Computer Science, 1994.