在 Pollard rho 整数分解中计算 GCD 的原因是什么？
What is the reason behind calculating GCD in Pollard rho integer factorisation?
这是从 CLRS 中计算整数因式分解的伪代码。但是计算 GCD 涉及 Line 8 的意义何在 doubling k when i == k 在 第 13 行 .?请帮忙
尽管有标签，但该伪代码不是 Pollard-rho 分解。是相关Brent's factorization method的一个试用版。在 Pollard-rho 分解中，在第 i 步计算 x_i 和 x_(2i)，并用 n 检查 x_(2i)-x_i 的 GCD。在 Brent 分解方法中，您计算 GCD(x_(2^a)-x_(2^a+b),n) for b=1,2, ..., 2^a。 （我使用以 1 开头的索引与伪代码一致，但在其他地方序列初始化为 x_0。）在代码中，k=2^a 和 i=2^a+b。当您检测到 i 已达到 2 的下一次幂时，您将 k 增加到 2^(a+1).
GCD 可以通过 Euclid's algorithm without knowing the factorizations of the numbers. Any time you find a nontrivial GCD with n, this helps you to factor n. In both Pollard-rho factorization and Brent's algorithm, one idea is that if you iterate a polynomial such as x^2-c, the differences between the values of the iterates mod n tend to be good candidates for numbers that share nontrivial factors with n. This is because (by the Chinese Remainder Theorem) 迭代多项式 mod n 与同时迭代多项式 mod 的素因式分解中的每个素数幂相同。如果 x_i=x_j mod p1^e1 而不是 mod p2^e2，则 GCD(xi-xj,n) 将 p1^e1 作为一个因子但不是p2^e2，所以这将是一个不平凡的因素。
这是一次试验，因为 x_1 被初始化了一次。如果你运气不好，你为 x_1 选择的值会启动一个前周期序列，该序列同时重复 mod 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 的一个重要因子。不仅一些sequences 没有帮助，其他的可能有用，但放弃并从另一个初始值开始可能会更快。所以，通常你不会永远增加 i，通常有一个终止阈值，你可以在其中尝试不同的初始值。
这是从 CLRS 中计算整数因式分解的伪代码。但是计算 GCD 涉及 Line 8 的意义何在 doubling k when i == k 在 第 13 行 .?请帮忙
尽管有标签，但该伪代码不是 Pollard-rho 分解。是相关Brent's factorization method的一个试用版。在 Pollard-rho 分解中，在第 i 步计算 x_i 和 x_(2i)，并用 n 检查 x_(2i)-x_i 的 GCD。在 Brent 分解方法中，您计算 GCD(x_(2^a)-x_(2^a+b),n) for b=1,2, ..., 2^a。 （我使用以 1 开头的索引与伪代码一致，但在其他地方序列初始化为 x_0。）在代码中，k=2^a 和 i=2^a+b。当您检测到 i 已达到 2 的下一次幂时，您将 k 增加到 2^(a+1).
GCD 可以通过 Euclid's algorithm without knowing the factorizations of the numbers. Any time you find a nontrivial GCD with n, this helps you to factor n. In both Pollard-rho factorization and Brent's algorithm, one idea is that if you iterate a polynomial such as x^2-c, the differences between the values of the iterates mod n tend to be good candidates for numbers that share nontrivial factors with n. This is because (by the Chinese Remainder Theorem) 迭代多项式 mod n 与同时迭代多项式 mod 的素因式分解中的每个素数幂相同。如果 x_i=x_j mod p1^e1 而不是 mod p2^e2，则 GCD(xi-xj,n) 将 p1^e1 作为一个因子但不是p2^e2，所以这将是一个不平凡的因素。
这是一次试验，因为 x_1 被初始化了一次。如果你运气不好，你为 x_1 选择的值会启动一个前周期序列，该序列同时重复 mod 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 的一个重要因子。不仅一些sequences 没有帮助，其他的可能有用，但放弃并从另一个初始值开始可能会更快。所以，通常你不会永远增加 i，通常有一个终止阈值，你可以在其中尝试不同的初始值。