密码学数学基础 - 连分数 | Alice and Bobの神秘小屋

不知道大家前面的章节学习如何，相比以你的聪明才智，一定是轻松愉快的吧！😎

如果学废了，也别灰心，这一章的内容相对来说是独立的，跟前面章节的内容没有太大关系，所以如果你觉得前面章节的内容有点难以理解或者记忆，那么这一章你可以先跳过，等到后面章节需要用到的时候再回来学习这一章的内容也完全没有问题。😉

那么，这一章我们将介绍一个非常有用的工具，叫做连分数（Continued Fraction）。连分数在数论中有着广泛的应用，特别是在求解某些类型的方程和近似数值方面。我们将从连分数的定义开始，逐步深入到它的性质和应用，最后我们还会介绍一些与连分数相关的算法和技巧。🤗

连分数的定义和表示 🧐

连分数是一种特殊的分数表示形式，它由一个整数部分和一个无限的分数部分组成。一个连分数可以表示为以下形式：

$a_0 + \frac{1}{a_1 + \frac{1}{a_2 + \frac{1}{a_3 + \cdots}}}$

其中 $a_0$ 是整数部分，$a_1, a_2, a_3, \ldots$ 是正整数，称为连分数的部分商。连分数可以用来表示实数，特别是无理数。对于一个实数 $x$，我们可以通过不断取整数部分和分数部分来构造它的连分数表示。我们可以直接用一个列表来表示连分数，例如，$[a_0, a_1, a_2, a_3, \ldots]$ 就表示上述的连分数形式。

而连分数可以分为有限连分数和无限连分数两种类型。有限连分数表示一个有理数，而无限连分数则表示一个无理数。对于一个有理数 $r$，它的连分数表示是有限的，而对于一个无理数 $x$，它的连分数表示是无限的。
这里有一个小定理（过于基础就不证明了）：任何有理数都可以表示成有限连分数；任何有限连分数都是一个有理数。

连分数的倒数 👽

有理数的倒数很简单，对应连分数的过程就是在前面加一个 $0$。

$[a_0, a_1, \ldots, a_n] = 0 + \frac{1}{[a_0, a_1, \ldots, a_n]} = [0, a_0, a_1, \ldots, a_n]$

负数的连分数表示 🥶

对于一个负数 $-x$，我们可以通过以下方式来表示它的连分数：

$\begin{align*} -x &= -\left(a_0 + \frac{1}{a_1 + \frac{1}{a_2 + \cdots}}\right) \\ &= -a_0 - \frac{1}{1 + \frac{1}{a_1 - 1 + \frac{1}{a_2 + \cdots}}} \\ &= [-(a_0 + 1), 1, a_1 - 1, a_2, \ldots] \end{align*}$

所以

$-x = [-(a_0 + 1), 1, a_1 - 1, a_2, \ldots]$

注意，如果 $a_1 = 1$，则需要将 $a_1$ 和 $a_2$ 合并成一个数，即 $-x = [-(a_0 + 1), a_2 + 1, a_3, \ldots]$。

连分数与有理数的转化 😜

有理数可以通过欧几里得算法来求解对应得连分数（当然我们也有专门的连分数算法更加高效），那么一个连分数怎么转化成一个有理数呢？

首先，我们发现连分数内部可以进行嵌套，例如 $[a0, a_1, a_2, a_3, \ldots, a_n] = [a_0, \ldots, a_m, [a{m+1}, a_{m+2}, \ldots, a_n]]$，其中 $0 \leq m < n$。
所以

$[a_0, a_1, \ldots, a_n] = a_0 + \frac{1}{a_1 + \frac{1}{a_2 + \frac{1}{\cdots + \frac{1}{a_n}}}} = \frac{a_0(a_1+\frac{1}{\ldots + \frac{1}{a_n}})+1}{a_1+\frac{1}{\ldots + \frac{1}{a_n}}}$

那么我们不断递推就可以得到一个有理数的分子和分母，最终得到连分数的有理数表示。

连分数唯一性定理① 😎

如果两个有限连分数 $[a_0, \ldots, a_n]$ 和 $[b_0, \ldots, b_m]$ 表示同一个有理数，那么它们的部分商必须完全相同，即 $a_i = b_i$ 对于所有 $i$ 都成立。

当然，有时候要注意，有限连分数的最后一个部分商不能为 $1$，要先进行合并，

$[a_0, a_1, \ldots, a_{n-1}, 1] = [a_0, a_1, \ldots, a_{n-1} + 1]$

否则会导致表示同一个有理数的连分数不唯一。例如，$[1, 2]$ 和 $[1, 1, 1]$ 都表示 $\frac{3}{2}$，但它们的部分商不同。

完全商 🥳

完全商是从连分数的最后一个元素开始分离出来的一段形成的连分数的有理数表示。
例如：$\frac{43}{19} = [2, 3, 1, 4]$，它的完全商是 $[4]$, $[1, 4]$, $[3, 1, 4]$ 和 $[2, 3, 1, 4]$，分别对应 $\frac{1}{4}$, $\frac{5}{4}$, $\frac{8}{5}$ 和 $\frac{43}{19}$。

周期连分数 🤩

周期连分数是一种特殊的无限连分数，它的部分商在某个位置开始重复出现，一般记作 $[a0, \ldots, a_m, \overline{a{m+1}, \ldots, an}]$，部分商 $[a{m+1}, \ldots, a_n]$ 无限重复出现，叫做周期。例如，$\sqrt{2}$ 的连分数表示为 $[1; \overline{2}]$，其中 $1$ 是整数部分，$2$ 是部分商，并且 $2$ 在后面无限重复出现。

这个周期连分数可以用来解一元二次方程，但是由于局限性不常用，所以我们只介绍一下一些好玩的东西。

对于一元二次方程 $ax^2 + bx + c = 0$，我们将 $u + \sqrt{w}$ 叫做二次不定根。
有两个相关定理（过于没必要证明，太麻烦了👻）：

欧拉定理：如果 $t$ 是周期连分数，它一定就是二次不定根
拉格朗日定理：如果 $t$ 是二次不定根，那么 $t$ 的连分数表示一定是周期连分数。

整点好玩的，介绍一个白银比例 $[2, 2, 2, \ldots] = 1 + \sqrt{2}$，首先对于方程 $x^2 - 2x -1 = 0$ 的解为 $1 + \sqrt{2}$。

$\begin{align*} x^2 - 2x -1 &= 0 \\ x^2 &= 2x + 1 \\ x &= 2 + \frac{1}{x} \\ &= 2 + \frac{1}{2 + \frac{1}{x}} \\ &= 2 + \frac{1}{2 + \frac{1}{2 + \frac{1}{x}}} \\ &= [2, 2, 2, \ldots] \end{align*}$

通过这样的迭代，我们就可以得到 $1 + \sqrt{2}$ 的连分数表示为 $[2, 2, 2, \ldots]$。

既然白银比例都出现了，那我们大名鼎鼎的黄金比例 $[1, 1, 1, \ldots] = \frac{1 + \sqrt{5}}{2}$ 也不例外了，对于方程 $x^2 - x -1 = 0$ 的解为 $\frac{1 + \sqrt{5}}{2}$。

$\begin{aligned} x^2 - x -1 &= 0 \\ x^2 &= x + 1 \\ x &= 1 + \frac{1}{x} \\ &= 1 + \frac{1}{1 + \frac{1}{x}} \\ &= 1 + \frac{1}{1 + \frac{1}{1 + \frac{1}{x}}} \\ &= [1, 1, 1, \ldots] \end{aligned}$

怎么样，是不是很有趣呢？😎

结论①证明 😭

结论①证明 😡

我们可以使用数学归纳法来证明结论①。

$[a_0, \ldots, a_n]$ 的整数部分是 $a_0$，$[b_0, \ldots, b_m]$ 的整数部分是 $b_0$，如果 $a_0 \neq b_0$，则 $[a_0, \ldots, a_n]$ 和 $[b_0, \ldots, b_m]$ 不可能表示同一个有理数。

$\frac{1}{x - a_0} = [a_1, \ldots, a_n]$，$\frac{1}{x - b_0} = [b_1, \ldots, b_m]$，如果 $a_0 = b_0$，则 $\frac{1}{x - a_0} = \frac{1}{x - b_0}$，所以 $[a_1, \ldots, a_n]$ 和 $[b_1, \ldots, b_m]$ 也表示同一个有理数。根据归纳假设，$a_i = b_i$ 对于所有 $i$ 都成立。

上一章：密码学数学基础 - 扩展二次剩余 👈
下一章：密码学数学基础 - 连分数进阶 👈
回到开始：关于我 👈

相关链接：
密码学算法 - 连分数算法 👈