Saturday, February 23, 2008


JSH: Test factorization

I've modified one of my existing programs to start testing out the latest surrogate factoring research though I haven't yet optimized it, so it kind of dumbly just looks for solutions around k approximately equal sqrt(nT/2) where n=1 if T mod 3 = 2, and n=5, if T mod 3 = 1.

Here's an example factorization:

T = 1342517983, k = 58480. surrogate = 127230885, which factors as


and T factors as (27893)(48131). The prime factors of the surrogate are of interest here and since T mod 3 = 1, the program multiplies it by 5, so

k^2 = 2^{-1}(5T) mod p

where you can check it for each prime. I haven't bothered to check.

Because the program is dumb, it took 183 checks of k's looping up from k approximately equals sqrt(5T/2), skipping over odd k's or k's divisible by 3.

Notice that k/2p approximately equals 14 using the largest prime, so you'd have a roughly a 1/14 chance of finding a solution, if you did it the smarter way, but that gave a good enough chance that even the dumb way stumbled across the factors.

It's not a complicated idea here, which is why it's amazing to me there are still people trying to argue over some rather basic algebra.

It just so happens that if you let k = 2x, and z = x+k, when

z^2 = y^2 + nT

then the maximum k that will give the minimum value for abs(nT - 2k^2) will tend to be close to the correct k, which must exist if z is divisible by 3 because

z = x + k = x + 2x = 3x.

Figuring that out just requires using

2x = k + pr

where p is some prime and r is an integer, and the substituting out z, with z = x+k, to get

if you substitute out z and simplify a bit you have

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

so you can substitute out 2x, and get

x^2 = y^2 + nT - 2k^2 - kpr

and now let k_0 be the value for which r=0, so you can let

k = k_0 + 2pj

where j is an integer and substitute, and you have

x^2 = y^2 + nT - 2(k_0^2 + 4pjk_0 + 4p^2j^2) - (k_0 + 2pj)pr

and x, y, nT, k_0 and p are all constant, so as j varies, the j^2 term will dominate and the r variable will tend to be negative to counterbalance it.

If you need it all multiplied out to help you with this basic point:

x^2 = y^2 + nT - 2k_0^2 - 8pjk_0 - 8p^2j^2 - (k_0 + 2pj)pr

where with k_0 positive (as why have it negative?), you'll notice that while

k_0 <2pj

the negativity of 8p^2j^2 can't be overridden by -8pjk_0 no matter what the sign of j, but y^2 + nT - 2k_0^2 is constant as is x^2, so r must be negative to compensate until k_0 = 2pj, which is when k=0 anyway.

So it's trivial mathematics that k_0 will tend to be near the correct answer for k, when it is the maximum value such that abs(nT - 2k^2) is a minimum.

That amazing bit of mathematics puts the factoring problem within reach, just like that just because the j^2 is always positive.

Trivial algebra gives you the range as k should be equal to or greater than k_0, and j should be negative and greater than -k/2p.

Figuring out that k^2 = 2^{-1}(nT) mod p, is a little more complicated but if you were paying attention when I was babbling on about factors mod p, I explained it exhaustively and ad nauseum.

So, oddly enough, to tackle a composite T, you just need to get a a prime for which k exists that makes it very likely that you will find k quickly.

And it's all trivial algebra.

Now if you people wish to argue on still and wait until I or someone else is motivated to fully implement the trivial algebra, then fine. But don't come crying later when I say you people don't really know math, as then you clearly don't.

Easy algebra ignored when it's the factoring problem does not make you brilliant.

It does still annoy me and I still wonder how I let some of you bother me, that you can pretend to give a damn about mathematics and come out with sophistry to attack a beautiful and simple argument, proving how much you hate math, but having the gall to keep at it as if you can just fool people one more day, that's all that matters.

I think some of you every day you post arguing with me just tell yourself, to just try to get people to believe wrong things mathematically one more day, and you win, as you make humanity as a whole lose. One more day yesterday you people won.

Did you win today? Is humanity still being fooled by you?

[A reply to someone who asked which constraint should one use to pick k when programming.]

Oh please. Like what you do matters.

If this result is correct then someone in the world will pick it up.

Your input is irrelevant as is the input of everyone else on these groups.

I'm mostly just talking to myself anyway.

When the real storm hits, your voice will disappear as nothing you will say at that point will make any difference at all.

I'm kind of just appreciating the calm before the storm, before the world knows fully who I am, and that I am the next great discoverer, of a long line of discoverers.

That I am the next legend—living, breathing and solving mega problems in the here and now.

Not just some person to be read about, but someone that can be asked important questions, which is what I truly dread. When people get smart enough to ask me the real questions.

<< Home

This page is powered by Blogger. Isn't yours?