Re: JSH: Step by step through the factoring algorithm

On Fri, 27 Feb 2009 16:55:38 -0800, JSH wrote:


Yeah, you want a minimum for abs(r(v) + t(v)) and abs(r(v) - t(v)).

There has been some debate about how hard that is, so I'll point out
that given that:

(r(v) + t(v))(r(v) - t(v) = D(s(v))^2

if D is a positive composite, then r(v) + t(v) and r(v) - t(v) must
match by signs, which makes the next step easy.

You wish to minimize the SUM of the two, so just add them through the
absolute values, meaning the problem reduces to solving for v with

d(r(v))/dv = 0

and then finding v such that r(v) and t(v) are integers, as you want
integers to non-trivially factor, so you find the nearest ones near the
minimum. If the minimum v works, fine.


So in terms of Step 2 Case 1
r'(v) = 2(D+1)v - 2*f_1 which equals zero at v = f_1/(D+1)
and for Case 2
r'(v) = -2*f_2*(f_2 * v+1) which equals zero at the local maximum when v
= -1/f_2

Ok for now with a caveat. The plus or minuses are a tricky area here as
the +/- from the underlying equations:

x^2 - Dy^2 = 1

and

(D-1)j^2 + (j+/-1)^2 = (x+y)^2

where j = ((x+Dy) -/+1)/D

are OR, not AND because you will get the right answer in only one
direction, but it's not determined which from what I've seen, so it's
probably random!

That means though that it's not clear that you can remove the +/- that
propagates through the equations as easily as posters repeatedly seem to
wish, as DEEP within the derivation, it can plus or minus.

Actually no. There are 16 possibilities (four +/- pairs) which can be
reduced to 8 since each possibility has an exact negative match.
Expanding out this 8 is possible (I did all 16) but if you want a short
cut plug in some simple values. You will find that

r(v)*r(v)-t(v)*t(v)-D*s(v)*s(v) <> 0

except in cases 1 and 2 above. It is possible to find values that
sometimes match but investigating these shows them to be trivial (e.g. r
(v)=t(v) and s(v)=0).

I will say that I suspect case 2 should also be rejected. In this case s
(v) is linear instead of quadratic and does not appear to produce factors
in the way the algorithm requires. Thoughts?

Note that this is the flaw in Rick Decker's rebuttal. It only takes one
case (what I call case 2) ending up with the linear s(v) and assuming
that this is the only solution.

Here I can clear up a misunderstanding as that is not correct. It IS
correct if you wish to set s(v), as the issue came up about finding s
(v) = 1. If you wish to find s(v) EXACTLY for some particular value
then yes, you need coprimeness, but otherwise it is irrelevant.

Thank goodness! That actually makes it a lot easier. Of course sometimes
all the values are even, but that is easy enough to deal with.

I've made corrections as necessary and notice it's EASY, and you need to
understand two things:

1. It's not necessarily true that your choices of f_1 and f_2 will
work! You need to find the minimum and see if it's small enough.
2. The plus or minus issue may bite you.

You have to loop through EVERY combination of f_1 and f_2 that will
work, and you have to check the plus or minuses correctly.
Ah. That was not clear, although I suspected as much. I selected for an
example D=1111=11*101 as it generated a lot of (f_1,f_2) pairs. I could
have gone with D=1199=11*109 which, since 1198=2*599 and 599 is prime
only has four possibilities. Which do you think is the more honest
approach?

It is a job better done I'd think by a computer.
A lot of this is actually done in code, I just can't present it on a
newsgroup except as output.

James Harris

Regards, Michael W.

.

Quantcast