CryptoBook
  • CryptoBook
  • Book Plan
  • Style Guide
    • Sample Page
  • Contributors
  • Fundamentals
    • Mathematical Notation
    • Division and Greatest common divisor
      • Euclidean Algorithm
    • Modular Arithmetic
      • Theorems of Wilson, Euler, and Fermat
        • Fermat's Little Theorem in Detail
        • Euler's Theorem in Detail
      • Quadratic Residues
    • Continued Fractions
  • Number Theory
  • Ideals
  • Polynomials With Shared Roots
  • Integer Factorization
    • Pollard rho
    • Sieves
  • Abstract algebra
    • Groups
      • Another take on groups
      • Discrete Log Problem
    • Rings
    • Fields
    • Polynomials
  • Elliptic Curves
    • Untitled
  • Lattices
    • Introduction
    • LLL reduction
      • Gram-Schmidt Orthogonalization
      • Lagrange's algorithm
      • LLL reduction
    • Lattice reduction
      • Minkowski reduced
      • HKZ reduced
      • LLL reduced
    • Applications
      • Coppersmith algorithm
      • Extensions of Coppersmith algorithm
    • Hard lattice problems
    • Lattices of interest
    • Cryptographic lattice problems
      • Short integer solutions (SIS)
      • Learning with errors (LWE)
      • Ring-LWE
      • NTRU
    • Interactive fun
    • Resources and notations
  • Asymmetric Cryptography
  • RSA
    • Proof of correctness
    • RSA application
    • Low Private Component Attacks
      • Wiener's Attack
      • Boneh-Durfee Attack
    • Common Modulus Attack
    • Recovering the Modulus
  • Diffie-Hellman
    • MITM
  • Elliptic Curve Cryptography
  • Symmetric Cryptography
    • Encryption
    • The One Time Pad
    • AES
      • Rijndael Finite Field
      • Round Transformations
  • Hashes
    • Introduction / overview
    • The Birthday paradox / attack
  • Isogeny Based Cryptography
    • Introduction to Isogeny Cryptography
    • Isogenies
    • Isogeny and Ramanujan Graphs
  • Appendices
    • Sets and Functions
    • Probability Theory
Powered by GitBook
On this page
  • Continued Fractions
  • Notation
  • Computation of simple continued fractions
  • Convergents of continued fraction

Was this helpful?

Export as PDF
  1. Fundamentals

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+b2⋱a_{0} + \frac{b_{0}}{ a_{1} + \frac{b_{1}}{ a_{2} + \frac{b_{2}}{ \ddots }}}a0​+a1​+a2​+⋱b2​​b1​​b0​​

ai,bia_{i}, b_{i}ai​,bi​are complex numbers. The continued fraction with bi=1 ∀ib_{i} = 1\ \forall ibi​=1 ∀i is called a simple continued fraction and continued fractions with finite number of aia_{i}ai​ 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 + 01117​=1+116​611​=1+65​56​=1+51​15​=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}}}15​=556​=1+51​611​=1+65​=1+56​1​=1+1+51​1​1117​=1+116​=1+611​1​=1+1+1+51​1​1​

Notation

a0+1a1+1a2+1⋱a_{0} + \frac{1}{ a_{1} + \frac{1}{ a_{2} + \frac{1}{ \ddots }}}a0​+a1​+a2​+⋱1​1​1​

A simple continued fraction is represented as a list of coefficients(aia_{i}ai​) 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]x=[a0​; a1​, a2​, a3​, a4​, a5​, a6​, …]

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;]1117​=[1; 1, 1, 5]  ,611​=[1; 1, 5]  ,56​=[1;5]  ,15​=[5;]

Computation of simple continued fractions

Given a number xxx, the coefficients(aia_{i}ai​) in its continued fraction representation can be calculated recursively using

x0=xai=⌊xi⌋xi+1=1xi−aix_{0} = x \\[4pt] a_{i} = \lfloor x_{i} \rfloor \\[4pt] x_{i+1} = \frac{1}{x_{i} - a_{i}}x0​=xai​=⌊xi​⌋xi+1​=xi​−ai​1​

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=1xi−aix_{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}}x0​=a0​+a1​+a2​1​1​,   x1​=a1​+a2​1​,   x2​=a2​xi​=ai​+xi+1​1​xi+1​=xi​−ai​1​

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

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 kthk^{th}kthconvergent of a continued fractionx=[a0;a1, a2, a3, a4,…]x = [a_{0}; a_{1},\ a_{2},\ a_{3},\ a_{4},\ldots] x=[a0​;a1​, a2​, a3​, a4​,…]is the numerical value or approximation calculated using the firstk−1k - 1k−1coefficients of the continued fraction. The firstkkkconvergents are

a01,   a0+1a1,   a0+1a1+1a2, …, a0+1a1+⋱ak−2+1ak−1\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}}}}1a0​​,   a0​+a1​1​,   a0​+a1​+a2​1​1​, …, a0​+a1​+ak−2​+ak−1​1​⋱​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

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∣x−ab∣<1b2\mid x - \frac{a}{b} \mid < \frac{1}{b^{2}}∣x−ba​∣<b21​, thenab\frac{a}{b}ba​is a convergent ofxxx.

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

PreviousQuadratic ResiduesNextIdeals

Last updated 4 years ago

Was this helpful?