Re: JSH: SF Algorithm

On Tue, 11 Sep 2007 03:02:25 -0000, JSH <jstevh@xxxxxxxxx> wrote:

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)),
How do you know that this gives a value for x that satisfies your
first relation: x^2 = y^2 mod T? If x does not satisfy the first
relation, then all the rest of your theory is not relevant for this
value of x.

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.
I am puzzled by that "if". There are already methods that will fully
factor any integer - for instance trial factorisation. How can you be
unable to fully factor a given integer? TF may be slow, but it will
factor any number in time.


If you cannot factor all 32 with the given x, you can increment it by
1 and try again, indefinitely.
This is likely to make it difficult for you to calculate an expected
running time for your algorithm.


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.
So you have a bit more work to do to tidy up your theory then. Are
sure it was really ready for release now?


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.
In that case just drop the recursion. Use surrogate factoring on the
main number but use trial factorisation, or whatever, to factorise the
surrogates. As I said above, there are no unfactorisable integers.


I am not confident that I can work that problem out so what I said
earlier was bravado on my part.
It is a pity that you do not have more moments of self-insight like
this. Try to hold onto them and build on them.

rossum



James Harris

.