密码学算法 - 连分数算法

当你在计算某个数的近似值时🔍，或者在求解某个方程的根时🧮，连分数算法 就像一把神奇的放大镜🔎，能帮你逐步逼近那个隐藏在数字背后的真相。

欢迎来到《密码学核心算法实战》的连分数专题！这里没有纸上谈兵的理论空谈（真的不画大饼😉），只有一把把能直接撬动数据安全的精密齿轮⚙️。

连分数算法的操作 🌟

这个算法可以直接将一个有理数或者无理数直接表示成一个连分数形式，当然因为这个算法的原理十分简单，所以就不单独拿出来讲了，直接进入正题！🤗

输入：一个实数x xx。
令i = 0 i = 0i=0，x 0 = x x_0 = xx0​=x

1. 令a i a_iai​为x i x_ixi​的整数部分
2. b i = x i − a i b_i = x_i - a_ibi​=xi​−ai​，如果b i = 0 b_i = 0bi​=0，则算法结束
3. 如果b i ≠ 0 b_i \neq 0bi​=0，则令x i + 1 = 1 b i x_{i+1} = \frac{1}{b_i}xi+1​=bi​1​，i = i + 1 i = i + 1i=i+1，回到步骤 1

输出：连分数的部分商a 0 , a 1 , a 2 , … a_0, a_1, a_2, \ldotsa0​,a1​,a2​,…，即x = [ a 0 , a 1 , a 2 , … ] x = [a_0, a_1, a_2, \ldots]x=[a0​,a1​,a2​,…]。

反过来，x = [ a 0 , a 1 , a 2 , … ] x = [a_0, a_1, a_2, \ldots]x=[a0​,a1​,a2​,…]也可以通过递推关系来计算出x xx的近似值。

设x n = [ a 0 , a 1 , … , a n ] x_n = [a_0, a_1, \ldots, a_n]xn​=[a0​,a1​,…,an​]，则有递推关系：

p n = a n p n − 1 + p n − 2 q n = a n q n − 1 + q n − 2 \begin{align*} p_n &= a_n p_{n-1} + p_{n-2} \\ q_n &= a_n q_{n-1} + q_{n-2} \end{align*}pn​qn​​=an​pn−1​+pn−2​=an​qn−1​+qn−2​​

其中p n p_npn​和q n q_nqn​分别是x n x_nxn​的分子和分母。
最终，x n = p n q n x_n = \frac{p_n}{q_n}xn​=qn​pn​​就是x xx的一个近似值。

连分数算法的实现 😎

下面是一个 Python 实现的连分数算法：

defcontinued_fraction(x,max_iterations=100):a=[]for_inrange(max_iterations):ai=int(x)a.append(ai)x-=aiifx==0:breakx=1/xreturnadefcontinued_fraction_convergents(coeffs):""" 用递推公式计算连分数 [a0,a1,...an] 的所有渐进分数 参数： coeffs: 连分数部分商列表 [a0,a1,a2,...] 返回： list: 每个元素是 (n, p_n, q_n, x_n)，包含每一步的递推结果 """ifnotcoeffs:raiseValueError("连分数系数列表不能为空！")p_prev_prev=0# p_{-2}p_prev=1# p_{-1}q_prev_prev=1# q_{-2}q_prev=0# q_{-1}convergents=[]# 存储每一步的渐进分数forn,a_ninenumerate(coeffs):# 递推计算 p_n 和 q_np_n=a_n*p_prev+p_prev_prev q_n=a_n*q_prev+q_prev_prev# 计算当前渐进分数 x_n = p_n/q_nx_n=p_n/q_n# 保存结果（n从0开始）convergents.append((n,p_n,q_n,x_n))# 更新前两项，为下一次递推做准备p_prev_prev,p_prev=p_prev,p_n q_prev_prev,q_prev=q_prev,q_nreturnconvergents

SageMath 偷懒 🤓👆

有同学说：“博主，博主，你的算法确实很厉害，但是还是太吃操作了，有没有更加简单无脑的用法？”👻
有的，兄弟有的，这样的算法在 SageMath 中早就已经被封装好了🤫，我们直接调用就行了：

fromsage.allimportcontinued_fraction# 这个 continued_fraction 函数既可以计算连分数的部分商，也可以计算连分数的渐进分数，具体用法如下：# 计算连分数部分商coeffs=continued_fraction(x)# 计算连分数的渐进分数convergents=continued_fraction(coeffs)

怎么样，是不是非常简单？🤣👉🤡

我的个人blog：Alice and Bobの神秘小屋