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 7 Nov 2009 21:46 On Nov 7, 4:26 pm, Enrico <ungerne...(a)aol.com> wrote: > 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? You don't. That result simply explains why you only need to check one trivial factorization. Though it also does tell you that you should only use any particular residues for f_1 and f_2 once. > As N gets larger than 35, the list of quadratic residues gets > unmanagably long. > > Enrico You decided to only check trivial factorizations so you had f_1 = 1. YOU decided. Don't ask me why you decided to do that thing, but you did. Mathematically that runs into the reality that if a trivial factorization will work, the very first one you check will work. I simply corrected you. The method is probabilistic. There is NO reason to ever check to see if 2q - f_1^2 is a quadratic residue modulo N, except curiosity. But that guarantee helps people to understand the power of this method. It has an absolute check. If 2q - f_1^2 is a quadratic residue modulo N, then it WILL work. One thing that's important here is the reality of the denial in the face of a fascinating method which actually has some extremely intriguing mathematics associated with it! My point is that many of you rip on and insult other people with the absolute belief that they are worthless and their work is worthless in a CLASS WAR. You feel some people are a second class in comparison to yourselves. So to you these peasants aren't capable of important work so you decide their research isn't important and here you are foot-dragging with a powerful method! You are nothing more than wannabe royalty. I'm simply proving it in a dramatic way. You're simply throwbacks to a medieval age, who have your own dreams of ruling the world as a dominant class with people like me beneath your feet. Which is why you lie about math. James Harris
From: Enrico on 7 Nov 2009 22:58 On Nov 7, 7:46 pm, JSH <jst...(a)gmail.com> wrote: > On Nov 7, 4:26 pm, Enrico <ungerne...(a)aol.com> wrote: > > > 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? > > You don't. That result simply explains why you only need to check one > trivial factorization. > > Though it also does tell you that you should only use any particular > residues for f_1 and f_2 once. > > > As N gets larger than 35, the list of quadratic residues gets > > unmanagably long. > > > Enrico > > You decided to only check trivial factorizations so you had f_1 = 1. > YOU decided. Don't ask me why you decided to do that thing, but you > did. > > Mathematically that runs into the reality that if a trivial > factorization will work, the very first one you check will work. > > I simply corrected you. > > The method is probabilistic. There is NO reason to ever check to see > if 2q - f_1^2 is a quadratic residue modulo N, except curiosity. > > But that guarantee helps people to understand the power of this > method. It has an absolute check. > > If 2q - f_1^2 is a quadratic residue modulo N, then it WILL work. > > One thing that's important here is the reality of the denial in the > face of a fascinating method which actually has some extremely > intriguing mathematics associated with it! > > My point is that many of you rip on and insult other people with the > absolute belief that they are worthless and their work is worthless in > a CLASS WAR. You feel some people are a second class in comparison to > yourselves. > > So to you these peasants aren't capable of important work so you > decide their research isn't important and here you are foot-dragging > with a powerful method! > > You are nothing more than wannabe royalty. > > I'm simply proving it in a dramatic way. You're simply throwbacks to > a medieval age, who have your own dreams of ruling the world as a > dominant class with people like me beneath your feet. > > Which is why you lie about math. > > James Harris ===================================================== > > Mathematically that runs into the reality that if a trivial > factorization will work, the very first one you check will work. > This is not true. A trivial factorization will always work on any odd composite N coprime to 3. *** eventually ***, NEVER on the first one I check. How do _you_ select "the very first one you check" ? I start at x=1 and increment by 1 for each iteration. I find R = X^2 mod N 2 * R + N factors as 1 and 2 * R + N, so f1 + f2 = 1 + 2 * R + N Multiply by 3^-1 mod N (f1 + f2) * [3^-1 mod N] Y = ((f1 + f2) * [3^-1 mod N]) mod N then check Y^2 mod N to see if it equals X ^2 mod N If they are equal, then the factors of N will split between (X+Y) mod N and (X-Y) mod N Enrico
From: JSH on 7 Nov 2009 23:19 On Nov 7, 7:58 pm, Enrico <ungerne...(a)aol.com> wrote: > On Nov 7, 7:46 pm, JSH <jst...(a)gmail.com> wrote: > > > On Nov 7, 4:26 pm, Enrico <ungerne...(a)aol.com> wrote: > > > > 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? > > > You don't. That result simply explains why you only need to check one > > trivial factorization. > > > Though it also does tell you that you should only use any particular > > residues for f_1 and f_2 once. > > > > As N gets larger than 35, the list of quadratic residues gets > > > unmanagably long. > > > > Enrico > > > You decided to only check trivial factorizations so you had f_1 = 1. > > YOU decided. Don't ask me why you decided to do that thing, but you > > did. > > > Mathematically that runs into the reality that if a trivial > > factorization will work, the very first one you check will work. > > > I simply corrected you. > > > The method is probabilistic. There is NO reason to ever check to see > > if 2q - f_1^2 is a quadratic residue modulo N, except curiosity. > > > But that guarantee helps people to understand the power of this > > method. It has an absolute check. > > > If 2q - f_1^2 is a quadratic residue modulo N, then it WILL work. > > > One thing that's important here is the reality of the denial in the > > face of a fascinating method which actually has some extremely > > intriguing mathematics associated with it! > > > My point is that many of you rip on and insult other people with the > > absolute belief that they are worthless and their work is worthless in > > a CLASS WAR. You feel some people are a second class in comparison to > > yourselves. > > > So to you these peasants aren't capable of important work so you > > decide their research isn't important and here you are foot-dragging > > with a powerful method! > > > You are nothing more than wannabe royalty. > > > I'm simply proving it in a dramatic way. You're simply throwbacks to > > a medieval age, who have your own dreams of ruling the world as a > > dominant class with people like me beneath your feet. > > > Which is why you lie about math. > > > James Harris > > ===================================================== > > > > > Mathematically that runs into the reality that if a trivial > > factorization will work, the very first one you check will work. > > This is not true. Yes, it is. if 2q - f_1^2 is NOT a quadratic residue modulo N, then you won't get the correct answer for k. > A trivial factorization will always work on any odd composite N No. It will not. My guess is you're confused on the details. If you're looking for q, such that q is a quadratic residue modulo N, then you find f_1 and f_2 such that f_1*f_2 = 2q + jN, where j is a nonzero integer. With k^2 = q mod N, you will get k, from k = 3^{-1}(f_1 + f_2) iff 2q - f_1^2 is a quadratic residue modulo N. If you look only at f_1*f_2 where you have a trivial factorization, then f_1 will not change, so if it doesn't work once, it will NEVER work. (f_1 and f_2 are interchangeable) > coprime to 3. *** eventually ***, NEVER on the first one I check. I have given an example where the trivial factorization DID work on the first one I checked. > How do _you_ select "the very first one you check" ? I use 2q + N. j=1. I GAVE an example. > I start at x=1 and increment by 1 for each iteration. > I find R = X^2 mod N > 2 * R + N factors as 1 and 2 * R + N, so > f1 + f2 = 1 + 2 * R + N > Multiply by 3^-1 mod N > (f1 + f2) * [3^-1 mod N] > Y = ((f1 + f2) * [3^-1 mod N]) mod N > then check Y^2 mod N to see if it equals X ^2 mod N > > If they are equal, then the factors of N will split between > (X+Y) mod N and (X-Y) mod N > > Enrico I've explained the mathematics to you. It is a mathematical absolute-- unless I'm wrong--that 2q - f_1^2 MUST be a quadratic residue modulo N for you to get the correct, such that k^2 = q mod N. If that's wrong then my research is in serious trouble! If a counterexample exists it should be easy for you to show one. Oh, sorry but I have to add that I have seen cases where when faced with absolute mathematics, people just kind of, make things up. It's another way you can have mathematical proof and not get acceptance as people claim problems that do not exist. It is ANOTHER reason I went to the factoring problem, as with my other research posters clearly understood that making things up could work to prevent widespread knowledge of and acceptance of the research! But it won't here. Yes, posters can deny the mathematics if they wish, but it will not change anything. It is your choice. If you all as a group wish to leave this mathematics freely floating out there on the hopes no one will notice then you are allowed to so act. You've done so for a year. Maybe you wish another? Remember your brain is what controls you. Reality is so much about perception. You will tell yourselves whatever you need to hear, but it does not mean that reality will not hold you accountable! Fantasy cannot save you. You are not royalty. You never were. You are not inherently better than anyone else. You are not noble blood. Let go of the fantasy!!! Let go. James Harris
From: Enrico on 8 Nov 2009 00:11 On Nov 7, 9:19 pm, JSH <jst...(a)gmail.com> wrote: > On Nov 7, 7:58 pm, Enrico <ungerne...(a)aol.com> wrote: > > > > > > > On Nov 7, 7:46 pm, JSH <jst...(a)gmail.com> wrote: > > > > On Nov 7, 4:26 pm, Enrico <ungerne...(a)aol.com> wrote: > > > > > 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? > > > > You don't. That result simply explains why you only need to check one > > > trivial factorization. > > > > Though it also does tell you that you should only use any particular > > > residues for f_1 and f_2 once. > > > > > As N gets larger than 35, the list of quadratic residues gets > > > > unmanagably long. > > > > > Enrico > > > > You decided to only check trivial factorizations so you had f_1 = 1.. > > > YOU decided. Don't ask me why you decided to do that thing, but you > > > did. > > > > Mathematically that runs into the reality that if a trivial > > > factorization will work, the very first one you check will work. > > > > I simply corrected you. > > > > The method is probabilistic. There is NO reason to ever check to see > > > if 2q - f_1^2 is a quadratic residue modulo N, except curiosity. > > > > But that guarantee helps people to understand the power of this > > > method. It has an absolute check. > > > > If 2q - f_1^2 is a quadratic residue modulo N, then it WILL work. > > > > One thing that's important here is the reality of the denial in the > > > face of a fascinating method which actually has some extremely > > > intriguing mathematics associated with it! > > > > My point is that many of you rip on and insult other people with the > > > absolute belief that they are worthless and their work is worthless in > > > a CLASS WAR. You feel some people are a second class in comparison to > > > yourselves. > > > > So to you these peasants aren't capable of important work so you > > > decide their research isn't important and here you are foot-dragging > > > with a powerful method! > > > > You are nothing more than wannabe royalty. > > > > I'm simply proving it in a dramatic way. You're simply throwbacks to > > > a medieval age, who have your own dreams of ruling the world as a > > > dominant class with people like me beneath your feet. > > > > Which is why you lie about math. > > > > James Harris > > > ===================================================== > > > > Mathematically that runs into the reality that if a trivial > > > factorization will work, the very first one you check will work. > > > This is not true. > > Yes, it is. if 2q - f_1^2 is NOT a quadratic residue modulo N, then > you won't get the correct answer for k. > > > A trivial factorization will always work on any odd composite N > > No. It will not. > > My guess is you're confused on the details. > > If you're looking for q, such that q is a quadratic residue modulo N, > then you find f_1 and f_2 such that f_1*f_2 = 2q + jN, where j is a > nonzero integer. > > With k^2 = q mod N, you will get k, from k = 3^{-1}(f_1 + f_2) iff 2q > - f_1^2 is a quadratic residue modulo N. > > If you look only at f_1*f_2 where you have a trivial factorization, > then f_1 will not change, so if it doesn't work once, it will NEVER > work. (f_1 and f_2 are interchangeable) > > > coprime to 3. *** eventually ***, NEVER on the first one I check. > > I have given an example where the trivial factorization DID work on > the first one I checked. > > > How do _you_ select "the very first one you check" ? > > I use 2q + N. j=1. > > I GAVE an example. > > > I start at x=1 and increment by 1 for each iteration. > > I find R = X^2 mod N > > 2 * R + N factors as 1 and 2 * R + N, so > > f1 + f2 = 1 + 2 * R + N > > Multiply by 3^-1 mod N > > (f1 + f2) * [3^-1 mod N] > > Y = ((f1 + f2) * [3^-1 mod N]) mod N > > then check Y^2 mod N to see if it equals X ^2 mod N > > > If they are equal, then the factors of N will split between > > (X+Y) mod N and (X-Y) mod N > > > Enrico > > I've explained the mathematics to you. It is a mathematical absolute-- > unless I'm wrong--that 2q - f_1^2 MUST be a quadratic residue modulo N > for you to get the correct, such that k^2 = q mod N. > > If that's wrong then my research is in serious trouble! If a > counterexample exists it should be easy for you to show one. > > Oh, sorry but I have to add that I have seen cases where when faced > with absolute mathematics, people just kind of, make things up. It's > another way you can have mathematical proof and not get acceptance as > people claim problems that do not exist. > > It is ANOTHER reason I went to the factoring problem, as with my other > research posters clearly understood that making things up could work > to prevent widespread knowledge of and acceptance of the research! > > But it won't here. Yes, posters can deny the mathematics if they > wish, but it will not change anything. > > It is your choice. If you all as a group wish to leave this > mathematics freely floating out there on the hopes no one will notice > then you are allowed to so act. > > You've done so for a year. Maybe you wish another? > > Remember your brain is what controls you. Reality is so much about > perception. You will tell yourselves whatever you need to hear, but > it does not mean that reality will not hold you accountable! > > Fantasy cannot save you. > > You are not royalty. You never were. You are not inherently better > than anyone else. > > You are not noble blood. Let go of the fantasy!!! Let go. > > James Harris- Hide quoted text - > > - Show quoted text - ================================================ >> How do _you_ select "the very first one you check" ? >I use 2q + N. j=1. Terrific. How do you select the first q without using the factors of N ? (What you call q is what I call X^2 mod N) Remember - I've got this whole thing on a speadsheet. Conditional color coding to make the solutions really obvious. I can type in any N and see the results instantly. Most importantly - it duplicates your results on the few examples you provided. Experimental results trump theory unless the experiment can be shown to be not a test of the theory. You'll want that second option, which is why I gave you my algorithm. Enrico
From: JSH on 8 Nov 2009 00:55
On Nov 7, 9:11 pm, Enrico <ungerne...(a)aol.com> wrote: > On Nov 7, 9:19 pm, JSH <jst...(a)gmail.com> wrote: <deleted> > > > > Mathematically that runs into the reality that if a trivial > > > > factorization will work, the very first one you check will work. > > > > This is not true. > > > Yes, it is. if 2q - f_1^2 is NOT a quadratic residue modulo N, then > > you won't get the correct answer for k. > > > > A trivial factorization will always work on any odd composite N > > > No. It will not. > > > My guess is you're confused on the details. > > > If you're looking for q, such that q is a quadratic residue modulo N, > > then you find f_1 and f_2 such that f_1*f_2 = 2q + jN, where j is a > > nonzero integer. > > > With k^2 = q mod N, you will get k, from k = 3^{-1}(f_1 + f_2) iff 2q > > - f_1^2 is a quadratic residue modulo N. > > > If you look only at f_1*f_2 where you have a trivial factorization, > > then f_1 will not change, so if it doesn't work once, it will NEVER > > work. (f_1 and f_2 are interchangeable) > > > > coprime to 3. *** eventually ***, NEVER on the first one I check. > > > I have given an example where the trivial factorization DID work on > > the first one I checked. > > > > How do _you_ select "the very first one you check" ? > > > I use 2q + N. j=1. > > > I GAVE an example. > > > > I start at x=1 and increment by 1 for each iteration. > > > I find R = X^2 mod N > > > 2 * R + N factors as 1 and 2 * R + N, so > > > f1 + f2 = 1 + 2 * R + N > > > Multiply by 3^-1 mod N > > > (f1 + f2) * [3^-1 mod N] > > > Y = ((f1 + f2) * [3^-1 mod N]) mod N > > > then check Y^2 mod N to see if it equals X ^2 mod N > > > > If they are equal, then the factors of N will split between > > > (X+Y) mod N and (X-Y) mod N > > > > Enrico > > > I've explained the mathematics to you. It is a mathematical absolute-- > > unless I'm wrong--that 2q - f_1^2 MUST be a quadratic residue modulo N > > for you to get the correct, such that k^2 = q mod N. > > > If that's wrong then my research is in serious trouble! If a > > counterexample exists it should be easy for you to show one. > > > Oh, sorry but I have to add that I have seen cases where when faced > > with absolute mathematics, people just kind of, make things up. It's > > another way you can have mathematical proof and not get acceptance as > > people claim problems that do not exist. > > > It is ANOTHER reason I went to the factoring problem, as with my other > > research posters clearly understood that making things up could work > > to prevent widespread knowledge of and acceptance of the research! > > > But it won't here. Yes, posters can deny the mathematics if they > > wish, but it will not change anything. > > > It is your choice. If you all as a group wish to leave this > > mathematics freely floating out there on the hopes no one will notice > > then you are allowed to so act. > > > You've done so for a year. Maybe you wish another? > > > Remember your brain is what controls you. Reality is so much about > > perception. You will tell yourselves whatever you need to hear, but > > it does not mean that reality will not hold you accountable! > > > Fantasy cannot save you. > > > You are not royalty. You never were. You are not inherently better > > than anyone else. > > > You are not noble blood. Let go of the fantasy!!! Let go. > > > James Harris- Hide quoted text - > > > - Show quoted text - > > ================================================ > > >> How do _you_ select "the very first one you check" ? > >I use 2q + N. j=1. > > Terrific. > > How do you select the first q without using > the factors of N ? That's trivial. Just pick a quadratic residue. I like to use the first non-perfect square quadratic residue, but check to be sure that it doesn't share prime factors with N. Like with my example I used 8^2 = 29 mod 35 because while 7^2 = 14 mod 35, is a non-perfect square 14 is not coprime to 35. > (What you call q is what I call X^2 mod N) Yeah the quadratic residue. I got that part. > Remember - I've got this whole thing on a speadsheet. Ok. > Conditional color coding to make the solutions Sounds really funky, and the significance escapes me. > really obvious. I can type in any N and see the results > instantly. Most importantly - it duplicates your results > on the few examples you provided. Including k=9, with N=35, gives q = 11, as 81 = 11 mod 35? But the trivial factorization didn't work, so I used the non-trivial factorization. From what I saw you're only using the trivial factorization, so how would you replicate an example using a non-trivial one? > Experimental results trump theory unless the experiment But not mathematical proof. The concept of mathematical proof seems to be escaping you. It's not like just having a theory. A mathematical proof trumps all else. If an argument fails it was not a proof!!! > can be shown to be not a test of the theory. You'll want > that second option, which is why I gave you my algorithm. > > Enrico I like getting notice of errors. If I yell "mathematical proof" and you can show a counterexample then I don't have a proof. And in finding out why, I learn something. Here it's an easy process and you keep doing weird stuff, like only doing trivial factorizations. My take on what you think the argument is, is that you will keep shifting q, the quadratic residue, and you're trying to say you always can get to one that will work, with the trivial factorization. So, you're trying to test this with only the trivial factorization, which should only work with diminishing probability as the number of quadratic residues rises, which would confirm a deep internal need you may have for this to work less the larger N is. So you gamed it. You put in your own arbitrary thing--not what I said to do--which I can explain easily will give diminishing returns as N increases in size. Do you understand why? It's trivial to explain. James Harris |