mersenneforum.org Another factoring method rides the bus
 Register FAQ Search Today's Posts Mark Forums Read

 2010-05-29, 13:05 #1 3.14159     May 2010 Prime hunting commission. 24×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 insta-factored. (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. 81-77 = 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.
 2010-05-29, 14:46 #2 jasonp Tribal Bullet     Oct 2004 3×1,193 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!
 2010-05-29, 15:14 #3 3.14159     May 2010 Prime hunting commission. 24×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 2010-05-29 at 15:22
 2010-05-29, 16:11 #4 3.14159     May 2010 Prime hunting commission. 110100100002 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 a2 is b-smooth modulo 149137, and b2 is b-smooth modulo 149137. This demands testing every integer a and every integer b from n0.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, slowed-down 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 2010-05-29 at 16:29
 2010-05-29, 17:55 #5 3.14159     May 2010 Prime hunting commission. 69016 Posts c86: (Factoring...) Code: SIQS parameters: 27856 primes, sieve limit: 93264 Multiplier: 11, factor base: 686837
 2010-05-29, 20:56 #6 kar_bon     Mar 2006 Germany 22·13·59 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. Less than 8 min for YAFU and 4 cores on a Quad 2.4GHz with one PFGW-thread in background! So 90 to 95 digits no problem with SIQS, too. Above msieve is the better choice. Last fiddled with by kar_bon on 2010-05-29 at 20:56
2010-05-29, 22:02   #7

"Richard B. Woods"
Aug 2002
Wisconsin USA

1E0C16 Posts

Quote:
 Originally Posted by 3.14159 I stumbled upon the following factoring method
Fermat left some trails for us to stumble upon, didn't he? :-)

Quote:
 4. If the difference itself is a perfect square, the number is insta-factored. (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)
No, you just gave up too soon.

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, P-1, ECM, ... are fine methods for certain cases (TF: small factor exists, P-1: factor exists that is one more than a product of small primes, ...).

Quote:
 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.
Given that prime number and factor are defined in terms of divisibility, just how do you expect any factorization method not to be more or less related to trial division?

Quote:
 The sad part: Out of the many, many variations, trial division is the fastest one.
The different variations are different ways of trying to efficiently choose candidate factors. Different variations are fastest in different cases; plain sequential trial division is not always fastest. That's not sad, is it?

What factorization method do you know of that's not more-or-less related to trial division?

Last fiddled with by cheesehead on 2010-05-29 at 22:17

2010-05-29, 23:02   #8
3.14159

May 2010
Prime hunting commission.

110100100002 Posts

Quote:
 5. Iterate through a sequence of squares (rearranged a la Fermat).
AKA, test every single square number after the square root to try and find that difference that is itself a perfect square. Therefore, the original statement "Proceed to trials" is valid. And it's true, it sucks for numbers that have a factor far from the square root. But either way, trials must be used. For numbers such as 4231828380109503038830895123971102456631, or 69337887448133 * 61031977405931910039000907, using Fermat would be a total disaster. But for numbers such as 42301547631053914879007648741 * 42783547631053914879007648763, using Fermat would be a good idea.

Last fiddled with by 3.14159 on 2010-05-29 at 23:07

2010-05-29, 23:12   #9
3.14159

May 2010
Prime hunting commission.

32208 Posts

Quote:
 Given that prime number and factor are defined in terms of divisibility, just how do you expect any factorization method not to be more or less related to trial division?
All factoring methods do not work similarly to trial division. Although the goal of trial division and a method differing from it are similar. Fermat's method is an elegant spin-off of trial division. (The trials are the squares.)

That point was a total strawman.

Last fiddled with by 3.14159 on 2010-05-29 at 23:13

2010-05-29, 23:17   #10
3.14159

May 2010
Prime hunting commission.

24·3·5·7 Posts

Quote:
 The different variations are different ways of trying to efficiently choose candidate factors
I call them variations of trial division due to the following:
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≥1055 )
2. They all use trial and error to factor.

 2010-05-30, 00:00 #11 3.14159     May 2010 Prime hunting commission. 24×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 2010-05-30 at 00:05

 Similar Threads Thread Thread Starter Forum Replies Last Post EdH Other Mathematical Topics 52 2021-01-29 21:17 JM Montolio A Miscellaneous Math 11 2018-02-28 11:29 3.14159 Miscellaneous Math 29 2010-05-31 23:21 1260 Miscellaneous Math 46 2010-05-31 17:37 Carlos Programming 0 2005-09-11 12:50

All times are UTC. The time now is 02:56.

Sat Sep 30 02:56:34 UTC 2023 up 17 days, 38 mins, 0 users, load averages: 1.00, 1.07, 0.95