A convergent is a finite rational approximation formed by truncating a continued fraction. For irrational numbers, adding terms generally produces increasingly accurate approximations. section 8.4.2
Approximating π
The continued fraction π = [3; 7, 15, 1, 292] produces convergents 3, 22/7, 333/106, 355/113, and 103993/33102. Each additional truncation improves the approximation shown here. section 8.4.2
In Wiener’s attack on textbook RSA, convergents turn a continued fraction into private-exponent candidates:
- Expand the public ratio e/n into continued-fraction quotients. section 8.4.2
- Compute each convergent’s numerator and denominator using the two-term recurrence. section 8.4.2
- Treat each denominator as a candidate d and test whether decryption recovers the plaintext. section 8.4.2
Equation 8.22
\[\begin{aligned} \begin{aligned} c_0 &= \cfrac{3}{1} = 3.0 \\ c_1 &= 3 + \cfrac{1}{7} = \frac{22}{7} = 3.142857142857143 \\ c_2 &= 3 + \cfrac{1}{7 + \cfrac{1}{15}} = \frac{333}{106} = 3.141509433962264 \\ c_3 &= 3 + \cfrac{1}{7 + \cfrac{1}{15 + \cfrac{1}{1}}} = \frac{355}{113} = 3.1415929203539825 \\ c_4 &= 3 + \cfrac{1}{7 + \cfrac{1}{15 + \cfrac{1}{1 + \cfrac{1}{292}}}} = \frac{103993}{33102} = 3.1415926530119025 \\ \end{aligned} \label{equation:cf_pi} \end{aligned}\]Inspect the explicit convergents of π and their numerical accuracy. section 8.4.2
