💻 computer science

A Survey on Complexity Measures of Pseudo-Random Sequences

本文综述了过去四十年间关于伪随机序列线性、二次及最大阶复杂度，及其与 Lempel-Ziv 复杂度、展开复杂度、2-adic 复杂度和相关测度之间关系的重要研究成果。

原作者： Chunlei Li

发布于 2026-04-15

📖 1 分钟阅读☕ 轻松阅读

原作者： Chunlei Li

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

这篇论文就像是一份**“密码学界的测谎仪使用指南”**。

在数字世界里，安全依赖于“随机性”。想象一下，如果你要锁一个保险箱，你需要一把完全随机的钥匙。如果这把钥匙有规律（比如是"123456"或者"101010"），黑客就能轻易猜出来，你的保险箱就完了。

这篇论文由挪威卑尔根大学的 Chunlei Li 教授撰写，它主要探讨了一个核心问题：我们如何判断一串数字（比如 0 和 1 组成的序列）是真正的“随机”，还是只是看起来像随机，实际上却藏着规律？

为了回答这个问题，作者回顾了过去 40 年来的各种“测谎工具”（也就是复杂度度量）。我们可以把这些工具想象成不同精度的“侦探”，用来抓出序列中的“规律鬼”。

以下是这篇论文的通俗解读：

1. 为什么要测“随机性”？

在加密通信中，我们需要生成大量的随机比特（0 或 1）作为密钥。

理想情况：就像抛硬币，每次结果都完全不可预测。
现实情况：计算机是确定性的机器，它们生成的“随机数”其实是伪随机数。如果生成的序列太有规律，黑客就能通过观察一小部分数据，推算出剩下的所有数据，从而破解密码。
目标：我们需要一种方法，能告诉我们这个序列“有多难被预测”。

2. 核心工具：反馈移位寄存器 (FSR)

论文中反复提到的一个概念是反馈移位寄存器 (FSR)。

比喻：想象一个自动售货机。你往里面投币（输入），它吐出一瓶饮料（输出）。如果这个机器内部有一个简单的规则（比如“投 1 个币吐 1 个可乐”），那它生成的序列就很简单，很容易被猜透。
复杂度：如果我们要用这种机器“完美复制”一段随机序列，我们需要多复杂的机器？
- 如果只需要一个简单的机器（比如只有几个开关），说明序列很简单（不安全）。
- 如果需要极其庞大、复杂的机器才能复制它，说明序列很复杂（比较安全）。

3. 三种主要的“测谎仪” (复杂度度量)

作者重点介绍了三种不同精度的测谎仪：

A. 线性复杂度 (Linear Complexity) —— “老练的侦探”

原理：这是最经典的方法。它假设生成序列的机器只使用加减法（线性关系）。
比喻：就像侦探只寻找“直线”规律。如果序列是 1, 2, 3, 4, 5，侦探一眼就能看出规律是“加 1"。
现状：这个方法研究得很透彻，计算也很快（就像有一个现成的公式）。它是目前很多安全标准（如 NIST）的必测项目。
缺点：如果黑客用的机器不仅会加减，还会乘法（非线性），这个侦探就失效了。

B. 二次复杂度 (Quadratic Complexity) —— “进阶侦探”

原理：这个侦探更聪明，它假设机器不仅会加减，还会做乘法（比如 $x \times y$ ）。
比喻：序列里可能藏着 $A \times B = C$ 这样的规律。
现状：比线性复杂度高，更难算。论文指出，目前对它的统计规律了解得还不够多，就像侦探手里只有半本地图，还需要更多探索。

C. 最大阶复杂度 (Maximum-order Complexity) —— “终极侦探”

原理：这是最强大的侦探。它不假设机器只能用加减或乘法，它假设机器可以用任何逻辑（只要是最短的）。它问的是：“要预测下一个数字，你至少需要看前面多少个数字？”
比喻：
- 如果序列是 000001，侦探发现只要看最后 1 个数字就能猜出下一个（如果是 0 就猜 0，如果是 1 就猜结束），这很简单。
- 如果序列是真正的随机，侦探发现必须看前面所有的数字才能猜对下一个。
现状：这是目前研究热点。论文发现，有些序列虽然看起来很难预测（复杂度很高），但它们的内部结构其实非常奇怪（比如全是重复的），这种序列虽然“难猜”但“质量差”，不适合做密码。

4. 其他有趣的发现

完美的序列不存在：有些序列虽然复杂度很高（很难被预测），但它们本身并不“随机”。比如，一个序列可能是 000...001，它很难被短机器复制，但它显然不是好随机数。
不同工具的关系：论文还梳理了这些工具之间的关系。比如，线性复杂度通常小于等于二次复杂度，二次复杂度小于等于最大阶复杂度。就像：如果连直线规律都找不到，那更复杂的规律肯定也找不到。
与其他指标的联系：除了这些“机器复杂度”，论文还提到了兰佩尔 - 齐夫复杂度（Lempel-Ziv，类似压缩率，越能压缩越不随机）和2-adic 复杂度（另一种数学视角的复杂度）。它们之间也有千丝万缕的联系。

5. 总结与未来

这篇论文就像是一个**“侦探工具箱”的说明书**。

现状：对于“线性复杂度”，我们已经是专家了，知道怎么算、怎么测。
挑战：对于“二次复杂度”和“最大阶复杂度”，我们还在摸索中。特别是如何快速计算它们，以及如何判断一个高复杂度的序列是否真的“好”，还需要新的数学工具。
结论：要设计真正安全的加密系统，不能只依赖一种测谎仪。我们需要结合多种工具，确保生成的随机数既难以预测（高复杂度），又符合随机统计规律（没有奇怪的结构性缺陷）。

一句话总结：
这篇论文告诉我们，在密码学里，“看起来乱”不等于“真的乱”。我们需要用各种复杂的数学尺子去测量，才能确保我们手中的“随机钥匙”是真正坚不可摧的。

这是一篇关于伪随机序列复杂度度量（Complexity Measures for Pseudo-Random Sequences）的综述论文，由挪威卑尔根大学（University of Bergen）的 Chunlei Li 撰写。文章系统回顾了自 20 世纪 60 年代以来，在反馈移位寄存器（FSR）框架下，针对线性、二次及最大阶复杂度等核心指标的研究进展，并探讨了它们与其他复杂度度量（如 Lempel-Ziv 复杂度、2-adic 复杂度等）之间的关系。

以下是对该论文的详细技术总结：

1. 研究背景与问题 (Problem)

背景：在密码学和信息安全中，随机比特（如密钥、初始化向量）的生成至关重要。理想的随机源应产生不可预测的独立均匀分布比特。然而，实际应用中广泛使用的是伪随机比特生成器（PRBGs），它们基于确定性算法（如流密码、分组密码、哈希函数或基于 FSR 的序列）。
核心问题：如何评估 PRBG 生成的伪随机序列 $s$ 的“随机性”？如果序列的复杂度较低，攻击者可能通过观测少量比特重构整个序列，从而破坏系统安全性。
挑战：
- Kolmogorov 复杂度虽然理论完美，但不可计算。
- 基于 FSR 的复杂度度量（如线性复杂度）虽然可计算，但仅考虑线性反馈不足以反映非线性序列的安全性。
- 对于非线性复杂度（二次、最大阶等）的统计行为、构造方法及其与其他度量（如 2-adic 复杂度、相关性）的深层联系，尚缺乏系统的理论理解和统一框架。

2. 方法论 (Methodology)

本文采用文献综述与理论分析相结合的方法：

理论框架：基于有限域 $F_q$ 上的反馈移位寄存器（FSR）模型。
分类讨论：将复杂度度量分为线性、二次、最大阶（非线性）三类，并分别讨论其定义、计算方法、统计特性及构造理论。
工具应用：
- 代数工具：利用生成函数、连分数（Continued Fractions）、离散傅里叶变换（DFT）、广义 DFT（GDFT）、分圆陪集（Cyclotomic Cosets）等分析周期性序列的性质。
- 算法工具：回顾 Berlekamp-Massey 算法（线性）、基于矩阵秩的算法（二次）、基于有向无环词图（DAWG）及特征词（Eigenwords）的递归算法（最大阶）。
- 概率统计：分析随机序列的期望复杂度、方差及分布规律。

3. 关键贡献与主要结果 (Key Contributions & Results)

3.1 线性复杂度 (Linear Complexity)

定义与计算：生成序列所需的最短线性反馈移位寄存器（LFSR）长度。可通过 Berlekamp-Massey 算法高效计算（ $O(n^2)$ ）。
统计行为：
- 对于随机序列，期望线性复杂度 $E[L_n] \approx n/2$ 。
- 对于 $n$ -周期序列，利用 GDFT 和 Gunther-Blahut 定理，给出了期望复杂度的精确公式（涉及分圆陪集）。
完美序列：讨论了 $d$ -完美序列（线性复杂度曲线接近 $n/2$ ）的构造，指出移位后的序列也应保持高复杂度。
结论：线性复杂度是 NIST 随机性测试套件中的核心指标，理论最为成熟。

3.2 二次复杂度 (Quadratic Complexity)

定义：生成序列所需的最短二次反馈 FSR 的长度。
计算方法：将问题转化为求解线性方程组 $M(n, m)F(m) = E(n, m)$ 。利用矩阵 $M(n, m)$ 的嵌套结构，提出了比高斯消元更高效的递归算法。
统计特性：目前缺乏严格的理论结果。文章引用了 Youssef 和 Gong 的猜想：随机序列的期望二次复杂度约为 $\sqrt{2n}$ 。
安全性警示：若序列的二次复杂度 $m$ 较小，则只需观测约 $O(m^2)$ 个比特即可唯一确定反馈函数，因此低二次复杂度的序列不适合密码应用。

3.3 最大阶复杂度 (Maximum-Order Complexity / Nonlinear Complexity)

定义：生成序列所需的最短任意非线性 FSR 的长度。这是衡量序列非线性随机性的关键指标。
计算与统计：
- DAWG 方法：Jansen 提出利用直接无环词图（DAWG）的深度来计算最大阶复杂度。
- 递归算法：Rizomiliotis 等人提出了类似 Berlekamp-Massey 的递归算法，利用“特征词”（Eigenwords）的概念，平均复杂度为 $O(n^2 \log n)$ 。
- 统计近似：对于随机序列，期望最大阶复杂度 $E[M_n] \approx 2 \log_q n$ 。
高复杂度序列的构造：
- 研究了具有最大可能复杂度（ $n-1$ ）的 $n$ -周期序列。
- 重要发现：虽然形式为 $(0, \dots, 0, 1)$ 的序列具有最大复杂度，但其随机性极差（不平衡、不稳定）。文章给出了具有最大阶复杂度 $n-1$ 的充要条件，指出这类序列具有强烈的递归结构，不适合直接用于密码学。

3.4 复杂度度量间的关系 (Relations)

文章系统梳理了不同复杂度度量之间的不等式关系和相互联系：

基本不等式： $M_n(s) \le Q_n(s) \le L_n(s) \le n$ 。
2-adic 复杂度：最大阶复杂度受限于 2-adic 复杂度（ $M(s) \le \Phi(s)$ ）。
Lempel-Ziv 复杂度：与最大阶复杂度均与序列的“特征词”分布有关，存在内在联系。
扩展复杂度 (Expansion Complexity)：与线性复杂度有明确的代数关系（取决于预周期 $u$ ）。
相关度量：给出了线性/最大阶复杂度与 $k$ -阶相关度量之间的下界关系。

4. 开放问题与未来方向 (Open Problems & Future Directions)

作者提出了几个尚未解决的关键问题：

构造问题：如何构造在所有移位下都保持 $d$ -完美性质的序列？
二次复杂度：缺乏关于二次复杂度统计行为的严格理论证明（目前多为猜想）。
最大阶复杂度：
- 如何刻画具有最大二次复杂度 $n-1$ 的 $n$ -周期序列？
- 如何确定具有最大阶复杂度 $n-1$ 的序列的 $k$ -误差最大阶复杂度的下界？
De Bruijn 序列：关于其二次复杂度的下界（猜想为 $m+2$ ）虽已被证实，但整体理解仍有限。

5. 意义与结论 (Significance & Conclusion)

理论价值：本文填补了非线性复杂度（二次、最大阶）研究综述的空白，系统整理了过去 40 年的算法、代数构造和统计理论。
实践意义：
- 强调了仅依靠线性复杂度评估序列安全性的不足，指出非线性复杂度（特别是最大阶复杂度）在评估 PRBG 安全性时的重要性。
- 揭示了“高复杂度”并不等同于“高随机性”（如 $0\dots01$ 序列），为密码学中的序列设计提供了重要的警示。
总结：尽管线性复杂度和最大阶复杂度的研究相对成熟，但二次复杂度及其他度量（如 2-adic、扩展复杂度）之间的深层联系仍需新的数学工具和理论突破。未来的研究应致力于建立更完善的统计模型和构造具有理想随机性且高复杂度的序列。

核心观点提炼：
该论文不仅是对现有知识的总结，更是一次对“随机性”定义的深度反思。它指出在密码学应用中，高复杂度是必要的，但非充分的；必须结合多种复杂度度量（线性、非线性、2-adic 等）以及统计特性（如平衡性、相关性）来综合评估伪随机序列的安全性。