20100529, 13:05  #1 
May 2010
Prime hunting commission.
2^{4}·3·5·7 Posts 
Another factoring method rides the bus
I stumbled upon the following factoring method, that's based on differences of squares. Here are the steps:
1. Choose integer n to be factored 2. Computer nearest square number larger than it 3. Find difference between the perfect square and integer n. 4. If the difference itself is a perfect square, the number is instafactored. (The square root of the square number larger than n and the difference provide the factors.) 5. If not, proceed to trials. (Which is why this ultimately bites the dust) Ex: 77 Square number greater than 77 = 81. 8177 = 4 4 = 2^2 81 = 9^2 Factors: 9 ± 2 9  2 = 7 9 + 2 = 11 7 * 11 = 77. 77 = 77 Ex2: 130950210547704929. Square number greater than 130950210547704929 = 361870434^2, or 130950211003348356. Difference between 130950211003348356 and 130950210547704929 = 455643427. 455643427 is not a perfect square: We proceed to trial and error: 3 consecutive odd numbers that add up to 130950210547704929. (None exist.) 5? None exist We would have to continue doing this until we actually bumped into one of its factors. This seems to be nothing more than another variation of trial division, except that it uses differences of square numbers to try and find the factors, instead of dividing by primes repeatedly. There sure are many variations of trial division. The sad part: Out of the many, many variations, trial division is the fastest one. 
20100529, 14:46  #2 
Tribal Bullet
Oct 2004
5·709 Posts 
You're describing Fermat's method. Replace an exact difference of squares with a GCD of random squares and you get Dixon's method. Replace the inputs to Dixon's method with the result of a sieve and you have QS. Use a much more complex sieve and some algebraic number theory and you get NFS.
All of these methods have wikipedia pages; join the party! 
20100529, 15:14  #3 
May 2010
Prime hunting commission.
2^{4}×3×5×7 Posts 
Isn't ECM based on Dixon?
A c84 I factored in 56 minutes, 7 seconds: Code:
234293053835980412526090924492607112545727897587010892776365305664957926315326650373 = 453099212038126398025303633885448659236467 x 517089960898598152631486542128206611972519 Code:
Factorization complete in 0d 0h 56m 7s ECM: 1862524 modular multiplications Prime checking: 99796 modular multiplications SIQS: 2359656 polynomials sieved 277730 sets of trial divisions 11223 smooth congruences found (1 out of every 18397873 values) 135398 partial congruences found (1 out of every 1524980 values) 13226 useful partial congruences Timings: Primality test of 2 numbers: 0d 0h 0m 0.0s Factoring 1 number using ECM: 0d 0h 0m 0.0s Factoring 1 number using SIQS: 0d 0h 56m 4.0s Last fiddled with by 3.14159 on 20100529 at 15:22 
20100529, 16:11  #4 
May 2010
Prime hunting commission.
2^{4}×3×5×7 Posts 
And, yet another bites the dust.
Dixon's method seems rather straightforward. But it degenerates into trial division, like the previous one. It bites the dust.
Update: Ex: 149137 B = 11 Factor base: {2, 3, 5, 7, 11} Find integers a and b in which a^{2} is bsmooth modulo 149137, and b^{2} is bsmooth modulo 149137. This demands testing every integer a and every integer b from n^{0.5} up to n until a solution is found. The method is again virtually useless as it resorts to blind guessing for thousands of candidate integers. Again, sloweddown trial division. Or is there a more deterministic way of doing it? An example that's way out of its league would be 387610246589. How did this extremely slow method ever give rise to QS/ECM? O_O Factoring even a c3 or c4 is a problem here. Last fiddled with by 3.14159 on 20100529 at 16:29 
20100529, 17:55  #5 
May 2010
Prime hunting commission.
2^{4}·3·5·7 Posts 
c86: (Factoring...)
Code:
SIQS parameters: 27856 primes, sieve limit: 93264 Multiplier: 11, factor base: 686837 
20100529, 20:56  #6 
Mar 2006
Germany
3×23×43 Posts 
Code:
05/29/10 22:40:41 v1.18 starting SIQS on c84: 234293053835980412526090924492607112545727897587010892776365305664957926315326650373 05/29/10 22:40:41 v1.18 random seeds: 0, 2917324952 05/29/10 22:40:42 v1.18 ==== sieve params ==== 05/29/10 22:40:42 v1.18 n = 85 digits, 280 bits 05/29/10 22:40:42 v1.18 factor base: 52071 primes (max prime = 1356737) (...) 05/29/10 22:40:42 v1.18 using multiplier of 5 (...) 05/29/10 22:48:32 v1.18 prp42 = 453099212038126398025303633885448659236467 05/29/10 22:48:32 v1.18 prp42 = 517089960898598152631486542128206611972519 05/29/10 22:48:32 v1.18 Lanczos elapsed time = 16.6650 seconds. 05/29/10 22:48:32 v1.18 Sqrt elapsed time = 0.4190 seconds. 05/29/10 22:48:32 v1.18 SIQS elapsed time = 470.7060 seconds. So 90 to 95 digits no problem with SIQS, too. Above msieve is the better choice. Last fiddled with by kar_bon on 20100529 at 20:56 
20100529, 22:02  #7  
"Richard B. Woods"
Aug 2002
Wisconsin USA
2^{2}·3·641 Posts 
Fermat left some trails for us to stumble upon, didn't he? :)
Quote:
5. Iterate through a sequence of squares (rearranged a la Fermat). Fermat's is a fine method for certain cases (factor exists near the square root of the number), just as TF, P1, ECM, ... are fine methods for certain cases (TF: small factor exists, P1: factor exists that is one more than a product of small primes, ...). Quote:
Quote:
What factorization method do you know of that's not moreorless related to trial division? Last fiddled with by cheesehead on 20100529 at 22:17 

20100529, 23:02  #8  
May 2010
Prime hunting commission.
2^{4}·3·5·7 Posts 
Quote:
Last fiddled with by 3.14159 on 20100529 at 23:07 

20100529, 23:12  #9  
May 2010
Prime hunting commission.
2^{4}×3×5×7 Posts 
Quote:
That point was a total strawman. Last fiddled with by 3.14159 on 20100529 at 23:13 

20100529, 23:17  #10  
May 2010
Prime hunting commission.
2^{4}·3·5·7 Posts 
Quote:
1. They only work for small n (If you can show a large integer that can be factored using trial division or any of its variations, feel free to do so. By large, I mean , n≥10^{55} ) 2. They all use trial and error to factor. 

20100530, 00:00  #11 
May 2010
Prime hunting commission.
2^{4}×3×5×7 Posts 
To be random: Could anyone give the data as to the amount of time it takes for ECM to find a factor of n digits, when n = 20, 30, 40, 50, 60, 70, 80, 90, 100, 110? I think I saw some of the data at some point, but don't remember it. Meh. Fine. I'll factor some random integers.
Last fiddled with by 3.14159 on 20100530 at 00:05 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Help with series convergence in Fermat method of factoring  EdH  Other Mathematical Topics  52  20210129 21:17 
A stupid factoring method  JM Montolio A  Miscellaneous Math  11  20180228 11:29 
A (very) weak factoring method.  3.14159  Miscellaneous Math  29  20100531 23:21 
Is this a feasible factoring method?  1260  Miscellaneous Math  46  20100531 17:37 
Fermat's factoring method with Gauss's inprovement  Carlos  Programming  0  20050911 12:50 