CryptoBook
Search…
Continued Fractions

Continued Fractions

Continued fractions are a way of representing a number as a sum of an integer and a fraction.
Mathematically, a continued fraction is a representation
a0+b0a1+b1a2+b2a_{0} + \frac{b_{0}}{ a_{1} + \frac{b_{1}}{ a_{2} + \frac{b_{2}}{ \ddots }}}
ai,bia_{i}, b_{i}
are complex numbers. The continued fraction with
bi=1 ib_{i} = 1\ \forall i
is called a simple continued fraction and continued fractions with finite number of
aia_{i}
are called finite continued fractions.
Consider example rational numbers,
1711=1+611116=1+5665=1+1551=5+0\frac{17}{11} = 1 + \frac{6}{11} \\[10pt] \frac{11}{6} = 1 + \frac{5}{6} \\[10pt] \frac{6}{5} = 1 + \frac{1}{5} \\[10pt] \frac{5}{1} = 5 + 0
the continued fractions could be written as
51=565=1+15116=1+56=1+165=1+11+151711=1+611=1+1116=1+11+11+15\frac{5}{1} =5 \\[10pt] \frac{6}{5} = 1 + \frac{1}{5} \\[10pt] \frac{11}{6} = 1 + \frac{5}{6} = 1 + \frac{1}{\frac{6}{5}} = 1 + \frac{1}{1 + \frac{1}{5}} \\[10pt] \frac{17}{11} = 1 + \frac{6}{11} = 1 + \frac{1}{\frac{11}{6}} = 1 + \frac{1}{1 + \frac{1}{1 + \frac{1}{5}}}

Notation

a0+1a1+1a2+1a_{0} + \frac{1}{ a_{1} + \frac{1}{ a_{2} + \frac{1}{ \ddots }}}
A simple continued fraction is represented as a list of coefficients(
aia_{i}
) i.e
x=[a0; a1, a2, a3, a4, a5, a6, ]x = [a_{0};\ a_{1},\ a_{2},\ a_{3},\ a_{4},\ a_{5},\ a_{6},\ \ldots]
for the above example
1711=[1; 1, 1, 5]  ,116=[1; 1, 5]  ,65=[1;5]  ,51=[5;] \frac{17}{11} = [1;\ 1,\ 1,\ 5]\ \ ,\frac{11}{6} = [1;\ 1,\ 5]\ \ ,\frac{6}{5} = [1; 5]\ \ ,\frac{5}{1} = [5;]

Computation of simple continued fractions

Given a number
xx
, the coefficients(
aia_{i}
) in its continued fraction representation can be calculated recursively using
x0=xai=xixi+1=1xiaix_{0} = x \\[4pt] a_{i} = \lfloor x_{i} \rfloor \\[4pt] x_{i+1} = \frac{1}{x_{i} - a_{i}}
The above notation might not be obvious. Observing the structure of continued fraction with few coefficients will make them more evident:
x0=a0+1a1+1a2,   x1=a1+1a2,   x2=a2xi=ai+1xi+1xi+1=1xiaix_{0} = a_{0} + \frac{1}{a_{1} + \frac{1}{a_{2}}},\ \ \ x_{1} = a_{1} + \frac{1}{a_{2}}, \ \ \ x_{2} = a_{2} \\[10pt] x_{i} = a_{i} + \frac{1}{x_{i+1}} \\[10pt] x_{i+1} = \frac{1}{x_{i} - a_{i}}
SageMath provides functions continued_fraction and continued_fraction_list to work with continued fractions. Below is presented a simple implementation of continued_fractions.
1
def continued_fraction_list(xi):
2
ai = floor(xi)
3
if xi == ai: # last coefficient
4
return [ai]
5
return [ai] + continued_fraction_list(1/(x - ai))
Copied!

Convergents of continued fraction

The
kthk^{th}
convergent of a continued fraction
x=[a0;a1, a2, a3, a4,]x = [a_{0}; a_{1},\ a_{2},\ a_{3},\ a_{4},\ldots]
is the numerical value or approximation calculated using the first
k1k - 1
coefficients of the continued fraction. The first
kk
convergents are
a01,   a0+1a1,   a0+1a1+1a2, , a0+1a1+ak2+1ak1\frac{a_{0}}{1},\ \ \ a_{0} + \frac{1}{a_{1}}, \ \ \ a_{0} + \frac{1}{a_{1} + \frac{1}{a_{2}}}, \ \ldots,\ a_{0} + \frac{1}{a_{1} + \frac{\ddots} {a_{k-2} + \frac{1}{a_{k-1}}}}
One of the immediate applications of the convergents is that they give rational approximations given the continued fraction of a number. This allows finding rational approximations to irrational numbers.
Convergents of continued fractions can be calculated in sage
1
sage: cf = continued_fraction(17/11)
2
sage: convergents = cf.convergents()
3
sage: cf
4
[1; 1, 1, 5]
5
sage: convergents
6
[1, 2, 3/2, 17/11]
Copied!
Continued fractions have many other applications. One such applicable in cryptology is based on Legendre's theorem in diophantine approximations.
Theorem: if
xab<1b2\mid x - \frac{a}{b} \mid < \frac{1}{b^{2}}
, then
ab\frac{a}{b}
is a convergent of
xx
.
Wiener's attack on the RSA cryptosystem works by proving that under certain conditions, an equation of the form
xab\mid x - \frac{a}{b} \mid
could be derived where
xx
is entirely made up of public information and
ab\frac{a}{b}
is made up of private information. Under assumed conditions, the inequality
xab<1b2\mid x - \frac{a}{b} \mid < \frac{1}{b^{2}}
is statisfied, and the value
ab\frac{a}{b}
(private information) is calculated from convergents of
xx
(public information), consequently breaking the RSA cryptosystem.
Last modified 5mo ago