COMPARATIVE STUDY BETWEEN A NOVEL DETERMINISTIC TEST FOR MERSENNE PRIMES AND THE WELL-KNOWN PRIMALITY TESTS
DOI:
https://doi.org/10.21123/bsj.2023.7791Keywords:
Deterministic test, Mersenne numbers, Primality test, Probabilistic test, Proth numbers.Abstract
In this article, a new deterministic primality test for Mersenne primes is presented. It also includes a comparative study between well-known primality tests in order to identify the best test. Moreover, new modifications are suggested in order to eliminate pseudoprimes. The study covers random primes such as Mersenne primes and Proth primes. Finally, these tests are arranged from the best to the worst according to strength, speed, and effectiveness based on the results obtained through programs prepared and operated by Mathematica, and the results are presented through tables and graphs.
Received 18/9/2022
Revised 22/11/2022
Accepted 23/11/2022
Published Online First 20/3/2023
References
Al-Bundi SS. On Subliminal Cryptography. Baghdad Sci J. 2006; 3(1): 124-130.
Khudhair ZN, Nidhal A, El Abbadi NK. Text Multilevel Encryption Using New Key Exchange Protocol. Baghdad Sci J. 2022; 19(3): 0619-0619. https://doi.org/10.21123/bsj.2022.19.3.0619
Albrecht MR, Massimo J, Paterson KG, Somorovsky J. Prime and Prejudice: Primality Testing Under Adversarial Conditions. Proc ACM SIGSAC Conf Comput Commun Secur. (CCS’18). 2018: 281-298. https://doi.org/10.1145/3243734.3243787
Bunder M, Nitaj A, Susilo W, Tonien J. A Generalized Attack on RSA Type Cryptosystems. Theor Comput Sci. 2017; 704: 74-81. https://doi.org/10.1016/j.tcs.2017.09.009
Menezes AJ, Kenneth HR, Van Oorschot PC, Vanstone SA. Handbook of Applied Cryptography. Boca Raton: CRC press; 2020. 810 p. https://doi.org/10.1201/9780429466335
Banerjee K, Mandal SN, Das SK. A Comparative Study of Different Techniques for Prime Testing in Implementation of RSA. Am J Adv Comput. 2020; 1(1): 1-7. https://doi.org/10.15864/ajac.1102
Landau E. Elementary Number Theory. USA: American Mathematical Society; 2021. 256 p.
Alqaydi L, Yeun CY, Damiani E. A Modern Solution for Identifying, Monitoring, and Selecting Configurations for SSL/TLS Deployment. Int Conf Appl Comput Inf Technol (ACIT 2018). Springer, Cham. 2018; 78-88. https://doi.org/10.1007/978-3-319-98370-7_7
Ramzy A A. Primality Test for Kpn + 1 Numbers and A Generalization of Safe Primes and Sophie Germain Primes. arXiv preprint arXiv: 2207.12407. 2022 Jul 25. https://doi.org/10.48550/arXiv.2207.12407
Zheng Z. Prime Test. Modern Cryptography. 2022; 1: 197-228. https://doi.org/10.1007/978-981-19-0920-7_5
Andrica D, Bagdasar O. On Generalized Lucas Pseudoprimality of Level k. Mathematics. 2021 Apr 12; 9(8): 838. https://doi.org/10.3390/math9080838
Andrica D, Bagdasar O. Pseudoprimality Related to the Generalized Lucas Sequences. Math Comput Simul. 2022; 201: 528-542. https://doi.org/10.1016/j.matcom.2021.03.003
Baillie R, Wagstaff SS. Lucas Pseudoprimes. Math Comput. October 1980; 35(152): 1391-1417. https://doi.org/10.2307/2006406
Baillie R, Fiori A, Wagstaff Jr S. Strengthening the Baillie-PSW Primality Test. Math Comput. 2021; 90(330): 1931-1955. https://doi.org/10.1090/mcom/3616
Crandall R, Pomerance CB. Prime Numbers: a Computational Perspective. Math Gaz. 2002; 86(507): 552-554. https://doi.org/10.2307/3621190
Agrawal M, Kayal N, Saxena N. Errata: PRIMES is in P. Ann Math. 2019; 189(1): 317-318. https://doi.org/10.4007/annals. 2019.189.1.6
Menon V. Deterministic Primality Testing-Understanding the AKS Algorithm. arXiv preprint arXiv:1311.3785. 2013. https://doi.org/10.48550/arXiv.1311.3785
Sridharan S, Balakrishnan R. Discrete Mathematics: Graph Algorithms, Algebraic Structures, Coding Theory, and Cryptography. 1st Ed. New York: Chapman and Hall/CRC Press; 2019. 340 p. https://doi.org/10.1201/9780429486326
Cao Z, Liu L. Remarks on AKS Primality Testing Algorithm and A Flaw in the Definition of P. arXiv preprint arXiv:1402.0146. 2014 Feb 2. https://doi.org/10.48550/arXiv.1402.0146
Lenstra Jr HW, Pomerance CB. Primality Testing with Gaussian Periods. J Eur Math Soc. 2019; 21(4): 1229-1269. https://doi.org/10.4171/JEMS/861
Bisson G, Ballet S, Bouw I. Arithmetic, Geometry, Cryptography and Coding Theory. Amer Math Soc. 2021; 770: 104-131. https://doi.org/10.1090/conm/770
Wu L, Cai HJ, Gong Z. The Integer Factorization Algorithm with Pisano Period. IEEE Access. 2019; 7: 167250-167259. https://doi.org/10.1109/ACCESS.2019.2953755
Bruce JW. A really trivial proof of the Lucas-Lehmer Primality Test. Am Math Mon. 1993; 100(4): 370-371. https://doi.org/10.1080/00029890.1993.11990414
Théry L, Antipolis S. Primality Tests and Prime Certificate. arXiv preprint arXiv: 2203. 16341. 2022. https://doi.org/10.48550/arXiv.2203.16341
Kundu S, Mazumder S. Number Theory and its Applications. 1st Ed. London: CRC Press; 2022. 366 p. https://doi.org/10.1201/9781003275947
Downloads
Published
Issue
Section
License
Copyright (c) 2023 Baghdad Science Journal
This work is licensed under a Creative Commons Attribution 4.0 International License.
How to Cite
