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: Mark Murray on 7 Nov 2009 03:24 JSH wrote: > So then, what could possibly have made me so confident without having > worked a SINGLE composite example? Your usual arrogant hubris. > It's actually very beautiful mathematics. .... like this. M -- Mark Murray
From: Enrico on 7 Nov 2009 11:57 On Nov 6, 7:57 pm, JSH <jst...(a)gmail.com> wrote: > 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- Hide quoted text - > > - Show quoted text - ================================================ Did a retake on T = 2q +jN I've been using j = 1 only With additional values of j things work alot better. Enrico
From: JSH on 7 Nov 2009 12:42 On Nov 7, 8:57 am, Enrico <ungerne...(a)aol.com> wrote: > On Nov 6, 7:57 pm, JSH <jst...(a)gmail.com> wrote: > > > > > > > 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- Hide quoted text - > > > - Show quoted text - > > ================================================ > > Did a retake on T = 2q +jN > > I've been using j = 1 only Yeah I noticed that in your description, but if 2q - f_1^2 is NOT a quadratic residue modulo N, then you won't get a solution so only one trivial factorization need be checked. > With additional values of j things work alot better. > > Enrico Showing you the power of mathematical proof. Examples can only do so much, though they can help clarify because I only recently noticed that latest myself though it's in my research results where it's been for over a year. I just didn't realize the significance in this context until recently. Surrogate factoring is already large enough that most of the answers are buried somewhere in the equations. But even I get lost often on the details. IN any event, it's a beautiful little result. A fundamental relationship between solutions to quadratic residues, and factoring. James Harris
From: Mark Murray on 7 Nov 2009 17:39 JSH wrote: > Showing you the power of mathematical proof. Proof? Where is the theorem? M -- Mark Murray
From: Enrico on 7 Nov 2009 19:26
On Nov 7, 10:42 am, JSH <jst...(a)gmail.com> wrote: > On Nov 7, 8:57 am, Enrico <ungerne...(a)aol.com> wrote: > > > > > > > On Nov 6, 7:57 pm, JSH <jst...(a)gmail.com> wrote: > > > > 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- Hide quoted text - > > > > - Show quoted text - > > > ================================================ > > > Did a retake on T = 2q +jN > > > I've been using j = 1 only > > Yeah I noticed that in your description, but if 2q - f_1^2 is NOT a > quadratic residue modulo N, then you won't get a solution so only one > trivial factorization need be checked. > > > With additional values of j things work alot better. > > > Enrico > > Showing you the power of mathematical proof. > > Examples can only do so much, though they can help clarify because I > only recently noticed that latest myself though it's in my research > results where it's been for over a year. I just didn't realize the > significance in this context until recently. > > Surrogate factoring is already large enough that most of the answers > are buried somewhere in the equations. > > But even I get lost often on the details. > > IN any event, it's a beautiful little result. A fundamental > relationship between solutions to quadratic residues, and factoring. > > James Harris- Hide quoted text - > > - Show quoted text - ===================================================== > Yeah I noticed that in your description, but if 2q - f_1^2 is NOT a > quadratic residue modulo N, then you won't get a solution so only one > trivial factorization need be checked. One thing bothers me here - how do you test if a number is a quadratic residue modulo a composite N without knowing its prime factors first? As N gets larger than 35, the list of quadratic residues gets unmanagably long. Enrico |