密码学算法 - 连分数算法

当你在计算某个数的近似值时或者在求解某个方程的根时连分数算法 就像一把神奇的放大镜能帮你逐步逼近那个隐藏在数字背后的真相。欢迎来到《密码学核心算法实战》的连分数专题这里没有纸上谈兵的理论空谈真的不画大饼只有一把把能直接撬动数据安全的精密齿轮⚙️。连分数算法的操作 这个算法可以直接将一个有理数或者无理数直接表示成一个连分数形式当然因为这个算法的原理十分简单所以就不单独拿出来讲了直接进入正题输入一个实数x xx。令i 0 i 0i0x 0 x x_0 xx0​x令a i a_iai​为x i x_ixi​的整数部分b i x i − a i b_i x_i - a_ibi​xi​−ai​如果b i 0 b_i 0bi​0则算法结束如果b i ≠ 0 b_i \neq 0bi​0则令x i 1 1 b i x_{i1} \frac{1}{b_i}xi1​bi​1​i i 1 i i 1ii1回到步骤 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_iterations100):a[]for_inrange(max_iterations):aiint(x)a.append(ai)x-aiifx0:breakx1/xreturnadefcontinued_fraction_convergents(coeffs): 用递推公式计算连分数 [a0,a1,...an] 的所有渐进分数 参数 coeffs: 连分数部分商列表 [a0,a1,a2,...] 返回 list: 每个元素是 (n, p_n, q_n, x_n)包含每一步的递推结果 ifnotcoeffs:raiseValueError(连分数系数列表不能为空)p_prev_prev0# p_{-2}p_prev1# p_{-1}q_prev_prev1# q_{-2}q_prev0# q_{-1}convergents[]# 存储每一步的渐进分数forn,a_ninenumerate(coeffs):# 递推计算 p_n 和 q_np_na_n*p_prevp_prev_prev q_na_n*q_prevq_prev_prev# 计算当前渐进分数 x_n p_n/q_nx_np_n/q_n# 保存结果n从0开始convergents.append((n,p_n,q_n,x_n))# 更新前两项为下一次递推做准备p_prev_prev,p_prevp_prev,p_n q_prev_prev,q_prevq_prev,q_nreturnconvergentsSageMath 偷懒 有同学说“博主博主你的算法确实很厉害但是还是太吃操作了有没有更加简单无脑的用法”有的兄弟有的这样的算法在 SageMath 中早就已经被封装好了我们直接调用就行了fromsage.allimportcontinued_fraction# 这个 continued_fraction 函数既可以计算连分数的部分商也可以计算连分数的渐进分数具体用法如下# 计算连分数部分商coeffscontinued_fraction(x)# 计算连分数的渐进分数convergentscontinued_fraction(coeffs)怎么样是不是非常简单我的个人blogAlice and Bobの神秘小屋