Re: JSH: Surrogate factoring, periodic behavior

JSH wrote:
On Aug 31, 3:14 pm, marcus_b <marcus_bruck...@xxxxxxxxx> wrote:
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:


<deleted>

Why? Who cares if the surrogate is prime? It might still factor.

Even trivial factorizations of the surrogate may work.

The central question is still: why should this process
have a high probability of working? The rationale seems
<deleted>

Yes, questions, the mark of true researchers and human beings in
general, as human curiosity is such a wonderful thing.

We wonder why and in looking for answers humanity finds new things.

So yeah, like I mentioned in another thread, the question in my mind
for some time has been how so many of you seem to lack basic human
curiosity.

Does the idea work at all? If not, why not? If so, how?

Learning begins with questions.

Now I have worked for years at answering questions presented by an
idea, which was, could you factor one number with another, and I kept
at it despite derision and insults from people like you.

You are the jocks of the schoolyard who tease that strange little boy
who is so fascinated with his books.

Whether you wanted to be or not, or thought you hated those people
growing up, that is your behavior against me and always has been.
Maybe you hated them growing up because you wanted to BE them, and
given the slightest excuse they are who you became.

You are the cruel jocks picking on the kid you call nothing.

And I am the genius.

So, how does 4773695331839566234818968439734627784374274207965089 factor?

David Bernier

.

Relevant Pages

  • Reality check, surrogate factoring
    ... Surrogate factoring is meant to beat the tactic of picking two hard ... and it will be really big for a big target. ... of the time for rationals x's. ...
    (sci.math)
  • Reality check, surrogate factoring
    ... Surrogate factoring is meant to beat the tactic of picking two hard ... and it will be really big for a big target. ... of the time for rationals x's. ...
    (sci.crypt)
  • Re: surrogate factoring
    ... "surrogate factoring" doesn't really mean anything specific. ... distinct (maybe odd) primes, and you want to find p and/or q. ...
    (sci.math)
  • Re: Surrogate factoring, update on research
    ... >numbers by instead factoring some surrogate number. ... >but didn't factor the target. ... That's an amazing breakthrough. ...
    (sci.crypt)
  • Re: Surrogate factoring, update on research
    ... >numbers by instead factoring some surrogate number. ... >but didn't factor the target. ... That's an amazing breakthrough. ...
    (sci.math)