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

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

请提供您的意见..如果需要更多信息，请随时联系我。

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

Answer 1

“线性时间”意味着时间与输入数据的长度成正比:在本例中，是您试图分解的数字中的位数。你的算法不是在线性时间内运行，或者任何接近它的时间，我担心它比许多现有的因子分解算法要慢得多。(例如包括GNFS。)

Answer 2

在这种情况下，输入的大小不是n，而是n中的位数，因此算法的运行时间与输入的大小成指数关系。这就是所谓的pseudo-polynomial time。

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"

这里用O( sqrt(n) )来确定n是否是质数，简单地通过检查所有可能的因子直到sqrt(N)。