Two Number-Theoretic Problems That Illustrate the Power and Limitations of Randomness
Andrew Shallue · 2007
This thesis contains work on two problems in algorithmic number theory. The first problem is to give an algorithm that constructs a rational point on an elliptic curve over a finite field. A fast and easy randomized algorithm has existed for some time. We prove that in the case where the finite field has characteristic 2, there is a deterministic algorithm with the same asymptotic running time as the existing randomized algorithm. The second problem is the random modular subset sum problem. Let t, n, m be given, and let a1,..., an ∈ Z/mZ be chosen uniformly at random. The goal is to find a subset of the ai that sum to t in Z/mZ. Define the density of a subset sum problem to be n/(log 2 m). For the case of constant density greater than 1, we apply the multi-set birthday problem to give the first algorithm that uses less time and space than dynamic pro-gramming. In particular, for parameter k < n and problems of density greater than k, the algorithm uses � O(m 1 / log 2 k) time and space. It is a randomized algorithm, and will output a solution with probability 1 − e −Ω(n) , where the constant depends on k and on the density. i