Improving regulator verification and compact representations in real quadratic fields

Abstract

The study of Diophantine equations, and in particular the erroneously-named Pell equation, has a long and intriguing history. In this work, we investigate solutions to the Pell equation and to a closely related quantity called the fundamental unit. Though it is somewhat simple to show these equations have non-trivial solutions, finding unconditionally correct solutions and being able to express them is extremely challenging, both from a theoretical and a computational perspective. We develop improvements to the algorithm presented by de Haan, Jacobson, and Williams [21, 22] which unconditionally verifies the regulator of a real quadratic number field and refinements to the concept of a compact representation of a quadratic integer, originally given by Buchmann, Thiel, and Williams [12]. In addition, we consider the well-known applications of this theory to principal ideal testing, finding integer points on elliptic curves, finding solutions to Diophantine equations, and some particular cryptographic applications.