Wagner 算法：如何解决广义生日问题？ | Baeldung 关于计算机科学

1. 简介

生日问题是概率论中最违反直觉的结果之一。在其经典形式中，它询问

房间里需要多少人，才能有超过 50% 的几率至少有两个人拥有相同的生日？

令人惊讶的是，只需要 23 个人，这种概率就会超过 50%。 虽然经典的生日问题是介绍概率论的基础，但它的推广在密码学、组合数学和计算复杂性方面具有广泛的应用。

在本教程中，我们将探讨广义生日问题，并重点介绍 Wagner 算法。 它使用平衡穷举搜索和中间相遇策略的技术来解决这个问题。我们还将讨论该算法的思想如何在现代工作量证明系统中实现，尤其是在 Zcash 等加密货币使用的 Equihash 算法中。

通过本文的结束，我们将理解 Wagner 算法的理论基础和实践考虑因素。

2. 重新审视经典的生日问题

在深入研究广义版本之前，让我们简要地回顾一下经典的生日问题。

为了解决它，我们首先问：在 n 个人的一组中，至少有两个人拥有相同生日的概率是多少？

相反的情况是所有人都拥有不同的生日日期。第一个人可以拥有 365 天中的任何一天作为他们的生日。第二个人必须拥有不同的生日，将其选择减少到 365 中的 364，第三个人减少到 363，依此类推。这会导致以下概率

(1) $\begin{equation*} $P(\text{all } n \text{ distinct}) = \prod_{i=0}^{n-1} \left(1 - \frac{i}{365}\right)$ \end{equation*}$

对于 n=23，这个概率降至 50% 以下，这意味着对于这样一个小的群体，共享生日的机会超过 50%。这种违反直觉的结果突出了概率理论中组合爆炸的本质。

3. 广义生日问题

广义生日问题扩展了经典场景。 我们不是寻找匹配的生日，而是可以将问题定框架为寻找满足特定模态条件的元素子集。

3.1. 数学公式

给定一个集合 S={x1, x2, …, xn}, 我们想要找到 S 的一个非空子集 S’ ，使得

(2) $\begin{equation*} $\left( \sum_{x \in S'} x \right) \mod M = T$ \end{equation*}$

其中

M 是一个模数
T 是一个目标值

在密码学中，像这样的碰撞查找问题构成了哈希函数攻击和工作量证明机制的基础。

4. Wagner 算法：概述

David Wagner 提出的 Wagner 算法是一种中间相遇方法，旨在有效地解决广义生日问题。

关键思想是将集合 S 分区为多个子集，为每个分区解决较小的子问题，然后组合结果来解决总体问题。这种方法通过在时间和空间复杂度之间找到平衡的权衡来减少指数级的搜索空间。

4.1. 中间相遇策略

“中间相遇”策略在问题可以被划分为可以独立解决的两个或更多部分时尤其有效。对于广义生日问题，该算法分为三个阶段

我们将原始输入集划分为 k 个较小的子集
对于每个子集，我们计算所有可能的偏和，结果取模 M
最后，该算法通过搜索这些偏和的组合来“中间相遇”，当这些偏和加在一起时，会得到目标值 T

“中间相遇”策略与分治法的不同之处在于它处理和组合子问题的方式。虽然分治法递归地将问题分解为更小的独立子问题，分别解决它们，然后合并结果（如归并排序所示），但 “中间相遇”将问题划分为两半，预先计算一半，并在另一半中有效地搜索匹配的解决方案。

与需要检查 $2^N$ 个子集的朴素穷举搜索相比，这种方法显著降低了计算量。

5. 瓦格纳算法的分步分解

5.1. 步骤 1：划分集合

在这里，我们将集合 S 划分为 k 个组，理想情况下，每个组的大小相等。

k 的选择至关重要，因为它会影响算法的时间和空间复杂度。一种常见的启发式方法是选择 k，以便每个划分中的搜索空间是可管理的。

5.2. 步骤 2：计算偏和

对于每个子集，我们计算所有可能的偏和，结果取模 M。

但是，由于我们对模 M 的和感兴趣，其中许多和会发生冲突，可以使用哈希表或其他查找结构进行潜在的减少。

def compute_partial_sums(group, M):
    """
    Computes all possible subset sums modulo M for a given group.
    
    :param group: A list of numbers representing the group
    :param M: The modulus value
    :return: A dictionary mapping sum modulo M to the subset
    """
    
    partial_sums = {}  # Dictionary: key = sum mod M, value = subset representation

    # Iterate over all subsets of the group
    for subset in power_set(group):  
        sum_mod = sum(subset) % M  # Compute sum modulo M
        partial_sums[sum_mod] = subset  # Store subset in dictionary

    return partial_sums

5.3. 步骤 3：合并偏和

算法在计算每个组的偏和后，将这些结果组合起来。目的是找到来自每个组的一个条目，使得它们的总和模 M 等于 T。我们可以将此概念化为多维“匹配”问题，其中每个维度代表一个组。

一种实用的方法是递归地组合偏和表。 在每个递归步骤中，我们将两个表合并，形成一个新表，其中包含通过组合两个组的子集得到的和。

合并时会检查任何和与组合其他组时是否匹配目标值

def wagner_algorithm(S, k, T, M):
    """
    Implements Wagner's algorithm to solve the generalized birthday problem.
    
    :param S: The set of elements to partition
    :param k: Number of partitions
    :param T: Target value
    :param M: Modulus value
    :return: A valid subset sum modulo M if found, else None
    """
    
    # Step 1: Partition the input set into k groups
    groups = partition_set(S, k)
    partial_sums_list = []

    # Step 2: Compute partial sums for each group
    for group in groups:
        partial_sums_list.append(compute_partial_sums(group, M))

    # Step 3: Merge tables iteratively
    while len(partial_sums_list) > 1:
        table1 = partial_sums_list.pop()
        table2 = partial_sums_list.pop()
        merged_table = merge_tables(table1, table2, M)
        partial_sums_list.append(merged_table)

    # Step 4: Retrieve the final table and return the valid subset if found
    final_table = partial_sums_list[0]
    return final_table.get(T)  # Returns None if no valid subset is found

5.4. 合并表

这里是函数 merge_tables，它有效地合并两个表，同时确保计算出的和模 M

def merge_tables(table1, table2, M):
    """
    Merges two tables containing partial sums and returns a new table
    with all possible sums modulo M.
    
    :param table1: Dictionary {sum_mod_M: subset_representation} from first group
    :param table2: Dictionary {sum_mod_M: subset_representation} from second group
    :param M: Modulus value
    :return: Merged dictionary containing sums modulo M
    """
    merged_table = {}

    for sum1, subset1 in table1.items():
        for sum2, subset2 in table2.items():
            merged_sum = (sum1 + sum2) % M  # Combine sums and apply modulus
            merged_table[merged_sum] = subset1 + subset2  # Store combined subset

    return merged_table

对于两个表中的每对和，它计算它们的和并取模 M 的结果，以确保考虑所有可能的子集组合。该函数将合并后的和以及组合后的子集表示存储在一个新表中。这种方法允许算法有效地探索有效的组合，而无需冗余计算，从而大大降低了复杂度。

合并步骤应用了“中间相遇”技术，并确保逐步组合部分结果，从而获得更易于管理的搜索空间。

5.4. 合并偏和表的示例

考虑一个小的集合 S={3, 7, 12, 18} 和一个模数 M=10。我们将 S 划分为两个组

$\text{Group 1: } \{3, 7\} \text{Group 2: } \{12, 18\}$

我们首先计算每个组的偏和，结果取模 M。对于第一个组，我们有

$\text{Group 1: \{3, 7\}} 3 \mod 10 = 3 7 \mod 10 = 7 (3 + 7) \mod 10 = 0$

对应的表是

$\text{Table 1:} \{3 : \{3\}, 7 : \{7\}, 0 : \{3, 7\} \}$

对于第二个组

$\text{Group 2: \{12, 18\}} 12 \mod 10 = 2 18 \mod 10 = 8 (12 + 18) \mod 10 = 0 \text{Table 2: } \{2: \{12\}, 8: \{18\}, 0: \{12,18\}\}$

现在，我们应用 merge_tables 函数，它将表 1 中的每个和与表 2 中的每个和组合起来，将它们相加，并取结果对 M 取模

$(3 + 2) \mod 10 = 5 \Rightarrow \{3,12\}$
$(3 + 8) \mod 10 = 1 \Rightarrow \{3,18\}$
$(3 + 0) \mod 10 = 3 \Rightarrow \{3,12,18\}$
$(7 + 2) \mod 10 = 9 \Rightarrow \{7,12\}$
$(7 + 8) \mod 10 = 5 \Rightarrow \{7,18\}$
$(7 + 0) \mod 10 = 7 \Rightarrow \{7,12,18\}$
$(0 + 2) \mod 10 = 2 \Rightarrow \{3,7,12\}$
$(0 + 8) \mod 10 = 8 \Rightarrow \{3,7,18\}$
$(0 + 0) \mod 10 = 0 \Rightarrow \{3,7,12,18\}$

最终合并后的表格是

$\text{Merged Table: }$
$\{5: \{3,12\}, 1: \{3,18\}, 3: \{3,12,18\}, 9: \{7,12\},$
$5: \{7,18\}, 7: \{7,12,18\}, 2: \{3,7,12\}, 8: \{3,7,18\}, 0: \{3,7,12,18\}\}$

6. 复杂度分析

Wagner 算法比蛮力方法提供了显著的改进。让我们比较一下复杂度

方法	时间复杂度	空间复杂度
蛮力法	O(2^N)	O(1)
Wagner 算法	O(k * 2^(N/k))	O(2^(N/k))

通过设置 $k = log_2N$ ，Wagner 算法在空间复杂度和时间复杂度之间实现了最佳平衡。

7. 实现注意事项

在实现 Wagner 算法时，我们必须解决一些实际问题。

7.1. 内存管理

存储每个组的部分和表可能会占用大量内存。

高效的数据结构，例如哈希表或平衡树，可以帮助管理内存使用量，同时允许快速查找。在 C++ 等语言中，仔细的内存分配和释放管理至关重要。

7.2. 并行化

为每个组独立计算部分和非常适合并行化。

利用多线程或分布式计算可以进一步减少整体运行时间。现代编程环境和库提供了使这种并行化更轻松高效的构造。

7.3. 优化技术

各种优化技术可以提高算法的性能。 一种方法是在合并过程中进行剪枝，丢弃不能导致解决方案的部分和。 可以通过检查部分和与剩余可能和的组合是否仍然可以达到目标模 M 来完成。如果不能，则尽早消除它以减少不必要的计算。

另一种方法是预先对部分和进行排序，当使用二分查找匹配和时，可以加快合并阶段的速度。

此外，当 M 很大时，高效的模运算变得很重要；预计算模逆或使用特定库可以帮助加快过程。

8. 在密码学中的应用：Equihash

Wagner 算法最著名的应用之一是在 Equihash 工作量证明算法中，该算法是 Zcash 等加密货币的基础.

Equihash 利用广义生日问题，确保挖矿需要大量的内存和计算资源，从而降低了基于 ASIC 的挖矿的可行性。

8.1. Equihash 如何使用广义生日问题

Equihash 被设计为内存困难型，这意味着它故意需要大量的内存才能解决。这一特性确保了该算法对专用硬件攻击的抵抗力更强。

Equihash 中的挖矿过程涉及找到问题的解决方案，该问题结构类似于广义生日问题，但具有不同的数学公式。 与 Wagner 算法中寻找模 M 等于 T 的子集不同，Equihash 要求矿工找到一个哈希值的子集，该子集满足由工作量证明方案定义的特定碰撞条件

因此，给定一组大型哈希输入，任务是找到一个子集，其组合值（在特定的 Equihash 定义的操作下）满足挖矿所需的难度标准。虽然 Equihash 利用了 Wagner 算法中的中间相遇策略，但它用一个确定有效解决方案的密码学条件代替了模 M 求和的约束。

通过将输入空间划分为更小的部分并有效地合并结果，Equihash 降低了计算开销，同时确保需要大量的内存。这种计算工作量和内存使用之间的平衡使得基于 ASIC 的优化更加困难，从而维护了挖矿的去中心化特性。

8.2. 加密货币挖矿的优势

在 Equihash 中采用 Wagner 算法提供了几个优势

抗 ASIC： Equihash 需要大量的内存，这缩小了通用硬件和专用 ASIC 之间的差距。这有助于防止挖矿算力的集中化。
可扩展性： 我们可以通过改变参数（例如 k 和 M）来调整算法，以微调内存使用量和计算工作负载之间的平衡。
安全性： 广义生日悖论的固有难度提供了额外的安全层。在没有进行大量工作的情况下找到有效子集的概率极低，从而确保了工作量证明系统的完整性。

9. Beyond Equihash：Wagner 算法的其他应用

虽然 Equihash 是最著名的应用，但 Wagner 算法在其他领域也有相关性

9.1. 密码分析

该算法攻击依赖于广义生日悖论难度的密码方案。

在密码分析中，研究人员研究这些算法以了解其局限性并设计能够抵御此类攻击的安全系统。

9.2. 组合优化

我们可以调整中间相遇技术来解决组合问题，在这些问题中，解空间对于穷举搜索来说太大。

通过将问题分解为更小的部分，可以更有效地找到解决方案。

9.3. 数据挖掘和大数据

在涉及大型数据集的情况下，高效的搜索算法至关重要。

受 Wagner 算法启发的技巧可以在大数据中搜索特定的模式或相关性，而蛮力方法在计算上是不可行的。

10. 结论

在本文中，我们讨论了 Wagner 算法，这是一种解决广义生日悖论的强大方法，它在空间和时间复杂度之间取得了最佳平衡。

其主要特点是

与蛮力方法相比，它显著缩小了搜索空间
它在 Equihash 中发挥着关键作用，确保了 Zcash 挖矿的抗 ASIC 性
它在密码分析、组合问题和大数据中具有广泛的应用

核心概念

操作系统

神经网络

图论

LaTeX

完整存档

关于 Baeldung