Tuesday, February 27, 2007
Discussion on surrogate-factoring
Theory is one thing, but examples can help gather interest after mathematical proof, as I guess there is just something about seeing an actual result that makes a difference even when something has been proven, so here are some examples with surrogate factoring using some small numbers.
With T = 599293, I picked k with a k/T ratio of 1/30, which means that k is approximately T/30, and found a factorization with k=19978, where I got
y=207419/2, and x=175011/2
so x+y=191215, which has 229 as a factor, and T = (229)(2617).
That took 7 iterations from the starting k.
My next example shows a rather bad run, where with T = 1972897, k = -65765, I have
y=387935/2, and x=561737/2
so x-y=86901, which has 349 as a factor and T = (349)(5653).
And that took a whopping 114 iterations from my starting k, but I'm just picking some primes multiplying them out and seeing what I get so I give that rather bad result.
Finally I have T = 2066147, where k=68873, works giving me
y=-430137/2, and x=334429/2
so, x+y=-47854, which has 337 as a factor and T = (337)(6131).
And it took 9 iterations.
For my examples I took a table of primes and just picked one 3 digit prime and one 4 digit prime, multiplied them together and factored with my surrogate factoring method, where I picked the starting k using
k = floor(T/30)
with a-b=-1, and incremented by 1, until something worked. For two cases that worked rather well, while for one it took a lot, and I didn't throw out any results but just sat here and did 3 in a row.
If you read my earlier posts you may know that a k/T ratio of 1/30 should not be optimal anyway, but smaller k's are easier to factor, and I think you can see that even there, the odds are not that terrible.
So I extended mathematics in the area of factoring with a simple idea where for years I've wondered why you couldn't factor a target composite by instead factoring a surrogate. In each of the examples above the surrogate that is being factored is
2k^2 - T
and by factoring that number I get x and y as explained in prior postings and in that way factor the target composite.
Notice then that surrogate factoring is another way to get a difference of squares.
It is a highly creative way to do so, using some remarkably simple algebra and very basic theory as explained in prior post, so why wasn't it thought of before?
Who knows? I just thought a couple of years ago that maybe there was some way to factor a target by instead factoring some other number, and wouldn't that be neat!
It is a simple idea where most of the mathematics is simple and it may be possible to turn this into an effective practical approach, so mathematicians and cryptographers around the world should be buzzing about this idea, I'd think.
But then again, I have lots of mathematical discoveries that should create buzz, and have had them for years.
Instead of cheering my research, mathematicians call me a crackpot.
Go figure.
But, then again, they are proud those people, and certain of their brilliance.
Maybe I just make them feel stupid, so they choose to ignore simple answers, no matter where I find them.
With T = 599293, I picked k with a k/T ratio of 1/30, which means that k is approximately T/30, and found a factorization with k=19978, where I got
y=207419/2, and x=175011/2
so x+y=191215, which has 229 as a factor, and T = (229)(2617).
That took 7 iterations from the starting k.
My next example shows a rather bad run, where with T = 1972897, k = -65765, I have
y=387935/2, and x=561737/2
so x-y=86901, which has 349 as a factor and T = (349)(5653).
And that took a whopping 114 iterations from my starting k, but I'm just picking some primes multiplying them out and seeing what I get so I give that rather bad result.
Finally I have T = 2066147, where k=68873, works giving me
y=-430137/2, and x=334429/2
so, x+y=-47854, which has 337 as a factor and T = (337)(6131).
And it took 9 iterations.
For my examples I took a table of primes and just picked one 3 digit prime and one 4 digit prime, multiplied them together and factored with my surrogate factoring method, where I picked the starting k using
k = floor(T/30)
with a-b=-1, and incremented by 1, until something worked. For two cases that worked rather well, while for one it took a lot, and I didn't throw out any results but just sat here and did 3 in a row.
If you read my earlier posts you may know that a k/T ratio of 1/30 should not be optimal anyway, but smaller k's are easier to factor, and I think you can see that even there, the odds are not that terrible.
So I extended mathematics in the area of factoring with a simple idea where for years I've wondered why you couldn't factor a target composite by instead factoring a surrogate. In each of the examples above the surrogate that is being factored is
2k^2 - T
and by factoring that number I get x and y as explained in prior postings and in that way factor the target composite.
Notice then that surrogate factoring is another way to get a difference of squares.
It is a highly creative way to do so, using some remarkably simple algebra and very basic theory as explained in prior post, so why wasn't it thought of before?
Who knows? I just thought a couple of years ago that maybe there was some way to factor a target by instead factoring some other number, and wouldn't that be neat!
It is a simple idea where most of the mathematics is simple and it may be possible to turn this into an effective practical approach, so mathematicians and cryptographers around the world should be buzzing about this idea, I'd think.
But then again, I have lots of mathematical discoveries that should create buzz, and have had them for years.
Instead of cheering my research, mathematicians call me a crackpot.
Go figure.
But, then again, they are proud those people, and certain of their brilliance.
Maybe I just make them feel stupid, so they choose to ignore simple answers, no matter where I find them.
# posted by James Harris @ 00:53 
