mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2010-05-29, 13:05   #1
3.14159
 
3.14159's Avatar
 
May 2010
Prime hunting commission.

24·3·5·7 Posts
Default 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.
3.14159 is offline   Reply With Quote
Old 2010-05-29, 14:46   #2
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

3×1,181 Posts
Default

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!
jasonp is offline   Reply With Quote
Old 2010-05-29, 15:14   #3
3.14159
 
3.14159's Avatar
 
May 2010
Prime hunting commission.

24×3×5×7 Posts
Default

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
3.14159 is offline   Reply With Quote
Old 2010-05-29, 16:11   #4
3.14159
 
3.14159's Avatar
 
May 2010
Prime hunting commission.

24·3·5·7 Posts
Default 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
3.14159 is offline   Reply With Quote
Old 2010-05-29, 17:55   #5
3.14159
 
3.14159's Avatar
 
May 2010
Prime hunting commission.

24×3×5×7 Posts
Default

c86: (Factoring...)

Code:
SIQS parameters: 27856 primes, sieve limit: 93264
Multiplier: 11, factor base: 686837
3.14159 is offline   Reply With Quote
Old 2010-05-29, 20:56   #6
kar_bon
 
kar_bon's Avatar
 
Mar 2006
Germany

32·52·13 Posts
Default

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
kar_bon is offline   Reply With Quote
Old 2010-05-29, 22:02   #7
cheesehead
 
cheesehead's Avatar
 
"Richard B. Woods"
Aug 2002
Wisconsin USA

769210 Posts
Default

Quote:
Originally Posted by 3.14159 View Post
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
cheesehead is offline   Reply With Quote
Old 2010-05-29, 23:02   #8
3.14159
 
3.14159's Avatar
 
May 2010
Prime hunting commission.

24×3×5×7 Posts
Default

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
3.14159 is offline   Reply With Quote
Old 2010-05-29, 23:12   #9
3.14159
 
3.14159's Avatar
 
May 2010
Prime hunting commission.

24·3·5·7 Posts
Default

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
3.14159 is offline   Reply With Quote
Old 2010-05-29, 23:17   #10
3.14159
 
3.14159's Avatar
 
May 2010
Prime hunting commission.

24·3·5·7 Posts
Default

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.
3.14159 is offline   Reply With Quote
Old 2010-05-30, 00:00   #11
3.14159
 
3.14159's Avatar
 
May 2010
Prime hunting commission.

24·3·5·7 Posts
Default

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
3.14159 is offline   Reply With Quote
Reply

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 2021-01-29 21:17
A stupid factoring method JM Montolio A Miscellaneous Math 11 2018-02-28 11:29
A (very) weak factoring method. 3.14159 Miscellaneous Math 29 2010-05-31 23:21
Is this a feasible factoring method? 1260 Miscellaneous Math 46 2010-05-31 17:37
Fermat's factoring method with Gauss's inprovement Carlos Programming 0 2005-09-11 12:50

All times are UTC. The time now is 14:26.


Sat Nov 27 14:26:42 UTC 2021 up 127 days, 8:55, 0 users, load averages: 1.04, 1.16, 1.08

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.