Re: SF Algorithm


"JSH" <jstevh@xxxxxxxxx> wrote in message
news:1189479745.082710.3370@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
Oh well, enough bravado on my part as I'm not certain this will work
and waiting for Wednesday just seems silly. The Bulletin of the AMS
did reject. Why would they change their minds between now and then?

They would easily spot if you were close and offer ideas to you to fix it.
Since they did not, you are miles off course in the dark woods and fell down
a deep hole with 3 feet of muddy water in the bottom, as a herd of camels
come over to the hole to deposit their weekly ***, which averages an
additional 9 feet of camel *** on top of you, then the sand, and pine
needles, fall into the hole. How do you factor you will get out ? if ever?
You could eat your way out. Then people will say JSH you are full of camel
***, which ain't no lie.



The expert opinion is noted. Here is what my research says, which
presumably then will not work, but I do not know why it would not.

Given a target composite T, from theory using x^2 = y^2 mod T and k =
2x mod T, it can be proven that

(x+k)^2 = y^2 + 2k^2 mod T

must be true for any solution of a difference of squares.

Explicitly to solve you need solutions for

(x+k)^2 = y^2 + 2k^2 + nT.

The algorithm picks x directly, choosing x = floor(sqrt(T)), so k =
2x, and then ranges for the n's from

n_max = floor(((x+k)^2 - 2k^2)/T)

and

n_min = floor((4(x+k-1) - 2k^2)/T)

which with my program has meant roughly 32 surrogates to factor.

By the theory, if you can fully factor all 32 surrogates for any
target T, then you will non-trivially factor T.

If you cannot factor all 32 with the given x, you can increment it by
1 and try again, indefinitely.

Note that you can also use x = floor(sqrt(2T)) to have about 64
surrogates and much greater odds but I'm not clear how that works
exactly and besides if you can factor 32 with the first one then you
have the target in hand.

It is so weirdly simple and I think the theory is correct, but I guess
I could be wrong.

it's wrong.


I have tried to implement with my own programs but as I pointed out in
a previous post, I use recursion and with big numbers fewer and fewer
of the surrogates get factored, so it craps out.

I am not confident that I can work that problem out so what I said
earlier was bravado on my part.


James Harris


A good learning lesson for you.


.

Quantcast