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: Enrico on 6 Nov 2009 16:04 On Nov 6, 7:06 am, rossum <rossu...(a)coldmail.com> wrote: > On Thu, 5 Nov 2009 20:41:32 -0800 (PST), Enrico <ungerne...(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- Hide quoted text - > > - Show quoted text -- Hide quoted text - > > - Show quoted text - ============================================ Remember, I'm testing James' method to see how it works. I started with the ideal scene where: GCD (X+Y, N) divides N GCD (X -Y, N) divides N With N a product of 2 primes, there seems to be 8 cases repeating with period = N There are also many cases where only one of the pair of GCD's gives a factor - that works also. For JSH's N = 35, (that's an upgrade from the 15 of old) both GCD's fail 10 out of 35 times. That means at least one of the GCD's will find a factor 25 out of 35 times -> 71 % of the time. Trouble is, James stops there and celebrates. (Or rants) As the size of the prime factors and the difference between them increases, the odds of finding at least one factor drops fast and seems to approach something like trial division using GDC's. Still, the method is interesting - seems to be a bit of Pollard - Rho in there. Maybe. Its interesting to put a prime in for N and see the pattern where it comes up. Enrico
From: rossum on 6 Nov 2009 17:35 On Fri, 6 Nov 2009 08:32:29 -0800 (PST), Arturo Magidin <magidin(a)member.ams.org> wrote: >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. Whoops. 1 Remove brain. 2 Wash brain. 3 Dry brain. 4 Reinsert brain. Ahh, much better. Should have been GCD(X, N) = 1 of course. Thanks for the correction. > >> GCD > 0 gives you a factor >> immediately. GCD > 1 and GCD < N > >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. Yes, that is what I meant to say, but my brain decided not to cooperate. Naughty brain! rossum
From: JSH on 6 Nov 2009 20:55 On Nov 6, 1:04 pm, Enrico <ungerne...(a)aol.com> wrote: > On Nov 6, 7:06 am, rossum <rossu...(a)coldmail.com> wrote: > > > > > > > On Thu, 5 Nov 2009 20:41:32 -0800 (PST), Enrico <ungerne...(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- Hide quoted text - > > > - Show quoted text -- Hide quoted text - > > > - Show quoted text - > > ============================================ > > Remember, I'm testing James' method to see how it works. > I started with the ideal scene where: > > GCD (X+Y, N) divides N > GCD (X -Y, N) divides N > > With N a product of 2 primes, there seems to be 8 cases > repeating with period = N > > There are also many cases where only one of the pair > of GCD's gives a factor - that works also. > > For JSH's N = 35, (that's an upgrade from the 15 of old) > both GCD's fail 10 out of 35 times. > > That means at least one of the GCD's will find a factor > 25 out of 35 times -> 71 % of the time. > > Trouble is, James stops there and celebrates. (Or rants) Nope. I stopped BEFORE using N=35, as I only did that recently to demonstrate with a composite. So I actually celebrated last year before I'd ever even done a composite N, at all. My original posting on this subject on my blog actually had an example with N=19. So then, what could possibly have made me so confident without having worked a SINGLE composite example? > As the size of the prime factors and the difference > between them increases, the odds of finding at least > one factor drops fast and seems to approach something > like trial division using GDC's. Then no worries!!! > Still, the method is interesting - seems to be a bit of > Pollard - Rho in there. Maybe. Its interesting to put > a prime in for N and see the pattern where it comes up. > > Enrico Nope, not Pollard - Rho. There's a linking between two factorizations. You're leveraging one number to factor another. You could say, the one number is helping you with information about the other. It can do that because it is intimately connected to the other number. It's actually very beautiful mathematics. Curiosity is a good thing, as without it you'll never understand the result. It'll just be this weird mathematical mystery which you think fails with increasing size of the number. But why? What mathematical reason would there be beyond your intuition that the bigger the number the harder to factor? Any guesses? James Harris
From: Enrico on 6 Nov 2009 21:49 On Nov 6, 6:55 pm, JSH <jst...(a)gmail.com> wrote: > On Nov 6, 1:04 pm, Enrico <ungerne...(a)aol.com> wrote: > > > > > > > On Nov 6, 7:06 am, rossum <rossu...(a)coldmail.com> wrote: > > > > On Thu, 5 Nov 2009 20:41:32 -0800 (PST), Enrico <ungerne...(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- Hide quoted text - > > > > - Show quoted text -- Hide quoted text - > > > > - Show quoted text - > > > ============================================ > > > Remember, I'm testing James' method to see how it works. > > I started with the ideal scene where: > > > GCD (X+Y, N) divides N > > GCD (X -Y, N) divides N > > > With N a product of 2 primes, there seems to be 8 cases > > repeating with period = N > > > There are also many cases where only one of the pair > > of GCD's gives a factor - that works also. > > > For JSH's N = 35, (that's an upgrade from the 15 of old) > > both GCD's fail 10 out of 35 times. > > > That means at least one of the GCD's will find a factor > > 25 out of 35 times -> 71 % of the time. > > > Trouble is, James stops there and celebrates. (Or rants) > > Nope. I stopped BEFORE using N=35, as I only did that recently to > demonstrate with a composite. > > So I actually celebrated last year before I'd ever even done a > composite N, at all. > > My original posting on this subject on my blog actually had an example > with N=19. > > So then, what could possibly have made me so confident without having > worked a SINGLE composite example? > > > As the size of the prime factors and the difference > > between them increases, the odds of finding at least > > one factor drops fast and seems to approach something > > like trial division using GDC's. > > Then no worries!!! > > > Still, the method is interesting - seems to be a bit of > > Pollard - Rho in there. Maybe. Its interesting to put > > a prime in for N and see the pattern where it comes up. > > > Enrico > > Nope, not Pollard - Rho. There's a linking between two > factorizations. You're leveraging one number to factor another. > > You could say, the one number is helping you with information about > the other. > > It can do that because it is intimately connected to the other number. > > It's actually very beautiful mathematics. > > Curiosity is a good thing, as without it you'll never understand the > result. It'll just be this weird mathematical mystery which you think > fails with increasing size of the number. > > But why? What mathematical reason would there be beyond your > intuition that the bigger the number the harder to factor? > > Any guesses? > > James Harris- Hide quoted text - > > - Show quoted text - =============================================== > But why? What mathematical reason would there be beyond your > intuition that the bigger the number the harder to factor? Direct observation of test results. with N = 35, the factors 5 and 7 are swarming all over the page. I have to look carefully to find cases where no factor is found. If I increase the value of one factor, leaving the other one small, the small one still occurs with the same density. The large one is more thinly distributed and has to be searched for. If I make both factors larger, both occur less frequently and have to be fished for. The bigger I make them, the more thinly they are distributed. The trend is obvious. However, I'm not done yet - there are some more ways to tweak this thing that I thought were impractical when I started. Enrico
From: JSH on 6 Nov 2009 21:57
On Nov 6, 6:49 pm, Enrico <ungerne...(a)aol.com> wrote: > On Nov 6, 6:55 pm, JSH <jst...(a)gmail.com> wrote: > > > > > > > On Nov 6, 1:04 pm, Enrico <ungerne...(a)aol.com> wrote: > > > > On Nov 6, 7:06 am, rossum <rossu...(a)coldmail.com> wrote: > > > > > On Thu, 5 Nov 2009 20:41:32 -0800 (PST), Enrico <ungerne...(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- Hide quoted text - > > > > > - Show quoted text -- Hide quoted text - > > > > > - Show quoted text - > > > > ============================================ > > > > Remember, I'm testing James' method to see how it works. > > > I started with the ideal scene where: > > > > GCD (X+Y, N) divides N > > > GCD (X -Y, N) divides N > > > > With N a product of 2 primes, there seems to be 8 cases > > > repeating with period = N > > > > There are also many cases where only one of the pair > > > of GCD's gives a factor - that works also. > > > > For JSH's N = 35, (that's an upgrade from the 15 of old) > > > both GCD's fail 10 out of 35 times. > > > > That means at least one of the GCD's will find a factor > > > 25 out of 35 times -> 71 % of the time. > > > > Trouble is, James stops there and celebrates. (Or rants) > > > Nope. I stopped BEFORE using N=35, as I only did that recently to > > demonstrate with a composite. > > > So I actually celebrated last year before I'd ever even done a > > composite N, at all. > > > My original posting on this subject on my blog actually had an example > > with N=19. > > > So then, what could possibly have made me so confident without having > > worked a SINGLE composite example? > > > > As the size of the prime factors and the difference > > > between them increases, the odds of finding at least > > > one factor drops fast and seems to approach something > > > like trial division using GDC's. > > > Then no worries!!! > > > > Still, the method is interesting - seems to be a bit of > > > Pollard - Rho in there. Maybe. Its interesting to put > > > a prime in for N and see the pattern where it comes up. > > > > Enrico > > > Nope, not Pollard - Rho. There's a linking between two > > factorizations. You're leveraging one number to factor another. > > > You could say, the one number is helping you with information about > > the other. > > > It can do that because it is intimately connected to the other number. > > > It's actually very beautiful mathematics. > > > Curiosity is a good thing, as without it you'll never understand the > > result. It'll just be this weird mathematical mystery which you think > > fails with increasing size of the number. > > > But why? What mathematical reason would there be beyond your > > intuition that the bigger the number the harder to factor? > > > Any guesses? > > > James Harris- Hide quoted text - > > > - Show quoted text - > > =============================================== > > > But why? What mathematical reason would there be beyond your > > intuition that the bigger the number the harder to factor? > > Direct observation of test results. > > with N = 35, the factors 5 and 7 are swarming all over the page. > I have to look carefully to find cases where no factor is found. > > If I increase the value of one factor, leaving the other one small, > the small one still occurs with the same density. The large one > is more thinly distributed and has to be searched for. > > If I make both factors larger, both occur less frequently and have > to be fished for. The bigger I make them, the more thinly they are > distributed. The trend is obvious. > > However, I'm not done yet - there are some more ways to tweak > this thing that I thought were impractical when I started. > > Enrico The algorithm has to work if: T - f_1^2 is a quadratic residue modulo N. But it will NOT work if that is not a quadratic residue modulo N. With that information you should be able to fix your program as your conclusions are wrong. Size of N is irrelevant to the algorithm. It only cares at best about the number of prime factors of N. Nothing else. Notice that if the trivial factorization does NOT work on the first try then it will not work for any T, as f_1 mod N will NOT change, so the key relation will never hold. James Harris |