Re: JSH: Finally useful theory?

[spared sci.crypt]

[jstevh@xxxxxxx]
Peters used math software,

True.

following my instructions,

False. I couldn't make sense of what you wrote, and _guessed_ at what you
actually wanted, based on aping the same steps you always take. You later
confirmed those were the steps you intended, although only God knows whether
that's right.

to solve out

S = (k_1*sqrt(x) + k_2*sqrt(y))*(k_3*sqrt(x) + k_4*sqrt(y))

but only posted it to sci.math--

True. Just like I cut sci.crypt from this reply.

his regular area where readers hate me and are rather gullible in
their trust of posters who disagree with me.

True or false, that's not why I cut sci.crypt: most speculation is
off-topic there, and all of the active sci.crypt regulars have made it
abundantly clear that your particular brand of hysterical speculation is
unwelcome there. I respect their wishes in this matter; you don't; that's
all there is to this one.

If/when you find an efficient factoring method and produce an interesting
integer factorization using it, I'll certainly leave sci.crypt on replies.
Likewise even if you present a factoring approach that just looks promising
to me.

I want to focus attention on the key piece at the end...

Which I'm going to replace with the clearer results posted a day later. To
eliminate transcription errors, I'm pasting these directly from a Macsyma
window; as a consequence, all symbols are lower case (Macsyma folds case),
and there are sometimes "extra" parentheses around k_i instances:

Start with:

s = (k_1*sqrt(x) + k_2*sqrt(y)) * (k_3*sqrt(x) + k_4*sqrt(y))

From that derive:

c^2 = (b + a*d)*(b - a*d)

where

a = (k_1)^2*(k_4)^2*y + (k_2)^2*(k_3)^2*y - 2*(k_1)^2*(k_3)^2*x +
2*k_1*k_3*s

b = (k_1*k_4 + k_2*k_3) * ((k_1*k_4 - k_2*k_3)^2*y + 2*k_1*k_3*s)

c = 2*k_1*k_3*(k_1*k_4 + k_2*k_3)*s

d = k_1*k_4 - k_2*k_3

Note that "a" can be partially factored as

a = ((k_1)^2*(k_4)^2 + (k_2)^2*(k_3)^2)*y - 2*k_1*k_3*(k_1*k_3*x - s)

if anyone thinks that's interesting ;-)

Then, as Rick Decker first posted (although this differs slightly from what
he posted, due to what I expect were minor transcription errors), the
following highly revealing expressions can be derived for b+a*d and b-a*d.
James, try to stop ranting long enough to pay attention to this part.
You've shown some signs of having seen at least one of the messages in which
this was posted before, but you're entirely missing the implications, and to
borrow a phrase from you, the implications are HUGE:

b + a*d = 2 *
(k_1)^2 *
(k_1*k_4 + k_2*k_3) *
(k_4*sqrt(y) + k_3*sqrt(x))^2 [1]

and

b - a*d = 2 *
(k_3)^2 *
(k_1*k_4 + k_2*k_3) *
(k_2*sqrt(y) + k_1*sqrt(x))^2 [2]

From that expression, assuming Peters did his work correctly, it's
clear that you can use

(k_1*k_4 + k_2*k_3) / (k_1*k_4 - k_2*k_3) = T

You can, but as I already explained in detail yesterday (but which you
showed no signs of reading), if you do then from [1] and [2] it necessarily
follows that:

gcd([1], T) = gcd([2], T) = T

That's because T is an integer, using your expression above k_1*k_4 +
k_2*k_3 is an integer multiple of T, and k_1*k_4 + k_2*k_3 is in turn a
factor of both [1] and [2]. Why? Just look at them. k_1*k_4 + k_2*k_3 is
the third factor in both.

To introduce your target composite to be factored, and solve out for
the k's where it's also clear that to be integers the k's are factors
of T+1 or T-1.

Maybe you want to manipulate the expressions above in some way to help you
with that. Go ahead, but be explicit, else you're going to remain lost
here. For example, it may be that you want to spell:

c^2 = (b + a*d)*(b - a*d) [3]

as:

(c/d)^2 = (b/d + a)*(b/d - a) [4]

instead. That's fine. I expect that most people actually paying attention
can "just see" the effects that would have on [1] and [2], and just as
easily see the implications. If you can't, I'll spell it out: they're
exactly the same, except that both grow an obfuscating denominator of
k_1*k_4 - k_2*k_3. The reason this will be obvious to most people is that
[4] is derived from [3] merely by dividing each RHS factor by d. It's still
the case that your favorite expression for T:

(k_1*k_4 + k_2*k_3) / (k_1*k_4 - k_2*k_3) = T

is a factor of both, so it's still the case that you _can't_ find a
non-trivial factor this way. The gcd will always be T. If you don't
believe me, before screaming "liar, liar" do yourself a favor and try it
with some _specific_ integers. You'll see for yourself that the gcd is
always T, regardless of which RHS factor in [4] you try, and regardless of
what you pick for k_1, k_2, k_3, k_4, s, x or y.

So just that one thing of using square roots to give an ambiguous
factorization allows you to create an expression that gives what NFS
works so hard to find, as using

S = (k_1*sqrt(x) + k_2*sqrt(y))*(k_3*sqrt(x) + k_4*sqrt(y))

you pick the surrogate S, so if

S = g_1 * g_2, then


k_1*sqrt(x) + k_2*sqrt(y) = g_1

k_3*sqrt(x) + k_4*sqrt(y) = g_2


which means that if you have the k's you can easily get squares x and
y, by picking the g's,

That's an absurdly strained way to approach this part. This is the easy and
obvious way: pick any x and y whatsoever that are squares of integers (pick
0, 1, 4, 9, 16, ..., any two you like). Then g_1, g_2, and S are
determined, and must also be integers. It's _not_ true that you can pick
any g_1 and g_2 you like (for some choices, there is no solution of the
required form). It is true you can pick any square x and y you like.

and then you have a solution to equations that can be expressed as

a(x,y)^2 = b(y)^2 - (2*k_1*k_3*T*S)^2

meaning you have a solution to a difference of squares, handed to you,
on a platter.

And, as above, and as was first shown days ago, when respelling the
difference of squares as (U+V)*(U-V), the factors of U+V and U-V are _so_
strongly related to the factors of T that, using _your_ expression for T, T
divides U+V and T divides U-V. 100% useless.

This is a mistake you make in virtually all of your factoring attempts, the
blind false belief that finding a difference of squares _must_ reveal
non-trivial factors. This method is an extreme case in that you've managed
to find expressions that can _never_ reveal a non-trivial factor.

Note that using Rick's c^2=(t*s)^2, or my later c^2=(2*t*s)^2, instead
_sometimes_ leads to non-trivial factors, because those don't systematically
leave t dividing both U+V and U-V as your way does. See earlier posts for
why those choices appear to be useless in practice anyway.

The result then indicates a surprising relationship between factors of
T, T+1, and T-1.

I've puzzled about that wondering if there were some way to put in T+k,
where k is some arbitrary integer, and don't seee it, so it may just be
one of those remarkable fundamental properties of numbers, unique.

Just a little oddity in the world of numbers that has implications for
the factoring problem.


James harris

The real reason this method got "blocked" is that the "only k_i and S"
expression turned out to be a perfect square. That in turn forced T^2 to be
a factor of the difference of squares, and that in turn _allowed_ T to be a
factor of both U+V and U-V. Your way of picking T _forces_ T to be a factor
of both. You _can_ use this method with my c^2=(2*T*S)^2 choice to factor
any composite T, but as explained earlier I don't see any way to do that
short of either being very lucky, or knowing T's factorization before you
start (if T=p*q, in "my way" you can pick k_1=p and k_3=q, after which point
you'd have to be _unlucky_ to get trivial factors back from the final gcds:
again, just look at the expressions for [1] and [2] to see why that's
_probably_ true; proving it requires more work).


.

Relevant Pages

  • Surrogate factoring, correcting sign problems
    ... really don't like an answer for some reason. ... That is, you can find integer Ax from the relation for Az, by factoring ... I talked about algorithms that just checked Ax to see if it has ... It turns out that you can use the Ax to do the difference of squares or ...
    (sci.crypt)
  • Difference of squares, SF
    ... Using a difference of squares you can sometimes factor a target ... After months of discussing surrogate factoring I've yet to hear anyone ... problem so there must be a reason that you wouldn't factor M. ...
    (sci.crypt)
  • Re: Difference of squares ,SF Theorem
    ... > of squares. ... > Surrogate Factoring Theorem: ... mathematics" and explain why each only gives trivial factors. ... ] But they DO disagree and they disagree quite boldly. ...
    (sci.crypt)
  • Re: Difference of squares ,SF Theorem
    ... > difference of squares, potentially non-trivial, like the SF Theorem ... In fact, factoring T j^2 as ... and the mathematics just does not show any preference for ... The chance that n is divisible by both p and q is 1/. ...
    (sci.crypt)
  • Re: JSH: SF Algorithm
    ... I've just discovered that the following calculations showing n being ... T/(Second GCD) 9524208139 ... With p a divisor of T, the form of a divisor of S that is needed has ... a "high" probability of successfully factoring T. It is not ...
    (sci.math)
Loading