An Efficient Algorithm to Find All Primes in A Given Interval

Abstract

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

Keywords

• Finding all frimes in an interval,deterministic algorithms for primality testing

References

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 Birkh\"{a}user.
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.