Computer Security and Cryptography

11.7 DIOPHANTINE APPROXIMATION

Diophantus was a Greek geometer who developed the theory of equations with integer solutions, a subject now referred to as diophantine equations.¹ Diophantus determined all the integer Pythagorean triples (x, y, z), solutions of x² + y² = z². He proved that if x and y are relatively prime and x − y is positive and odd, then (x, y, z) = (x² − y², 2xy, x² + y²) is a Pythagorean triple x² + y² = z², and conversely all primitive Pythagorean triples arise in this manner.

A standard reference on diophantine approximation is Cassels [1957].

Diophantine approximation studies the accuracy with which a real number x can be approximated by a rational number p/q. The accuracy of the approximation is measured by ||x − p/q||, where

It should be obvious that an approximation by rational numbers p/q of a real number, say π = 3.1415927…, is improved by increasing q. A basic result is

Proposition 11.10: [Cassels, 1957]:

11.10a	Given x and Q > 1, there exists an integer q with 0 < q < Q such that ||qx|| ≤ Q−1.
11.10b	There are infinitely many integers q such that ||qx|| < q−1.
11.10c	For every ∈ > 0 and real number x there are only finitely many integers q such that ||qx|| < q− 1 − ∈.
11.10d	If ||qx|| < 1, there exists an integer p such that ||qx|| = |qx − p| < 1. Equivalently, |z − p/q| < 1, which asserts that p is the best choice for the numerator for the ...