Farhat Mechkene

An Efficient Algorithm to Find All Primes in A Given Interval

ISSN: 2148-1830
Yayın Aralığı: 2
Başlangıç: 2013
Yayıncı: MATEMATİKÇİLER DERNEĞİ

In this paper, we propose a deterministic algorithm for primality testing and primes search in a giveninteger interval. The algorithm use a new primality test method, which replace modulo operator with elementaryarithmetic operations, hence a better efficiency than divisibility test. The algorithm is working; it generates a primebase by an expansion process and is appropriate for a fast search for small primes (a dozen of digits). We propose afiltering method to overcome memory constraints, and use the algorithm to expand much more the prime base andfind medium size primes (dozens of digits).

PDF

___

[1] Duta, C., Gheorghe, L., Tapus, N., Framework for Evaluation and Comparison of Primality Testing Algorithms, 20th Int. Conf. on Control Systems and Science, 2015.
[2] Kumar, A., Kim, T., Lee, H., An Improved Divisibility Test Algorithm for Primality Testing, Ubiquitous Information Technologies and Applications, pp. 547–554, Y.-H. Han et al. eds., 2013.
[3] Liang, Y.D., Efficient Algorithms for Finding Prime Numbers In Introduction to Java Programming, 10th Edition, Pearson, pp. 860-866, 2015.
[4] Riesel, H., Prime Numbers and Computer Methods for Factorization, Chap. Basic Concepts in Higher Algebra, Springer Science+Business Media, LLC 2012, Modern Birkhauser.
[5] Schoof, R., Four Primality Testing Algorithms, Algorithmic Number Theory, MSRI Publications, Volume 44, 2008.
[6] Wang, X., Mathematical Foundations of Public Key Cryptography, CRC Press, pp.27-30. 2016.
[7] Yan, S. Y., Computational Number Theory and Modern Cryptography, Chap. Primality Testing, Wiley, 2017.