Two Number-Theoretic Problems That Illustrate the Power and Limitations of Randomness

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.