Harristotelian Logic

Having finally done some experimentation versus just play with theory, I have a better handle now on the theory and think I can give a succinct explanation, finally, that should be, well, perfect which covers the practical implementation of surrogate factoring.

Practically surrogate factoring can be considered to be finding prime factors of a target composite using the factors of what I call the surrogate where the surrogate is

2k^2 - wT

where k is a non-zero integer, and w is a non-zero integer.

(For an explanation of the 'why' of surrogate factoring please go to my Extreme Mathematics group:

http://groups.google.com/group/extrememathematics/web/surrogate-factoring)

With factors

4f_1*f_2 = 2k^2 - wT

then it's trivial to find that functionally using surrogate factoring involves checking

2f_1 +/- k and 2f_2 +/- k

for prime factors in common with T, as

x+y = 2f_1 +/- k

and

x - y = 2f_2 +/- k

gives

x^2 = y^2 mod p, where p is a prime factor of the target T, when this method works.

So when does it work?

Theory indicates that for a given w, k pair, you will get a non-trivial factorization for SOME f_1 and f_2 as defined above, 50% of the time.

So, for instance, if you hold k constant, and increment w, then the probability goes as

(1 - (1/2)^i)*100%

so, for instance, with a single k, and using -1, - 2 and -3 in succession for w, the probability that you will non-trivially factor T, with one of your combinations of factors f_1 and f_2 is

(1 - 1/8)*100% = 87.5%

but that requires that EACH of the surrogates is fully factored, which means that you need to be able to factor rather well first, before you start with surrogate factoring, though then you get an additional boost to any factoring method, according to the theory, and my limited experiments with small numbers have held to that theory.

When the surrogates are fully factored, the method works extremely well, factoring numbers very few iterations, as I've pointed out on my math sites.

If this simple theory was done correctly by me, it means that an approach to an RSA sized number would require use of heavy factoring machinery already known, like the Number Field Sieve to factor the surrogates, as they'd be very large.

But if a particular surrogate is hard to factor—you can go to another.

And that's how surrogate factoring could be a very powerful and practical method, as given any hard target, you can turn it into multiple targets where methods may be found to make them a lot easier to factor, and you have a high probability of success once you do so, though you may loop through a lot of combinations as you find every
possible f_1 and f_2 to check, which is where you can get into heavy iterations.

Most of the above is easy to figure out from the mathematics itself, which is very trivial algebra, and from playing around with actual factoring using this technique.

The reason it has interesting properties like the 50% probability with every w, k has to do with the fundamental nature of the equations used, as astute readers may note that if you take away the restriction that k be non-zero, and let k=0, then you just find the well-known difference of squares.

Surrogate factoring can be described as yet another way to get a difference of squares.

The mathematics is easy to the point of triviality.

There is no mathematical doubt that this method works as described.