JSH: Some history
in [Math]
|
Prev: nearness to the Nucleus of the Atom Totality Chapter 4, Missing Mass #227 Atom Totality
Next: 3SAT - Super Resolution
From: JSH on 22 Jul 2010 22:38 On Jul 22, 7:09 pm, MichaelW <ms...(a)tpg.com.au> wrote: > On Jul 23, 9:42 am, JSH <jst...(a)gmail.com> wrote: > > > > > > > On Jul 22, 4:22 pm, James Kravitz <jskrav...(a)gmail.com> wrote: > > > > On Jul 22, 10:31 am, JSH <jst...(a)gmail.com> wrote: > > > > > On Jul 22, 7:26 am, Mark Murray <w.h.o...(a)example.com> wrote: > > > > > > On 07/22/10 15:13, JSH wrote: > > > > > > >>> If there is, demonstrate it with k^m = 52 mod 103. > > > > > > >> You haven't specified k, so m can be just about anything. Feel free > > > > > >> to provide a value of k though. > > > > > > >> - Tim > > > > > > > Sorry, that should be 2^m = 52 mod 103. > > > > > > > I was thinking 2, but put k. The answer is 101. Solve for m using > > > > > > integer factorization, and show your work. > > > > > > You are now fixated on getting folks to calculate something that is > > > > > known. > > > > > Yup, to demonstrate solving for m, with integer factorization. > > > > > > The problem is that your claim to be the discoverer of the link > > > > > between discrete logarithms and factoring is a false claim. The > > > > > above exercise does nothing except show an instance of this being > > > > > true. > > > > > > Address this: > > > > > > > On Jul 21, 9:22 pm, Tim Little<t...(a)little-possums.net> wrote: > > > > > >> On 2010-07-22, JSH<jst...(a)gmail.com> wrote: > > > > > >> > > > > > >>> Give a technique for finding m, when k^m = q mod N, with k, q and N > > > > > >>> known, by integer factorization in reply > > > > > >> > > > > > >> Sure. Since you appear to ignore almost all links that don't go to > > > > > >> Wikipedia or Mathworld, try: > > > > > >> http://en.wikipedia.org/wiki/Index_calculus_algorithm > > > > > >> and > > > > > >> http://en.wikipedia.org/wiki/Pohlig-Hellman_algorithm > > > > > >> > > > > > >> Both of these involve factorizations to solve the discrete log > > > > > >> problem. Feel free to ask if you don't understand anything there. > > > > > >> > > > > > >> Note that these methods are massive overkill for the trivial problems > > > > > >> you post here. It would be like using the Space Shuttle to go next > > > > > >> door instead of into space. They are useful for computer solution of > > > > > >> much bigger problems. > > > > > >> > > > > > >> There is also a website with Java applet and source code that solves > > > > > >> discrete logarithms using the Pohlig-Hellman algorithm: > > > > > >> > > > > > >> http://www.alpertron.com.ar/DILOG.HTM > > > > > >> > > > > > >> Not that you will look at it, as you are no doubt scared of what you > > > > > >> might find there. I mention it only since other people reading this > > > > > >> thread might be interested. > > > > > > M > > > > > Fine. Use WHATEVER YOU WANT, and solve for m, when 2^m = 52 mod 103. > > > > SHOW YOUR WORK. > > > > Others have covered Pohlig-Hellman, so let's step through an example > > > of the index calculus method. I'll do it twice; the first time I'll do > > > it inefficiently, but in a manner that will demonstrate where > > > factoring comes in; the second time I'll do it efficiently, but > > > because your example is so trivial we won't see any real factoring > > > going on. > > > > As a preliminary, its worth noting that 51 is the largest exponent > > > worth considering since 2^51 mod 103 = 1, so larger exponents are just > > > looping back through the same values (that is, we consider exponents > > > mod 51). I'm sure there are better ways to find that out, but I just > > > did the first thing that occurred to me and used Lagrange's theorem > > > and the fact that 2 generates a subgroup of the multiplicative group > > > of F_103. > > > > Now for the inefficient index calculus version. We will need a factor > > > base, and I've somewhat arbitrarily chosen primes up to 13. We then > > > need to find discrete logs (base 2) of those primes mod 103. To do > > > that we generate relations that involve discrete logs of those primes > > > and then solve for the discrete logs. We do that by simply calculating > > > a small number of powers of 2 modulo 103 and factoring them. So > > > > 2^1 mod 103 = 2 which implies that 1 * dlog(2) = 1 mod 51 -- this is > > > our first relation > > > 2^2 mod 103 = 4 = 2^2; doesn't involve any new primes > > > 2^3 mod 103 = 8 = 2^3; doesn't involve any new primes > > > 2^4 mod 103 = 16 = 2^4; doesn't involve any new primes > > > 2^5 mod 103 = 32 = 2^5; doesn't involve any new primes > > > 2^6 mod 103 = 64 = 2^6; doesn't involve any new primes > > > 2^7 mod 103 = 25 = 5^2 which implies 2 * dlog(5) = 7 mod 51 -- this is > > > our second relation > > > 2^8 mod 103 = 50 = 5^2 * 2; doesn't involve any new primes > > > 2^9 mod 103 = 100 = 5^2 * 2^2; doesn't involve any new primes > > > 2^10 mod 103 = 97; a new prime, but not one we care about > > > 2^11 mod 103 = 91 = 7 * 13 which implies dlog(7) + dlog(13) = 11 mod > > > 51 -- this is our third relation > > > 2^12 mode 103 = 79; a new prime, but not one we care about > > > 2^13 mod 103 = 55 = 5 * 11 which implies dlog(5) + dlog(11) = 13 mod > > > 51 -- this is our fourth relation > > > 2^14 mod 103 = 7 which implies dlog(7) = 14 mod 51 -- this is our > > > fifth relation > > > > And we can stop there -- we don't have a relation for dlog(3), but > > > we'll come back to that. Solving the relations we have we get: > > > > dlog(2) = 1 mod 51 > > > dlog(5) = 29 mod 51 > > > dlog(7) = 14 mod 51 > > > dlog(11) = 35 mod 51 > > > dlog(13) = 48 mod 51 > > > > Now if we try and verify these we note that some aren't quite right > > > (I've been sweeping details under the rug a little): for example 2**29 > > > mod 103 = 98 not 5. But wait, 98 = -5 mod 103 -- and in fact no power > > > of 2 will give 5 mod 103. We get the same with 11 (we actually have > > > the dlog of -11), and noting this we can see that since 2^9 mod 103 = > > > 100 = -3 mod 103, then dlog(-3) = 9, and we have dlogs for all the > > > primes in our factor base. > > > > Now to use all that information. For the specific case you've given > > > (2^m = 52 mod 103) we merely need to factor 52 as 2^2 * 13 and see > > > that > > > > m = dlog(52) > > > = dlog(2^2 * 13) > > > = dlog(2^2) + dlog(13) > > > = 2*dlog(2) + dlog(13) > > > > and then substitute in the values we computed for the dlogs of 2 and > > > 13 to get > > > > m = 2*1 + 48 = 50. > > > > And indeed 2^50 mod 103 = 52 as required. > > > > Okay, that was rather laborious. It need not be so -- it demonstrated > > > factoring at work (both in gathering relations, and in solving for the > > > discrete log) but we can do better. We don't need such a large factor > > > base for such a small problem; we can just use 2 as our factor base > > > (the dlog of 2 is easy enough to find, it's just 1). > > > > So now for the second, more efficient demonstration of the index > > > calculus method to show you that it can be quick. Following the > > > Wikipedia explanation, to actually solve for the dlog we should try > > > factoring "g^s * h" for s = 0, 1, 2, ... Where, in our case, g = 2, > > > and h = 52. We did s = 0 above, but now that we don't have 13 in our > > > factor base, that won't work. Next we try s = 1: > > > > 2^1 * 52 mod 103 = 1 > > > > But we know the dlog of 1, so we can use that to get the relation: > > > > dlog(2) + m = dlog(1) mod 51 > > > implies 1 + m = 0 mod 51 > > > implies m = -1 mod 51 = 50 mod 51 > > > > So that's the quick version. Not much factoring apparent, but very > > > little work indeed. Of course with a less trivial problem factoring > > > will show up in exactly the sort of way that it did in the more > > > laborious first approach. > > > Cool. Thanks! Nice when someone will actually "show the math" as > > requested. Some of these posters may just not be able to any more, > > and would be lost without their computers. > > Okay then, you do an example, showing the maths. Bet you won't. That's a fair request. I HAVE done examples, so the relevant thing to do here is to do the same example. 2^m = 52 mod 103 I need T = 52^2 mod 103 = 26 mod 103. Solutions should be densest around 103^2, and I'll check just below: T = 26 + 103^2 - 103 = 10532. Which I checked and it doesn't work. Subtracting 2*103, gives: 10326 = 2*3*1721. Which doesn't work. Subtracting 2*103, gives: 10120 = 2^3*5*11*23 = 4*5*22*23. 4+5+22+23 - 4 = 50. 2^50 = 52 mod 103. That ALWAYS freaks me out as it's so wacky. And I'll admit I was looking for 50 as a solution so I didn't check every possible combination of factors. But that is still just kind of creepy weird to me. It's is too creepy. It makes me just feel weird. Ok, I'm wandering off now. It was only fair for me to show an example from my research since I was asked and I'd asked others to show their work. I didn't show all of mine but it was mostly just adding factors to try and get 50. Rule is: f_1+...+f_c - c = m where the f's are the factors and c is the count of factors. This technique can conceivably factor an m of ANY size with only 4 factors like above. The math doesn't care. People care as people are, well, people. But the math doesn't give a damn what people think. Ok, going to drink more Absolut & orange juice. Then I think I'll have a beer. You people do not understand fear like I have to face. And you can be so arrogant and so stupid because you don't matter. No one gives a damn what you say because it isn't important!!! And I get to live in fear because I figured out some freaking math. It IS a stupid world. What makes you think you'll keep having discoverers when you give them pain for their efforts? After what I'm facing the next person who even dares to make a major discovery should just go ahead and slit their wrists and not even bother as this world no longer wants people to actually learn. It loves its lies instead. The age of the discoverer has ended. There is nothing more for us to do here. The human race is done learning. It has decided to live lies instead. There shall be no more discoverers. We will not return. James Harris
From: Tim Little on 23 Jul 2010 00:56 On 2010-07-22, JSH <jstevh(a)gmail.com> wrote: > On Jul 21, 9:22 pm, Tim Little <t...(a)little-possums.net> wrote: >> http://en.wikipedia.org/wiki/Pohlig-Hellman_algorithm I'm curious to see whether it is feasible to do this with effectively "pencil and paper". I have personally never used this algorithm before: only heard of it, glanced at some program source code that implements part of it, and read a rough overview of how it works. > Sorry, that should be 2^m = 52 mod 103. > > I was thinking 2, but put k. The answer is 101. Solve for m using > integer factorization, and show your work. That problem is easily solved by inspection: 2*52 = 1 mod 103, so 2^-1 = 2^101 = 52 mod 103. A less trivial problem next time perhaps? But despite that it's massive overkill for such a tiny problem, here's an application of the Pohlig-Hellman algorithm: First, factor the order of the multiplicative group: phi(103) = 102 = 2 x 3 x 17. For the first step, remove the first factor 2 and solve 52^(3x17) = (2^(3x17))^a mod 103. The multiplicative group here has order at most 2. In fact it turns out to have trivial order 1, so a=0 and a=1 are both solutions. Now we remove the factor 3; 52^34 = (2^34)^b mod 103, reducing to equation 56 = 46^b mod 103, having group order at most 3. The solution is b = 2. Finally we remove the factor 17: 52^6 = (2^6)^c mod 103, which reduces to 66 = 64^c mod 103 with order at most 17. We could easily check each of the 16 possibilities, but let's get very slightly fancy and use the baby-step/giant-step algorithm instead: Let m = ceiling(sqrt(17)) = 5. Make a table of powers up to m-1: (1, 64, 79, 9, 61). Find 64^-m = 64^12 = 72 mod 103 Let g = 66, and multiply by 72 mod 103 until the result is in the table: 14, 81, 64 - a hit So 66 * (64^-5)^3 = 64^1 mod 103, which means 66 = 64^16 mod 103. Now gathering up our results, we know that m = a = 0 mod 2, m = b = 2 mod 3, m = c = 16 mod 17. Using the Chinese Remainder Theorem we get m = 50 mod 102. If we had chosen a=1 instead, we would have found the other set of solutions m = 101 mod 102. Note that this does depend right from the start on the factorization of phi(103). If instead of baby-step/giant-step we had used the index calculus algorithm (a more complicated algorithm much faster for large prime orders) then factorization would have featured even more prominently, as it depends upon finding smooth factorizations of powers of the numbers involved. One of the other algorithms I linked uses factorizations in Gaussian integers. The function field sieve (listed on Wikipedia) uses factorization in rings of polynomials over a finite field. So factorization has been heavily involved in algorithms for solving discrete logarithm problems for some time already. That's on top of the fact that most of these algorithms themselves are quite direct adaptations of algorithms for factorization. Using factorizations to help solve discrete log problem is well-known. The hard part has been to find types of factorization that reduce the search space to something feasible for very large (more than 150 digit) numbers. Playing around with 2-4 digit numbers will never be any use for that. - Tim
From: Jesse F. Hughes on 23 Jul 2010 09:41 JSH <jstevh(a)gmail.com> writes: > What makes you think you'll keep having discoverers when you give them > pain for their efforts? > > After what I'm facing the next person who even dares to make a major > discovery should just go ahead and slit their wrists and not even > bother as this world no longer wants people to actually learn. > > It loves its lies instead. > > The age of the discoverer has ended. > > There is nothing more for us to do here. The human race is done > learning. > > It has decided to live lies instead. There shall be no more > discoverers. > > We will not return. That was a pretty good Absolut and Vodka, was it? -- Jesse F. Hughes "Philosophy, Socrates, if pursued in moderation and at the proper age, is an elegant accomplishment, but too much philosophy is the ruin of human life." -- Callicles, in "Gorgias"
From: JSH on 23 Jul 2010 10:12 On Jul 23, 6:41 am, "Jesse F. Hughes" <je...(a)phiwumbda.org> wrote: > JSH <jst...(a)gmail.com> writes: > > What makes you think you'll keep having discoverers when you give them > > pain for their efforts? > > > After what I'm facing the next person who even dares to make a major > > discovery should just go ahead and slit their wrists and not even > > bother as this world no longer wants people to actually learn. > > > It loves its lies instead. > > > The age of the discoverer has ended. > > > There is nothing more for us to do here. The human race is done > > learning. > > > It has decided to live lies instead. There shall be no more > > discoverers. > > > We will not return. > > That was a pretty good Absolut and Vodka, was it? Yup! A lot of my most you could say creative postings are alcohol fueled. You can really get some wild ideas with some good vodka. Of course you can also say some really wacky things. And I actually managed to censor the worst of it which thankfully got discarded before posting. Wow though even with that what got through was fascinating. Oh, I am one of my favorite writers, and like to read and re-read what I write with fascination at times. So at times who knows? I may be writing mostly for myself. James Harris
From: Mark Murray on 23 Jul 2010 13:12
On 22/07/2010 01:03, JSH wrote: > I'm trying to let this drop, but you're making false statements. > > Give a technique for finding m, when k^m = q mod N, with k, q and N > known, by integer factorization in reply or concede you made a false > statement. > > There is no accepted method for doing that, while my approach isn't > being accepted. > > If there is, demonstrate it with k^m = 52 mod 103. > > Show your work to find m. This has now been done with the Pohlig-Hellman algorithm, to your aparrent satisfaction. Likewise with the index calculus method. I was therefore not making a false statement, right? >>> But if there are people out there who have that result fully developed >>> and figured out the k^m = q mod N result two years ago, then maybe I >>> should just leave them alone, you know? >> >> Right (do you realise that this is what folks have been saying to you >> since you picked up this topic?) > > You're insane. > > But to prove it I have to give you a challenge which you will fail, > which means I'm STILL talking on this topic for one day more than I > wished just to handle one insane person. And where does this find itself now? >>> I'm not a cop. I'm not a secret service. Governments have that job >>> of protection, not me. >> >> Correct. Not relevant. > > It is, because you're spreading falsehoods. There WAS no way known to > find the discrete log by integer factorization before my research > path, and governments SHOULD care but there is silence meaning our > world is not behaving correctly. As you've seen the Pohlig-Hellman algorithm and the index calculus method demonstrated the above can be seen to be false. > Now fall flat on your face with my request for a solution to m, say > something irrelevant in reply to justify your complete failure, and > then come back and chortle victory like you know you'll do no matter > what. Just get it over with, but then I WILL step away, as this > thread should reflect both my prediction and your response letting me > walk away as I wish. As there is the complete opposite of complete failure (_I_ didn't do the calulations requested, but they were done), I believe that you owe an apology. I don't have much of a chance of ever seeing one. You are way too spineless for that. I do have the pleasure of seeing your argument annihilated (sp?), follwed by the usual predictable, drunken, megalomaniacal rants on both Twitter and your so-called "discussion" group. This usually marks the end of your credibility on a particular topic. M -- Mark "No Nickname" Murray Notable nebbish, extreme generalist. |