我有一个新的算法，可以在线性时间内找到因子或质数 - 需要验证此算法。

Question

我已经开发了一个算法来查找给定数字的因数。这也有助于查找给定数字是否为质数。我认为这是查找因数或质数的最快算法。

该算法在5*N（其中N是输入数字）的时间范围内判断一个数字是否为质数。因此，我希望将其称为线性时间算法。

如何验证这是可用的最快算法？有人能帮忙吗？（比GNFS和其他已知算法更快）

以下是算法:

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

请提供您的评论...如需更多信息，请随时与我联系。

谢谢， 哈里什 http://randomoneness.blogspot.com/2011/09/algorithm-to-find-factors-or-primes-in.html

- harish

---

如果有超过两个因素会怎样？ - BlackBear

+1 针对您的好问题和不错的尝试。我简直无法相信您的问题被浏览了68次，一个答案得到了+6个赞，而没有人给您点赞。SO已经崩溃了。很简单。提问的人应该在每次答案被投票时获得声望。也许每个答案赞成票可以获得1/10的声望点数。 - SyntaxT3rr0r

@SyntaxT3rr0r：好的，建议在meta上提出（尽管我认为它会被拒绝，考虑到像这样的问题）。 - BlueRaja - Danny Pflughoeft

@BlueRaja - Danny Pflughoeft：这个问题可以通过为每个问题设置上限来轻松解决。例如，您每个“答案”最多只能获得+10声望值，因此对于他获得的400个赞成票，他只会获得+10分，而且由于他的问题得到-40分，他仍然会获得负的声望值。好主意：我会在以后的某个时候在元社区中提出建议。 - SyntaxT3rr0r

Answer 1

"

“线性时间”指的是与输入数据的长度成正比的时间：在这种情况下，即试图分解的数字中比特数。您的算法不以线性时间运行，也离它非常远，恐怕比许多现有的分解算法慢得多。（包括例如GNFS等）

"

- Gareth McCaughan

---

谢谢您的回复。如果您有时间，我想更深入地了解一下。我的算法分析理解确实不够。根据这个算法，我计算出确定一个数字是否为质数所需的步骤数约为5N（其中N是输入数字）。以1个单位作为时间，我将算法的时间设置为5N。这里的步骤数仅包括基本的加法、减法和比较（基于我博客中给出的算法）。您是否有任何参考资源可以告诉我如何根据输入大小找到所需的时间？或者您能告诉我需要哪些步骤吗？ - harish

输入大小约为log_2(N)，即N约为2^b，其中b是输入的比特数。因此，算法的运行时间与2^b成比例......除非针对非常大的数字，例如加法和乘法等操作不是恒定时间操作；加法需要与b成比例的时间，而乘法和除法则需要更类似于b log b的时间。因此，您的算法运行时间大约为2^b b log b。另一方面，GNFS的运行时间大约为exp((Ab)^1/3(log b)^2/3)，其中A是一个常数，恰好为64/9。 - Gareth McCaughan

如果b=100，那么2^b b log b约为33位数字长，而exp((Ab)^1/3 (log b)^2/3)则约为11位数字长。 - Gareth McCaughan

因此，如果我们忽略这两个估计前面的常数因子，并假设它们是操作次数，如果我们假设我们可以每秒执行10^9次操作，那么GNFS可以在大约100秒内分解一个100位数，而您的算法将需要大约10^16年。 - Gareth McCaughan

Answer 2

在这种情况下，输入的大小不是 n，而是 n 的位数，因此您的算法运行时间是与输入大小呈指数关系的。这被称为伪多项式时间。

- hammar

Answer 3

我还没有仔细研究你的算法，但是素数测试通常比O(n)（其中n是输入数字）更快。例如，可以使用以下简单方法：

def isprime(n):
   for f in range(2,int(sqrt(n))):
      if n % f == 0:
         return "not prime"
   return "prime"

通过检查所有可能的因子，最多到sqrt(n)，可以在O(sqrt(n))中确定n是否为质数。

- sth

---

@hammar和@sth：请查看我对你们的评论的回复，它在Gareth McCaughan对我的问题的回复下面。感谢你们中任何一个能帮助我计算这个算法所需时间。 - harish