本篇部分整理自《初等数论(第四版)》(闵嗣鹤,严士健编)

连分数的定义

形如: (1)a1+1a2+1a3++1an 的分数被称作连分数。

在平常的使用中,为了节省篇幅,我们一般使用以下符号来表示上述连分数: a1+1a2+1a3+1a4+1an[a1,a2,,an] 其中第二种表示方式最常用。

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

定义1(连分数的渐进分数):

[a1,a2,,ak]=pkqk (1kn)叫做连分数(1)的第k渐进分数

定义2(简单连分数):

a1是整数,a2,a3,,ak,是正整数,则连分数 [a1,a2,,ak,] 称为简单连分数,若a的个数有限,则称为有限简单连分数,若a的个数无限,则称为无限简单连分数.

对于无限连分数,若当k[a1,a2,,an,]的渐进分数pkqk存在极限,则称这个极限为连分数[a1,a2,,an,]的值.

定义3(循环连分数):

对于一个无限连分数[a1,a2,,an,],如果能找到两个整数s0,t>0使得 as+i=as+kt+i,   i=1,2,,t;    k=0,1,2, 这个无限简单连分数就叫循环连分数,并简单地把它记作 [a1,a2,,as,as+1,,as+t]

定理1:

若连分数[a1,a2,,an]的渐进分数是p1q1,p2q2,,pnqn,则在这些渐进分数之间,下列关系成立: p1=a1,p2=a2a1+1pk=akpk1+pk2,q1=1,q2=a2             qk=akqk1+qk2,,   3kn

定理2:

若连分数[a1,a2,,an]n个渐进连分数是pkqk,k=1,2,,n,则下列两关系成立: (1)(1)  pkqk1pk1qk=(1)k,          k2(2)(2)  pkqk2pk2qk=(1)k1ak,  k3

定理3:

[a1,a2,,an,]是简单连分数,pkqk(k=1,2,)是它的渐进分数,则: (3)(1)  k3qkqk1+1k,qkk1(4)(2)  p2(k1)q2(k1)>p2kq2k,p2k1q2k1>p2k3q2k3,p2kq2k>p2k1q2k1(5)(3)pkqk(k=1,2,)

定理4:

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

定理5:

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

定理5的推论:

对于实无理数α,有 α=pkqk+(1)k1δkqkqk+1α=pkqk+(1)k1δkqk2,0<δk<1,0<δk<1

定理6:

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

定理7:

(6)(1)ab=[a1,a2,,an]=[b1,b2,,bn],an>1,bm>1m=n,ai=bi  (i=1,2,,n)(7)(2)abab=[a1,a2,,an]=[a1,a2,,an1,1]

定理8:

α是任一实数,pkqkα的第k个渐进分数,则在分母小于等于qk的一切有理数中,pkqkα最好的有理近似值,即若0<qqk,则 |αpkqk||αpq|

定理9:

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

定理10:

f(x)=ax2+bx+c是一个整系数二次不可约多项式,αf(x)=0的一个实根,则表示α的简单连分数是一循环连分数.

定理11(Legendre定理):

对于有理数α,若整数c,d满足 |αcd|<12d2 那么cd就是α的一个有理近似.

连分数的应用实例

佩尔方程(Pell equation)

定义:

形如x2dy2=1的不定方程被称为佩尔方程

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

在实数域对方程x2dy2=1进行分解有(x+dy)(xdy)=1

(1)当d为完全平方数

则有x+dy,xdy均为整数,那么若(x+dy)(xdy)=1,则必有x+dy=xdy=1

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

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

定理12:

对任何正整数n,都存在两个整数Pn,Qn,使得 αn=d+PnQn,Pn2d (mod Qn) 成立.

定理13:

d是一个非平方的正整数,Qn定理12中所定义,则二次不定方程x2dy2=(1)nQn有正整数解x,y(x,y)=1.

定理14:

若有d=[a1,a2,,as,as+1,,as+t],n>sQn定理12所定义,则方程x2dy2=(1)nQn有无穷多个正整数解 |pm+lt|,qn+lt,2 | l,l0 .(其中 pm+ltqm+ltd 的第 m+lt 个渐进分数).

定理14可知存在一正整数Q(取Q=(1)nQn,n>s)使得不定方程x2dy2=Q有无穷多组正整数解,则在这些解中必存在两组不同的正整数x1y1;x2y2使得 x1x2 (mod |Q|) , y1y2 (mod |Q|) 成立.由于x12dy12=x22dy22=Q,故有 Q2=(x12dy12)(x22dy22)=(x1x2dy1y2)2d(x1y2x2y1)2x1x2 (mod |Q|) , y1y2 (mod |Q|)可得: x1x2dy1y2x12dy120 (mod |Q|),x1y2x2y1x1y1x1y10 (mod |Q|) 故若令|x1x2dy1y2Q|=x,|x1y2x2y1Q|=y,可知x,y均为非负整数且为方程x2dy2=1的一解.

显然有x0,否则有dy2=1,与d>0矛盾;且有y0否则有x1y2x2y1=0,由引理2知(x1,y1)=(x2,y2)=1,所以有x1 | x2,x2 | x1,由于x1,x2均为正整数,所以有x1=x2,y1=y2,与x1,y1;x2;yn不同的定义相悖.故可知x,y为方程x2dy2=1的一组正整数解.

综上所述,当d为完全平方数时,不定方程x2dy2=1有正整数解.

现在求不定方程x2dy2=1的正整数解:

定理15:

x0,y0是方程x2dy2=1的一组正整数解,且x0+dy0是形如x+dyx,y是方程x2dy2=1的正整数解)的最小数,则方程x2dy2=1的一切正整数解x,y可以由 x±dy=(x0+dy0)n,n=1,2, 确定.

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

实际上,对于不为完全平方数的d=[a1,a2,,an,]我们总能找到an+1满足ai=2a1(i=2,3,,n),则xy=[a1,a2,,an]可能为d定义的佩尔方程的一组解.

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

python
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

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

定义

形如x2dy2=c的方程称为广义佩尔方程.

求解

通过连分数求出广义佩尔方程的最小正整数解(x0,y0)后,可以知道(x0r+Dy0s,x0s+y0r)也是该方程的整数解(其中r,s为方程r2ds2=1的整数解)

求解代码

python
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,cme (mod n),n=pqp,q均为质数,在这里e非常大,这也是适用维纳攻击的RSA的明显特征,有φ(n)=(p1)(q1),则有 φ(n)=(p1)(q1)=pqpq+1=Npnp+1 故有p2+p[φ(n)n1]+n=0

故若我们已知nφ(n),我们就可以对n进行分解.

又由于在RSA中,有ed1 (mod φ(n)),所以存在整数k使得ed=kφ(n)+1

即有 |eφ(n)kd|=1dφ(n)定理11(Legendre定理)可知:kdeφ(n)的一个有理近似,故我们可以通过eφ(n)的有理近似获得kd,当n=pqq<p<2q时,若满足d<13n14,则kden的一个有理近似.

求解步骤

(1)估测是否满足d<13n14

(2)求en的连分数展开

(3)迭代连分数kidi:先使用ki,di求出φi(n),再通过φi(n)计算出n,验证φi(n)是否正确

解密脚本:

python
#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)