Re: I was right, surrogate factoring proof

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

Date: Sun, 13 Feb 2005 20:21:29 -0500

[JSH]
>>> Ok. An algorithm is easy.

[Tim Peters]
>> BTW, thank you for posting this! You can believe it's because I'm
>> stupid if you want to, but I never would have guessed that this is
>> the algorithm you had in mind based on your list of equations.

[JSH]
> I don't have a negative opinion on the subject.

As I said, I don't care to what you ascribe this.

> Believe it or not, I'm just trying to figure some things out.
>
> I don't have a lot of personal interest in most of you, one way or
> another.

I believe that.

>>> Given an odd natural number M to be factored.

>> As it seems to have turned out later, M can't be a square (although
>> the algorithm actually works for M=9).

> That's an interesting tidbit. I'll have to think about it later.
>
> If it did work for that case, it's a special case, possibly having to
> do with...I don't know why it would work.
>
> I'd have to think about it, but if it did work, that's a special case.

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.

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

>>> Select j. Simplest is to let j = floor(M/2).
>>>
>>> If j is even, add 1.
>>>
>>> Calculate T.
>>>
>>> T = M^2 - j^2.
>>>
>>> Factor T, and j.
>>>
>>> Iterate through integer f_1 and f_2 such that f_1 f_2 = Tj^2.

>> This part wasn't entirely clear. Is there an implicit assumption
>> that f1>1 and f2>1?

I think your answer to this was "no", but it wasn't clear.

>> Just because it wasn't clear, in most of the results I reported I
>> used _all_ integer f_1 and f_2 whose product was Tj^2. For example,
>> if Tj^2 factored to 2*3 (which no Tj^2 could factor to, but I just
>> want to keep this list small), I tried these 8 possibilites for f_1
>> and f_2:
>>
>> f_1 f_2
>> 2 3
>> 3 2
>> -2 -3
>> -3 -2
>> 1 6
>> 6 1
>> -1 -6
>> -6 -1
>>
>> I doubt that's what you intended, but since it wasn't clear I tried
>> to use the union of everything that might have been intended.

> You need to get every possible integer Ax, so whatever does that should
> be done.

So it sounds like you do need to consider the trivial factorization (Tj^2 =
(1)*(Tj^2)), and negations too. OK, I've been doing that.

> Some of those I'd think would necessarily give the same answers though.

Yes, for each pair <f1, f2> above, the pair <f2, f1> is necessarily
redundant, due to the specific forms of the two equations for Ax given
later. I'm trying 'em anyway.

> Doesn't hurt, but would just be a waste. You just need every distinct
> Ax.

[...]
> It seems right to me, so I don't know why it wouldn't work.

Take a small failing numeric example (I gave one before, and could give many
more), and trace it out, step by step, against what you think you proved.
At some point you must find a step where you've made an incorrect conclusion
("or algebra itself is wrong" <wink>).

> The math seems straightforward but if it doesn't work then something is
> wrong somewhere, either in the theory or implementations.
>
> I'm more of a theory guy, like I'm a theoretical amateur mathematician.
>
> Sure, I can code and test, but I kind of do it as a last resort,
> preferring to work it all out theoretically first to see what MUST be
> true.

Well, it doesn't look like that's been working for you.

Quantcast