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
are complex numbers. The continued fraction with is called a simple continued fraction and continued fractions with finite number of are called finite continued fractions.
Consider example rational numbers,
the continued fractions could be written as
A simple continued fraction is represented as a list of coefficients() i.e
for the above example
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_list to work with continued fractions. Below is presented a simple implementation of
def continued_fraction_list(xi):ai = floor(xi)if xi == ai: # last coefficientreturn [ai]return [ai] + continued_fraction_list(1/(x - ai))
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
sage: cf = continued_fraction(17/11)sage: convergents = cf.convergents()sage: cf[1; 1, 1, 5]sage: convergents[1, 2, 3/2, 17/11]
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.