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

$a_{i}, b_{i}$are complex numbers. The continued fraction with $b_{i} = 1\ \forall i$ is called a simple continued fraction and continued fractions with finite number of $a_{i}$ are called finite continued fractions.

Consider example rational numbers,

the continued fractions could be written as

Notation

A simple continued fraction is represented as a list of coefficients() i.e

for the above example

Computation of simple continued fractions

Given a number , the coefficients() in its continued fraction representation can be calculated recursively using

The above notation might not be obvious. Observing the structure of continued fraction with few coefficients will make them more evident:

SageMath provides functions continued_fraction and continued_fraction_list to work with continued fractions. Below is presented a simple implementation of continued_fractions.

Convergents of continued fraction

The convergent of a continued fractionis the numerical value or approximation calculated using the firstcoefficients of the continued fraction. The firstconvergents are

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

Continued fractions have many other applications. One such applicable in cryptology is based on Legendre's theorem in diophantine approximations.

Theorem: if, thenis a convergent of.

Wiener's attack on the RSA cryptosystem works by proving that under certain conditions, an equation of the formcould be derived whereis entirely made up of public information andis made up of private information. Under assumed conditions, the inequalityis statisfied, and the value(private information) is calculated from convergents of(public information), consequently breaking the RSA cryptosystem.