Tuesday, February 05, 2008
JSH: Situation has changed
Turns out the factoring problem is not only trivial to solve with modern computing technology, but it's trivial to explain why, as I showed in a previous post, but I want to emphasize to the physics community why that is correct.
If you have T = r_1 mod p_1 where p_1 is some prime and r_1 is some residue modulo that prime you have a certain amount of information about the target T.
For instance, if T = 119, then T = 9 mod 11, and there are other composites that are 9 mod 11 that are less than T, like 20.
But if all you have are residues modulo T, it takes a certain number to constrain T to one equal to your target or greater, like I demonstrated in my previous post by using T = 2 mod 13.
T = 9 mod 11 and T = 2 mod 13, force T equal to 119 or greater.
But if you have factors f_1 and f_2 where f_1*f_2 = T, then they are being constrained as well.
So there is information wrapped up in the intersection between the primes.
That information determines a minimum value for T, so it determines values for factors of T.
If you know that then you just go looking for how to pull that information out.
And that's the high level explanation for why the factoring problem can be easily solved.
The actual solution is not that complicated but I think it less important than explaining HOW you know there must be a simple solution available.
This technique can tackle numbers easily up to 143!, using primes from 100 to 1000, where to get an understanding how the estimate of primes needed using m where m is chosen such that T/m! < 1 is such an overestimate let's go back to T = 119, where only 2 primes were needed.
With it, m = 5, as 119/5! < 1.
So 143! is a vast underestimate to the size of the composite that can be tackled by just using the primes from 100 to 1000.
Who knows exactly why mathematicians presented factoring as a hard problem with which the world could secure its information systems.
But what you know now if you can understand informational complexity is that the system can be easily broken if it really is breakable just by factoring large composites.
Throw out what you know about information theory if you want to ignore these posts and then go back to work doing what you're doing—waiting for the world to come crashing down around your ears.
But if you do that then you are not a physicist, or not any kind of physicist that the world needs in what could be one of its most desperate times.
It still is remarkable to me that a simple exercise in considering the information available tells you that the factoring problem must have an easy solution.
The example I like the example with T = 9 mod 11 and T = 2 mod 13 constraining you to T = 119 mod 143, where 119 is the target composite shows that the primes TELL something about the composite that you wish to factor, and there is information in there that can be exploited.
So if you have a target composite like an RSA public key, you can use primes to probe the damn thing, with a series of values taken modulo various primes and just pull the information out of it as to how to factor it.
And why would the mathematicians not know this?
I think they just don't think like problem solvers in other fields, and actually LIKE to believe more than prove and they aren't great experimenters from what I've seen.
In short, I think modern mathematicians are trained wrong.
And the way that is dramatically evident is that they put forward a system that is being used to protect your information and mine, as well as millions of people worldwide that can be explained to be flawed with only a tad bit of information theory.
How you train students can decide how well they think and that determines what they can discover.
A physics student could figure this out.
Math students might never have.
[A reply to someone who asked which was James' excuse for not testing you method on RSA-sized composites.]
Information theory is in the domain of physicists. So it is my hope that it is less easy for the math community to try and hide something really basic by using trivial taunts.
Physicists who just never pondered limiting solutions by using residues modulo multiple primes can now look at how easy it is with my T = 9 mod 11 and T = 2 mod 13 example, where T = 119, is the first positive integer that will work.
As you limit the target you limit its factors so information is wrapped up in there SOMEWHERE.
Now physicists can then say to themselves, it's the mathematicians area and walk away, but if the mathematicians DID screw up here, then a massive financial collapse created by the demise of this system grabs the physicists along with everyone else.
And they were warned, so it's not like later they can just say, oh, we didn't want to step over academic lines and shrug to themselves.
They will feel the kick in the gut of having the knowledge and not using it to save themselves, their loved ones or their countries just because of medieval academic conventions, when cross-discipline should rule the world.
If the math people screw up, the physics people should help them, not just throw up their hands and say, not my area.
If you have T = r_1 mod p_1 where p_1 is some prime and r_1 is some residue modulo that prime you have a certain amount of information about the target T.
For instance, if T = 119, then T = 9 mod 11, and there are other composites that are 9 mod 11 that are less than T, like 20.
But if all you have are residues modulo T, it takes a certain number to constrain T to one equal to your target or greater, like I demonstrated in my previous post by using T = 2 mod 13.
T = 9 mod 11 and T = 2 mod 13, force T equal to 119 or greater.
But if you have factors f_1 and f_2 where f_1*f_2 = T, then they are being constrained as well.
So there is information wrapped up in the intersection between the primes.
That information determines a minimum value for T, so it determines values for factors of T.
If you know that then you just go looking for how to pull that information out.
And that's the high level explanation for why the factoring problem can be easily solved.
The actual solution is not that complicated but I think it less important than explaining HOW you know there must be a simple solution available.
This technique can tackle numbers easily up to 143!, using primes from 100 to 1000, where to get an understanding how the estimate of primes needed using m where m is chosen such that T/m! < 1 is such an overestimate let's go back to T = 119, where only 2 primes were needed.
With it, m = 5, as 119/5! < 1.
So 143! is a vast underestimate to the size of the composite that can be tackled by just using the primes from 100 to 1000.
Who knows exactly why mathematicians presented factoring as a hard problem with which the world could secure its information systems.
But what you know now if you can understand informational complexity is that the system can be easily broken if it really is breakable just by factoring large composites.
Throw out what you know about information theory if you want to ignore these posts and then go back to work doing what you're doing—waiting for the world to come crashing down around your ears.
But if you do that then you are not a physicist, or not any kind of physicist that the world needs in what could be one of its most desperate times.
It still is remarkable to me that a simple exercise in considering the information available tells you that the factoring problem must have an easy solution.
The example I like the example with T = 9 mod 11 and T = 2 mod 13 constraining you to T = 119 mod 143, where 119 is the target composite shows that the primes TELL something about the composite that you wish to factor, and there is information in there that can be exploited.
So if you have a target composite like an RSA public key, you can use primes to probe the damn thing, with a series of values taken modulo various primes and just pull the information out of it as to how to factor it.
And why would the mathematicians not know this?
I think they just don't think like problem solvers in other fields, and actually LIKE to believe more than prove and they aren't great experimenters from what I've seen.
In short, I think modern mathematicians are trained wrong.
And the way that is dramatically evident is that they put forward a system that is being used to protect your information and mine, as well as millions of people worldwide that can be explained to be flawed with only a tad bit of information theory.
How you train students can decide how well they think and that determines what they can discover.
A physics student could figure this out.
Math students might never have.
[A reply to someone who asked which was James' excuse for not testing you method on RSA-sized composites.]
Information theory is in the domain of physicists. So it is my hope that it is less easy for the math community to try and hide something really basic by using trivial taunts.
Physicists who just never pondered limiting solutions by using residues modulo multiple primes can now look at how easy it is with my T = 9 mod 11 and T = 2 mod 13 example, where T = 119, is the first positive integer that will work.
As you limit the target you limit its factors so information is wrapped up in there SOMEWHERE.
Now physicists can then say to themselves, it's the mathematicians area and walk away, but if the mathematicians DID screw up here, then a massive financial collapse created by the demise of this system grabs the physicists along with everyone else.
And they were warned, so it's not like later they can just say, oh, we didn't want to step over academic lines and shrug to themselves.
They will feel the kick in the gut of having the knowledge and not using it to save themselves, their loved ones or their countries just because of medieval academic conventions, when cross-discipline should rule the world.
If the math people screw up, the physics people should help them, not just throw up their hands and say, not my area.
# posted by James Harris @ 21:31 
