Primality Testing: A Comprehensive Analysis of Methods and Time Complexity


Year : 2024 | Volume : 02 | Issue : 02 | Page : 25-31
    By

    Sheetal S. Patil,

  • Avinash M. Pawar,

  1. Assistant Professor, Department of Computer Engineering, Bharati Vidyapeeth Deemed University College of Engineering, Pune, Maharashtra, India
  2. Associate Professor, Department of Mechanical Engineering, Bharati Vidyapeeth’s College of Engineering for Women, Pune, Maharashtra, India

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: Primality testing, trial division, probabilistic method, randomized algorithm

[This article belongs to International Journal of Algorithms Design and Analysis Review ]

How to cite this article:
Sheetal S. Patil, Avinash M. Pawar. Primality Testing: A Comprehensive Analysis of Methods and Time Complexity. International Journal of Algorithms Design and Analysis Review. 2024; 02(02):25-31.
How to cite this URL:
Sheetal S. Patil, Avinash M. Pawar. Primality Testing: A Comprehensive Analysis of Methods and Time Complexity. International Journal of Algorithms Design and Analysis Review. 2024; 02(02):25-31. Available from: https://journals.stmjournals.com/ijadar/article=2024/view=181471


References

  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 Univ Sapientiae Inform. 2015;7:125–42. DOI: 10.1515/ausi-2015-0015.
  3. Lenstra HW, Pomerance CB. Primality testing with Gaussian periods. J Eur Math Soc. 2019;21:1229–69. 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, Santa Fe, NM, USA, 1994. p. 124–34. 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 J Comput. 1977;6:84–5. 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. J Number Theory. 1980;12:128–38. 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 a prime field. IEEE Access. 2019;7:178811–26. 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 J Math. 2022;43:3420–9. 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. Ann Math. 1994;139:703–22. DOI: 10.2307/2118576.
  14. Bos JW, Costello C, Longa P, Naehrig M. Selecting elliptic curves for cryptography: An efficiency and security analysis. J Cryptogr Eng. 2016;6:259–86. DOI: 10.1007/s13389-015-0097-y.
  15. Rivest RL, Shamir A, Adleman L. A method for obtaining digital signatures and public-key cryptosystems. Commun ACM. 1978;21:120–6. DOI: 10.1145/359340.359342.
Regular Issue Subscription Original Research
Volume 02
Issue 02
Received 19/10/2024
Accepted 22/10/2024
Published 06/11/2024
Total Visits: 142


Loading citations…