Another factoring method rides the bus

[3.14159]

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.

[jasonp]

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!

[3.14159]

Isn't ECM based on Dixon?

A c84 I factored in 56 minutes, 7 seconds:

234293053835980412526090924492607112545727897587010892776365305664957926315326650373 
= 453099212038126398025303633885448659236467 x 
517089960898598152631486542128206611972519

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

[3.14159]

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² is b-smooth modulo 149137, and b² is b-smooth 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, 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.

[3.14159]

c86: (Factoring...)

SIQS parameters: 27856 primes, sieve limit: 93264
Multiplier: 11, factor base: 686837

[kar_bon]

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.

[cheesehead]

Originally Posted by 3.14159

I stumbled upon the following factoring method

Fermat left some trails for us to stumble upon, didn't he? :-)

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, ...).

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?

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?

[3.14159]

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.

[3.14159]

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.

[3.14159]

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≥10⁵⁵ )
2. They all use trial and error to factor.

[3.14159]

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.