Re: JSH: Step by step through the factoring algorithm

On Feb 27, 10:00 pm, MichaelW <ms...@xxxxxxxxxx> wrote:
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

Yeah, the second case is what I already noticed. I hadn't noticed the
first, but I've just been doing it in my head for some reason.

Interesting. I wonder why the dependency on D+1. Seems kind of
odd...

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

Cool. Thanks for working through that.

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?

If it doesn't work, then ok. Here it's all very, very practical.
It's one reason I'm less enthralled with the factoring research as I
don't see it as being as elegant. It's just to prove a point.

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.

Yeah, I knew he had to be wrong, from the mathematical proof.

It's why people who value mathematics say that proof is more important
than example.

It's why I just ignored him.

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.

And again, mathematical proof meant I knew there had to be a reason
for why you had problems setting s(v) directly to 1 and got a non-
rational v. Sometimes mathematical proof can mean you know so much
without having to directly check things.

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's about what works. Mathematically the logic requires that you
have the combinations available.

Notice it's like an automatic transmission as in there isn't an exact
direct connect between factorizations of D and D-1, but a loose
connection.

To the math, it's not about factoring D, as the math doesn't care.

It's about a connection between factorizations of D and D-1. To the
math that's all that's happening.

We humans get to care about more though.

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.

Fine. Thanks a lot for the help! I knew a lot of things based on the
proof, but haven't been able to motivate myself to do anything else.

I still find the situation bizarre and very depressing but am curious
about what you have to say next.

For others, yes, it is possible to have a very simple and rational
discussion about mathematics.

IN fact, mathematics makes that easy.

It takes work to make a mess of things, and unfortunately, there are
people on the newsgroups who do that work.


James Harris
.