Tuesday, November 18, 2008


JSH: Settled factoring research, what now?

I ended up bringing factoring back up after I brought up solving for quadratic residues mod N, and yesterday recognized that I'm just tired of this area, and am ready to move on. But as one last parting shot I decided today to give what is my settled factoring research, which is what I derived the method for solving quadratic residues from, and the surprise is that it is mostly straightforward.

Simply enough I worked out that given non-zero integers, z, y and nT, where

z^2 = y^2 + nT

it must be true that

z = (1 + 2a^2)k/(2a)

where k and 'a' are to be determined.

That solution for z is not trivial because it can be shown that

k^2 = (1 + a^2)^{-1}(nT) mod p

for some odd prime p, where p is what I call a helper prime as it is only there for these results! And I ran into trouble trying to define rules for what p's will work where posters kept finding counterexamples to what I thought were the rules.

It's not a minor issue either as, it can be shown that, if f_1*f_2 = nT, then

f_1 = ak mod p


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

so if p is large enough then you have a factorization!!!

ALL issues with the research boiled down then on whether or not you can get a large enough p. To be a very useful technique the method should allow you to use a VERY large p, so that you can easily get f_1 and f_2.

But before I get back to that issue or try to resolve it, there are more equations as it can be shown that with all positive integers, so all the variables are positive integers, the MINIMUM k, which I call k_0 can be found by finding k_0 such that

abs(nT - (1 + a^2)k_0^2)

is a minimum.

And the k that will work to give you z, must be within floor(k_0/(2p)) steps, so clearly you'd want a p large enough so that you'd have the least number of steps! Where 0 steps is the best.

So again, everything with this approach comes down to picking a large helper prime p, and if you can do so, then the theory says you can very quickly factor, but there are problems with picking a very large prime p and they go back to

f_1 = ak mod p

as if f_1 is less than p, because it's so HUGE, and ak is less than p, then f_1 = ak, so that is an explicit equation, which forces k into f_1, which forces k into nT, and means that with

z^2 = y^2 + nT

k is a factor of all, as it is then a factor of z, y and nT, as remember from before:

z = (1 + 2a^2)k/(2a)

so that is the crucial equation and I fumbled around with various rules that were meant to force p to be LESS than f_1, when the actual requirement is clearly seen to be that ak must be less than p, if f_1 is less than p, if not then it doesn't matter.

So p CAN be very large, as long as you do things carefully without the rules I thought were necessary before.

And that is what I realized yesterday, so I updated things and thought to myself I'm sick of this factoring research so I so posted.

But a couple of hours ago, I realized something that worried me enough to put it out there and see if it's not a big deal, as if the issue is getting an ak bigger than p, why not just pick 'a' and k?

The equations do not say you cannot.

So, you pick a large k near the sqrt(T), and then pick a large prime p BIGGER than k, but next you pick an 'a' such that ak is GREATER than p.

Then you go to

k^2 = (1 + a^2)^{-1}(nT) mod p

and REVERSE it to solve for n, which gives

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

and now you just solve for z using

z = (1 + 2a^2)k/(2a),

and solve for y using y = sqrt(z^2 - nT), and you have a factorization from

(z-y)(z+y) = nT.

So you have this straightforward easy approach, but I seem to remember coming up with something like this months ago and I'm sure it was shot down by replies from posters.

One immediate issue of course is that the factorization you get may not factor T itself!!!

Also I wonder if I'm right that you solve for z, as maybe you still have to search for k, but part of the point of this approach is that floor(k_0/(2p)) = 0, but if n is HUGE then maybe k_0 is still much bigger than p, and you need a lot of steps, which could be the problem then.

So it's up in the air. But I've covered the settled research with this approach and also tossed in one unsettled piece at the end.

I know, annoying, since I said I was done. But I wish I had everything tied down so that I was sure. And posting is a way to get feedback and critiques.

And it IS kind of remarkable to me at least that you can just solve for z given

z^2 = y^2 + nT

in this way, with such wacky variables as 'a' and k, where I haven't even fully delved into their wackiness as they can be non-rational and STILL help you factor rationals, but the vote is from the mathematical community.

And I discovered what I call the z constraint more than half a year ago, so it seems that community has voted against this research as interesting, which leaves me chattering about it as an afterthought before moving on.

<< Home

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