STM Journals Peer-reviewed research from Consortium e-Learning Network

International Journal of Algorithms Design and Analysis Review Original Research

Primality Testing: A Comprehensive Analysis of Methods and Time Complexity

  1. Sheetal S. Patil Department of Computer Engineering, Bharati Vidyapeeth Deemed University College of Engineering, Pune
  2. Avinash M. Pawar Department of Mechanical Engineering, Bharati Vidyapeeth’s College of Engineering for Women, Pune

Abstract

This paper examines various primality testing algorithms and analyzes their time complexity. The algorithms we examine include the trial division, which is straightforward but becomes inefficient with large numbers; Fermat’s little theorem which is a probabilistic method included in Monte Carlo type of randomized algorithm; the Solovay–Strassen, based on properties from number theory, particularly those related to Euler’s criterion and Jacobi symbols; and the Miller–Rabin Probabilistic Test, which balances efficiency and accuracy, providing probable results for very large numbers. The advantages and disadvantages of each algorithm are evaluated, considering both their theoretical efficiency and practical use in real-world scenarios. Additionally, we analyze the applicability of these algorithms in cryptography and other real-world contexts where identifying prime numbers is critical.

Keywords

References (15)

  1. Agrawal M, Kayal N, Saxena N. PRIMES is in P. Ann Math. 2004;781–93.
  2. Kiss G. A strategy for elliptic curve primality proving. Acta Universitatis Sapientiae, Informatica. 2015;7(2):125-142. doi:10.1515/ausi-2015-0015
  3. Lenstra, Jr. HW, Pomerance CB. Primality testing with Gaussian periods. Journal of the European Mathematical Society. 2019;21(4):1229-1269. doi:10.4171/jems/861
  4. Shor PW. Algorithms for quantum computation: discrete logarithms and factoring. Proceedings 35th Annual Symposium on Foundations of Computer Science. 124-134. doi:10.1109/sfcs.1994.365700
  5. Agrawal M. Primality tests based on Fermat’s little theorem. In: International Conference on Distributed Computing and Networking; 2006 Dec 27. Springer Berlin Heidelberg; p. 288–93.
  6. Solovay R, Strassen V. A Fast Monte-Carlo Test for Primality. SIAM Journal on Computing. 1977;6(1):84-85. doi:10.1137/0206006
  7. Pocklington HC. The determination of the prime or composite nature of large numbers by Fermat’s theorem. Proc Camb Philos Soc. 1915;18:29–30.
  8. Rabin MO. Probabilistic algorithm for testing primality. Journal of Number Theory. 1980;12(1):128-138. doi:10.1016/0022-314x(80)90084-0
  9. Lenstra HW Jr. Elliptic curve factorisation and primality testing. Paper presented at: Computational Number Theory Conference; 1985 Aug; Arcata, California. Available from: https://www.math. leidenuniv.nl/~lenstrahw/PUBLICATIONS/1986d/art.pdf.
  10. Islam MM, Hossain MS, Hasan MK, Shahjalal M, Jang YM. FPGA Implementation of High-Speed Area-Efficient Processor for Elliptic Curve Point Multiplication Over Prime Field. IEEE Access. 2019;7:178811-178826. doi:10.1109/access.2019.2958491
  11. Antonov N, Ishmukhametov S. An Intelligent Choice of Witnesses in the Miller–Rabin Primality Test. Reinforcement Learning Approach. Lobachevskii Journal of Mathematics. 2022;43(12):3420-3429. doi:10.1134/s1995080222150045
  12. Schoof R. Four primality testing algorithms. arXiv Preprint ArXiv:0801.3840 [Preprint]. 2008 Jan 24.
  13. Alford WR, Granville A, Pomerance C. There are Infinitely Many Carmichael Numbers. The Annals of Mathematics. 1994;139(3):703. doi:10.2307/2118576
  14. Bos JW, Costello C, Longa P, Naehrig M. Selecting elliptic curves for cryptography: an efficiency and security analysis. Journal of Cryptographic Engineering. 2015;6(4):259-286. doi:10.1007/s13389-015-0097-y
  15. Rivest RL, Shamir A, Adleman L. A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM. 1978;21(2):120-126. doi:10.1145/359340.359342