Dirichlet's approximation theorem: Difference between revisions

Revision as of 15:56, 11 November 2024

Revision as of 04:19, 13 December 2024

Line 45:

=== Legendre's theorem on continued fractions ===

{{see also|Simple continued fraction}}

In his ''Essai sur la théorie des nombres'' (1798), [[Adrien-Marie Legendre]] derives a necessary and sufficient condition for a rational number to be a convergent of the [[simple continued fraction]] of a given real number.<ref>{{cite book|last=Legendre|first=Adrien-Marie|author-link=Adrien-Marie Legendre|title=Essai sur la théorie des nombres|date=1798|publisher=Duprat|___location=Paris|publication-date=1798|pages=27–29|language=fr}}</ref> A consequence of this criterion, often called '''Legendre's theorem''' within the study of continued fractions, is as follows:<ref>{{cite journal|lastlast1=Barbolosi|firstfirst1=Dominique|last2=Jager|first2=Hendrik|date=1994|title=On a theorem of Legendre in the theory of continued fractions|url=https://www.jstor.org/stable/26273940|journal=[[Journal de Théorie des Nombres de Bordeaux]]|volume=6|issue=1|pages=81–94|doi=10.5802/jtnb.106 |jstor=26273940 |via=JSTOR}}</ref>

'''Theorem'''. If ''α'' is a real number and ''p'', ''q'' are positive integers such that <math>\left|\alpha - \frac{p}{q}\right| < \frac{1}{2q^2}</math>, then ''p''/''q'' is a convergent of the continued fraction of ''α''.

{{collapse top|title = Proof}}

'''Proof'''. We follow the proof given in ''[[An Introduction to the Theory of Numbers]]'' by [[G. H. Hardy]] and [[E. M. Wright]].<ref>{{cite book|lastlast1=Hardy|firstfirst1=G. H.|author-linklink1=G. H. Hardy|last2=Wright|first2=E. M.|author-link2=E. M. Wright|title=An Introduction to the Theory of Numbers|title-link=An Introduction to the Theory of Numbers|publisher=[[Oxford University Press]]|year=1938|isbn=|___location=London|publication-date=1938|pages=140–141, 153|language=en}}</ref>

Suppose ''α'', ''p'', ''q'' are such that <math>\left|\alpha - \frac{p}{q}\right| < \frac{1}{2q^2}</math>, and assume that ''α'' > ''p''/''q''. Then we may write <math>\alpha - \frac{p}{q} = \frac{\theta}{q^2}</math>, where 0 < ''θ'' < 1/2. We write ''p''/''q'' as a finite continued fraction [''a''₀; ''a''₁, ..., ''a_n''], where due to the fact that each rational number has two distinct representations as finite continued fractions differing in length by one (namely, one where ''a_n'' = 1 and one where ''a_n'' ≠ 1), we may choose ''n'' to be even. (In the case where ''α'' < ''p''/''q'', we would choose ''n'' to be odd.)

Line 58:

{{collapse bottom}}

This theorem forms the basis for [[Wiener's attack]], a polynomial-time exploit of the [[RSA (cryptosystem)|RSA cryptographic protocol]] that can occur for an injudicious choice of public and private keys (specifically, this attack succeeds if the prime factors of the public key ''n'' = ''pq'' satisfy ''p'' < ''q'' < 2''p'' and the private key ''d'' is less than (1/3)''n''^1/4).<ref>{{cite journal|last=Wiener|first=Michael J.|date=1990|title=Cryptanalysis of short RSA secret exponents|url=https://ieeexplore.ieee.org/document/54902|journal=[[IEEE Transactions on Information Theory]]|volume=36|issue=3|pages=553–558|doi=10.1109/18.54902 |via=IEEE}}</ref>

==See also==

Line 70:

==References==

*{{cite book |authorlink=Wolfgang M. Schmidt |first=Wolfgang M |last=Schmidt |title=Diophantine approximationApproximation |publisher=Springer |series=Lecture Notes in Mathematics |volume=785 |year=1980 |isbn=978-3-540-38645-2 |doi=10.1007/978-3-540-38645-2}}

*{{cite book |first=Wolfgang M. |last=Schmidt |title=Diophantine Approximations and Diophantine Equations |publisher=Springer |series=Lecture Notes in Mathematics book series |volume=1467 |year=1991 |isbn=978-3-540-47374-9 |doi=10.1007/BFb0098246|s2cid=118143570 }}