「ZJOI2020」密码 题解

算法思路分析

这是一个带误差的模方程求解问题，需要从带噪声的模线性方程中恢复出密钥 $x$。

问题建模

给定 $m$ 个方程：

$$a_i x + b_i \equiv c_i \pmod{p}, \quad |b_i| \leq \text{err} $$

其中 $\text{err} = \lceil \frac{\text{err}}{2} \rceil$，需要求解 $x \in [0, p-1]$。

关键观察

1. 误差范围小：$\text{err} \leq 0.01p$，误差相对模数很小
2. 区间约束：每个方程实际上给出了 $x$ 的近似范围
3. 交集求解：通过多个方程的约束交集来定位 $x$

核心算法：区间收缩法

算法步骤

1. 数据预处理和筛选

up(i, 0, 5) {
    sort(ve.begin(), ve.end());
    ve.erase(unique(ve.begin(), ve.end()), ve.end());
    if (ve.size() > SZ) ve.resize(SZ);  // 限制数据规模
    v[i] = ve;
    // 生成差分方程
    for (int j = i+1; j <= sz-1 && s.size()-nw <= 20; ++j)
        if (ve[i].p1 != ve[j].p1)
            s.insert(ve[j].p1 - ve[i].p1), 
            vec.p_b(m_p(ve[j].p1-ve[i].p1, (ve[j].p2-ve[i].p2+P)%P));
}

2. 多层级区间收缩

down(i, 5, 0) {
    ll x = err << i;  // 逐级缩小误差范围
    for (auto it : v[i]) {
        ll k = it.p1, L = it.p2 - x, R = it.p2 + x;
        // 计算当前方程对x的约束区间
        vector<pair<ll, ll>> ve;
        for (auto x : RES) {
            // 解模方程: k * t ∈ [L, R] (mod P)
            for (ll j = (i128)l*(i128)k/P; j <= (i128)r*(i128)k/P; j++) {
                // 处理模运算的周期性，得到三个可能区间
                pair<ll, ll> A, B, C;
                A = solve(j*P + max(L,0ll), j*P + min(R,P-1), k);
                if (L < 0) B = solve(j*P + L + P, j*P + P-1, k);
                if (R >= P) C = solve(j*P, j*P + R - P, k);
                // 合并有效区间
            }
        }
        RES = ve;  // 更新候选区间
    }
}

3. 最终验证

for (auto it : RES)
    for (ll i = it.p1; i <= it.p2; ++i)
        if (chk(i))  // 验证候选解
            return printf("%lld\n", i), void();

验证函数

bool chk(ll u) {
    up(i, 1, m) {
        ll x = (mul(u, d[i].a) - d[i].c + P) % P;
        if (x <= err || x >= P - err);  // 在误差范围内
        else return 0;
    }
    return 1;
}

复杂度分析

• 时间复杂度：$O(\text{层级} \times \text{方程数} \times \text{区间数} \times \text{周期数})$，在实际数据下可接受
• 空间复杂度：$O(m)$，存储方程和候选区间

算法标签

主要分类

• 数论 ⭐⭐⭐⭐⭐
• 区间搜索 ⭐⭐⭐⭐
• 模运算 ⭐⭐⭐⭐

技术子标签

• 误差分析 ⭐⭐⭐⭐
• 约束传播 ⭐⭐⭐⭐
• 候选验证 ⭐⭐⭐⭐

问题类型

• 密码分析 ⭐⭐⭐⭐
• 方程求解 ⭐⭐⭐⭐
• 数值计算 ⭐⭐⭐

关键算法技巧

1. 差分方程生成

通过构造方程间的差分来获得新的约束：

$$(a_j - a_i)x \equiv (c_j - c_i) + (b_j - b_i) \pmod{p} $$

其中 $|b_j - b_i| \leq 2\text{err}$

2. 多尺度收缩

从大误差范围开始，逐步收缩到小误差范围：

• 层级 5: $\text{err} \times 32$
• 层级 0: $\text{err} \times 1$

3. 模区间处理

正确处理模运算的周期性，将模方程转化为多个整数区间：

$$kx \equiv c \pm \delta \pmod{p} \Rightarrow x \in \bigcup_j [l_j, r_j] $$

算法优势

1. 鲁棒性：能处理带噪声的模方程
2. 高效性：通过区间收缩快速缩小搜索范围
3. 正确性：最终验证确保找到唯一解
4. 适用性：适用于大模数情况 ($p \leq 10^{18}$)

该解法通过巧妙的区间分析和多尺度收缩策略，成功解决了带误差模方程的密钥恢复问题，展现了数值计算在密码分析中的重要应用。