密码学算法 - Wiener 算法 | Alice and Bobの神秘小屋

当我们要计算一个与已知数近似的数的确定值时，连分数算法就像一把精确的放大镜🔍，能帮我们在无尽的小数世界中找到那个最接近的整数解。

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

Wiener算法 🌟

Wiener算法是基于连分数的一个算法，主要用于求解近似整数问题。它的核心思想是利用连分数的性质来找到一个数的最佳近似值，从而求解一些特定的数学问题。

具体来说，有一个已知数 $x$ 满足：

$x = \frac{p}{q} (1 - \epsilon)$

其中 $\epsilon$ 是一个很小的正数，且 $p$ 和 $q$ 是两个整数。Wiener算法的目标是通过已知的 $x$ 来找到 $p$ 和 $q$ 的值。

Wiener算法的原理 😭

由 $Ad - Bk = 1$，可以得到 $\vert \frac{A}{B} - \frac{k}{d} \vert = \frac{1}{Bd}$，所以 $\frac{k}{d}$ 是 $\frac{A}{B}$ 的一个近似值。

引入连分数收敛项的判别定理（选证，后面放上证明过程）：

对于任意实数 $\alpha$ 和任意有理数 $\frac{p}{q}$，如果 $\vert \alpha - \frac{p}{q} \vert < \frac{1}{2q^2}$，那么 $\frac{p}{q}$ 是 $\alpha$ 的一个连分数近似值。

因此，满足 $\vert \frac{A}{B} - \frac{k}{d} \vert < \frac{1}{2d^2}$，那么 $\frac{k}{d}$ 就是 $\frac{A}{B}$ 的一个连分数近似值。

Wiener算法的操作 🙃

输入：一个实数 $x$。
输出：整数 $p$ 和 $q$，使得 $x \approx \frac{p}{q}$。
算法步骤：

使用连分数算法计算 $x$ 的连分数部分商 $a_0, a_1, a_2, \ldots$。
计算连分数的渐进分数 $x_n = [a_0, a_1, \ldots, a_n]$，直到满足 $\vert x - x_n \vert < \frac{1}{2q_n^2}$（可根据实际用更加方便的方法验证）。
输出 $p_n$ 和 $q_n$，其中 $x_n = \frac{p_n}{q_n}$。
如果没有找到满足条件的 $n$，则返回 None。

Wiener算法的实现 😎

以下是一个Python实现：

def wiener_algorithm(x):
    a = [] # 连分数部分商
    while x != int(x):
        a.append(int(x))
        x = 1 / (x - int(x))
    a.append(int(x))
    # 计算连分数的渐进分数
    p0, q0 = 1, 0
    p1, q1 = a[0], 1
    # 判断是否满足条件
    for i in range(1, len(a)):
        if abs(x - p1 / q1) < 1 / (2 * q1 * q1):
            return p1, q1
        p2 = a[i] * p1 + p0
        q2 = a[i] * q1 + q0
        p0, q0 = p1, q1
        p1, q1 = p2, q2

    return None

SageMath 偷懒 🤓👆

有同学说：“博主，博主，你的算法确实很厉害，但是还是太吃操作了，有没有更加简单无脑的用法？”👻
艾，今天还真没有直接可以用的。😝但是我们还是可以用sage来简化的：

from sage.all import *

def wiener_algorithm(x):
    # 构造所有的连分数近似值
    cf = continued_fraction(x).convergents()
    for x_frac in cf[1:]: # 第一个一般为0/1，不考虑
        p, q = x_frac.numerator(), x_frac.denominator()
        ''' 这个判断条件只是理论的，实际中一般会有更好的条件验证
        if abs(x - p/q) < 1/(2*q^2):
            return p, q
        '''

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

连分数收敛项的判别定理证明 😡

这里要结合密码学数学基础 - 连分数进阶这篇文章的结论证明。

目标：
对于任意实数 $\alpha$ 和任意有理数 $\frac{p}{q}$，如果 $\vert \alpha - \frac{p}{q} \vert < \frac{1}{2q^2}$，那么 $\frac{p}{q}$ 是 $\alpha$ 的一个连分数近似值。

前置结论：

$结论①：渐进分数 \frac{p_n}{q_n} 满足 q_n = a_n q_{n-1} + q_{n-2}，且分母单调递增$
$推论：对于任意 n \geq 1，有 \vert \alpha - \frac{p_n}{q_n} \vert < \frac{1}{q_n q_{n+1}}$
$结论④：如果 \frac{p}{q} 是 \alpha 的最佳逼近，则 \frac{p}{q} 是 \alpha 的一个渐进分数$

我们使用反证法来证明目标。

设 $\alpha$ 是一个实数，$\frac{p}{q}$ 是一个满足误差条件的有理数，即

$\vert \alpha - \frac{p}{q} \vert < \frac{1}{2q^2} \ (1)$

假设 $\frac{p}{q}$ 不是 $\alpha$ 的任何一个渐进分数。

根据结论①，渐进分数的分母 $q_n$ 是一个严格递增的无穷序列。
因此，必然存在某个整数 $n$，使得分母 $q$ 落在两个相邻渐进分数的分母之间，即

$q_n < q \leq q_{n+1} \ (2)$

根据文章的最佳逼近定理（结论④），既然 $\frac{p}{q}$ 不是 $\alpha$ 的一个渐进分数，那么它不是“分母不超过$q$” 范围内的最佳逼近。
这意味着，存在一个比它更好的逼近分数（即第 $n$ 个渐进分数 $\frac{p_n}{q_n}$），满足

$\vert \alpha - \frac{p_n}{q_n} \vert < \vert \alpha - \frac{p}{q} \vert \ (3)$

且分母 $q_n \leq q$。

考虑两个分数的差值：

通分下界：因为 $p,q,p_n,q_n$ 都是整数，且 $\frac{p}{q} \neq \frac{p_n}{q_n}$，所以分子至少为1，因此有

$\vert \frac{p}{q} - \frac{p_n}{q_n} \vert = \vert \frac{p q_n - p_n q}{q q_n} \vert \geq \frac{1}{q q_n} \ (4)$