This link has an online application which factors large numbers using the Elliptic Curve method. http://www.alpertron.com.ar/ECM.HTM
Try a value like 12991627363868130524522557049357159496792541860595064869631. On my computer this application factors this number in 15 seconds. Anything relying on trial division would take longer than your computer will last. Don On Apr 7, 9:11 am, harish <hareeshgn...@gmail.com> wrote: > Hi All, > > I got a reply at another forum; here is the link for > thathttp://stackoverflow.com/questions/5581040/i-have-a-new-algorithm-to-... > > .. Don i believe you are correct. > > Thanks > Harish > > On Apr 7, 4:56 pm, harish <hareeshgn...@gmail.com> wrote: > > > Hi Don, I reposting my reply to you to all now.. > > > The GNFS mentioned here is polynomial time as I got to understand from > > wikipedia. I claim that the above algorithm is linear time. > > > I putting the proof here for correctness and linear time (warning its > > big and messy). Also this one applies to the algorithm given in the > > blog:http://randomoneness.blogspot.com/2011/04/algorithm-to-find-factors-o... > > > (The above given is a faster version of the one given in my blog) > > > Analysis of algorithms: > > > In below proof used: > > Operation A is: While r is smaller than mL then, mL can be > > decremented by one and the new r can be computed as r + mR. > > As taking out one mL, means one mR is send to remainder. (first inner > > while loop) > > Operation B is: While r is bigger than mL, then mL can be taken out > > from r and this basically increases mR by one. (2nd inner while loop) > > Operation C is: Operations A and B can be repeated till, r not equals > > mL. When we arrive at the results, Operation C is > > exited. (main while loop) > > > 1. Proof of correctness: If the number is a perfect square root then, > > the answer is found when square root is found. > > For more reading on Square root > > refer:http://en.wikipedia.org/wiki/Square_root > > Else if the number is not a perfect square, then r is not equal to 0. > > Hence it enters the while loop. > > Operation A: While mL is greater than r, then mL is decremented by 1, > > and r is incremented by mR. > > The step is correct because, mL * mR means mR added mL times. If one > > is taken from mL, then mR is added > > (mL-1) times. So, one mR is added less, when taking one out of mL. > > This mR is added to r. – (1) > > Operation B: While mL is less than r, then mR is incremented by 1 and > > r is decremented by mL. This > > step is correct because, mL * mR means mL added mR times. If one is > > added to mR, then mL is added (mR + 1) > > times in mL*mR. So if mR is incremented by 1, then to equate to N, mL > > can be taken away from r the > > remainder. – (2) > > Operation C: Operation A and B are repeated till mL is equal to r. > > This leads to the answer because: > > We start from the approximate square root of the number. As operation > > A and B, calculates the remainder r, > > when the factors are mL and mR. Operation A never leads to the answer > > as, r + mR is always greater than mL, > > as mL is smaller than mR. Operation B, leads to the answer. If for any > > case mL is a factor, then, when r is > > reduced by mL in operation B to mL (r becomes a factor of mL). As > > Operation A and B are correct (refer 1 and > > 2), if there is a factor then this leads to r to be zero. And before r > > becomes zero, r should be equal to mL. At this > > point the answer is found. > > > 2. Proof that the number of Operations required is linear: Let’s take > > only the case of numbers which are not > > perfect squares. > > The algorithm consists of basic operations, of addition, subtraction > > and comparison. Let’s see how > > many times a different while loops are invoked. > > We take mL as nearest square root. And take mR > mL. > > There for Operation A is invoked only once during one iteration of the > > Operation C. This is because, by > > incrementing r by mR, increases r to be greater than mL (mR > mL) and > > hence invalidates the loop condition. > > The basic number of steps in Operation A is 3: 1. While loop > > evaluation, 2. decrement mL by 1 and 3. Increment > > r by mR. > > Operation B is repeated to find a r which is greater than mL. As mR > > varies as algorithm progress, its > > hard to calculate number of time r Operation B is repeated. The basic > > number of steps in Operation B is 3: 1. > > while loop evaluation, 2. Increment mR by 1 and 3. Decrement r by mL. > > However two things are certain, for worst case scenario i.e. N is > > prime number, mL is reduced to 1 and > > mR is incremented to N. From this we can conlude that, Operation B is > > repeated N-sqrt(N) times i.e. Increment > > mR to N from sqrt(N) and Operation A is repeated till mL becomes 1 i.e > > from sqrt(N) to 1. Based on this the > > number of steps required is: > > Operation B : N – sqrt(N) > > Operation A : sqrt(N) > > And the Operation C, which apart from the steps we calculate from > > Operation A and Operation B, will > > have 2 basic steps; 1. the main while evaluation, 2. the exit > > evaluation of one of the while either of Operation A > > or B; during each loop execution. Operation C is called maximum of N > > times in worst case, as its sum of > > number of times Operation A and B = (N- sqrt(N) + sqrt(N) = N. > > The total number of steps is: > > => Operation B + Operation A + Operation C > > => (N – sqrt(N))* 3 + sqrt(N) * 3 + 2*N > > => 3*N+ 2*N > > => 5*N > > Hence the total number of steps is 5*N in worst case and lesser in all > > other cases. > > However, in normal computers as the input size increases the time > > taken to do addition, subtraction and > > comparison varies. As the input size increases above the size of > > computers word size, the number of operations > > required for the computing basic steps are higher. But for a given > > arbitrarily large number (higher than computer > > word size), the time taken for each basic operation would be fixed, > > even though is larger than in case of smaller > > number. Hence time taken would increase by the hidden factor times > > 5*N. > > > On Apr 7, 1:14 am, Don <dondod...@gmail.com> wrote: > > > > The General Number Field Sieve is the fastest known method of > > > factoring large numbers, but the elliptic curve method may be faster > > > in some cases. Either one is much faster than your method. > > > Don > > > > On Apr 6, 12:58 pm, harish <hareeshgn...@gmail.com> wrote: > > > > > Hi all, > > > > > 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. > > > > > I have put the algorithm > > > > here:http://randomoneness.blogspot.com/2011/04/algorithm-to-find-factors-o... > > > > This one finds if a give number is prime in say time frame of 5*N > > > > (where N is the input number). So I hope I can call this a linear time > > > > algorithm. > > > > > Can anybody verify the above for me? > > > > > A faster version of algorithm i put here: > > > > > 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- Hide quoted text - > > > > - Show quoted text -- Hide quoted text - > > > - Show quoted text - > > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
