连分数（Continued Fractions）笔记

本篇部分整理自《初等数论（第四版）》（闵嗣鹤，严士健编）

连分数的定义

形如：

的分数被称作连分数。

在平常的使用中，为了节省篇幅，我们一般使用以下符号来表示上述连分数：

其中第二种表示方式最常用。

有关连分数的一些定理&定义

定义1（连分数的渐进分数）：

$[a_1,a_2,\cdots ,a_k]=\frac{p_k}{q_k}\ (1\le k\le n)$叫做连分数$(1)$的第$k$个渐进分数

定义2（简单连分数）：

若$a_1$是整数，$a_2,a_3,\cdots,a_k,\cdots$是正整数，则连分数

称为简单连分数，若$a$的个数有限，则称为有限简单连分数，若$a$的个数无限，则称为无限简单连分数.

对于无限连分数，若当$k→∞$时$[a_1,a_2,\cdots,a_n,\cdots]$的渐进分数$\frac{p_k}{q_k}$存在极限，则称这个极限为连分数$[a_1,a_2,\cdots,a_n,\cdots]$的值.

定义3（循环连分数）：

对于一个无限连分数$[a_1,a_2,\cdots,a_n,\cdots]$，如果能找到两个整数$s\ge0,t>0$使得

这个无限简单连分数就叫循环连分数，并简单地把它记作

定理1：

若连分数$[a_1,a_2,\cdots ,a_n]$的渐进分数是$\frac{p_1}{q_1},\frac{p_2}{q_2},\cdots ,\frac{p_n}{q_n}$，则在这些渐进分数之间，下列关系成立：

定理2：

若连分数$[a_1,a_2,\cdots ,a_n]$的$n$个渐进连分数是$\frac{p_k}{q_k},k=1,2,\cdots,n$，则下列两关系成立：

定理3：

设$[a_1,a_2,\cdots,a_n,\cdots]$是简单连分数，$\frac{p_k}{q_k}(k=1,2,\cdots)$是它的渐进分数，则：

定理4：

每一简单连分数表示一个实数.

定理5：

任一实无理数可以表成无限简单连分数.

定理5的推论：

对于实无理数$\alpha$，有

定理6：

每一实无理数只有一种唯一的方法表成无限简单连分数.

定理7：

定理8：

若$\alpha$是任一实数，$\frac{p_k}{q_k}$是$\alpha$的第$k$个渐进分数，则在分母小于等于$q_k$的一切有理数中，$\frac{p_k}{q_k}$是$\alpha$最好的有理近似值，即若$0<q\le q_k$，则

定理9：

每一循环连分数一定是某一整系数二次不可约方程的实根.

定理10：

若$f(x)=ax^2+bx+c$是一个整系数二次不可约多项式，$\alpha$是$f(x)=0$的一个实根，则表示$\alpha$的简单连分数是一循环连分数.

定理11（Legendre定理）：

对于有理数$\alpha$，若整数$c,d$满足

那么$\frac{c}{d}$就是$\alpha$的一个有理近似.

连分数的应用实例

佩尔方程(Pell equation)

定义：

形如$x^2-dy^2=1$的不定方程被称为佩尔方程

现求佩尔方程有正整数解的条件：

在实数域对方程$x^2-dy^2=1$进行分解有$(x+\sqrt{d}y)(x-\sqrt{d}y)=1$

(1)当$d$为完全平方数

则有$x+\sqrt{d}y,x-\sqrt{d}y$均为整数，那么若$(x+\sqrt{d}y)(x-\sqrt{d}y)=1$，则必有$x+\sqrt{d}y=x-\sqrt{d}y=1$

而满足这种情况的非负整数对$(x,y)=(1,0)$所以方程$x^2-dy^2=1$并不存在正整数解.

(2)当$d$为非完全平方数

定理12：

对任何正整数$n$，都存在两个整数$P_n,Q_n$，使得

成立.

定理13：

若$d$是一个非平方的正整数，$Q_n$为定理12中所定义，则二次不定方程$x^2-dy^2=(-1)^nQ_n$有正整数解$x,y$且$(x,y)=1$.

定理14：

若有$\sqrt{d}=[a_1,a_2, \cdots ,a_s,a_{s+1}, \cdots ,a_{s+t}],n>s$而$Q_n$为定理12所定义，则方程$x^2-dy^2=(-1)^nQ_n$有无穷多个正整数解 $|{p_{m+lt}}|,q_n+lt,2\ |\ l,l\ge0$ .（其中 $\frac {p_{m+lt}}{q_{m+lt}}$ 为 $\sqrt {d}$ 的第 $m+lt$ 个渐进分数）.

由定理14可知存在一正整数$Q$（取$Q=(-1)^nQ_n,n>s$）使得不定方程$x^2-dy^2=Q$有无穷多组正整数解，则在这些解中必存在两组不同的正整数$x_1y_1;x_2y_2$使得

成立.由于$x^2_1-dy^2_1=x^2_2-dy^2_2=Q$，故有

由$x_1\equiv x_2\ (mod\ |{Q}|)\ ,\ y_1\equiv y_2\ (mod\ |{Q}|)$可得：

故若令$|{\frac{x_1x_2-dy_1y_2}{Q}}|=x,|{\frac{x_1y_2-x_2y_1}{Q}}|=y$，可知$x,y$均为非负整数且为方程$x^2-dy^2=1$的一解.

显然有$x\neq0$，否则有$-dy^{2}=1$，与$d>0$矛盾；且有$y\neq0$否则有$x_1y_2-x_2y_1=0$，由引理2知$(x_1,y_1)=(x_2,y_2)=1$，所以有$x_1\ |\ x_2,x_2\ |\ x_1$，由于$x_1,x_2$均为正整数，所以有$x_1=x_2,y_1=y_2$，与$x_1,y_1;x_2;y_n$不同的定义相悖.故可知$x,y$为方程$x^2-dy^2=1$的一组正整数解.

综上所述，当$d$为完全平方数时，不定方程$x^2-dy^2=1$有正整数解.

现在求不定方程$x^2-dy^2=1$的正整数解：

定理15：

若$x_0,y_0$是方程$x^2-dy^2=1$的一组正整数解，且$x_0+\sqrt{d}y_0$是形如$x+\sqrt{d}y$（$x,y$是方程$x^2-dy^2=1$的正整数解）的最小数，则方程$x^2-dy^2=1$的一切正整数解$x,y$可以由

确定.

有了定理15，我们可以通过一个佩尔方程的最小正整数解求出这个佩尔方程的所有解.现在我们的目标就成为找到如何求佩尔方程的最小正整数解.

实际上，对于不为完全平方数的$\sqrt{d}=[a_1,a_2,\cdots,a_n,\cdots]$我们总能找到$a_{n+1}$满足$a_i=2a_1(i=2,3,\cdots,n)$，则$\frac{x}{y}=[a_1,a_2,\cdots,a_{n}]$可能为$d$定义的佩尔方程的一组解.

求佩尔方程最小整数解的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
from sage.all import*
d = ...
cf = continued_fraction(sqrt(d))
a0 = cf[0]
i = 1
while True:
    if cf[i] == 2*a0:
        c = cf.convergent(i-1)
        x, y = c.as_integer_ratio()
        if x**2 - d*y**2 == 1:
            print((x,y))
            break
    i = i + 1

在这里扩展地提一下广义佩尔方程：

定义

形如$x^2-dy^2=c$的方程称为广义佩尔方程.

求解

通过连分数求出广义佩尔方程的最小正整数解$(x_0,y_0)$后，可以知道$(x_0r+Dy_0s,x_0s+y_0r)$也是该方程的整数解（其中$r,s$为方程$r^2-ds^2=1$的整数解）

求解代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
from sage.all import *
def pell_roots(D: int, C: int = 1):
    intervals = 2**10
    def get_a_root(D: int, C: int):
        cf = continued_fraction(sqrt(D))
        for i in range(1, intervals):
            c = cf.convergent(i - 1)
            x, y = c.as_integer_ratio()
            if x**2 - D * y**2 == C:
                return x, y
        for y in range(1, intervals):
            x2 = C + D * y**2
            if x2 <= 0:
                continue
            x = isqrt(x2)
            if x ** 2 == x2:
                return x, y
        return 0, 0 
    r, s = get_a_root(D, 1)
    x, y = get_a_root(D, C)
    while True:
        yield x, y
        x, y = x * r + D * y * s, r * y + s * x
D = ...
C = ...
x, y = next(pell_roots(D, C))
print(x**2 - D * y**2 == C)
print((x,y))

RSA的维纳攻击

原理

考虑一般的RSA，$c\equiv m^e\ (mod\ n),n=pq$，$p,q$均为质数，在这里$e$非常大，这也是适用维纳攻击的RSA的明显特征，有$\varphi(n)=(p-1)(q-1)$，则有

故有$p^2+p\big[\varphi(n)-n-1\big]+n=0$

故若我们已知$n$和$\varphi(n)$，我们就可以对$n$进行分解.

又由于在RSA中，有$ed\equiv1\ (mod\ \varphi(n))$，所以存在整数$k$使得$ed=k\varphi(n)+1$

即有

由定理11（Legendre定理）可知：$\frac{k}{d}$是$\frac{e}{\varphi(n)}$的一个有理近似，故我们可以通过$\frac{e}{\varphi(n)}$的有理近似获得$\frac{k}{d}$，当$n=pq$且$q<p<2q$时，若满足$d<\frac{1}{3}n^\frac{1}{4}$，则$\frac{k}{d}$为$\frac{e}{n}$的一个有理近似.

求解步骤

(1)估测是否满足$d<\frac{1}{3}n^\frac{1}{4}$

(2)求$\frac{e}{n}$的连分数展开

(3)迭代连分数$\frac{k_i}{d_i}$：先使用$k_i,d_i$求出$\varphi_i(n)$，再通过$\varphi_i(n)$计算出$n$，验证$\varphi_i(n)$是否正确

解密脚本：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#sage
def wienerAttack(n, e):
    cf = continued_fraction(e / n)
    convers = cf.convergents()
    for pkd in convers:
        pk, pd = pkd.as_integer_ratio()
        if pk == 0:
            continue
        if (e * pd - 1) % pk != 0:
            continue
        pphi = (e * pd - 1) // pk
        p = var('p', domain=ZZ)
        roots = solve(p ** 2 + (pphi - n - 1) * p + n, p)
        if len(roots) == 2:
            pp, pq = roots
            if pp * pq == n:
                return pp, pq, pd
    raise ValueError('Error')
n = ...
e = ...
c = ...
p, q, d = wienerAttack(n, e)
m = pow(c, d, n)