主要观点：Blum-Blum-Shub（BBS）是基于分解大合数难度的伪随机数生成器，1986 年由 Lenore Blum、Manuel Blum 和 Michael Shub 引入，因其在某些假设下的可证明安全性而备受关注。

关键信息和重要细节：

• 内部状态步函数：(x_{n+1} = x_n^2 \bmod M)，其中(M = pq)，(p)、(q)为不同大素数，(x_0)为与(M)互质且大于 1 的随机种子，(p)、(q)需为 Sophie Germain 素数且模 4 同余 3，(\gcd((p - 3)/2, (q - 3)/2))应尽可能小。
• 二次剩余相关定义：如整数(x\in\mathbb{Z}_n^)是模(n)的二次剩余当存在(y)使(y^2\bmod n = x)；Jacobi 符号定义；(\mathbb{Z}_n^)分为(\mathbb{Z}_n^{*,-1})和(\mathbb{Z}_n^{*,1})等。
• 与 BBS 的联系：W. B. Alexi 等证明在 BBS 中 QRP 假设可等价替换为因子分解假设；Blum、Blum、Shub 证明若有逆推 BBS 生成器的算法则可解 QRP；U.V. Vazirani 和 V.V. Vazirani 表明可安全提取(O(\log\log M))位；通过 Carmichael 函数可在 BBS 中定位到任意位置等。
• 安全影响：若(p)、(q)公开可创建可搜索生成器并近似周期，保留(p)、(q)可提升合法生成器性能，如通过 CRT 计算模(M)的根。
• 玩具实验：通过给定两素数计算(n = pq)，预计算 CRT 常数，实现 BBS 生成器并比较 CRT 和常规方法生成的比特。
• C 实现：cbbs-rng 实现了 BBS 生成器，支持 OpenMP 并行化，通过多种函数实现素数生成、GCD 计算、状态初始化和推进等功能。
• 其他结果：BBS 周期与 Carmichael 函数相关，单向函数存在等价于伪随机生成器通过所有多项式时间统计测试，关于 BBS 的安全证明有误导性，生成器速度慢，使用 GMP 的简单实现可提升速率等。