Wednesday, May 10, 2006
Factoring idea, trying to recover something
I may as well admit that I was really excited about a fairly trivial quadratic residue result, and it just bugs me that I was so certain it was a big deal, when it turned out to be so trivial, so I find myself trying to rescue something from the idea.
Earlier I noted a way to use quadratic residues to find m as a congruence relationship to factor with
sqrt(1 + 8*mT)
where the idea of looking mod some particular n, goes back to Fermat and later Gauss, which shows you how old this way of looking at things is. Sigh. But I find myself working at it anyway, maybe because I'm just looking for something to mull over, no matter how trivial and old it might be.
Since m = (r-1)*(8*T)^{-1} mod n, where n is an odd natural of your choosing coprime to T—the target to be factored—and r is some quadratic residue of n, where I was just picking r=4.
So you can let
c = (r-1)*(8*T)^{-1) mod n
to have explicitly
m = kn + c
where k is to be determined.
But, it must be true that sqrt(1+8*mT) for a solution is a natural equal to k plus some number, which I will call x, so I have
(k+x)^2 = 1 + 8(kn + c)T
and expanding and collecting to the left side I have
k^2 + 2kx + x^2 - 1 - 8nkT - 8cT = 0
and collecting with respect to the k's I have
k^2 + 2(x-4nT)k + x^2 - 1 - 8cT = 0
and completing the square gives
k^2 + 2(x-4nT)k + (x-4nT)^2 + x^2 - 1 - 8cT - (x-rnT)^2= 0
so
(k + x-4nT)^2 + x^2 - 1 - 8cT - x^2 + 2xnT - n^2 T^2 = 0
and simplifying further and collecting everything outside the square to the right side gives
(k + x-4nT)^2 = 1 + 8cT + n^2 T^2 - 2nTx
which is a lot like what I started with, except if x is positive (it could be negative so it's not necessarily a natural) then you're going down mod 2nT, and with n odd and T odd, it looks like x must be divisible by 4, so you're actually searching mod 8nT.
Besides that, I got nothing. I admit, I did it again. Wandered off into some old area and managed to re-discover what was already known.
But it was fun for a while.
Here's something maybe. That c in there is defined as
c = (r-1)*(8*T)^{-1) mod n
so you can make it as negative as you want by subtracting n.
What if you went for a positive minimum? Subtracting such that
1 + 8cT + n^2 T^2 > 0
was the smallest possible? It looks like that would increase k, and shrink x, if x were positive, and it might shrink the search space.
The logic of it is so damn simple it's almost beyond belief, but what I've given in this thread is the simple solution to the factoring problem.
I will make another post explaing it in boring detail.
The gist of it though is that for a solution to m, there must exist a natural number k, but also you can do this weird thing of decrementing x, while incrementing k, without changing m, so that you can find a simple answer.
What's remarkable is that in my post I solved the factoring problem, and did anyone notice?
Earlier I noted a way to use quadratic residues to find m as a congruence relationship to factor with
sqrt(1 + 8*mT)
where the idea of looking mod some particular n, goes back to Fermat and later Gauss, which shows you how old this way of looking at things is. Sigh. But I find myself working at it anyway, maybe because I'm just looking for something to mull over, no matter how trivial and old it might be.
Since m = (r-1)*(8*T)^{-1} mod n, where n is an odd natural of your choosing coprime to T—the target to be factored—and r is some quadratic residue of n, where I was just picking r=4.
So you can let
c = (r-1)*(8*T)^{-1) mod n
to have explicitly
m = kn + c
where k is to be determined.
But, it must be true that sqrt(1+8*mT) for a solution is a natural equal to k plus some number, which I will call x, so I have
(k+x)^2 = 1 + 8(kn + c)T
and expanding and collecting to the left side I have
k^2 + 2kx + x^2 - 1 - 8nkT - 8cT = 0
and collecting with respect to the k's I have
k^2 + 2(x-4nT)k + x^2 - 1 - 8cT = 0
and completing the square gives
k^2 + 2(x-4nT)k + (x-4nT)^2 + x^2 - 1 - 8cT - (x-rnT)^2= 0
so
(k + x-4nT)^2 + x^2 - 1 - 8cT - x^2 + 2xnT - n^2 T^2 = 0
and simplifying further and collecting everything outside the square to the right side gives
(k + x-4nT)^2 = 1 + 8cT + n^2 T^2 - 2nTx
which is a lot like what I started with, except if x is positive (it could be negative so it's not necessarily a natural) then you're going down mod 2nT, and with n odd and T odd, it looks like x must be divisible by 4, so you're actually searching mod 8nT.
Besides that, I got nothing. I admit, I did it again. Wandered off into some old area and managed to re-discover what was already known.
But it was fun for a while.
Here's something maybe. That c in there is defined as
c = (r-1)*(8*T)^{-1) mod n
so you can make it as negative as you want by subtracting n.
What if you went for a positive minimum? Subtracting such that
1 + 8cT + n^2 T^2 > 0
was the smallest possible? It looks like that would increase k, and shrink x, if x were positive, and it might shrink the search space.
The logic of it is so damn simple it's almost beyond belief, but what I've given in this thread is the simple solution to the factoring problem.
I will make another post explaing it in boring detail.
The gist of it though is that for a solution to m, there must exist a natural number k, but also you can do this weird thing of decrementing x, while incrementing k, without changing m, so that you can find a simple answer.
What's remarkable is that in my post I solved the factoring problem, and did anyone notice?
# posted by James Harris @ 20:01 
