2

几个月前，我在 StackOverflow中提出了一个关于“在线性时间内找到素数因子的算法”的问题。

在回复中，我很清楚我的假设错误并且算法无法在线性时间内找到因素。

但是我想知道该算法是否是进行除法和查找因子的独特方法；那就是知道做任何类似/相同的划分方式吗？我再次在这里发布算法：

Input: A Number (whose factors is to be found)
Output: The two factor of the Number. If the one of the factor found is 1 then it can be concluded that the
Number is prime.

Integer N, mL, mR, r;
Integer temp1; // used for temporary data storage
mR = mL = square root of (N);
/*Check if perfect square*/
temp1 = mL * mR;
if temp1 equals N then
{
  r = 0; //answer is found
  End;
}
mR = N/mL; (have the value of mL less than mR)
r = N%mL;
while r not equals 0 do
{
  mL = mL-1;
  r = r+ mR;

  temp1 = r/mL;
  mR = mR + temp1;
  r = r%mL;
}
End; //mR and mL has answer

让我知道您的输入/这个问题纯粹是出于个人兴趣，想知道是否存在类似的算法来进行除法和查找因子，而我无法找到。

我理解并感谢您可能需要了解我的有趣算法才能给出答案！:)

进一步解释：是的，它确实适用于 10 以上的数字（我测试过）和所有正整数。该算法依赖于余数 r 继续进行。我基本上形成了这样的想法，即对于一个数字，它的因子为我们提供了面积是数字本身的矩形的边。对于所有其他不是因数的数字，都会留下余数，或者因此无法完整地形成矩形。因此想法是对于mL的每减少，我们可以增加r = mR + r（基本上从mR移动一个mRmL 到 r），然后这个大的 r 除以 mL 以查看我们可以增加多少 mR（每减少一次 mL，我们可以增加多少次 mR）。因此剩余的 r 是 r mod mL。我已经计算了查找因子所需的 while 循环数，对于所有数字，它都低于或等于 5*N。审判庭需要更多时间。*

谢谢你的时间，哈里什

4

2 回答 2

2

主循环等价于以下 C 代码：

mR = mL = sqrt(N);
...
mR = N/mL; // have the value of mL less than mR
r = N%mL;
while (r) {
  mL = mL-1;
  r += mR;
  mR = mR + r/mL;
  r = r%mL;
}

请注意，在每个r += mR语句之后， r 的值为r%(mL-1)+mR。因为r%(mL-1) < mL，r/mL在下一条语句中的值是mR/mLor 1 + mR/mL。我同意（作为数值测试的结果），mR*mL = N当你退出循环时，它可以解决，但我不明白为什么。如果你知道为什么，你应该解释为什么，如果你想让你的方法被认真对待。

就效率而言，您的方法使用与费马分解相同数量的循环，尽管费马分解的内部循环可以在不使用任何除法的情况下编写，您的方法在其内部循环中使用两个除法运算 (r/mL和)。r%mL在这两种方法的最坏情况下，内部循环运行大约 sqrt(N) 次。

于 2011-09-16T15:32:46.887 回答
1

还有其他的，例如Pollard 的 rho 算法和 GNFS，您在上一个问题中已经被告知。

于 2011-09-16T07:41:38.683 回答