Saturday, September 15, 2007
Factoring and identities
Much of my research is about using identities and with my factoring research I have a completely traditional usage in contrast with the very complex identities of non-polynomial factorization. I'm going to step through a derivation once again and highlight the identity more this time as the situation is sort of puzzling to me.
For ANY composite T, x and y can be found such that
x^2 = y^2 mod T
and x+y and x-y reveal factors of T, which is just the familiar congruence of squares relation.
I was puzzling over that a bit over a year ago back in August of last year as I began a serious assessment of a concept I called surrogate factoring, wondering if there were any hope for the idea as I had a string of failures trying to get it to work mathematically, and I thought about identities.
To see what occurred to me in a simple way that I think makes it more obvious as it's not exactly how I figured it out over a year ago, start with
y^2 = x^2 mod T
and introduce k, where k = 2x mod T, so it must exist, right? You're just doubling x modulo T, so given x, k MUST exist, so now I have
k = 2x mod T
and do something clever, which is multiply both sides by k, to get
k^2 = 2xk mod T
and with
y^2 = x^2 mod T
it kind of jumps out at you what's needed next as you just add one to the other to get
y^2 + k^2 = x^2 + 2xk mod T
which just begs for a completing of the square and now we have use of an identity!
y^2 + 2k^2 = x^2 + 2xk + k^2 mod T
as k^2 is added to both sides, so I have
y^2 + 2k^2 = (x+k)^2 mod T
and that is
(x+k)^2 = y^2 + 2k^2 mod T
and you have a new congruence result, which exists for ANY solution of a congruence of squares.
That is the absolute which is easily derived and it must exist, so there isn't a doubt about whether or not it is there.
So what happened over a year ago when I was puzzling over the concept of surrogate factoring trying to mathematicize it, I realized that completion of the square was key, so I deliberately looked to complete the square against x, which is why I needed 2kx.
But why hasn't anyone thought of that before? I don't know, but I have use of identities where I use far more complicated ones than y^2 = y^2, and subtract out equations from them to analyze the residue, and why hasn't anyone thought of that before? Who knows.
How does anyone figure anything out? And why one person and not another? And why now?
Using the derived result requires an explicit equation, so I toss in an integer n to get
(x+k)^2 = y^2 + 2k^2 + nT
and let S = 2k^2 + nT, and you have
(x+k)^2 = y^2 + S
and another congruence of squares! Where now S is potentially factored, or you can factor S, to get x and y, and maybe factor T.
So every congruence of squares
x^2 = y^2 mod T
is connected to another where
(x+k)^2 = y^2 + S
and S = 2k^2 + nT.
And that is then a fundamental result in number theory showing a deep underlying connection between any given factorization and some other number, where I found it because I wanted to complete the square on x^2 = y^2 mod T, in order to implement a concept I call surrogate factoring.
The research then is on picking k and n in the optimal way, which goes to the practical matter of making this into a powerful technique, but regardless of that practical aspect, it is fascinating number theory.
I'll end with a factorization that I like to use so it's scattered around on my web pages as my demonstration example:
T = 732367903, k=floor(T/30) = 24412263, n= -2
S = 2k^2 + nT = 1191915704826532 = ( 2^2 )( 7 )( 73 )( 583129014103 )
y=-170273672118069/2 and x=170273623293557/2
so, x+y=-24412256, which has 223 as a factor.
T = 732367903 = (223)(3284161).
One thing you may note is that the factorization actually works to pull just one prime factor of T, so that you do not have
x^2 = y^2 mod T
but have x^2 = y^2 mod p, where p is a prime factor, which of course, works just as well, and the derivation is hardly different except you have p instead of T.
For me it is a wonderful sense of satisfaction in applying simple ideas and techniques against a well-known problem to find a new approach, and it's kind of odd thinking back that it was about a concept first, and then a deliberate attempt to get to a place where I could use an identity, by completing the square.
On the political side, factoring represents a way for me to demonstrate the power of techniques I call extreme mathematics, as well as highlight how obvious it is the mathematical community is not obeying its own rules.
So a fundamental number theory result is ignored—unless I or someone else rapidly figures out the applied mathematics that would follow from the theory to produce a real world and powerful application.
For me it's just another result where I can see what I saw years ago, when I found my prime counting function, back when I still had some faith in the math community, which is that my research methods work.
Now I test factoring with what I call surrogate factoring, like before I watched my screen fill with prime numbers as the math declared to me the arrival of my prime counting function, and with those absolutes I know absolutely that lesser people who could not, who now will not even be bothered to acknowledge one who could—and did, are liars.
For ANY composite T, x and y can be found such that
x^2 = y^2 mod T
and x+y and x-y reveal factors of T, which is just the familiar congruence of squares relation.
I was puzzling over that a bit over a year ago back in August of last year as I began a serious assessment of a concept I called surrogate factoring, wondering if there were any hope for the idea as I had a string of failures trying to get it to work mathematically, and I thought about identities.
To see what occurred to me in a simple way that I think makes it more obvious as it's not exactly how I figured it out over a year ago, start with
y^2 = x^2 mod T
and introduce k, where k = 2x mod T, so it must exist, right? You're just doubling x modulo T, so given x, k MUST exist, so now I have
k = 2x mod T
and do something clever, which is multiply both sides by k, to get
k^2 = 2xk mod T
and with
y^2 = x^2 mod T
it kind of jumps out at you what's needed next as you just add one to the other to get
y^2 + k^2 = x^2 + 2xk mod T
which just begs for a completing of the square and now we have use of an identity!
y^2 + 2k^2 = x^2 + 2xk + k^2 mod T
as k^2 is added to both sides, so I have
y^2 + 2k^2 = (x+k)^2 mod T
and that is
(x+k)^2 = y^2 + 2k^2 mod T
and you have a new congruence result, which exists for ANY solution of a congruence of squares.
That is the absolute which is easily derived and it must exist, so there isn't a doubt about whether or not it is there.
So what happened over a year ago when I was puzzling over the concept of surrogate factoring trying to mathematicize it, I realized that completion of the square was key, so I deliberately looked to complete the square against x, which is why I needed 2kx.
But why hasn't anyone thought of that before? I don't know, but I have use of identities where I use far more complicated ones than y^2 = y^2, and subtract out equations from them to analyze the residue, and why hasn't anyone thought of that before? Who knows.
How does anyone figure anything out? And why one person and not another? And why now?
Using the derived result requires an explicit equation, so I toss in an integer n to get
(x+k)^2 = y^2 + 2k^2 + nT
and let S = 2k^2 + nT, and you have
(x+k)^2 = y^2 + S
and another congruence of squares! Where now S is potentially factored, or you can factor S, to get x and y, and maybe factor T.
So every congruence of squares
x^2 = y^2 mod T
is connected to another where
(x+k)^2 = y^2 + S
and S = 2k^2 + nT.
And that is then a fundamental result in number theory showing a deep underlying connection between any given factorization and some other number, where I found it because I wanted to complete the square on x^2 = y^2 mod T, in order to implement a concept I call surrogate factoring.
The research then is on picking k and n in the optimal way, which goes to the practical matter of making this into a powerful technique, but regardless of that practical aspect, it is fascinating number theory.
I'll end with a factorization that I like to use so it's scattered around on my web pages as my demonstration example:
T = 732367903, k=floor(T/30) = 24412263, n= -2
S = 2k^2 + nT = 1191915704826532 = ( 2^2 )( 7 )( 73 )( 583129014103 )
y=-170273672118069/2 and x=170273623293557/2
so, x+y=-24412256, which has 223 as a factor.
T = 732367903 = (223)(3284161).
One thing you may note is that the factorization actually works to pull just one prime factor of T, so that you do not have
x^2 = y^2 mod T
but have x^2 = y^2 mod p, where p is a prime factor, which of course, works just as well, and the derivation is hardly different except you have p instead of T.
For me it is a wonderful sense of satisfaction in applying simple ideas and techniques against a well-known problem to find a new approach, and it's kind of odd thinking back that it was about a concept first, and then a deliberate attempt to get to a place where I could use an identity, by completing the square.
On the political side, factoring represents a way for me to demonstrate the power of techniques I call extreme mathematics, as well as highlight how obvious it is the mathematical community is not obeying its own rules.
So a fundamental number theory result is ignored—unless I or someone else rapidly figures out the applied mathematics that would follow from the theory to produce a real world and powerful application.
For me it's just another result where I can see what I saw years ago, when I found my prime counting function, back when I still had some faith in the math community, which is that my research methods work.
Now I test factoring with what I call surrogate factoring, like before I watched my screen fill with prime numbers as the math declared to me the arrival of my prime counting function, and with those absolutes I know absolutely that lesser people who could not, who now will not even be bothered to acknowledge one who could—and did, are liars.
# posted by James Harris @ 23:55 
