Saturday, February 24, 2007
Surrogate factoring and the k/T ratio
For years I've done research on ways you might factor a target composite T by factoring some other number I call the surrogate, and after a lot of failed approaches I realized that the idea mathematically reduced to a couple of very simple relations:
x^2 =E2=89=A1 y^2 mod T
and
k^2 =E2=89=A1 2xk mod T
where the first should be familiar enough, while the second is an addition needed mathematically by the concept of surrogate factoring.
So after a lot of years of fumbling around I found mathematically I could reduce the idea quite simply to the given relations.
Now using those requires going to explicit equations:
x^2 =3D y^2 + aT
and
k^2 =3D 2xk + bT
and I can add one to the other, and complete the square to find:
(x+k)^2 =3D y^2 + 2k^2 + (a-b)T
So, if you have
4f_1f_2 =3D 2k^2 + (a-b)T
then y =3D f_1 - f_2 and
x =3D f_1 + f_2 - k
and now the idea is just slightly more complicated, and you can see that actually trying to factor with it requires that you pick a-b and k=2E
Some analysis I won't go into here indicates that the value of a-b should be 1 or -1, so things got simpler there, but now that just leaves k.
So after all that research—the product of years of effort on my part distilling this idea down—I have one variable—k—which controls the outcome.
I have talked about this idea and approach on the newsgroups before as I came across it last year, with a few problems still figuring out details, but the essence has been around for months, and there were posters claiming it worked no better than random.
I refused to test it myself while I considered theoretical issues and worried about other things, but finally sat down and checked myself, and noticed they were wrong, but there is some interesting behavior around how big k is relative to T—the k/T ratio.
That is, I checked with very small primes—to see if the idea worked at all—so I used three digit primes, and found that it factored remarkably well, but I did do other checks and saw it factoring rather badly, though it still would factor.
Thinking about it, I realized that the k/T ratio was dropping, and that when it was factoring very well the k/T ratio was about 0.2 or 20%. But I don't know if that is the prime value, as the research is very rough at this point. But an optimal k/T ratio seems key.
The lower the ratio the better as the surrogate you factor is 2k^2 + (a-b)T, so the smaller it is, the better, so I used a-b=3D-1, and a k that was about 20% of T, and got great results.
I mean, like it factored as I expected, and clearly was not random, so those other posters either screwed up or lied. But that was with the product of three digit primes.
It is a new factoring technique that follows from that simple concept, and extends from the basic congruence of squares with only a single other congruence, from which follows some rather basic equations where a little analysis indicates you need only change one variable—k—and that the ratio of that variable to your target composite T, may be the key to this idea.
For more information on the earlier analysis (I don't have anything on my current research like the k/T ratio) go to my Extreme Mathematics group:
http://groups.google.com/group/extrememathematics/web/surrogate-factoring
I will say that I am puzzled at why any person would put themselves on the record arguing against a new factoring technique claiming it's random when it's not.
That is the one big surprise and tells me why the newsgroups are not a good resource or a place to do research—only to announce results, maybe—as, well, people lie on them.
Posters can easily lie about math. It's just a fact no matter what anyone says to the contrary.
It may be easier to lie about math than most things as it can be hard for others to check, so they trust more than they should, and lies about math can for that reason be convincing, despite the ability of someone to check and see that a poster is lying, because no one does.
Maybe because most people who bother to read math newsgroups are naive and trusting, so they believe posters who learn to lie routinely about math, knowing they have a trusting audience that is easily manipulated.
x^2 =E2=89=A1 y^2 mod T
and
k^2 =E2=89=A1 2xk mod T
where the first should be familiar enough, while the second is an addition needed mathematically by the concept of surrogate factoring.
So after a lot of years of fumbling around I found mathematically I could reduce the idea quite simply to the given relations.
Now using those requires going to explicit equations:
x^2 =3D y^2 + aT
and
k^2 =3D 2xk + bT
and I can add one to the other, and complete the square to find:
(x+k)^2 =3D y^2 + 2k^2 + (a-b)T
So, if you have
4f_1f_2 =3D 2k^2 + (a-b)T
then y =3D f_1 - f_2 and
x =3D f_1 + f_2 - k
and now the idea is just slightly more complicated, and you can see that actually trying to factor with it requires that you pick a-b and k=2E
Some analysis I won't go into here indicates that the value of a-b should be 1 or -1, so things got simpler there, but now that just leaves k.
So after all that research—the product of years of effort on my part distilling this idea down—I have one variable—k—which controls the outcome.
I have talked about this idea and approach on the newsgroups before as I came across it last year, with a few problems still figuring out details, but the essence has been around for months, and there were posters claiming it worked no better than random.
I refused to test it myself while I considered theoretical issues and worried about other things, but finally sat down and checked myself, and noticed they were wrong, but there is some interesting behavior around how big k is relative to T—the k/T ratio.
That is, I checked with very small primes—to see if the idea worked at all—so I used three digit primes, and found that it factored remarkably well, but I did do other checks and saw it factoring rather badly, though it still would factor.
Thinking about it, I realized that the k/T ratio was dropping, and that when it was factoring very well the k/T ratio was about 0.2 or 20%. But I don't know if that is the prime value, as the research is very rough at this point. But an optimal k/T ratio seems key.
The lower the ratio the better as the surrogate you factor is 2k^2 + (a-b)T, so the smaller it is, the better, so I used a-b=3D-1, and a k that was about 20% of T, and got great results.
I mean, like it factored as I expected, and clearly was not random, so those other posters either screwed up or lied. But that was with the product of three digit primes.
It is a new factoring technique that follows from that simple concept, and extends from the basic congruence of squares with only a single other congruence, from which follows some rather basic equations where a little analysis indicates you need only change one variable—k—and that the ratio of that variable to your target composite T, may be the key to this idea.
For more information on the earlier analysis (I don't have anything on my current research like the k/T ratio) go to my Extreme Mathematics group:
http://groups.google.com/group/extrememathematics/web/surrogate-factoring
I will say that I am puzzled at why any person would put themselves on the record arguing against a new factoring technique claiming it's random when it's not.
That is the one big surprise and tells me why the newsgroups are not a good resource or a place to do research—only to announce results, maybe—as, well, people lie on them.
Posters can easily lie about math. It's just a fact no matter what anyone says to the contrary.
It may be easier to lie about math than most things as it can be hard for others to check, so they trust more than they should, and lies about math can for that reason be convincing, despite the ability of someone to check and see that a poster is lying, because no one does.
Maybe because most people who bother to read math newsgroups are naive and trusting, so they believe posters who learn to lie routinely about math, knowing they have a trusting audience that is easily manipulated.
# posted by James Harris @ 10:39 
