{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T03:05:03Z","timestamp":1760151903233,"version":"build-2065373602"},"reference-count":33,"publisher":"MDPI AG","issue":"12","license":[{"start":{"date-parts":[[2022,11,30]],"date-time":"2022-11-30T00:00:00Z","timestamp":1669766400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"Scientific Research Deanship at the University of Ha\u2019il, Saudi Arabia","award":["RG-21 124"],"award-info":[{"award-number":["RG-21 124"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Symmetry"],"abstract":"<jats:p>Generating prime numbers less than or equal to an integer number m plays an important role in many asymmetric key cryptosystems. Recently, a new sequential prime sieve algorithm was proposed based on set theory. The main drawback of this algorithm is that the running time and storage are high when the size of m is large. This paper introduces three new algorithms for a prime sieve based on two approaches. The first approach develops a fast sequential prime sieve algorithm based on set theory and some structural improvements to the recent prime sieve algorithm. The second approach introduces two new parallel algorithms in the shared memory parallel model based on static and dynamic strategies. The analysis of the experimental studies shows the following results. (1) The proposed sequential algorithm outperforms the recent prime sieve algorithm in terms of running time by 98% and memory consumption by 80%, on average. (2) The two proposed parallel algorithms outperform the proposed sequential algorithm by 72% and 67%, respectively, on average. (3) The maximum speedups achieved by the dynamic and static parallel algorithms using 16 threads are 7 and 4.5, respectively. As a result, the proposed algorithms are more effective than the recent algorithm in terms of running time, storage and scalability in generating primes.<\/jats:p>","DOI":"10.3390\/sym14122527","type":"journal-article","created":{"date-parts":[[2022,11,30]],"date-time":"2022-11-30T04:05:24Z","timestamp":1669781124000},"page":"2527","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Efficient Sequential and Parallel Prime Sieve Algorithms"],"prefix":"10.3390","volume":"14","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9448-6168","authenticated-orcid":false,"given":"Hazem M.","family":"Bahig","sequence":"first","affiliation":[{"name":"Information and Computer Science Department, College of Computer Science and Engineering, University of Ha\u2019il, Ha\u2019il 81481, Saudi Arabia"},{"name":"Computer Science Division, Department of Mathematics, Faculty of Science, Ain Shams University, Cairo 11566, Egypt"}]},{"given":"Mohamed A. G.","family":"Hazber","sequence":"additional","affiliation":[{"name":"Information and Computer Science Department, College of Computer Science and Engineering, University of Ha\u2019il, Ha\u2019il 81481, Saudi Arabia"}]},{"given":"Khaled","family":"Al-Utaibi","sequence":"additional","affiliation":[{"name":"Computer Engineering Department, College of Computer Science and Engineering, University of Ha\u2019il, Ha\u2019il 81481, Saudi Arabia"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5550-3372","authenticated-orcid":false,"given":"Dieaa I.","family":"Nassr","sequence":"additional","affiliation":[{"name":"Computer Science Division, Department of Mathematics, Faculty of Science, Ain Shams University, Cairo 11566, Egypt"}]},{"given":"Hatem M.","family":"Bahig","sequence":"additional","affiliation":[{"name":"Computer Science Division, Department of Mathematics, Faculty of Science, Ain Shams University, Cairo 11566, Egypt"}]}],"member":"1968","published-online":{"date-parts":[[2022,11,30]]},"reference":[{"key":"ref_1","first-page":"101","article-title":"A new explicit algorithmic method for generating the prime numbers in order","volume":"22","author":"Elnabya","year":"2021","journal-title":"Egypt. Inf. J."},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Paillard, G., Franca, F.M., and Lavault, C. (2019, January 20\u201324). A distributed wheel sieve algorithm. Proceedings of the 2019 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW), Rio de Janeiro, Brazil.","DOI":"10.1109\/IPDPSW.2019.00107"},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Aiazzi, B., Baronti, S., Santurri, L., and Selva, M. (2019). An Investigation on the prime and twin prime number functions by periodical binary sequences and symmetrical runs in a modified sieve procedure. Symmetry, 11.","DOI":"10.3390\/sym11060775"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"781","DOI":"10.4007\/annals.2004.160.781","article-title":"Primes is in p","volume":"160","author":"Agrawal","year":"2004","journal-title":"Ann. Math."},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Ishmukhametov, S.T., Mubarakov, B.G., and Rubtsova, R.G. (2020). On the number of witnesses in the Miller-Rabin primality test. Symmetry, 12.","DOI":"10.3390\/sym12060890"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"235","DOI":"10.21608\/joems.2018.2540.1008","article-title":"Speeding up multi-exponentiation algorithm on a multicore system","volume":"26","author":"Fathy","year":"2018","journal-title":"J. Egypt. Math. Soc."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"324","DOI":"10.1007\/s11227-017-2129-0","article-title":"A fast optimal parallel algorithm for a short addition chain","volume":"74","author":"Bahig","year":"2018","journal-title":"J. Supercomput."},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Bahig, H., and Kotb, Y. (2019). An efficient multicore algorithm for minimal length addition chains. Computers, 8.","DOI":"10.3390\/computers8010023"},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Tahir, R.R., Asbullah, M.A., Ariffin, M.R., and Mahad, Z. (2021). Determination of a good indicator for estimated prime factor and its modification in Fermat\u2019s factoring algorithm. Symmetry, 13.","DOI":"10.3390\/sym13050735"},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Bahig, H.M., Nassr, D.I., Mahdi, M.A., and Bahig, H.M. (2022). Small private exponent attacks on RSA using continued fractions and multicore systems. Symmetry, 14.","DOI":"10.3390\/sym14091897"},{"key":"ref_11","first-page":"340","article-title":"Performance analysis of Fermat factorization algorithms","volume":"11","author":"Bahig","year":"2020","journal-title":"Int. J. Adv. Comput. Sci. Appl."},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Somsuk, K. (2022). An Efficient variant of Pollard\u2019s p-1 for the case that all prime factors of the p-1 in B-Smooth. Symmetry, 14.","DOI":"10.3390\/sym14020312"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"120","DOI":"10.1145\/359340.359342","article-title":"A method for obtaining digital signatures and public-key cryptosystems","volume":"21","author":"Rivest","year":"1978","journal-title":"Commun. ACM"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"644","DOI":"10.1109\/TIT.1976.1055638","article-title":"New directions in cryptography","volume":"22","author":"Diffie","year":"1976","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"469","DOI":"10.1109\/TIT.1985.1057074","article-title":"A public key cryptosystem and a signature scheme based on discrete logarithms","volume":"31","author":"Elgamal","year":"1985","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"2167","DOI":"10.1007\/s10586-017-0992-3","article-title":"Fast prime number generation algorithms on smart mobile devices","volume":"20","author":"Jo","year":"2017","journal-title":"Cluster Comput."},{"key":"ref_17","unstructured":"Cayrel, P.L., Alaoui, S.M.E.Y., Hoffmann, G., and V\u00e9ron, P. (2021, January 16\u201319). An improved threshold ring signature scheme based on error correcting codes. Proceedings of the International Workshop on the Arithmetic of Finite Fields, Bochum, Germany."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"664","DOI":"10.1145\/359810.359838","article-title":"Some new upper bounds on the generation of prime numbers","volume":"20","author":"Mairson","year":"1977","journal-title":"Commun. ACM"},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"999","DOI":"10.1145\/359657.359660","article-title":"A linear sieve algorithm for finding prime numbers","volume":"21","author":"Gries","year":"2014","journal-title":"Commun. ACM"},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1016\/0167-6423(87)90024-4","article-title":"Linear prime-number sieves: A family tree","volume":"9","author":"Pritchard","year":"2005","journal-title":"Sci. Comput. Progr."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"344","DOI":"10.1145\/62065.62072","article-title":"A practical sieve algorithm finding prime numbers","volume":"32","author":"Luo","year":"2010","journal-title":"Commun. ACM"},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"18","DOI":"10.1145\/358527.358540","article-title":"A sublinear additive sieve for finding prime number","volume":"24","author":"Pritchard","year":"2007","journal-title":"Commun. ACM"},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1016\/0020-0190(96)00099-3","article-title":"A space-efficient fast prime number sieve","volume":"59","author":"Dunten","year":"2010","journal-title":"Inf. Process. Lett."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"332","DOI":"10.1016\/0196-6774(83)90014-7","article-title":"Fast compact prime number sieves (among others)","volume":"4","author":"Pritchard","year":"2000","journal-title":"J. Algorithms"},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1007\/BF01932283","article-title":"The segmented sieve of eratosthenes and primes in arithmetic progressions to 1012","volume":"17","author":"Bays","year":"1999","journal-title":"BIT"},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"333","DOI":"10.1090\/mcom\/3438","article-title":"An improved sieve of eratosthenes","volume":"89","author":"Helfgott","year":"2020","journal-title":"Math. Comput."},{"key":"ref_27","unstructured":"Wainwright, R.L. (2009, January 21\u201323). Parallel sieve algorithms on a hypercube multiprocessor. Proceedings of the 17th conference on ACM Annual Computer Science Conference, New York, NY, USA."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1006\/inco.1994.1082","article-title":"2 fast parallel prime number sieves","volume":"114","author":"Sorenson","year":"2014","journal-title":"Inf. Comput."},{"key":"ref_29","doi-asserted-by":"crossref","unstructured":"Hwang, S., Chung, K., and Kim, D. (2007, January 16\u201319). Load balanced parallel prime number generator with sieve of eratosthenes on cluster computers. Proceedings of the 7th IEEE International Conference on Computer and Information Technology, Aizu-Wakamatsu, Japan.","DOI":"10.1109\/CIT.2007.139"},{"key":"ref_30","unstructured":"Paillard, G., Lavault, C., and Franca, F.A. (2005, January 4\u20136). Distributed prime sieving algorithm based on scheduling by multiple edge reversal. Proceedings of the 4th International Symposium on Parallel and Distributed Computing, Villeneuve-d\u2019Ascq, France."},{"key":"ref_31","unstructured":"Reif, J.H. (1993). Prefix sums and their applications. Synthesis of Parallel Algorithms, Morgan Kaufmann."},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"5267","DOI":"10.1007\/s11227-020-03473-x","article-title":"An efficient parallel strategy for high-cost prefix operation","volume":"77","author":"Bahig","year":"2021","journal-title":"J. Supercomput."},{"key":"ref_33","doi-asserted-by":"crossref","unstructured":"Li, C., Dong, M., Li, J., Xu, G., Chen, X., Liu, W., and Ota, K. (IEEE Syst. J., 2022). Efficient medical big data management with keyword-searchable encryption in healthchain, IEEE Syst. J., Early Access.","DOI":"10.1109\/JSYST.2022.3173538"}],"container-title":["Symmetry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2073-8994\/14\/12\/2527\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T01:29:59Z","timestamp":1760146199000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2073-8994\/14\/12\/2527"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,11,30]]},"references-count":33,"journal-issue":{"issue":"12","published-online":{"date-parts":[[2022,12]]}},"alternative-id":["sym14122527"],"URL":"https:\/\/doi.org\/10.3390\/sym14122527","relation":{},"ISSN":["2073-8994"],"issn-type":[{"type":"electronic","value":"2073-8994"}],"subject":[],"published":{"date-parts":[[2022,11,30]]}}}