Re: JSH: Surrogate factoring, periodic behavior

On Aug 31, 12:47 pm, marcus_b <marcus_bruck...@xxxxxxxxx> wrote:
On Aug 31, 12:44 pm, marcus_b <marcus_bruck...@xxxxxxxxx> wrote:



On Aug 31, 11:09 am, JSH <jst...@xxxxxxxxx> wrote:

Having completed better analysis on surrogate factoring I found the
equations that explain a periodic behavior at least one person has
noted in posts, where for a given k and n, if you find a prime factor
p of your target T with that n, then you will find other solutions by
adding multiples of p to n.

Two of the equations determining that behavior are

Cw = n + (k + 2xr_1*p_1)( k + 2xr_2*p_2) - ((k + 2xr_1*p_1)( k +
2xr_2*p_2) - 2k^2)/T

and

w = k + 2xr_2*p_2 mod T

where if the second equation is true for a given n, then you will have
a solution to the surrogate factoring equations at that n, but that is
an only if. There C doesn't matter but is just some non-zero integer,
as w just needs to be any factor of the right side--which is an
integer I should note as the T must divide through--for which the
second condition is met.

That is the primary decision relation that determines if a surrogate
factorization can work or not.

Remember the surrogate factorization involves factoring a target
composite T by solving

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

where the primary question has been, how do you pick k and n?

If they are picked correctly then some solution for x and y will also
be a solution for

x^2 = y^2 mod p

where p is a prime factor of T.

James Harris

.

Here is how I understand your algorithm.

You want to factor integer T.

You choose k and n, and let

S = 2*k + n*T.

S is your 'surrogate'. Perhaps S is easier to factor than T. You
then hope that the factors of S lead to a nontrivial factorization of
T.

Specifically, suppose k = 1, and S = F1 * F2.

Let X = (F1 + F2 - 2)/2

Let Y = (F1 - F2)/2.

You hope that X^2 - Y^2 has factors in common with T.

Since X^2 - Y^2 = (X + Y) * (X - Y), you consider X + Y
and X - Y.

You note that

X + Y = F1 - 1 and

X - Y = F2 - 1.

So the question is: what are

g1 = GCD(F1 - 1, T) and

g2 = GCD(F2 - 1, T).

If 1 < g1 < T, you have a nontrivial factor. Similarly
for g2.

Of course it may happen that S factors in several different
ways. That is, there may be other choices for F1 and F2.
If your first choice for F1 and F2 don't work, you try the
others.

If none of those work, you increment n and compute a new
S and start over.

Is that the surrogate factoring process?


*** Different Example Here

Say T = 21. Let k = 1, n = 1. Then

S = 2*k + n*T = 2 + 21 = 23. This is prime, so increment n
by 1 and try again:

S = 2*k + 2*T = 2 + 42 = 44 = 4 * 11.

Thus let F1 = 11, F1 = 4.

X = (F1 + F2 - 2)/2 = (11 + 4 - 2)/2 = 13/2.

Y = (F1 - F2)/2 = 7/2.

Then X + Y = F1 - 1 = 10, and

X - Y = F2 - 1 = 3.

Thus g1 = GCD(F1 - 1, T) = GCD(10, 21) = 1 and

g2 = GCD(F2 - 1, T) = GCD(3, 21) = 3,

the latter of which leads to the factorization of T.

Again: is this the process?

So, the main question about this is, why do you expect it
to work? It is true that S is a function of T, so the factors
of S are dependent on T. But if F1 and F2 are the factors
of S, why do you have any reason to expect that F1 - 1 and
F2 - 1 might be factors of T?

This post was incomplete - more on this later -


The central question is still: why should this process
have a high probability of working? The rationale seems
lacking. This is unlike, say, the quadratic sieve process,
where a rationale is given. The lack of rationale accounts,
I think for two things: (1) why your method is not being
taken seriously by most people interested in factoring, and
(2) why so far it does not seem to work. You seem to be
hoping that either there is hidden magic in what you are
doing, or maybe you will just get lucky. It could happen.
But neither of these is a logical basis for an algorithm.

Marcus.

Marcus.


.