JSH: This factoring thing is scary
in [Cryptography]
|
Prev: My view on factoring problem situation
Next: Factoring numbers with boolean algebra: public domain source code
From: JSH on 5 Nov 2009 21:29 On Nov 4, 6:53 pm, JSH <jst...(a)gmail.com> wrote: > You people need to wake up. I'm telling you the underlying math is > EASY. It's a technique to solve quadratic residues modulo N. > > If you think it's not possible then use all of your mathematical > training to explain the second example: > > So now let's do, k=9. So q = 11 mod 35, and T = 22 mod 35, so I can > try T = 57. > > The trivial factorization didn't work here, so I'll just jump to, f_1 > = 19, and f_2 = 3, so: > > k = 3^{-1}(19 + 3) mod 35 = 12(22) mod 35 = 264 mod 35 = 19 mod 35. > > 19^2 = 11 mod 35 > > so it worked! (It's so weird though watching it. Even though I know > the underlying mathematics it seems like magic.) Often f_1 or f_2 will BE the answer as above, so one way short-hand to beginning to understand the fundamental result is that given a quadratic residue q modulo N, and f_1*f_2 = 2q mod N, where f_1*f_2 does not equal 2q, either f_1 or f_2 will tend to be a solution to the quadratic residue. i.e. if k^2 = q mod N, then f_1 or f_2 will tend to equal k. What's interesting is that is a fundamental algebraic congruence result, apparently previously unknown. James Harris
From: Enrico on 5 Nov 2009 23:41 On Nov 4, 7:53 pm, JSH <jst...(a)gmail.com> wrote: > You people need to wake up. I'm telling you the underlying math is > EASY. It's a technique to solve quadratic residues modulo N. > > If you think it's not possible then use all of your mathematical > training to explain the second example: > > So now let's do, k=9. So q = 11 mod 35, and T = 22 mod 35, so I can > try T = 57. > > The trivial factorization didn't work here, so I'll just jump to, f_1 > = 19, and f_2 = 3, so: > > k = 3^{-1}(19 + 3) mod 35 = 12(22) mod 35 = 264 mod 35 = 19 mod 35. > > 19^2 = 11 mod 35 > > so it worked! (It's so weird though watching it. Even though I know > the underlying mathematics it seems like magic.) > > And that is a factoring example, as I know k=9 is a solution, so I > have > > 19^2 = 9^2 mod 35 > > so (19-9)(19+9) = 0 mod 35, so (10)(28) = 0 mod 35, and you pull 5 and > 7 as factors with a gcd. > > THAT is how you use a method for solving quadratic residues modulo N: > you find one quadratic residue and then go looking for another. > > Factoring problem solved. > > Happy one year birthday to the solution as it's a year old about now. > > James Harris ====================================================== I set up a routine to factor odd composites using the ideas you listed. The general idea is to get X^2 = Y^2 mod the target composite N. X = 1, 2, 3, ... Y is calculated from X^2 mod N using 3 ^ (-1) mod N and the sum of the factors of the result are used - to keep things simple, I just used 1 as the first factor. (Sloppy description - I assume you know your own stuff) The results seem to be periodic over intervals of N. Example: N = 299 = 13 * 23 A = 0, 1, 2, 3, ... X = 299 * A + 12, 58, 116, 137, 162, 183, 241, 287 Y = 196, 150, 1, 254, 254, 1, 150, 196 X^2 mod N = Y^2 mod N = 144, 75, 1, 231, 231, 1, 75, 144 GCD (X+Y, N) divides N GCD (X -Y, N) divides N Works. Practical ? Dunno. Enrico
From: Mark Murray on 6 Nov 2009 03:00 JSH wrote: > And I HATE ranting and posters just get on my case for ranting as they > ALREADY MADE UP THEIR MINDS!!! > > But it's so frustrating when you have the math and it's so easy. You're not so much ranting as whining. You're not getting your way, and just like a petulant 4-year-old, you throw a tantrum. With great inevitability you bring out SWJPAM and whine some more about that. Either do maths, or don't do maths. Either way, don't whine about it. If you choose to do maths, FINISH it CHECK it THEN publish it. "Checking" includes ensuring that it is correct, relevant and original (in more or less that order). "Relevant" includes ensuring it somehow adds to maths in a meaningful way and "Original" means it hasn't been done before. Put heart-and-soul into avoiding writing essays about how great you are, or whining about how the reception you got is not the mass adulation you expected. Try to learn how real mathematicians do this. M -- Mark Murray
From: rossum on 6 Nov 2009 09:06 On Thu, 5 Nov 2009 20:41:32 -0800 (PST), Enrico <ungernerik(a)aol.com> wrote: >On Nov 4, 7:53 pm, JSH <jst...(a)gmail.com> wrote: >> You people need to wake up. I'm telling you the underlying math is >> EASY. It's a technique to solve quadratic residues modulo N. >> >> If you think it's not possible then use all of your mathematical >> training to explain the second example: >> >> So now let's do, k=9. So q = 11 mod 35, and T = 22 mod 35, so I can >> try T = 57. >> >> The trivial factorization didn't work here, so I'll just jump to, f_1 >> = 19, and f_2 = 3, so: >> >> k = 3^{-1}(19 + 3) mod 35 = 12(22) mod 35 = 264 mod 35 = 19 mod 35. >> >> 19^2 = 11 mod 35 >> >> so it worked! (It's so weird though watching it. Even though I know >> the underlying mathematics it seems like magic.) >> >> And that is a factoring example, as I know k=9 is a solution, so I >> have >> >> 19^2 = 9^2 mod 35 >> >> so (19-9)(19+9) = 0 mod 35, so (10)(28) = 0 mod 35, and you pull 5 and >> 7 as factors with a gcd. >> >> THAT is how you use a method for solving quadratic residues modulo N: >> you find one quadratic residue and then go looking for another. >> >> Factoring problem solved. >> >> Happy one year birthday to the solution as it's a year old about now. >> >> James Harris > >====================================================== > >I set up a routine to factor odd composites using the ideas you >listed. >The general idea is to get X^2 = Y^2 mod the target composite N. > >X = 1, 2, 3, ... You need to check that GCD(X, N) = 0 here. GCD > 0 gives you a factor immediately. Trying to proceed will get you into all sorts of trouble. 10^2 mod 35 = 30, but 30 is not a quadratic residue because GCD(10, 35) = 5. rossum > >Y is calculated from X^2 mod N using 3 ^ (-1) mod N and the sum of the >factors of the result are used - to keep things simple, I just used 1 >as >the first factor. (Sloppy description - I assume you know your own >stuff) > >The results seem to be periodic over intervals of N. > >Example: >N = 299 = 13 * 23 >A = 0, 1, 2, 3, ... > >X = 299 * A + 12, 58, 116, 137, 162, 183, 241, 287 >Y = 196, 150, 1, 254, 254, 1, 150, 196 > >X^2 mod N = Y^2 mod N = 144, 75, 1, 231, 231, 1, 75, 144 > >GCD (X+Y, N) divides N >GCD (X -Y, N) divides N > >Works. Practical ? Dunno. > > > Enrico
From: Arturo Magidin on 6 Nov 2009 11:32
On Nov 6, 8:06 am, rossum <rossu...(a)coldmail.com> wrote: > On Thu, 5 Nov 2009 20:41:32 -0800 (PST), Enrico <ungerne...(a)aol.com> > wrote: > > > > >I set up a routine to factor odd composites using the ideas you > >listed. > >The general idea is to get X^2 = Y^2 mod the target composite N. > > >X = 1, 2, 3, ... > > You need to check that GCD(X, N) = 0 here. GCD(a,b) = 0 if and only if a=b=0, so no, he does not have to check that. > GCD > 0 gives you a factor > immediately. GCD(X,N) always gives you a factor of N; however, for it to be a *nontrivial* factor, you ned to check 1 < GCD(X,N) < n. -- ArturO Magidin |