Prime Generation and Factorization Parallelization: A comparative Study of CPU and GPU Parallelization
Journal
2025 International Conference Automatics and Informatics (ICAI)
Date Issued
2025-10-09
Author(s)
Tasevska, Sofija
Kostadinoski, Viktor
DOI
10.1109/icai67591.2025.11324654
Abstract
Generation of prime numbers and factorization are very important topics in number theory and cryptography. Sieve-based methods like Sieve of Eratosthenes and Sieve of Euler have widespread usage. Pollard’s Rho algorithm, a probabilistic method for integer factorization, is also widely used in cryptographic applications. This paper explores a parallel approach alternative to these methods employing CPU and GPU acceleration to improve efficiency. Although parallelization imposes overhead on small inputs, experience suggests significant speedup for bigger prime boundaries. Our experiments show the potential of parallel computation to improve cryptographic computations, and in particular, this paper aims to demonstrate how increasing the number of CPUs in a system impacts the performance of these algorithms.