This article analyzes the theoretical foundations, operating principles, and practical efficiency of primality testing algorithms. The role of prime numbers in modern cryptographic systems and the necessity of testing large integers are discussed. The mathematical foundations, advantages, and limitations of the Fermat, Solovay–Strassen, Miller–Rabin, and AKS primality tests are examined. In addition, the computational complexity of probabilistic and deterministic algorithms and their impact on the security of cryptographic systems are evaluated. The research results demonstrate that primality testing algorithms play a crucial role in public-key cryptosystems such as RSA.
Analysis Of Primality Testing Algorithms And Their Applications In Cryptography
DOI:
Keywords:
Prime number
primality test
Miller–Rabin algorithm
Abstract
References
Hardy G. H., Wright E. M. An Introduction to the Theory of Numbers. — Oxford University Press, 2008.
Crandall R., Pomerance C. Prime Numbers: A Computational Perspective. — Springer, 2005.
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.
Solovay R., Strassen V. “A Fast Monte-Carlo Test for Primality”. SIAM Journal on Computing, 1977.
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.
Agrawal M., Kayal N., Saxena N. “PRIMES is in P”. Annals of Mathematics, 2004.
Rivest R., Shamir A., Adleman L. “A Method for Obtaining Digital Signatures and Public-Key Cryptosystems”. Communications of the ACM, 1978.