A fully distributed prime numbers generation using the wheel sieve, Parallel and Distributed Computing and networks

This article presents a new distributed approach for generating all prime numbers up to a given limit. From Er-atosthenes, who elaborated the first prime sieve (more than 2000 years ago), to the advances of the parallel comput-ers (which have permitted to reach large limits or to ob-tain the previous results in a shorter time), prime numbers generation still represents an attractive domain of research. Nowadays, prime numbers play a central role in cryptogra-phy and their interest has been increased by the very recent proof that primality testing is in P. In this work, we propose a new distributed algorithm which generates all prime num-bers in a given finite interval [2,..., n], based on the wheel sieve. As far as we know, this paper designs the first fully distributed wheel sieve algorithm. KEY WORDS Distributed algorithms, prime numbers generation, wheel sieve, broadcast and leader election.