2

Few months ago I had asked a question on an "Algorithm to find factors for primes in linear time" in StackOverflow.

In the replies i was clear that my assumptions where wrong and the Algorithm cannot find factors in linear time.

However I would like to know if the algorithm is an unique way to do division and find factors; that is do any similar/same way to do division is known? I am posting the algorithm here again: 

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

Let me know your inputs/ The question is purely out of personal interest to know if a similar algorithm exists to do division and find factors, which I am not able to find.

I understand and appreciate thay you may require to understand my funny algorithm to give answers! :)

Further explanation: Yes, it does work on numbers above 10 (which i tested) and all positive integers. The algorithm depends on remainder r to proceed further.I basically formed the idea that for a number, its factors gives us the sides of the rectangles whose area is the number itself. For all other numbers which are not factors there would be a remainder left, or consequently the rectangle cannot be formed in complete. Thus idea is for each decrease of mL, we can increase r = mR+r (basically shifting one mR from mRmL to r) and then this large r is divided by mL to see how much we can increase mR (how many times we can increase mR for one decrease of mL). Thus remaining r is r mod mL. I have calculated the number of while loop it takes to find the factors and it comes below or equal 5*N for all numbers. Trial division will take more.*

Thanks for your time, Harish

Community
  • 1
  • 1
harish
  • 103
  • 6
  • Worst case is 5*N, for what kind of numbers it is? BTW, worst case for simple trial division is sqrt(N) and seems like your method have the same worst case running time. – actual Sep 16 '11 at 15:36

2 Answers2

2

The main loop is equivalent to the following C code:

mR = mL = sqrt(N);
...
mR = N/mL; // have the value of mL less than mR
r = N%mL;
while (r) {
  mL = mL-1;
  r += mR;
  mR = mR + r/mL;
  r = r%mL;
}

Note that after each r += mR statement, the value of r is r%(mL-1)+mR. Since r%(mL-1) < mL, the value of r/mL in the next statement is either mR/mL or 1 + mR/mL. I agree (as a result of numerical testing) that it works out that mR*mL = N when you come out of the loop, but I don't understand why. If you know why, you should explain why, if you want your method to be taken seriously.

In terms of efficiency, your method uses the same number of loops as Fermat factorization although the inner loop of Fermat factorization can be written without using any divides, where your method uses two division operations (r/mL and r%mL) inside its inner loop. In the worst case for both methods, the inner loop runs about sqrt(N) times.

James Waldby - jwpat7
  • 8,593
  • 2
  • 22
  • 37
  • The explanation; for a number 371. Square Root of 371 ~ 19. Hence starting as: >>18*20+11 = 371 >>17*20+31 = 371 >>17*21+14 = 371 >>16*21+35= 371 >>16*22+19= 371 >>16*23+3= 371 ..so on.. Consider if 18*20 (height*breadth) is a rectangle. With 11 as a remainder(line). When one line is removed from 18, it implies I can move an amount 20 to the remainder, to get 31. As 31 is larger than 18,I remove one 18 from 31,which i can add to the rectangles breadth i.e. from 20 to 21, this operation is the division operation.And left is remainder. – harish Sep 20 '11 at 07:36
1

There are others, for example Pollard's rho algorithm, and GNFS which you were already told about in the previous question.

harold
  • 61,398
  • 6
  • 86
  • 164
  • Ya I understand that there are other ways to find factors. My question is: is this a unique way - like Pollard's rho algorithm and GNFS are different - is this different from all other existing methods? Please let me know if i am not clear. – harish Sep 16 '11 at 09:40
  • @harish ok so what you mean is, is this fundamentally different from all other factorization algorithms? To be honest I'm not sure whether this is a factorization algorithm at all, it appears to be doing trial division but on a moving target, does it really work? – harold Sep 16 '11 at 09:52
  • I am editing the question - to answer for your comment and explain further on the question as 550 characters in comments section was little less for reply :) – harish Sep 16 '11 at 14:27