Tuesday, February 05, 2008
JSH: Factoring problem and prime intersection
Remarkably the much vaunted factoring problem can be understood as requiring an easy solution by considering some very simple mathematics, like consider
T = r_1 mod p_1
where p_1 is a prime, and r_1 is, of course then the residue of that prime modulo T, where T is the target composite. And now add another prime:
T = r_1 mod p_2
and add a series of primes, and what must happen?
You must constrain T to a minimum value.
For instance, consider T = 9 mod 11, and T = 2 mod 13.
You can use the Chinese Remainder theorem, or the little congruence result that I thought I had discovered and found was old news:
f_1 = r_1 + j*n_1 mod n_1*n_2
where j = (r_2 - r_1)*n_1^{-1} mod n_2.
So with n_1 = 11, n_2 = 13, and r_1 = 9 and r_2 = 2, I have
f_1 = 9 + 11j mod 143, where j = (2 - 9)*11^{-1} mod 13 = (-7)(6) mod 13 = 10 mod 13, so
f_1 = 9 + 11(10) mod 143 = 119 mod 143
and yes, I was thinking of T=119 as my target and somehow the math knew!
Ok, it was simply an intersection of results from two different primes that constrained T to my target when the product of the primes exceeded that target.
So wrapped up in those residues modulo each prime is information about the target composite, which constrains it and therefore its factors are constrained as well!!!
Therefore it must be the case that a method exists to find those factors by considering residues modulo multiple primes.
The intersection of primes forces T and therefore forces factors of T.
IN case you're wondering to tackle an RSA public key you'd need less than 200 primes, and could probably do it with the primes from 100 to 1000 as there are 143 of them, and for any target T, the maximum number of primes needed m, is less than m such that T/m! < 1.
So yeah 143! is how big of a number you can tackle with just the primes from 100 to 1000.
ONCE you know it must be there then looking for it is easy, and, um, I tossed the answer on my math blog, but I find it interesting that the factoring problem is so easily solved, and so easily explained to be easy to solve as it's kind of weird. (I challenge readers to try and figure it out on their own though once you realize it must be there and if you give up, just read my math blog.)
But maybe it's about point of view. If you know that there MUST be a simple answer then it's just a matter of finding it, but if you THINK that it's a hard problem then you won't look for a simple answer!!!
And that answer is simple to us today as we have computers.
Gauss would have shrugged at it as being too inelegant, as it's like brute force, and takes a lot of annoying effort by hand though he did do a lot by hand—as he had no choice—but I don't know. I don't know. Who knows? Maybe buried in some text somewhere one of the past mathematical greats DID just toss out the answer as this trivial thing that was too tedious to implement during their times.
T = r_1 mod p_1
where p_1 is a prime, and r_1 is, of course then the residue of that prime modulo T, where T is the target composite. And now add another prime:
T = r_1 mod p_2
and add a series of primes, and what must happen?
You must constrain T to a minimum value.
For instance, consider T = 9 mod 11, and T = 2 mod 13.
You can use the Chinese Remainder theorem, or the little congruence result that I thought I had discovered and found was old news:
f_1 = r_1 + j*n_1 mod n_1*n_2
where j = (r_2 - r_1)*n_1^{-1} mod n_2.
So with n_1 = 11, n_2 = 13, and r_1 = 9 and r_2 = 2, I have
f_1 = 9 + 11j mod 143, where j = (2 - 9)*11^{-1} mod 13 = (-7)(6) mod 13 = 10 mod 13, so
f_1 = 9 + 11(10) mod 143 = 119 mod 143
and yes, I was thinking of T=119 as my target and somehow the math knew!
Ok, it was simply an intersection of results from two different primes that constrained T to my target when the product of the primes exceeded that target.
So wrapped up in those residues modulo each prime is information about the target composite, which constrains it and therefore its factors are constrained as well!!!
Therefore it must be the case that a method exists to find those factors by considering residues modulo multiple primes.
The intersection of primes forces T and therefore forces factors of T.
IN case you're wondering to tackle an RSA public key you'd need less than 200 primes, and could probably do it with the primes from 100 to 1000 as there are 143 of them, and for any target T, the maximum number of primes needed m, is less than m such that T/m! < 1.
So yeah 143! is how big of a number you can tackle with just the primes from 100 to 1000.
ONCE you know it must be there then looking for it is easy, and, um, I tossed the answer on my math blog, but I find it interesting that the factoring problem is so easily solved, and so easily explained to be easy to solve as it's kind of weird. (I challenge readers to try and figure it out on their own though once you realize it must be there and if you give up, just read my math blog.)
But maybe it's about point of view. If you know that there MUST be a simple answer then it's just a matter of finding it, but if you THINK that it's a hard problem then you won't look for a simple answer!!!
And that answer is simple to us today as we have computers.
Gauss would have shrugged at it as being too inelegant, as it's like brute force, and takes a lot of annoying effort by hand though he did do a lot by hand—as he had no choice—but I don't know. I don't know. Who knows? Maybe buried in some text somewhere one of the past mathematical greats DID just toss out the answer as this trivial thing that was too tedious to implement during their times.
# posted by James Harris @ 20:54 
