Monday, June 09, 2008


JSH: Wow, cool factoring relations

There are times that I just wonder why I'm the only person who seems to really get it that it is just so incredible to try and figure these things out and it's not just about some people supposedly being the only ones with the training or whatever. Like check these out:

With a target composite T, I find 'a' by the use of k, where

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

with p an odd prime, and c is a natural number of arbitrary size.

Then, incredibly, I have that with factors f_1 and f_2, where f_1*f_2 = T:

f_1 = ak mod p^c


f_2 = a^{-1}(1 + a^2)k mod p^c.

One of the reasons they work is that

a^2 = f_1(f_2 - f_1)^{-1} mod p^c

and in fact, no matter what, if you get an 'a' for a k, then you have a factorization of T, but you can get non-rational ones, which is where I can end up in arguments with people who'd still like to call the relations useless.

But there is so much simple beauty in them, how (T - k^2) has to be a quadratic residue. How 'a' is related to the factors through a prime.

Knowledge unknown to the world before now though it's not new. It's always been there.

<< Home

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