Cryptography is defined to be the practice and studying of hiding information and is used in applications present today; examples include the security of ATM cards and computer passwords ([34]). In order to transform information to make it unreadable, one needs a series of algorithms. Many of these algorithms are based on elliptic curves because they require fewer bits. To use such algorithms, one must find the rational points on an elliptic curve. The study of Algebraic Number Theory, and in particular, rare objects known as power bases, help determine what these rational points are. With such broad applications, studying power bases is an interesting topic with many research opportunities, one of which is given below. There are many similarities between Cyclic and Dihedral fields of prime degree; more specifically, the structure of their field discriminants is comparable. Since the existence of power bases (i.e. monogenicity) is based upon finding solutions to the index form equation - an equation dependant on field discriminants - does this imply monogenic properties of such fields are also analogous? For instance, in [14], Marie-Nicole Gras has shown there is only one monogenic cyclic field of degree 5. Is there a similar result for dihedral fields of degree 5? The purpose of this thesis is to show that there exist infinitely many monogenic dihedral quintic fields and hence, not just one or finitely many. We do so by using a well- known family of quintic polynomials with Galois group D₅. Thus, the main theorem given in this thesis will confirm that monogenic properties between cyclic and dihedral quintic fields are not always correlative.

Let $E$ be an elliptic curve over the rationals without complex multiplication such that any elliptic curve $\mathbb{Q}$-isogenous to $E$ has trivial $\mathbb{Q}$-torsion. Koblitz conjectured that the number of primes less than $x$ for which $|E(\mathbb{F}_p)|$ is prime is asymptotic to $$C_E\frac{x}{(\log{x})^2} $$ for $C_E$ some constant dependent on $E.$ Miri and Murty showed that for infinitely many $p,$ $|E(\mathbb{F}_p)|$ has at most 16 prime factors using the lower bound sieve and assuming the Generalized Riemann Hypothesis. This thesis generalizes Koblitz's conjectures to a function field setting through Drinfeld modules. Let $\phi$ be a Drinfeld module of rank 2, and $\mathbb{F}_q$ a finite field with every $\mathbb{F}_q[t]$-isogeny having no $\mathbb{F}_q[t]$-torsion points and with $\text{End}_{\overline{k}}(\phi)=\mathbb{F}_q[t].$ Furthermore assume that for each monic irreducible $l\in \mathbb{F}_q[t],$ the extension generated by adjoining the $l$-torsion points of $\phi$ to $\mathbb{F}_q(t)$ is geometric. Then there exists a positive constant $C_{\phi}$ depending on $\phi$ such that there are more than $$ C_{\phi}\frac{q^x}{x^2}$$ monic irreducible polynomials $P$ with degree less then $x$ such that $\chi_{\phi}(P)$ has at most 13 prime factors. To prove this result we develop the theory of Drinfeld modules and a translation of the lower bound sieve to function fields.

This thesis will survey a group of problems related to certain number-theoretic functions. In particular, for said functions, these problems take the form of when and how often they are equal over consecutive integers, n and n+1. The first chapter will introduce the functions and the histories of the related problems. The second chapter will take on a variant of the Ruth-Aaron pairs problem, which asks how often sums of primes of two consecutive integers are equal. The third chapter will examine, in depth, a proof by D.R. Heath-Brown of the infinitude of consecutive integer pairs with the same number of divisors---i.e. such that d(n)=d(n+1). After that we examine a similar proof of the infinitude of pairs with the same number of prime factors---ω(n)=ω(n+1).

Let $E$ be an elliptic curve over the rationals without complex multiplication such that any elliptic curve $\mathbb{Q}$-isogenous to $E$ has trivial $\mathbb{Q}$-torsion. Koblitz conjectured that the number of primes less than $x$ for which $|E(\mathbb{F}_p)|$ is prime is asymptotic to $$C_E\frac{x}{(\log{x})^2} $$ for $C_E$ some constant dependent on $E.$ Miri and Murty showed that for infinitely many $p,$ $|E(\mathbb{F}_p)|$ has at most 16 prime factors using the lower bound sieve and assuming the Generalized Riemann Hypothesis. This thesis generalizes Koblitz's conjectures to a function field setting through Drinfeld modules. Let $\phi$ be a Drinfeld module of rank 2, and $\mathbb{F}_q$ a finite field with every $\mathbb{F}_q[t]$-isogeny having no $\mathbb{F}_q[t]$-torsion points and with $\text{End}_{\overline{k}}(\phi)=\mathbb{F}_q[t].$ Furthermore assume that for each monic irreducible $l\in \mathbb{F}_q[t],$ the extension generated by adjoining the $l$-torsion points of $\phi$ to $\mathbb{F}_q(t)$ is geometric. Then there exists a positive constant $C_{\phi}$ depending on $\phi$ such that there are more than $$ C_{\phi}\frac{q^x}{x^2}$$ monic irreducible polynomials $P$ with degree less then $x$ such that $\chi_{\phi}(P)$ has at most 13 prime factors. To prove this result we develop the theory of Drinfeld modules and a translation of the lower bound sieve to function fields.

This thesis will survey a group of problems related to certain number-theoretic functions. In particular, for said functions, these problems take the form of when and how often they are equal over consecutive integers, n and n+1. The first chapter will introduce the functions and the histories of the related problems. The second chapter will take on a variant of the Ruth-Aaron pairs problem, which asks how often sums of primes of two consecutive integers are equal. The third chapter will examine, in depth, a proof by D.R. Heath-Brown of the infinitude of consecutive integer pairs with the same number of divisors---i.e. such that d(n)=d(n+1). After that we examine a similar proof of the infinitude of pairs with the same number of prime factors---ω(n)=ω(n+1).

In the last twenty years, algebraic techniques have been applied with great success to several areas in theoretical computer science. However, for many problems involving modular counting, there is a huge gap in our understanding depending on whether the modulus is prime or composite. A prime example is the problem of showing lower bounds for circuits with Mod gates in circuit complexity. Proof techniques that work well for primes break down over composites. Moreover, in some cases, the problem for composites turns out to be very different from the prime case. Making progress on these problems seems to require a better understanding of polynomials over composites. In this thesis, we address some such "prime vs. composite" problems from algorithms, complexity and combinatorics, and the surprising connections between them. We consider the complexity-theoretic problem of computing Boolean functions using polynomials modulo composites. We show that symmetric polynomials can viewed as simultaneous communication protocols. This equivalence allows us to use techniques from communication complexity and number theory to prove degree bounds. We use these to give the first tight degree bounds for a number of Boolean functions. We consider the combinatorial problem of explicit construction of Ramsey graphs. We present a simple construction of such graphs using polynomials modulo composites. This approach gives a unifying view of many known constructions,and explains why they all achieve the same bound.We show that certain approaches to this problem cannot give better bounds. Finally, we consider the algorithmic problem of interpolation for polynomials modulo composites. We present the first query-efficient algorithms for interpolation and learning under a distribution. These results rely on some new structural results about such polynomials.

We prove several theorems in the intersection of harmonic analysis, combinatorics, probability and number theory. In the second section we use combinatorial methods to construct various sets with pathological combinatorial properties. In particular, we answer a question of P. Erdos and V. Sos regarding unions of Sidon sets. In the third section we use incidence bounds and bilinear methods to prove several new endpoint restriction estimates for the Paraboloid over finite fields. In the fourth and fifth sections we study a variational maximal operators associated to orthonormal systems. Here we use probabilistic techniques to construct well-behaved rearrangements and base changes. In the sixth section we apply our variational estimates to a problem in sieve theory. In the seventh section, motivated by applications to sieve theory, we disprove a maximal inequality related to multiplicative characters. / text

This report discusses some of the uses of algorithms within number theory. Topics examined include the applications of algorithms in the study of cryptology, the Euclidean Algorithm, prime generating functions, and the connections between algorithmic number theory and high school algebra. / text

In many emerging applications, such as sensor networks, location-based services, and data integration, the database is inherently uncertain. To handle a large amount of uncertain data, probabilistic databases have been recently proposed, where probabilistic queries are enabled to provide answers with statistical guarantees. In this thesis, we study the important issues of managing the quality of a probabilistic database. We first address the problem of measuring the ambiguity, or quality, of a probabilistic query. This is accomplished by computing the PWS-quality score, a recently proposed measure for quantifying the ambiguity of query answers under the possible world semantics. We study the computation of the PWS-quality for the top-k query. This problem is not trivial, since directly computing the top-k query score is computationally expensive. To tackle this challenge, we propose efficient approximate algorithms for deriving the quality score of a top-k query. We have performed experiments on both synthetic and real data to validate their performance and accuracy. Our second contribution is to study how to use the PWS-quality score to coordinate the process of cleaning uncertain data. Removing ambiguous data from a probabilistic database can often give us a higher-quality query result. However, this operation requires some external knowledge (e.g., an updated value from a sensor source), and is thus not without cost. It is important to choose the correct object to clean, in order to (1) achieve a high quality gain, and (2) incur a low cleaning cost. In this thesis, we examine different cleaning methods for a probabilistic top-k query. We also study an interesting problem where different query users have their own budgets available for cleaning. We demonstrate how an optimal solution, in terms of the lowest cleaning costs, can be achieved, for probabilistic range and maximum queries. An extensive evaluation reveals that these solutions are highly efficient and accurate. / published_or_final_version / Computer Science / Master / Master of Philosophy

This report discusses the history, use, and future of elliptic curves. Uses of elliptic curves in various number theory settings are presented. Fermat’s Last Proof is shown to be proven with elliptic curves. Finally, the future of elliptic curves with respect to cryptography and primality is shown. / text