# 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\_{0} + \frac{b\_{0}}{
a\_{1} + \frac{b\_{1}}{
a\_{2} + \frac{b\_{2}}{
\ddots
}}}
$$

$$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,

$$
\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

$$
\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

$$
a\_{0} + \frac{1}{
a\_{1} + \frac{1}{
a\_{2} + \frac{1}{
\ddots
}}}
$$

A simple continued fraction is represented as a list of coefficients($$a\_{i}$$) i.e 

$$
x = \[a\_{0};\ a\_{1},\ a\_{2},\ a\_{3},\ a\_{4},\ a\_{5},\ a\_{6},\ \ldots]
$$

for the above example 

$$
\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 $$x$$, the coefficients($$a\_{i}$$) in its continued fraction representation  can be calculated recursively using

$$
x\_{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:

$$
x\_{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`.

```python
def continued_fraction_list(xi):
    ai = floor(xi)
    if xi == ai: # last coefficient
        return [ai]
    return [ai] + continued_fraction_list(1/(x - ai))
```

## Convergents of continued fraction

The $$k^{th}$$convergent of a continued fraction$$x = \[a\_{0}; a\_{1},\ a\_{2},\ a\_{3},\ a\_{4},\ldots]$$is the numerical value or approximation calculated using the first$$k - 1$$coefficients of the continued fraction. The first$$k$$convergents are

$$
\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

```python
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$$\mid x - \frac{a}{b} \mid < \frac{1}{b^{2}}$$, then$$\frac{a}{b}$$is a convergent of$$x$$.

Wiener's attack on the RSA cryptosystem works by proving that under certain conditions, an equation of the form$$\mid x - \frac{a}{b} \mid$$could be derived where$$x$$is entirely made up of public information and$$\frac{a}{b}$$is made up of private information. Under assumed conditions, the inequality$$\mid x - \frac{a}{b} \mid < \frac{1}{b^{2}}$$is statisfied, and the value$$\frac{a}{b}$$(private information) is calculated from convergents of$$x$$(public information), consequently  breaking the RSA cryptosystem.


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://cryptohack.gitbook.io/cryptobook/fundamentals/continued-fractions.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.