Re: JSH: SF: Simpler factoring idea, but does it work?

[added "JSH:" to subject, spared sci.crypt and alt.math]

[jstevh@xxxxxxx, comes out of retirement in less than a day :-)]
After yet another failure with what I call surrogate factoring, where
this time I had been doing some basic algebra wrong, I sat down to
think about it all for a while, and considered that I was quite
reasonably just going in circles, using equations to try and factor
that could only give one answer.

So I started thinking about equations that could give two.

It didn't take long till I was concentrating on:

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

Here the square roots mean that expression can't just factor S, which
is what I call the surrogate, as something else is being factored as
well, but how do I get that something else to be a target composite?

After I posted that equation and started talking about it, a Tim Peters
worked out details following my instructions, but unfortunately, he is
a dedicated, um, "crank" buster you might call it, who spends his time
trying to shoot down my ideas, so when he worked out the equations, and
got to something useable, he promptly began throwing up distracting
posts meant to show it was useless.

Including a rigorous proof that it was in fact 100% useless -- although some
variations could be salvaged, and those appeared to be equivalent to the
random-gcd algorithm.

However, oddly enough, his results can be used quite simply, where the
first thing is to use some of his equations, to introduce a target
composite, which I call T.

You posted the same stuff yesterday; see my reply yesterday.

You introduce T using

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

Multiply both sides by

k_1*k_4 - k_2*k_3

to get

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

and just subtract the left from the right to get

0 = (T-1)* k_1*k_4 - (T+1)*k_2*k_3

So

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

And you have

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

so k_1 and k_4 are integer factors of T+1, and k_2 and k_3 are integer
factors of T-1.

Easy. Just like that you're most of the way to using the equations.

That gives a finite set of possibles for the k's.

For instance, with

So, for instance if T=15, you have

(k_1*k_4)/(k_2*k_3) = 16/14 = 8/7

so k_1*k_4 = 8, and k_2*k_3 = 7

and one possible setup then is

k_1 = 2, k_4 = 4, k_2 = 7, k_3 = 1

so plug those into

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

and you need S, and can use any square you like, so it's easiest just
to use

x=y=1, and take the positive result of the square roots to get

S = (2 + 7)(1 + 4) = 45

which promptly factors it, but I'll continue, as that's just one
possibility, so you have to check for it.

Are you unable to find an example that shows something interesting?

Let's try a small but not utterly trivial one off the top of my head, T =
143 = 11*13. Pick, say,

T+1 = 144 = 36 * 4 = k1*k4
T-1 = 142 = 2 * 71 = k2*k3

and pick x=y=1. Then S = (36 + 2)*(4 + 71) = something irrelevant, and

gcd(-36+2, T) = gcd(36-2, T) = gcd(-4+71, T) = gcd(4-71, T) = 1

That's the usual outcome in a non-utterly-trivial example. As below, you
_can_ always find choices that work, but if you don't know T's factorization
before you begin you have no way to find choices that are _likely_ to work.

If S were coprime to T, then you now use factors of S, where with

S = g_1*g_2

you have

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

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

and you just find find squares for x and y that will work to give you
g_1 and g_2, and here's where that second solution from the square
roots comes in, as with each set of squares for x and y that will work,
you just change the sign of one of the square roots, to get the shadow
factorization.

That's it. Remarkably simple, as you go for the hidden factorization.

It is indeed simple ;-)

For instance, still using x=y=1, with my simple example, now take the
negative of ONE of the square roots:

S = (2 - 7)(1 + 4) = 55

I guess T=15 is too dinky of an example as it just keeps factoring it,
no matter what you do, but at least that still shows the basic idea
here.

To recap, I looked at an expression

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

that can't just be the factorization of a single number because of the
use of square roots.

That claim doesn't make sense, but I'm not going to challenge it because it
doesn't change that this method doesn't work well. I'll only note that if
you could understand _why_ that claim doesn't make sense, you'd be close to
understanding why this method has no legs to stand on.

I posted about it and a Tim Peters worked through some analysis
following instructions I gave, which gives up the simple equation

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

which can be solved to get

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

so you can find the k's based on the factors of T+1 and T-1, to plug
back into the original equations and get an S, and then you use the
factors of S to find squares that are solutions for x and y, and then
you do the remarkable trick of just switching signs one at a time to
get to the hidden factorization.

But does it work beyond toy examples like factoring 15?

Provided k_1 and k_2 are coprime (if they're not, you can divide both by
their gcd to make them coprime), and T is composite, there are an infinite
number of <x, y> pairs for which:

1 < gcd(k_1 * -sqrt(x) - k_2 * sqrt(y), T) < T

That statement is true regardless of how k_1, k_2, x and y are chosen (i.e.,
this much has nothing to do with the specific equations you're using).
Alas, there's no reason to hope that "your way" of picking them is better
than picking them at random.

Unfortunately, as I said, Tim Peters is a hostile when it comes to my
research, so he promptly busied himself trying to obscure use of the
equations, while claiming that they don't work.

It was you who suggested using a derived difference of squares, and for the
specific way you suggested it was straightforward to prove that a
non-trivial factor could _never_ be found. I (and Rick Decker) found
variations for you that worked better than your idea, but nobody (including
you) found a variation of the differences-of-squares idea of any real use.

You can look at recent threads I've created on sci.crypt and sci.math
to see him at work.

Of course I usually cut sci.crypt from repiles.

Some of you might be shocked by such behavior, as, hey, it's the
factoring problem.

If proof shocks you, you should take up a different hobby.

But consider for YEARS Peters and people like him have been shadowing
my posts working to convince people that my research is useless.

Your factoring methods to date _have_ been useless. Why shoot the
messenger? Or do you believe you've thrown away dozens of useful factoring
methods to get to this one? LOL.

The results would be the same if you did the algebra (provided you did it
correctly). Blaming me for that your methods haven't worked makes you look
like a crank.

I assure you that he has worked in this way many times.

He is only doing what he has always been doing, so there is nothing new
in his behavior.

Nor yours. You make wild claims, I investigate some of them, and then you
make a fool of yourself whining, moaning, bitching, threatening and
slandering because you don't like the results. From a day to a year later,
so far you've always been forced to agree that each method in fact didn't
work well. I don't often object to your bad behavior because making a fool
of yourself doesn't actually injure me. I don't know why you _want_ to do
that to yourself, and sincerely suggest you'd be happier if you didn't, but
in the end your reputation and honor are yours to throw away.

So the question is an open one. Does this method work?

AFAICT, it works exactly as well as random-gcd, but is more complicated. If
I'm wrong about that, it will be possible for you to demonstrate it.

I can assure you that the math society that has busied itself ignoring
my research for years

Actually, taking the time to prove results about your claims is nothing at
all like ignoring them. You're just crabby because your factoring claims
_so far_ have been shot down. Sorry, but this one isn't going to fare
better. If that pisses you off, find a better method. Trying to blame
others for the failure of the methods is crackpot behavior.

is in no hurry to acknowledge a result of mine like this one--if it
does work--as then they would be completely overturned, now wouldn't
they?

And what is your security against theirs?

So they wait, seeing if the "crackpot" label will hold, and they wait,
to see if no one can tell if these ideas will work or not, and if they
do work, they wait until there is a disaster big enough for the world
to care about the truth.

And then, finally, they will be able to wait, no more.


James Harris

From all evidence, I pay more _serious_ attention to your methods than you
do. In fact, that's why I discover whether they work long before you do.
This method is no exception.


.

Relevant Pages

  • Integer factorization, basics
    ... The factoring problem concerns itself with finding non-trivial values ... square that adds to 4M to get a square, then you have a value of 'b' ... and you may choose to do so now, for whatever reasons are motivating ...
    (sci.math)
  • Re: Integer factorization, basics
    ... > The factoring problem concerns itself with finding non-trivial values ... > So the congruence of squares method works by having the square root ... > Being large primes, they are rare. ...
    (sci.math)
  • Surrogate factoring, objective look
    ... I have found a factorization method which I claim is new and important. ... Congruence of square relies on a simple idea to factor numbers using ... What I did was concentrate on two quadratics instead of one, ... That is how you can see that what I call surrogate factoring is a new ...
    (sci.crypt)
  • Re: Factoring large composite numbers
    ... Now let y = the smallest factor greater than x, where y - x is a square ... It is the first step for more advanced factoring algorithms, ... By itself, it is too inefficient. ...
    (sci.crypt)
  • Re: The factoring problem
    ... > multiplication is an algorithm invented by man. ... All known solutions for factoring ... square roots modulo pq. ... If you gave me the square roots of "x" modulo pq I could trivially ...
    (sci.crypt)