JSH: SF Algorithm

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?

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.

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

.

Relevant Pages

  • JSH: Surrogate Factoring Paper Accepted!
    ... enough bravado on my part as I'm not certain this will work ... The Bulletin of the AMS ... which with my program has meant roughly 32 surrogates to factor. ... have the target in hand. ...
    (sci.math)
  • Re: JSH: SF Algorithm
    ... Bulletin of the AMS ... Why would they change their minds ... which with my program has meant roughly 32 surrogates ... have the target in hand. ...
    (sci.math)
  • Re: JSH: SF Algorithm
    ... you have provided no rationale for having a high probability ... have the target in hand. ... of the surrogates get factored, ... That should be a manageable technical problem. ...
    (sci.math)
  • Re: JSH: Surrogate Factoring Paper Accepted!
    ... which with my program has meant roughly 32 surrogates to factor. ... have the target in hand. ... State the case (in spite of the rejection) for the paper's value ... to the mathematical community. ...
    (sci.math)
  • Re: JSH: SF Algorithm
    ... Why would they change their minds between now and then? ... The expert opinion is noted. ... which with my program has meant roughly 32 surrogates to factor. ... have the target in hand. ...
    (sci.math)