我有一个新的算法来找到线性时间因素或素数 - 需要验证此 [英] I have a new algorithm to find factors or primes in linear time - need verification for this

问题描述

我已经开发了一种算法找到给定数量的因素。因此，它也有助于寻找如果给定数量是素数。我觉得这是最快的算法找出因素或质数。

I have developed an algorithm to find factors of a given number. Thus it also helps in finding if the given number is a prime number. I feel this is the fastest algorithm for finding factors or prime numbers.

此算法找到如果一个给数是素在5 * N（其中N是输入数）的时间框架。所以，我希望我能称之为线性时间的算法。

This algorithm finds if a give number is prime in time frame of 5*N (where N is the input number). So I hope I can call this a linear time algorithm.

如何可以验证这是否是最快的算法可用？能否在这个问题上任何人帮助吗？ （快于GNFS和其他已知的）

How can I verify if this is the fastest algorithm available? Can anybody help in this matter? (faster than GNFS and others known)

算法下面给出

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

请提供您的意见..不要犹豫与我联系更多的信息。

Please provide your comments.. dont hesitate to contact me for any more information.

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

推荐答案

线性时间是指时间成正比的长度的输入数据：位的数数你想因式分解，在这种情况下。你的算法不在线性时间，或任何接近它跑，我怕这比许多现有的保理算法慢得多。 （包括，例如，GNFS。）

"Linear time" means time proportional to the length of the input data: the number of bits in the number you're trying to factorize, in this case. Your algorithm does not run in linear time, or anything close to it, and I'm afraid it's much slower than many existing factoring algorithms. (Including, e.g., GNFS.)

这篇关于我有一个新的算法来找到线性时间因素或素数 - 需要验证此的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！