这是从 CLRS 获取的用于计算整数分解的伪代码。但是，计算第 8 行中涉及的GCD以及当第 13 行中i == k时需要将 k 加倍有什么意义？请帮忙。
问问题
576 次
1 回答
3
尽管有标签，但该伪代码不是 Pollard-rho 分解。这是相关布伦特因式分解方法的一种尝试。在 Pollard-rho 分解中，在第 i 步计算 x_i 和 x_(2i)，并检查 x_(2i)-x_i 与 n 的 GCD。在布伦特的分解方法中，您计算 GCD(x_(2^a)-x_(2^a+b),n) 为 b=1,2, ..., 2^a。（我使用从 1 开始的索引与伪代码一致，但在其他地方，序列用 x_0 初始化。）在代码中，k=2^a 和 i=2^a+b。当您检测到 i 已达到 2 的下一个幂时，您将 k 增加到 2^(a+1)。
欧几里得算法可以非常快速地计算 GCD，而无需知道数字的因式分解。任何时候你找到一个具有 n 的非平凡 GCD，这都可以帮助你分解 n。在 Pollard-rho 因式分解和 Brent 算法中，一个想法是，如果您迭代诸如 x^2-c 之类的多项式，则迭代 mod n 的值之间的差异往往是与 n 共享非平凡因子的数字的良好候选者. 这是因为（根据中国剩余定理）迭代多项式 mod n 与在 n 的素数分解中同时迭代多项式 mod 每个素数幂是相同的。如果 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 的重要因子。不仅某些序列没有帮助，其他序列可能会起作用，但它放弃并从另一个初始值开始可能会更快。所以，通常你不会
于 2015-06-14T15:33:06.967 回答