Pell Equation - Theory and applications to cryptography

The Pell equation $x^2 − d y^2 = 1$ is a classical topic in number theory. There are well known methods for solving this equation, but there are still several important issues. One of the most interesting from the point of view of cryptographic applications is the study of its solutions over a generic field, in which case new interesting open problems arise. This work focuses on studying the theoretical and practical potential of the Pell equation in this context. Firstly, the required theoretical results from the state of the art are collected using a new unique and simple notation. This allows to obtain easily and elegantly new properties also for the generalization of the Pell equation in the cubic case. Then, all the theoretical results are adopted to formulate new public–key encryption and digital signature schemes with security based on the integer factorization problem or on the discrete logarithm problem, namely new RSA–like and ElGamal cryptosystems, and new Digital Signature Algorithms. The obtained cryptosystems are compared in terms of security, data–size and performance with the classical alternatives, and the results are very interesting especially in the case of the quadratic Pell equation. Finally, the properties of the Pell equation are exploited for defining new powerful probabilistic primality tests, related to the Lucas test included in the widely used Baillie–PSW test. In particular, the new primality tests are equipped with adaptations of the Selfridge method for choosing the parameters, resulting in very powerful tests.