A review of primarily tests and algorithms: Engaging students to code for mathematics
Abstract views: 61
/ 
PDF downloads: 40
Keywords:
Prime, Primality, Algorithm, Test, AKS, Ferma- Euler, Divisor, Euclid, Sieve, EratosthenesAbstract
The concept of prime numbers has intrigued mathematicians for centuries. The attempt to
understand prime numbers dates back to ancient times, with great mathematicians like Euclid, who, among
many other topics, explored integers and prime numbers’ properties. Determining whether a number is
prime or composite lies at the heart of many mathematical problems, leading to the development of
primality tests. Since the first primality algorithm, the Sieve of Eratosthenes, the need to verify very large
prime numbers has driven the development of many efficient tests and algorithms. This article presents an
overview of some of the most important primality algorithms, as well as corresponding Python programs
developed by computer science and mathematics students. The cooperation between theoretical
mathematics and programming has become the premise for progress in the development of tests and helps
students gain a better understanding of the theoretical problems while also encouraging and guiding them
in their future research and new discoveries.
Downloads
References
McGregor-Dorsey, Z. S. (1999). Methods of primality testing. MIT Undergraduate Journal of Mathematics, 1, 133-141.
Lander, L. J., & Parkin, T. R. (1966). Counterexample to Euler’s conjecture on sums of like powers. Bull. Amer. Math. Soc, 72(6), 1079.
Duta, C. L., Gheorghe, L., & Tapus, N. (2015, May). Framework for evaluation and comparison of primality testing algorithms. In 2015 20th International Conference on Control Systems and Computer Science (pp. 483-490). IEEE.
Kuang, R., & Barbeau, M. (2021, September). Indistinguishability and non-deterministic encryption of the quantum safe multivariate polynomial public key cryptographic system. In 2021 IEEE Canadian Conference on Electrical and Computer Engineering (CCECE) (pp. 1-5). IEEE.
AbuDaqa, A., Abu-Hassan, A., & Imam, M. (2020). Taxonomy and Practical Evaluation of Primality Testing Algorithms. arXiv preprint arXiv:2006.08444.
Zaka, O. (2021). A description of some facts and open problems in Discrete-Geometry, related to Coverings. In Mathematical methods in economy: Research and Practice, Conference, Paris, France (Vol. 25).
Zaka, O. (2022). Computing efficiently the weighted greatest common divisor. arXiv preprint arXiv:2210.07961.
Wehrwein, J. (2022). Primality testing (Doctoral dissertation, Middlebury).
Kosova, R., Kapçiu, R., Hajrulla, S., & Kosova, A. M. (2023). A Review of Mathematical Conjectures: Exploring Engaging Topics for University Mathematics Students. International Journal of Advanced Natural Sciences and Engineering Researches (IJANSER), 7(11), 180–186. https://doi.org/10.59287/as-ijanser.581
Kosova, R., Thanasi, T., Mukli, L., & Pëllumbi, L. N. (2016). Traditional mathematics and new methods of teaching through programming together with students.
Kosova, A. G. R. The Performance of University Students and High School Factors. Statistical Analyses And ANCOVA.
Kosova, R., Kapçiu, R., Hajrulla, S., & Kosova, A. M. (2023). The Collatz Conjecture: Bridging Mathematics and Computational Exploration with Python. International Journal of Advanced Natural Sciences and Engineering Researches (IJANSER), 7(11), 328–334. https://doi.org/10.59287/as-ijanser.637
Gjana, A., & Kosova, R. Traditional Class, and Online Class Teaching. Comparing the Students Performance Using ANCOVA. Journal of Multidisciplinary Engineering Science and Technology (JMEST), 14806-14811.
Hajrulla, S., Demir, T., Bezati, L., & Kosova, R. (2023). The impact of constructive learning applied to the teaching of numerical methods. CONSTRUCTIVE MATHEMATICS: FOUNDATION AND PRACTICE, 39.
Diab, A. (2021). Development of sieve of Eratosthenes and sieve of Sundaram's proof. arXiv preprint arXiv:2102.06653.
Ganti, I. (2022). Comparing and Reviewing Modern Primality Tests. Journal of Student Research, 11(3).
Valluri, M. R. (2021). Combinatorial primality test. ACM Communications in Computer Algebra, 54(4), 129-133.
Agrawal, M., Kayal, N., & Saxena, N. (2004). PRIMES is in P. Annals of mathematics, 781-793.
Tao, T. (2009). The AKS primality test. Blog post by Terence Tao.
Gradini, E. (2012). Comparison Study of Fermat, Solovay-Strassen and Miller-Rabin Primality Test Using Mathematica 6.0. Visipena, 3(1), 1-10.
Wang, A. (2023). Gauss-Euler Primality Test. arXiv preprint arXiv:2311.07048.
Stüwe, D., & Eberl, M. (2019). Probabilistic primality testing. Archive of Formal Proofs.
Burkhardt, J., Damgård, I., Frederiksen, T. K., Ghosh, S., & Orlandi, C. (2023, November). Improved Distributed RSA Key Generation Using the Miller-Rabin Test. In Proceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security (pp. 2501-2515).
Ishmukhametov, S. T., Rubtsova, R. G., & Khusnutdinov, R. R. (2022). A new primality test for natural integers. Russian Mathematics, 66(2), 70-73.
