I have a new algorithm to find factors or primes in linear time - need verification for this

Question

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.

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.

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

Algorithm is given below

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.

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

+1 for your nice question and nice trial. I can't believe your question got seen 68 times, that an answer got +6 upvotes and that **NOBODY** voted you up. SO is broken. Plain and simple. People asking question should get rep every time an answer is upvoted. Maybe something like 1/10th of a rep point for every answer upvote. — SyntaxT3rr0r, Apr 07 '11 at 16:33
@SyntaxT3rr0r: Well, suggest that on [meta](http://meta.stackoverflow.com) (though I think it will get rejected, in light of questions like [this](http://stackoverflow.com/questions/3905734)) — BlueRaja - Danny Pflughoeft, Apr 07 '11 at 16:37
@BlueRaja - Danny Pflughoeft: well, it would be easily solved by putting a cap on every single question. For example you could get at most +10 rep points per "answers", so for the 400 +upvotes he'd get only +10 points, and he'd still get negative rep overall seen that he's a -40 for his question. Good idea: I'll suggest that on meta one of these days. — SyntaxT3rr0r, Apr 07 '11 at 16:41

score 14 · Accepted Answer · answered Apr 07 '11 at 12:34

14

"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.)

answered Apr 07 '11 at 12:34

Gareth McCaughan

19,888
1
41
62

Thanks for your reply. If you have time, I would like to understand more. My understanding of algorithm analysis is indeed less. I calculated the number of steps to determine a number is prime to be around 5*N (where N is the input number) by this algorithm. And taking 1 unit as time, I put the time of algorithm as 5*N. Here number of steps include basic addition, subtraction, comparsion only (based on the algorithm given in my blog). Do you have any reference to any resource, by which I can know how to find time taken based on input size? Or can you tell me the steps required? Thank – harish Apr 07 '11 at 13:15
4

The input size will be about log_2(N); that is, N is about 2^b where b is the input size in bits. So the running time of your algorithm is proportional to 2^b ... except that actually it's worse than that, because for very large numbers operations like addition and multiplication aren't constant-time operations; addition takes time proportional to b, and multiplication and division something more like b log b. So your algorithm's runtime is something like 2^b b log b. GNFS, on the other hand, is something like exp((Ab)^1/3 (log b)^2/3) where A is a constant that happens to be 64/9. – Gareth McCaughan Apr 07 '11 at 13:40
2

If b=100, for instance, then 2^b b log b is a number about 33 digits long, whereas exp((Ab)^1/3 (log b)^2/3) is a number about 11 digits long. – Gareth McCaughan Apr 07 '11 at 13:43
2

So, if we ignore the constant factors in front of those two estimates and just suppose they're operation counts, and if we suppose we can do 10^9 operations per second, then GNFS can factorize a 100-bit number in something like 100 seconds whereas your algorithm will take something like 10^16 years. – Gareth McCaughan Apr 07 '11 at 13:45

score 5 · Answer 2 · answered Apr 07 '11 at 12:43

5

The size of the input in this case is not n, but the number of bits in n, so the running time of your algorithm is exponential in the size of the input. This is known as pseudo-polynomial time.

answered Apr 07 '11 at 12:43

hammar

138,522
17
304
385

score 3 · Answer 3 · answered Apr 07 '11 at 12:42

3

I haven't looked closely at your algorithm, but prime number tests are usually faster than O(n) (where n is the input number). Take for example this simple one:

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

Here it is determined in O(sqrt(n)) if n is prime or not, simply by checking all possible factors up to sqrt(n).

answered Apr 07 '11 at 12:42

sth

222,467
53
283
367

@hammar and @sth : please find my reply for your comments as a comment under Gareth McCaughan's reply for my question. Thanking you if any of you could help me on how to calculate time taken for this algorithm? – harish Apr 07 '11 at 13:36

I have a new algorithm to find factors or primes in linear time - need verification for this

3 Answers3

Linked