Re: JSH: SF Algorithm

On Sep 10, 10:02 pm, JSH <jst...@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)), so k =
2x, and then ranges for the n's from


You started off right, requiring, or desiring, that x^2 = y^2 mod
T.
But now you start with x = floor(sqrt(T)) and k = 2x, and you choose n
in a certain range. Here is how it works for, say, T = 77:

T = 77

x = floor(sqrt(77)) = 8

k = 2x = 16.

n_max = floor((24^2 - 2*16^2)/77) =
= floor(576 - 512)/77 = floor(64/77) = 0

n_min = floor((4*23 - 256)/77) = floor(-420/77) = -5.

So choose n = -1. Then from what you say above,

(x + k)^2 = y^2 + 2k^2 + nT, or

24^2 = y^2 + 512 - 77 = y^2 + 435, so

y^2 = 576 - 435 = 141

which is not the perfect square of an integer;
y = 11.874342...

[Note here, incidentally, that the computation of y can
be carried out without any factoring of the surrogate.]

You wanted INTEGERS x and y such that x^2 = y^2 mod T;
if your algorithm had a high probability of achieving this,
it would very likely be competitive with others. But
you have provided no rationale for having a high probability
that

(x + k)^2 - 2k^2 - nT

will be a perfect square of an integer, and clearly in general
it is not.

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.


See above. You have included no justification for the key
ingredient: that your algorithm has a high probability of
finding an integer value for y.


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.


That should be a manageable technical problem. The more important
problem occurs as described above.

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


Really! Well, that has happened a few times before ...

Marcus.

James Harris


.

Relevant Pages

  • 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: looking for a lexical scanner (lexer)
    ... And the algorithm becomes way more interesting when one would consider ... surrogates, variation selectors, combining characters, etc. :-) ...
    (microsoft.public.vc.mfc)
Loading