这是来自 CLRS 的用于计算整数分解的伪代码。但是，计算第8行中涉及的GCD以及当i == k时需要加倍k有什么意义呢？ > 在第 13 行中。？请帮忙。
最佳答案
尽管有标签，该伪代码并不是 Pollard-rho 分解。这是相关的一项试验Brent's factorization method 。在 Pollard-rho 分解中，在第 i 步中计算 x_i 和 x_(2i)，并检查 x_(2i)-x_i 与 n 的 GCD。在布伦特分解方法中，您可以计算 b=1,2, ..., 2^a 的 GCD(x_(2^a)-x_(2^a+b),n)。 (我使用以 1 开头的索引来与伪代码一致，但在其他地方，序列用 x_0 初始化。)在代码中，k=2^a 和 i=2^a+b。当您检测到 i 已达到 2 的下一个幂时，您将 k 增加到 2^(a+1)。
GCD 可以通过 Euclid's algorithm 非常快速地计算出来不知道数字的因式分解。任何时候当你找到一个包含 n 的非平凡 GCD 时，这都可以帮助你对 n 进行因式分解。在 Pollard-rho 分解和 Brent 算法中，一个想法是，如果迭代一个多项式(例如 x^2-c)，则迭代 mod n 的值之间的差异往往是与 n 共享非平凡因子的数字的良好候选者。这是因为(通过 Chinese Remainder Theorem )迭代多项式 mod n 与同时迭代多项式 mod n 的素因数分解中的每个素数幂相同。如果 x_i=x_j mod p1^e1 但不是 mod p2^e2，则 GCD(xi-xj,n) 将 p1^e1 作为因子，而不是 p2^e2，因此它将是一个不平凡的因子。
这是一次试验，因为 x_1 已初始化一次。如果你运气不好，你为 x_1 选择的值会启动一个前周期序列，该序列会同时重复对 n 的素数分解中的每个素数幂取模，即使 n 不是素数。例如，假设 n=1711=29*59，并且 x_1 = 4, x_2=15, x_3=224, x_4=556, x_5=1155, x_6=1155, ... 这个序列不能帮助您找到一个非平凡的序列因式分解，因为不同元素与 1711 之间的差异的所有 GCD 均为 1。如果从 x_1=5 开始，则 x_2=24、x_3=575、x_4=401、x_5=1677、x_6=1155、x_7=1155， ...在任何一种分解方法中，您都会发现 GCD(x_4-x_2,1711)=GCD(377,1711)=29，这是 1711 的一个不平凡的因子。不仅某些序列没有帮助，其他序列也可能有效，但它放弃并从另一个初始值开始可能会更快。因此，通常您不会永远增加 i，通常有一个终止阈值，您可以在其中尝试不同的初始值。
关于algorithm - Pollard rho 整数分解中计算 GCD 的原因是什么？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/30829461/