JSH: Discrete log solution and degrees of freedom analysis
in [Math]
|
Prev: New Differential Equation website
Next: How Can ZFC/PA do much of Math - it Can't Even Prove PA isConsistent (EASY PROOF)
From: Tim Little on 2 Jul 2010 02:35 On 2010-07-01, big gus <invalid(a)invalid.com> wrote: > you are just not smart in Math. You have not shown me anything to > think that you are over 12 years. The only thing that lets me know that JSH is over 12 years old is that he has been posting to Usenet for more than 14 years. Certainly he hasn't shown much more than 12-year-old understanding of mathematics, about a 4-year-old's emotional maturity, and virtually no ability to learn (thus falling below any X-year-old grading). - Tim
From: Tim Little on 2 Jul 2010 04:58 On 2010-07-02, JSH <jstevh(a)gmail.com> wrote: > All but two of the factors are likely to be small primes like 2, 3 > or 5. Once again, you study only small examples and think for no reason at all that it generalises to large ones. For random numbers of RSA sizes, multiple large prime factors are very common. > If you know that with small prime factors, you still have a large > composite, it's likely to have only two prime factors. That's false. >> Let's go for a more interesting problem: >> 2^m = 1 mod 5123819881 > > And there you go again, putting up an example that requires a computer > program, where said program might be close to something that is > military grade. That's *nowhere near* a military grade problem. It's a toy, even a trivial toy. If you knew anything about the problem at all, you would know that and be able to whip up a program to solve it using ancient techniques (hundreds of years old) in microseconds. I know it's a toy from personal experience because I solved that size problem and quite a lot larger when I first read about RSA encryption in the Mathematical Recreations column from Scientific American as an adolescent. In fact anyone of education following Fermat could solve that problem with pencil and paper and a few hours. With a fairly pathetic "toy" computer (the sort that plugged into a TV and had rubber keys), that size problem took a small fraction of a second. Even *this* problem is a toy: 2^m = 1 mod 1130790155285048141425963293464787670791221272246438856673 6618041723006272113911. It might take more than a pocket calculator, and I couldn't have solved it back in high school, but it's still trivial by cryptographic standards and falls rapidly to modern algorithms running on a single CPU. Here's an example closer to "military grade" (which is still laughable, they won't be using anything as likely to be attacked as discrete logarithms): 2^m = 1 mod 5769755246236355631828697731617434392665694519686030207243 9351426386778483045201334567040107717371791127106134089756443448945761 2381768429426751583388320690162038512303628647681210662930989399578579 2261903733346902807570079121654405917626566867259441003953235429263177 0888183648551431764232326786062112132495957203076797326246447100384545 8186832791273916930559985135587563021738168656394574833313142577678531 6331174526758671749368759237344430668078314545297484794634067167489074 8758767535511343643205695428834833165862484932183154294204682326218098 8406219197587162963125534296794414357094150807602983435382561192130338 8164254329432594114321836160084529748148842358860656290047349132301763 6495577270184853193742469168693250831468874711181294215411468757143209 0649280997295560044312030237697989263764407403994617866912606446481204 7825237657471150408208497546417626519204361042207596617982582426809735 2526431459499298489257413469733379847163516023736917939508735174123344 2667059375676264316220438857866894757053478941356342333159616165236182 7065825819808536652315846457590842492380769726223147841782598433527209 0563853889111508574381601817691172512052294700794711192572815459774453 02418654538040123684798707. Do you see now why the earlier examples are all very obviously childish toy problems? Or do you have a delusion that 1200 digit problems are only 120 times as hard to solve as 10 digit problems? - Tim
From: Jesse F. Hughes on 2 Jul 2010 08:25 Tim Little <tim(a)little-possums.net> writes: > On 2010-07-01, big gus <invalid(a)invalid.com> wrote: >> you are just not smart in Math. You have not shown me anything to >> think that you are over 12 years. > > The only thing that lets me know that JSH is over 12 years old is that > he has been posting to Usenet for more than 14 years. > > Certainly he hasn't shown much more than 12-year-old understanding of > mathematics, about a 4-year-old's emotional maturity, and virtually no > ability to learn (thus falling below any X-year-old grading). Come on. The storylines he comes up with (the men with guns pursuing the brilliant but hapless researcher, the fight against "white collar welfare", the possibility that aliens put him here to observe humans) all suggest he's been immersed in popular American culture and devouring their movies for more than twelve years. -- "Even if a man has good parts, still, if he carries philosophy into later life, he is necessarily ignorant of all those things which a gentleman and a person of honor ought to know." --Callicles, in "Gorgias"
From: Doug on 7 Jul 2010 16:07
"JSH" <jstevh(a)gmail.com> wrote in message news:1711ec7d-f8d1-4a9f-9545-a3d8edb3154c(a)y2g2000pra.googlegroups.com... On Jun 30, 7:44 pm, MichaelW <ms...(a)tpg.com.au> wrote: > On Jul 1, 12:09 pm, JSH <jst...(a)gmail.com> wrote: > > > > > > > On Jun 30, 7:01 pm, MichaelW <ms...(a)tpg.com.au> wrote: > > > > On Jul 1, 9:54 am, JSH <jst...(a)gmail.com> wrote: > > > > > I've noted a way to solve for m, when k^m = q mod N, through integer > > > > factorization, which is then an approach to solving discrete > > > > logarithms in a prior post. In this post I'll explain when the > > > > equations MUST work, where a simple analysis can be done trivially > > > > using methods familiar to those who've solved simultaneous equations > > > > in regular algebra. > > > > > Here are relevant equations without the complete detail explaining > > > > them all of the prior post which should be read for reference: > > > > > Everything follows from use of a simple system of equations: > > > > > f_1 = a_1*k mod N thru f_m = a_m*k mod N > > > > > Two important constraining equations: > > > > > a_1*...*a_m = q mod N > > > > > and > > > > > a_1+...+a_m = m mod N > > > > > Resultant equations: > > > > > f_1*...*f_m = q^2 mod N > > > > > and > > > > > f_1+...+f_m = mk mod N > > > > > (These are arbitrary constraints that I used. There may be others > > > > that are of practical use.) > > > > > Now assume that for some unknown number m-c of the f's that the a's > > > > are simply the modular inverse of k, then for that number the f's > > > > simply equal 1, which allows me to solve for m with: > > > > > (k-1)*m = (f_1+...+f_c - c) mod N > > > > > If k-1 is coprime to N, you can simply use the modular inverse to > > > > get > > > > m. Otherwise you'd to divide off common factors from both sides and > > > > then use the modular inverse with what remained. > > > > > All of which was given in my prior post, but notice I can now go > > > > back > > > > to the constraining equations for the a's with the information that > > > > some of the a's have been set to the modular inverse of k: > > > > > a_1*...*a_c*k^{-(m-c)} = q mod N, so a_1*...*a_c= q*k^{-(m-c)} > > > > > and > > > > > a_1+...+a_c + (m-c)k^{-1} = m mod N, so a_1+...+a_c = -(m-c)k^{-1} + > > > > m > > > > mod N > > > > > which means there are two simultaneous congruence equations with c > > > > unknowns: > > > > > a_1*...*a_c= q*k^{-(m-c)} > > > > > and > > > > > a_1+...+a_c = -(m-c)k^{-1} + m mod N > > > > > Using the first to substitute out a_1 into the second and > > > > simplifying > > > > slightly gives: > > > > > q*k^{-(m-c)} + a_2^2*a_3*...*a_c + a_2*a_3^2*...*a_c...+ > > > > a_2*...*a_c^2 = a_2*...*a_c[-(m-c)k^{-1} + m] mod N > > > > > Notice then that with any c-2 variables set arbitrarily, the > > > > existence > > > > of the remaining one is set if a quadratic residue exists. > > > > > So for instance if c=4, then you can have a_3 and a_4 completely > > > > free > > > > variables, as long as quadratic residues exist to allow for a_2, > > > > which > > > > would indicate a 50% probability in that case if N is prime. > > > > > However, you can also further constrain one more of the a's to > > > > remove > > > > squares, for instance let a_3 = a_2^{-1} mod N, and you have: > > > > > q*k^{-(m-c)} + a_2*a_4*...*a_c + a_3*a_4*...*a_c...+ a_4*...*a_c^2 = > > > > a_4*...*a_c[-(m-c)k^{-1} + m] mod N > > > > > which allows a solution for a_2 to always exist. Which would leave > > > > with c=4, a_4 completely free. > > > > > Assuming human nature will be to look for smaller values to factor > > > > to > > > > actually use the algorithm, one can assume that > > > > > f_1*...*f_m = q^2 mod N > > > > > will be with smaller values of q^2 mod N, based on human preference, > > > > so if a_4 is completely free, and is non-unit, it would likely in > > > > many > > > > cases mean that f_4 will be 2. > > > > > If a_3 and a_4 are free then one would expect f_3 and f_4 to be 2. > > > > > With c = 4 or greater then the area to consider variability that > > > > cannot just be arbitrarily set to a convenience value is with a_1 > > > > and > > > > a_2 which could make f_1 and f_2 just about any residue mod N. Worst > > > > case they are both near N, so you'd have a size of approximately > > > > 4N^2. > > > > > So algorithms based on this method should exit within q^2 mod N less > > > > than 4N^2. > > > > > Here's the example given in my prior post, which should make more > > > > sense given the information above: > > > > > Solve for m, where: > > > > > 2^m = 13 mod 23 > > > > > so k = 2, and f_1*...*f_m = q^2 mod N = 13^2 mod 23 = 8 mod 23. > > > > > And I found a solution with f_1*...*f_m = 54, and > > > > > f_1 = 2, f_2 = 3, f_3 = 3, f_4 = 3 > > > > > so c=4, and > > > > > m = (k-1)^{-1}(f_1 +...+ f_c - c) mod N = 2+3+3+3 - 4 = 7 > > > > > And 2^7 = 128 = 13 mod 23. > > > > > Notice that 2 is a factor as are small primes. The method will try > > > > to > > > > fit small primes if you are using small values which is about human > > > > preference. The algebra tries to give you what you want based on the > > > > size of the numbers you are factoring. > > > > > The value of c is dynamically set by the factorization of q^2 mod N. > > > > But the results above indicate that the algebra must give you a > > > > factorization within that range which will work. > > > > > And that is what's found with a first blush basic analysis. It's not > > > > clear at this time what further information might result from more > > > > basic research. My aim at this point is to answer criticism against > > > > this approach. > > > > > Routinely posters reply requesting I demonstrate by breaking current > > > > encryption. Well, if I could do that I wouldn't need to bother > > > > posting on newsgroups now would I? > > > > > It's basic research. Early stages. > > > > > James Harris > > > > Solve one of the following with your algorithm. > > > > 2^m = 16 mod 23 > > > 2^m = 2 mod 107 > > > 2^m = 4 mod 107 > > > 2^m = 10 mod 107 > > > 2^m = 14 mod 107 > > > 2^m = 15 mod 107 > > > 2^m = 16 mod 107 > > > > My criticism is that the algorithm does not on average produce a > > > solution in a reasonable time. > > > So? You keep puzzling me here. > > > Why do you think that is significant at this stage? > > > What do you believe it proves or may prove? > > > Please, be detailed in your response. I find your postings to be > > curiously odd. > > > James Harris- Hide quoted text - > > > - Show quoted text - > > Your algorithm is too inefficient to be of any use. No amount of > research will ever make it more efficient than the brute method. There > is no next stage, there is no advanced research, there is no > breakthrough. You have no evidence to suggest otherwise but my many > examples provide evidence that I am correct. Many examples? I've ran my own "many examples". I've found it didn't work that well, which is why I released it. >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> ***** so you took a poop, finally. |