Sunday, March 02, 2008
JSH: Switching gears, surrogate factoring
Somewhere around 4 years ago, as I think it was back in 2004 or maybe earlier I started wondering about factoring one number through the factorization of some other number that I eventually called the surrogate, so I called the entire concept surrogate factoring.
And I just kind of put that in the incubator as this concept that I'd work on from time to time while I did other things as I had a few other mathematical things going on at the time, including eventually the publication and the withdrawal by the SWJPAM editors of my paper introducing non-polynomial factorization. And there was also some prime research I was doing, still contemplating my prime counting function and later I presented the prime gap equation (search for "prime gap equation" in Google to get more info there).
So I had quite a few things going on mathematically as well as what I was doing outside of mathematics including my open source project Class Viewer (Google search again for more info) which I was fiddling with here and there during that period, and I'm digressing as the point is that I was working on surrogate factoring here and there between other things.
And at times I'd think I'd have something, brainstorm it a bit, including posting online and find out that what I had was crap, and it didn't help that I was giving dire warnings about the negative potentials of a simple solution to the factoring problem—as it scared me—and then having to just quiet down anyway when I didn't have same.
But the breakthrough came with simplification back in August 2007, as I'd done various things here and there as I tried to factor one number with another, and one day just sat down and said to myself that I needed to resolve this thing one way or the other, including maybe just giving up on the concept as just not practical, and at some point I started writing out something like:
x^2 = y^2 mod T
and
k = 2x mod T
and I realized that I was doing that JUST to get to a difference of squares which looked like
(x+k)^2 = y^2 + 2k^2 mod T
and I had a second difference of squares where with T the target composite I had connected a factorization of T at the start, with a factorization of 2k^2 mod T at the bottom—so an infinity of factorizations but it's easier to think of one—and that was surrogate factoring!!!
And there was this odd sense of the bizarre simplicity of the answer I'd been spending YEARS, literally years searching for, though as I said I was doing other things at the time as well, but it's kind of odd to get a simple answer when you've looked at something for years and puzzled and pondered, wondering exactly which way to go, and then it just leaps out at you.
And it took me MONTHS to go from there to what is currently the full surrogate factoring theory, where there was another surprise in store, as puzzling over those equations I found that primes stepped in, in a BIG WAY and would just help you out and then quietly exit, so here is the gist of what comes from the full surrogate factoring theory, leaving the next step being implementation as I switch gears from theoretical mode—which is like prospecting for gold—to the steady plodding of experimental mode:
Now there is
z^2 = y^2 + nT
as the primary factorization equation where T is the target and n is one of the many helper variables used to get to the factorization of T, where the latest research indicates that nT mod 3 = 2 is desired, so n is used to make that happen. It may have other uses which experiment will show.
My early idea of using 2x = k mod T, has evolved so that now the key equation is
2αx = k mod p
where p is an odd prime and now you also have alpha, which comes in with text in posts as "α", where usually I have the explicit with
2αx = k + pr_2
and I use r_2 for historical reasons as in the full theory there is also an r_1.
And then I have z = x + αk, and you can substitute out z, from
z^2 = y^2 + nT
and multiply everything out and simplify to get
x^2 = y^2 + nT - (1 + α^2)k^2 - kpr_2
and a truly remarkable result presents itself as low-hanging fruit at this point, and it is such a huge result as it allows you to get a good idea of where to find k, and you can get it easily enough by substituting with
k = k_0 + pj
where j is some integer and p is still your odd prime, as then you get:
x^2 = y^2 + nT - (1 + α^2)(k_0^2 + 2pjk_0 + p^2*j^2) - (k_0 + pj)pr_2.
And focusing on the behavior of
nT - (1 + α^2)(k_0^2 + 2pjk_0 + p^2*j^2)
as you increment or decrement k with j, you can just look to (k_0 + pj)pr_2 where you have j linear versus the quadratic j^2 in the previous so it's trivial to work out the behavior, which then indicates that k_0 will tend to be where you have the maximum k such that
abs(nT - (1 + α^2)k^2)
is a minima, which is just such a HUGE result, and an amazing one besides as it's such a powerful result for the ease with which it is gathered.
So one of the big surprises you can give yourself with this powerful new factoring theory is just to look at factorizations of small composite T's as they're easier to play with, and find out how close z is to the value given JUST be finding k such that abs(nT - (1 + α^2)k^2), and then checking with
z = (1 + 2α^2)k_0/(2α)
which is derived by using 2αx = k_0, and z = x + αk_0.
Notice that since z has 1 + 2α^2 as a factor, 3 is a factor unless α has 3 as a factor, so forcing z to have 3 as a factor is a good way to make things easier.
It's actually kind of weird to see how z skips around with various values of α focusing on easy cases as 1 + 2α^2 can be easier for the algebra to satisfy for certain values, like α=1, when it's equal to 3 and much harder for others, so it's about probability at the DEPTHS of factoring that was previously unknown to the mathematical world.
So all along values for z that solved z^2 = y^2 mod T, or as mathematicians traditionally put it, z^2 = y^2 mod N, were following these mathematical rules that preferred easy to harder cases when it was a necessity to satisfy:
z = (1 + 2α^2)k_0/(2α).
So the surrogate factoring approach to the factoring problem is really tackling finding how to get z, and all those variables are just helpers in that task.
They're like friendly neighbors trying to get you next to z.
And it can be shown that
k^2 = (1 + α^2)^{-1}(nT) mod p
so you can go looking for z by looking for k modulo a prime p that YOU GET TO CHOOSE, though not every choice will work, at least you get k about 50% of the time for your choice since p has (p-1)/2 quadratic residues.
The most preferred case still is with α=1, but that case may not give you k, for a particular odd prime p as explained by the theory, while another value may. And even when you get a k, it can be for a case where x, y and z are not all rational as the math it seems prefers to use k for the largest value of α that will work!
And so far that is something determined by experiment, as a result still just outside the reach of my understanding of the current theory, as a complex system is demanding an experimental approach which may be foreign to many mathematicians who aren't used to dealing with complex systems, unlike scientists in the real world who deal exclusively with complex systems, so they must rely on experiment.
Regardless there is this incredible result that in general
z = (1 + 2α^2)k_0/(2α)
which puts constraints on z itself which is a huge find, from simple algebra which affects any factoring idea out there, so I toss that in so that you know we are not in trivial territory here, and claims that we are or that I MUST factor an RSA number first are just specious, and defy reason.
And it is just incredible too that you have have prime numbers as helpers that disappear after helping you to factor, and you have a surprisingly simple result with a parabolic minima, and you get quadratic residues in there, and it is the factoring problem.
So why is there still primarily me just talking about my research as I begin switching gears to doing a factoring demonstration that will end any debate about the value of this research when already it can do things never done before, and show rules never known?
People go towards what attracts them—It's like a tautology.
The simple answer is that modern mathematicians are repulsed by the results.
The truth in this area is not what they like—not what attracts them— so they vote against it with their feet, as I like to say. They can't be interested, so far in the truth.
Showing democratically their disdain for how mathematics does the factoring problem.
That is the only answer that fits the behavior.
People go towards what they like. Math society is running from these results.
Ergo, math society dislikes them.
And I just kind of put that in the incubator as this concept that I'd work on from time to time while I did other things as I had a few other mathematical things going on at the time, including eventually the publication and the withdrawal by the SWJPAM editors of my paper introducing non-polynomial factorization. And there was also some prime research I was doing, still contemplating my prime counting function and later I presented the prime gap equation (search for "prime gap equation" in Google to get more info there).
So I had quite a few things going on mathematically as well as what I was doing outside of mathematics including my open source project Class Viewer (Google search again for more info) which I was fiddling with here and there during that period, and I'm digressing as the point is that I was working on surrogate factoring here and there between other things.
And at times I'd think I'd have something, brainstorm it a bit, including posting online and find out that what I had was crap, and it didn't help that I was giving dire warnings about the negative potentials of a simple solution to the factoring problem—as it scared me—and then having to just quiet down anyway when I didn't have same.
But the breakthrough came with simplification back in August 2007, as I'd done various things here and there as I tried to factor one number with another, and one day just sat down and said to myself that I needed to resolve this thing one way or the other, including maybe just giving up on the concept as just not practical, and at some point I started writing out something like:
x^2 = y^2 mod T
and
k = 2x mod T
and I realized that I was doing that JUST to get to a difference of squares which looked like
(x+k)^2 = y^2 + 2k^2 mod T
and I had a second difference of squares where with T the target composite I had connected a factorization of T at the start, with a factorization of 2k^2 mod T at the bottom—so an infinity of factorizations but it's easier to think of one—and that was surrogate factoring!!!
And there was this odd sense of the bizarre simplicity of the answer I'd been spending YEARS, literally years searching for, though as I said I was doing other things at the time as well, but it's kind of odd to get a simple answer when you've looked at something for years and puzzled and pondered, wondering exactly which way to go, and then it just leaps out at you.
And it took me MONTHS to go from there to what is currently the full surrogate factoring theory, where there was another surprise in store, as puzzling over those equations I found that primes stepped in, in a BIG WAY and would just help you out and then quietly exit, so here is the gist of what comes from the full surrogate factoring theory, leaving the next step being implementation as I switch gears from theoretical mode—which is like prospecting for gold—to the steady plodding of experimental mode:
Now there is
z^2 = y^2 + nT
as the primary factorization equation where T is the target and n is one of the many helper variables used to get to the factorization of T, where the latest research indicates that nT mod 3 = 2 is desired, so n is used to make that happen. It may have other uses which experiment will show.
My early idea of using 2x = k mod T, has evolved so that now the key equation is
2αx = k mod p
where p is an odd prime and now you also have alpha, which comes in with text in posts as "α", where usually I have the explicit with
2αx = k + pr_2
and I use r_2 for historical reasons as in the full theory there is also an r_1.
And then I have z = x + αk, and you can substitute out z, from
z^2 = y^2 + nT
and multiply everything out and simplify to get
x^2 = y^2 + nT - (1 + α^2)k^2 - kpr_2
and a truly remarkable result presents itself as low-hanging fruit at this point, and it is such a huge result as it allows you to get a good idea of where to find k, and you can get it easily enough by substituting with
k = k_0 + pj
where j is some integer and p is still your odd prime, as then you get:
x^2 = y^2 + nT - (1 + α^2)(k_0^2 + 2pjk_0 + p^2*j^2) - (k_0 + pj)pr_2.
And focusing on the behavior of
nT - (1 + α^2)(k_0^2 + 2pjk_0 + p^2*j^2)
as you increment or decrement k with j, you can just look to (k_0 + pj)pr_2 where you have j linear versus the quadratic j^2 in the previous so it's trivial to work out the behavior, which then indicates that k_0 will tend to be where you have the maximum k such that
abs(nT - (1 + α^2)k^2)
is a minima, which is just such a HUGE result, and an amazing one besides as it's such a powerful result for the ease with which it is gathered.
So one of the big surprises you can give yourself with this powerful new factoring theory is just to look at factorizations of small composite T's as they're easier to play with, and find out how close z is to the value given JUST be finding k such that abs(nT - (1 + α^2)k^2), and then checking with
z = (1 + 2α^2)k_0/(2α)
which is derived by using 2αx = k_0, and z = x + αk_0.
Notice that since z has 1 + 2α^2 as a factor, 3 is a factor unless α has 3 as a factor, so forcing z to have 3 as a factor is a good way to make things easier.
It's actually kind of weird to see how z skips around with various values of α focusing on easy cases as 1 + 2α^2 can be easier for the algebra to satisfy for certain values, like α=1, when it's equal to 3 and much harder for others, so it's about probability at the DEPTHS of factoring that was previously unknown to the mathematical world.
So all along values for z that solved z^2 = y^2 mod T, or as mathematicians traditionally put it, z^2 = y^2 mod N, were following these mathematical rules that preferred easy to harder cases when it was a necessity to satisfy:
z = (1 + 2α^2)k_0/(2α).
So the surrogate factoring approach to the factoring problem is really tackling finding how to get z, and all those variables are just helpers in that task.
They're like friendly neighbors trying to get you next to z.
And it can be shown that
k^2 = (1 + α^2)^{-1}(nT) mod p
so you can go looking for z by looking for k modulo a prime p that YOU GET TO CHOOSE, though not every choice will work, at least you get k about 50% of the time for your choice since p has (p-1)/2 quadratic residues.
The most preferred case still is with α=1, but that case may not give you k, for a particular odd prime p as explained by the theory, while another value may. And even when you get a k, it can be for a case where x, y and z are not all rational as the math it seems prefers to use k for the largest value of α that will work!
And so far that is something determined by experiment, as a result still just outside the reach of my understanding of the current theory, as a complex system is demanding an experimental approach which may be foreign to many mathematicians who aren't used to dealing with complex systems, unlike scientists in the real world who deal exclusively with complex systems, so they must rely on experiment.
Regardless there is this incredible result that in general
z = (1 + 2α^2)k_0/(2α)
which puts constraints on z itself which is a huge find, from simple algebra which affects any factoring idea out there, so I toss that in so that you know we are not in trivial territory here, and claims that we are or that I MUST factor an RSA number first are just specious, and defy reason.
And it is just incredible too that you have have prime numbers as helpers that disappear after helping you to factor, and you have a surprisingly simple result with a parabolic minima, and you get quadratic residues in there, and it is the factoring problem.
So why is there still primarily me just talking about my research as I begin switching gears to doing a factoring demonstration that will end any debate about the value of this research when already it can do things never done before, and show rules never known?
People go towards what attracts them—It's like a tautology.
The simple answer is that modern mathematicians are repulsed by the results.
The truth in this area is not what they like—not what attracts them— so they vote against it with their feet, as I like to say. They can't be interested, so far in the truth.
Showing democratically their disdain for how mathematics does the factoring problem.
That is the only answer that fits the behavior.
People go towards what they like. Math society is running from these results.
Ergo, math society dislikes them.
# posted by James Harris @ 15:58 
