Background. Prime numbers are integers divisible only on 1 and themselves, and one of the oldest methods of finding them is through a process known as sieving. A prime number sieving algorithm produces every prime number in a span, usually from the number 2 up to a given number n. In this thesis, we will cover the three sieves of Eratosthenes, Sundaram, and Atkin. Objectives. We shall compare their sequential CPU implementations to their parallel GPGPU (General Purpose Graphics Processing Unit) counterparts on the matter of performance, accuracy, and suitability. GPGPU is a method in which one utilizes hardware indented for graphics rendering to achieve a high degree of parallelism. Our goal is to establish if GPGPU sieving can be more effective than the sequential way, which is currently commonplace.   Method. We utilize the C++ and CUDA programming languages to implement the algorithms, and then extract data regarding their execution time and accuracy. Experiments are set up and run at several sieving limits, with the upper bound set by the memory capacity of available GPU hardware. Furthermore, we study each sieve to identify what characteristics make them fit or unfit for a GPGPU approach. Results. Our results show that the sieve of Eratosthenes is slow and ill-suited for GPGPU computing, that the sieve of Sundaram is both efficient and fit for parallelization, and that the sieve of Atkin is the fastest but suffers from imperfect accuracy.   Conclusions. Finally, we address how the lesser concurrent memory capacity available for GPGPU limits the ranges that can be sieved, as compared to CPU. Utilizing the beneficial characteristics of the sieve of Sundaram, we propose a batch-divided implementation that would allow the GPGPU sieve to cover an equal range of numbers as any of the CPU variants.

In this thesis a heuristic method for factoring semiprimes by multiagent depth-limited search of PG2N graphs is presented. An analysis of PG2N graph connectivity is used to generate heuristics for multiagent search. Further analysis is presented including the requirements on choosing prime numbers to generate 'hard' semiprimes; the lack of connectivity in PG1N graphs; the counts of spanning trees in PG2N graphs; the upper bound of a PG2N graph diameter and a conjecture on the frequency distribution of prime numbers on Hamming distance. We further demonstrated the feasibility of the HD2 breadth first search of PG2N graphs for factoring small semiprimes. We presented the performance of different multiagent search heuristics in PG2N graphs showing that the heuristic of most connected seedpick outperforms least connected or random connected seedpick heuristics on small PG2N graphs of size N

No description available.

No description available.

No description available.

Em Teoria Analítica de Números, a expressão \"Fórmula Explícita\" se refere a uma igualdade entre, por um lado, uma soma de alguma função aritmética feita sobre todos os primos e, por outro lado, uma soma envol- vendo os zeros não triviais da função zeta de Riemann. Essa igualdade não é habitual em Teoria Analítica de Números, que trata principalmente de aproximações assintóticas de funções aritméticas e não de fórmulas exatas. A expressão se originou do trabalho seminal de Riemann, de 1859, onde aparece uma expressão exata para a função (x), que conta o número de primos que não excedem x. A prova do Teorema dos Números Primos, de Hadamard, também se baseia numa fórmula explícita de (x) (função de Tschebycheff). Mais recentemente, o trabalho de André Weil reforçou o inte- resse em compreender-se melhor a natureza de tais fórmulas. Neste trabalho, apresentaremos a fórmula explícita de Riemann-von Mangoldt, a de Delsarte e um caso particular da fórmula explícita de Weil. / In the field of Analytic Theory of Numbers, the expression \"Explicit For- mula\" refers to an equality between, on one hand, the sum of some arithmetic function over all primes and, on the other, a sum over the non-trivial zeros of Riemann s zeta function. This equality is not common in the analytic theory of numbers, that deals mainly with asymptotic approximations of arithmetic functions, and not of exact formulas. The expression originated of Riemann s seminal work, of 1859, in which we see an exact expression for the function (x), that counts the number of primes that do not exceed x. The proof of the Prime Number Theorem, by Hadamard, is also based on an explicit formula of (x) (Tschebycheff s function). More recently, the work of André Weil increased the interest in better comprehending the nature of such formulas. In this work, we shall present the Riemann-von Mangoldt formula, Delsarte s explicit formula, and one particular case of Weil s explicit formula.

Cryptography plays a crucial role in today’s society. Given the influence, cryptographic algorithms need to be trustworthy. Cryptographic algorithms such as RSA relies on the problem of prime number factorization to provide its confidentiality. Hence finding a way to make it computationally feasible to find the prime factors of any integer would break RSA’s confidentiality. The approach presented in this thesis explores the possibility of trying to construct φ(n) from n. This enables factorization of n into its two prime numbers p and q through the method presented in the original RSA paper. The construction of φ(n) from n is achieved by analyzing bitwise relations between the two. While there are some limitations on p and q this thesis can in favorable circumstances construct about half of the bits in φ(n) from n. Moreover, based on the research a conjecture has been proposed which outlines further characteristics between n and φ(n).

This thesis deals with new teaching software, which supports asymmetric encryption algorithms based on the issue of large numbers´ factorization. A model program was created. It allows to carry out operations related to encryption and decryption with an interactive control. There is a simple way to understand the principle of the RSA encryption method with its help. The encryption of algorithms is generally analysed in chapters 1,2. Chapters 3 and 4 deals with RSA encryption algorithm in much more details, and it also describes the principles of the acquisition, management and usage of encryption keys. Chapters 5 suggest choosing of appropriate technologies for the creation of the final software product, which allow an appropriate way to present the characteristics of the extended RSA encryption algorithm. The final software product is the java applet. Aplet is described in the chaprers 6 and 7. It is divided into a theoretical and practical part. The theoretical part presents general information about the RSA encryption algorithm. The practical part allows the users of the program to have a try at tasks connected with the RSA algorthm in their own computers. The last part of Java applet deals with the users´ work results. The information obtained by the user in the various sections of the program are satisfactory enough to understand the principle of this algorithm´s operations.

In this thesis we provide a body of knowledge that concerns Riemann zeta-function and its generalizations in a cohesive manner. In particular, we have studied and mentioned some recent results regarding Hurwitz and Lerch functions, as well as Dirichlet's L-function. We have also investigated some fundamental concepts related to these functions and their universality properties. In addition, we also discuss different formulations and approaches to the proof of the Prime Number Theorem and the Riemann Hypothesis. These two topics constitute the main theme of this thesis. For the Prime Number Theorem, we provide a thorough discussion that compares and contrasts Norbert Wiener's proof with that of Newman's short proof. We have also related them to Hadamard's and de la Vallee Poussin's original proofs written in 1896. As far as the Riemann Hypothesis is concerned, we discuss some recent results related to equivalent formulations of the Riemann Hypothesis as well as the Generalized Riemann Hypothesis.

No description available.