liveBook · Manning

Simple continued fraction

As explained in Hacking Cryptography

A simple continued fraction represents a number as an integer part followed by reciprocals of integers, with all numerators equal to one.

Represents a number as an integer followed by nested reciprocals of integers: [a0; a1, a2, ...]. Every numerator is one, making rational approximations easy to generate. section 8.4.2

For a rational fraction, repeatedly divide the numerator by the denominator, record each quotient, and continue with the remainder. Reconstructing successive prefixes produces convergents, increasingly useful rational approximations. section 8.4.2 section 8.4.2

Worked expansions

The fraction 44237/111361 expands to [0; 2, 1, 1, 13, 1, 8, 6, 1, 2, 1, 1, 3]. For π, successive convergents include 22/7 and 355/113. section 8.4.2 section 8.4.2

Equation 8.20
\[\begin{aligned} \begin{aligned} a_0 + \cfrac{1}{ a_1 + \cfrac{1}{ a_2 + \cfrac{1}{ a_3 + \cdots}}} \end{aligned} \label{equation:simple_cf} \end{aligned}\]

Displays the nested-reciprocal structure of a simple continued fraction. section 8.4.2

How Hacking Cryptography covers it

How deep it goes
Explains notation, expansion, and convergents, then implements quotient extraction and convergent generation in Go.
Examples
Uses π, 44237/111361, convergent lists, and Go tests implementing continued-fraction expansion.
What it assumes
Uses integer arithmetic, rational fractions, division, remainders, and basic RSA notation.
What you can do after
Apply it via integer quotient and remainder operations to generate convergents and test RSA private-exponent candidates.
How it connects
Connects rational approximation and convergents to RSA and Wiener’s attack.
Cover of Hacking Cryptography
liveBookmanning.com
Read Hacking Cryptography on liveBook Get the book at manning.com

This explainer was generated by Manning's knowledge graph from the text of Hacking Cryptography. The section links point to the parts of the book it draws on.