我有一个新的算法来查找线性时间内的因子或素数 - 需要对此进行验证

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

在这种情况下,输入的大小不是ñ,但在比特数ñ,所以你的算法的运行时间是在输入的大小指数.这被称为伪多项式时间.