Re: I was right, surrogate factoring proof

From: Tim Peters (tim.one_at_comcast.net)
Date: 02/14/05 

Date: Mon, 14 Feb 2005 00:40:21 -0500

[...]
[Tim Peters]
>> This one is easy. _Any_ method that tries lots of gcds is going to
>> do a good job of factoring _most_ small composites. You may not
>> realize how effective purely-random gcd is for small composites.
>> Finding any integer divisible by 3 (but not by 9) is all it takes to
>> factor 9 via gcd. It's very easy to find such an integer by blind
>> luck, and the odds favor success if you try just twice.

[JSH]
> No, I see you don't understand.
>
> There's a proof that the method does not work for primes squared.
>
> The reason is that an x that works has a factor squared in common with
> M.
>
> So, if M=9, then the algorithm will return x's that have 9 as a factor,
> and not 3.

It's 2-digit arithmetic (are you incapable of this?):

# Given an odd natural number M to be factored.

OK, M=9. That's 3 squared, and 3 is a prime.

# Select j. Simplest is to let j = floor(M/2).
#
# If j is even, add 1.

I'm going to pick j=3.

# Calculate T.
#
# T = M^2 - j^2.

OK, T = 81 - 9 = 72.

# Factor T, and j.

OK, T = 2*2*2*3*3, and j=3.

# Iterate through integer f_1 and f_2 such that f_1 f_2 = Tj^2.

So Tj^2 = 2*2*2*3*3 * 3*3

There are 16 ways to get gcd(Ax, 9) = 3 now. Here are two of them, from one
<f1, f2> pair:

f1 = 2*2*2*3 = 24
f2 = 3*3*3 = 27

# For each f_1 and f_2 calculate Ax using
#
# Ax = (f_1 - f_2) + 2j^2

OK, Ax = (24 - 27) + 2*3^2 = 15, and gcd(15, 9) = 3.

# and
#
# Ax = (f_2 - f_1) + 2j^2

OK, Ax = (27 - 24) + 2*3^2 = 21, and gcd(21, 9) = 3.

# to handle plus or minus, and take the gcd of Ax with M.
#
# The gcd of Ax with M will be a single prime factor of M, for at least
# one set of f_1 and f_2.

As above, that happened to be true for at least one way of picking odd j for
M=9. For the older method Rick Dicker explained, it looked like j was a
winner for p^2 if and only if j was a multiple of p. That may be true here
too; haven't checked beyond M=9 and j=3; the concrete example above is
consistent with that.

>> Random gcd gets very much less effective as the smallest prime factor
>> gets larger, though, and your algorithms to date (seemingly including
>> this one) show that behavior too. For example, as I type this, each
>> odd j in 3 through 3571 has failed to find a factor of M = 112554401 *
>> 221667653 (the expected number of random gcds needed to factor this
>> is about 75 million, and it doesn't look like your method is going to
>> do better than that (I expect I'll _eventually_ find a j "that works"
>> for this M)).

> Well, it should work.
>
> And it's not random. To prove that, mess with the algorithm.
>
> Change it slightly, like take f_1 + f_2 instead of f_1 - f_2, and see
> if it factors.

I played with that for the last version of this algorithm; it didn't matter
to the results; I don't want to spend time on that again.

> I think some of you just wish to believe it's random.
>
> Now you can fiddle with the algorithm and see if varying it still gives
> you factors, which it would if it were random.
>
> You're also vastly underestimating how many numbers are being checked

No, I'm not estimating anything. I use actual counts obtained by
instrumenting the code.

> through as 75 million is so huge in terms of combinations that it's
> getting in that range I mentioned earlier of the first 1000 primes
> multiplied together.

Ah! You don't read the threads you start. If you had, you would have
already seen that your analysis of this business was incorrect. If P is the
product of n _distinct_ primes, then the number of distinct ways to express
P as the product of two integers >= 1 is 2^(n-1) (a proof was given
earlier). All estimates you've given for that have been wildly too small.
For example, for n=1000, the actual number of distinct <f1, f2> pairs is
2^999 ~= 5.4*10^300, not the relatively insignificant 150 million you
claimed it was (but without showing your work, so I don't know how you got
so far off track).

Take a small example, say the first 4 primes: 2, 3, 5, 7. The product is
201. There are 2^(4-1) = 8 distinct ways to factor that as the product of
two integers >= 1:

   (1)(2 3 5 7)
   (2)(3 5 7)
   (3)(2 5 7)
   (5)(2 3 7)
   (7)(2 3 5)
   (2 3)(5 7)
   (2 5)(3 7)
   (2 7)(3 5)

If you add 11 to the pile, you can stick it into the first or second half of
each of those 8, giving 16 ways in all. If you then add 13, it doubles
again to 32; etc.

With your latest method, we have to double it to 2^n, because for every
unique <f1, f2> with f1 and f2 >= 1 and f1*f2=Tj^2, it's apparently
necessary to consider <-f1, -f2> too.

> Fiddle with the algorithm and see for yourself it's not random.

As above, I did that last time and don't see a point to doing it again.

[...]
> Whether you wish to believe it or not, if a mathematical argument is a
> proof then it must be true, and it must work.

The most likely resolution to me is that you don't actually have a proof.
There are deeper reasons for that expectation than just your track record
here, but I'm not going into them.

[...]
> My analysis is that it is without error,

Ya, except that's _always_ your claim. I confess that I don't try to make
sense of the posts you call proofs anymore -- it's too time-consuming,
because you routinely say "oops!" and replace them with another pile of
equations, over and over. I can't make much time for this, and writing
programs is much less demanding for me, so that's what I do -- it's all I
can make time for.

> so there is a flaw in your implementation, or a flaw in the algorithm
> I gave.

So apply your algorithm to one of the counterexamples that have been posted.
Then it's your proof and your understanding of your algorithm. I gave you a
3-digit counterexample before small enough to work out entirely by hand. Do
the arithmetic (as you should have done for M=9 above!).