# Multiscale Sieve for Smart Prime Generation and Application in Info-Security, IoT and Blockchain
## 1 Introduction  
The generation of prime numbers and their distribution and the research of a possible deterministic method to discover new primes have been important issues in mathematics over the last two centuries (see, for example, [1; 2; 3; 4; 5; 6; 7]). Sieve algorithms, therefore, play a fundamental role in the field of number theory, particularly in the identification of prime numbers. These algorithms are used in numerous application contexts, including cryptography, data analysis, and scientific computing. To date, we know of numerous sieving algorithms, starting with the oldest sieves that laid the foundations, such as the Sieve of Eratosthenes, the Sieve of Sundaram, the linear sieve, and many other well-known methods that iteratively eliminate composite numbers (see [8; 9]). While some of these algorithms are efficient for small to medium-sized numbers, they become inefficient when dealing with very large numbers without further optimization. Modern sieving algorithms, which allow slightly larger numbers to be handled more efficiently, have built on the foundations of ancient algorithms. For instance, the Sieve of Atkin improves upon the Sieve of Eratosthenes by using a more complex mathematical approach to reduce the number of unnecessary operations [10], while the Segmented Sieve of Eratosthenes with Wheel Factorization optimizes the memory usage and reduces the computational load by segmenting the range of numbers and incorporating wheel factorization to skip multiples of small primes [11]. Meanwhile, there are others, such as AKS [12]. In contrast to deterministic sieving algorithms, probabilistic algorithms do not guarantee the identification of a prime but provide a probability of correctness, such as the Rabin, Solovay, and Strassen tests and the Baillie-PSW test using the Lucas-Lehmer test (for details, see [13; 14; 15; 16]). These probabilistic methods, while faster, have several disadvantages, including a high false positive rate, making them unsuitable for applications requiring absolute certainty, and their complex and computationally intensive implementation. In Table 1, we report some of more relevant sieves and their time and space complexity. In this paper, we show that, through our work in [17; 18; 19; 20], where we performed a multiscale analysis showing how the primes in one fixed scale become the seeds that generate new primes in the next scale, we can create a deterministic multiscale sieve with drastically better performance than the deterministic algorithms known so far, providing a more efficient solution for the generation of primes and even new primes at a large scale. In addition, as we will see, our approach is very useful for distributed and decentralized infrastructures. In [21], we find an interesting example of a new security approach in the context of IoT, while, in [22], another interesting application to blockchain is presented. Therefore, the present work could be the basis for the proof of work in the blockchain context. Furthermore, considering that a multiscale approach like the one proposed lends itself very well to simple but highly parallel computation, the proposed system is also very attractive in the IoT context, in relation to aspects of both info-security and gamification. This article is organized as follows. In Section 2, we describe the forms that prime numbers can assume and how the automation of this process is the basis of the sieve, while, in Section 3, we present an overview of the key elements and fundamental logic on which the algorithm is based. In Section 4, we analyze the sets of prime candidates generated at each level and explain the important optimization of their generation through the reduction of the search space. We next describe the steps that follow the generation, for the search of prime numbers.