Sunday, October 01, 2006
Surrogate factoring, key points
Some years ago I started thinking about factoring and wondered if there might be some way to factor a target composite T by finding some other numbers to factor, which I called surrogate factoring.
In my search over the years I've had lots of possibles where for various reasons—like they provably didn't work or didn't work well—I've dropped all past approaches except the following:
With T the target composite:
x^2 - y^2 = 0 mod T
and
S - 2*x_res*k = 0 mod T
you can solve for x and y using
x+k = sqrt(y^2 + S + k^2)
as getting y is just a matter of factoring (S+k^2)/4, once S and k are chosen.
Which is then a simple approach, which took me years to find, and now there is the question of how useful is it?
First off, notice that with a target composite T, the only variables you have any control over are S and k, and provably for any target composite T, there must exist S and k for every possible non-zero residue modulo T that x can have.
So, a solution must exist, but how do you pick S and k?
Well, provably there must also exist an S that will work for any non-zero k that you pick as long as k is coprime to T, so now it looks like S is the only variable that matters, but how do you pick S?
Well, a solution must exist S mod T, so it now comes down to searching modulo T.
That is, if you have S = r mod T, there must exist a solution for any non-zero residue r, so there exists some integer n, such that
S = r + n*T
will work to factor T.
Now I can finally get to the question of, is this a good idea, as it is simple now to change that to, how easy is it to find n?
I don't know.
The natural assumption is that n is a needle in a haystack that gets bigger and bigger as T increases in size, but I have not seen any mathematical proof that the natural assumption is correct.
If it is wrong, then someone might be able to develop a practical factoring method from this approach, and the next natural assumption is that if it could be made practical then SOMEONE would have noticed and raised an alarm.
Yeah but, has our world impressed you with being that brilliant? If so, fine. Rest easy and don't worry about it.
Maybe guardian angels are protecting us or something, or hey, the idea just can't be made practical, as I don't know, I refuse to check further out of sheer fear.
But I do know that I haven't found a mathematical reason for n to be a needle in a haystack, nor has anyone replied to me in posts—as I've talked about this idea before—with even a basic understanding of how this thing works with a cogent response showing that n would be ever harder to find as T increases in size.
Posters instead have avoided the proper mathematical analysis to look for ways to claim it doesn't work without showing it doesn't work!!!
I suspect the same will happen in reply to this post, as remember there is only one variable where a search is needed as you're looking for a solution to
S = r + n*T
where r can be any residue modulo T, so only n matters, and there must exist some integer n, such that
x^2 - y^2 = 0 mod T
where you solve for x and y using
x+k = sqrt(y^2 + S + k^2)
and it's surrogate factoring because you get y by factoring S + k^2.
Does it work?
Yes. It's easy to prove solutions must exist.
But can it be made practical?
Don't know.
But consider, you can't find this idea in math textbooks, or in the mathematical mainstream, so I just thought about a problem for a couple of years and figured out a new way to factor, previously unknown.
[A reply to someone who said that he had programmed James' methods, and that some have failed entirely, but most of them do find factors.]
Unfortunately this idea is stupid simple—as in so damn easy it takes effort to get it wrong.
I think you made that effort.
Now I refuse to implement because I am too terrified both of the idea and of a world that lets something like this just sit out there because a few people are, well, pathological.
I fear this idea is what turned the Hezbollah and Israel conflict.
I fear that this idea is now allowing terrorist organizations to get funding by simply scooping money out of the world network.
And I fear that terrorists have not yet fully reacted because they are in shock that they can do this and keep doing it, and even have evidence that they are doing it, which is being ignored, so they can keep doing it, when supposedly countries like the United States and Israel are so brilliant.
I fear they are not quite reacting yet because they can't quite comprehend this either.
It makes no sense. This situation should be impossible. I find I can't wrap a logical argument around it.
It is puzzling to an extreme. Denial on this level shouldn't be possible.
But countries in the know are maybe increasingly bold as they know they have knowledge of an Achilles heel, giving them the power to do, well, just about anything they want.
So like now North Korea wants to test a nuke. What can stop them? What if they can break military codes? What kind of bloodbath in Iraq might we expect? Where will this end?
In my search over the years I've had lots of possibles where for various reasons—like they provably didn't work or didn't work well—I've dropped all past approaches except the following:
With T the target composite:
x^2 - y^2 = 0 mod T
and
S - 2*x_res*k = 0 mod T
you can solve for x and y using
x+k = sqrt(y^2 + S + k^2)
as getting y is just a matter of factoring (S+k^2)/4, once S and k are chosen.
Which is then a simple approach, which took me years to find, and now there is the question of how useful is it?
First off, notice that with a target composite T, the only variables you have any control over are S and k, and provably for any target composite T, there must exist S and k for every possible non-zero residue modulo T that x can have.
So, a solution must exist, but how do you pick S and k?
Well, provably there must also exist an S that will work for any non-zero k that you pick as long as k is coprime to T, so now it looks like S is the only variable that matters, but how do you pick S?
Well, a solution must exist S mod T, so it now comes down to searching modulo T.
That is, if you have S = r mod T, there must exist a solution for any non-zero residue r, so there exists some integer n, such that
S = r + n*T
will work to factor T.
Now I can finally get to the question of, is this a good idea, as it is simple now to change that to, how easy is it to find n?
I don't know.
The natural assumption is that n is a needle in a haystack that gets bigger and bigger as T increases in size, but I have not seen any mathematical proof that the natural assumption is correct.
If it is wrong, then someone might be able to develop a practical factoring method from this approach, and the next natural assumption is that if it could be made practical then SOMEONE would have noticed and raised an alarm.
Yeah but, has our world impressed you with being that brilliant? If so, fine. Rest easy and don't worry about it.
Maybe guardian angels are protecting us or something, or hey, the idea just can't be made practical, as I don't know, I refuse to check further out of sheer fear.
But I do know that I haven't found a mathematical reason for n to be a needle in a haystack, nor has anyone replied to me in posts—as I've talked about this idea before—with even a basic understanding of how this thing works with a cogent response showing that n would be ever harder to find as T increases in size.
Posters instead have avoided the proper mathematical analysis to look for ways to claim it doesn't work without showing it doesn't work!!!
I suspect the same will happen in reply to this post, as remember there is only one variable where a search is needed as you're looking for a solution to
S = r + n*T
where r can be any residue modulo T, so only n matters, and there must exist some integer n, such that
x^2 - y^2 = 0 mod T
where you solve for x and y using
x+k = sqrt(y^2 + S + k^2)
and it's surrogate factoring because you get y by factoring S + k^2.
Does it work?
Yes. It's easy to prove solutions must exist.
But can it be made practical?
Don't know.
But consider, you can't find this idea in math textbooks, or in the mathematical mainstream, so I just thought about a problem for a couple of years and figured out a new way to factor, previously unknown.
[A reply to someone who said that he had programmed James' methods, and that some have failed entirely, but most of them do find factors.]
Unfortunately this idea is stupid simple—as in so damn easy it takes effort to get it wrong.
I think you made that effort.
Now I refuse to implement because I am too terrified both of the idea and of a world that lets something like this just sit out there because a few people are, well, pathological.
I fear this idea is what turned the Hezbollah and Israel conflict.
I fear that this idea is now allowing terrorist organizations to get funding by simply scooping money out of the world network.
And I fear that terrorists have not yet fully reacted because they are in shock that they can do this and keep doing it, and even have evidence that they are doing it, which is being ignored, so they can keep doing it, when supposedly countries like the United States and Israel are so brilliant.
I fear they are not quite reacting yet because they can't quite comprehend this either.
It makes no sense. This situation should be impossible. I find I can't wrap a logical argument around it.
It is puzzling to an extreme. Denial on this level shouldn't be possible.
But countries in the know are maybe increasingly bold as they know they have knowledge of an Achilles heel, giving them the power to do, well, just about anything they want.
So like now North Korea wants to test a nuke. What can stop them? What if they can break military codes? What kind of bloodbath in Iraq might we expect? Where will this end?
# posted by James Harris @ 15:29 
