O'Reilly logo

Computer Security and Cryptography by Alan G. Konheim

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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.1 Diophantus determined all the integer Pythagorean triples (x, y, z), solutions of x2 + y2 = z2. He proved that if x and y are relatively prime and xy is positive and odd, then (x, y, z) = (x2y2, 2xy, x2 + y2) is a Pythagorean triple x2 + y2 = z2, 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

image

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|| = |qxp| < 1. Equivalently, |z − p/q| < 1, which asserts that p is the best choice for the numerator for the ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required