This is an unedited manuscript accepted for publication and provided as an Article in Press for early access at the author’s request. The article will undergo copyediting, typesetting, and galley proof review before final publication. Please be aware that errors may be identified during production that could affect the content. All legal disclaimers of the journal apply.
Sheetal S. Patil,
Avinash M. Pawar,
- Assistant Professor, Department of Computer Engineering, Bharati Vidyapeeth Deemed University College of Engineering, Pune, Maharashtra, India
- Associate Professor, Department of Mechanical Engineering, Bharati Vidyapeeth’s College of Engineering for Women, Pune, Maharashtra, India
Abstract document.addEventListener(‘DOMContentLoaded’,function(){frmFrontForm.scrollToID(‘frm_container_abs_111337’);});Edit Abstract & Keyword
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 (ijadar)]
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):-.
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):-. Available from: https://journals.stmjournals.com/ijadar/article=2024/view=0
References
document.addEventListener(‘DOMContentLoaded’,function(){frmFrontForm.scrollToID(‘frm_container_ref_111337’);});Edit
- Agrawal M. Primality tests based on Fermat’s little theorem. InInternational Conference on Distributed Computing and Networking 2006 Dec 27 (pp. 288-293). Berlin, Heidelberg: Springer Berlin Heidelberg.
- Antonov N, Ishmukhametov S. An intelligent choice of witnesses in the Miller–Rabin primality test. Reinforcement learning approach. Lobachevskii Journal of Mathematics. 2022 Dec;43(12):3420-9.
- Agrawal M, Kayal N, Saxena N. PRIMES is in P. Annals of mathematics. 2004 Sep 1:781-93.
- Kiss G. A strategy for elliptic curve primality proving. Acta Universitatis Sapientiae, Informatica. 2015 Dec 1;7(2):125-42.
- Solovay R, Strassen V. A fast Monte-Carlo test for primality. SIAM journal on Computing. 1977 Mar;6(1):84-5.
- C. Pocklington, “The Determination of the Prime or Composite Nature of Large Numbers by Fermat’s Theorem,” Proceedings of the Cambridge Philosophical Society, vol. 18, pp. 29-30, 1915.
- Rabin MO. Probabilistic algorithm for testing primality. Journal of number theory. 1980 Feb 1;12(1):128-38.
- Schoof R. Four primality testing algorithms. arXiv preprint arXiv:0801.3840. 2008 Jan 24.
- Alford WR, Granville A, Pomerance C. There are infinitely many Carmichael numbers. Annals of Mathematics. 1994 May 1;139(3):703-22.
- Rivest RL, Shamir A, Adleman L. A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM. 1978 Feb 1;21(2):120-6.
- Lenstra, “Elliptic Curve Factorization and Primality Testing,” in Advances in Cryptology, Springer, 1986, pp. 31-39.
- Shor PW. Algorithms for quantum computation: discrete logarithms and factoring. InProceedings 35th annual symposium on foundations of computer science 1994 Nov 20 (pp. 124-134). Ieee..
- Lenstra HW, Pomerance C. Primality testing with Gaussian periods. Journal of the European Mathematical Society. 2019;21(4):1229-69.
- 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 Dec 9;7:178811-26.
- Bos JW, Costello C, Longa P, Naehrig M. Selecting elliptic curves for cryptography: an efficiency and security analysis. Journal of Cryptographic Engineering. 2016 Nov;6:259-86.
International Journal of Algorithms Design and Analysis Review
| Volume | 02 |
| Issue | 02 |
| Received | 19/10/2024 |
| Accepted | 22/10/2024 |
| Published | 06/11/2024 |
function myFunction2() {
var x = document.getElementById(“browsefigure”);
if (x.style.display === “block”) {
x.style.display = “none”;
}
else { x.style.display = “Block”; }
}
document.querySelector(“.prevBtn”).addEventListener(“click”, () => {
changeSlides(-1);
});
document.querySelector(“.nextBtn”).addEventListener(“click”, () => {
changeSlides(1);
});
var slideIndex = 1;
showSlides(slideIndex);
function changeSlides(n) {
showSlides((slideIndex += n));
}
function currentSlide(n) {
showSlides((slideIndex = n));
}
function showSlides(n) {
var i;
var slides = document.getElementsByClassName(“Slide”);
var dots = document.getElementsByClassName(“Navdot”);
if (n > slides.length) { slideIndex = 1; }
if (n (item.style.display = “none”));
Array.from(dots).forEach(
item => (item.className = item.className.replace(” selected”, “”))
);
slides[slideIndex – 1].style.display = “block”;
dots[slideIndex – 1].className += ” selected”;
}