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: Mark Murray on 22 Jul 2010 14:03 On 22/07/2010 18:51, Arte Atem wrote: > See? it is not a 1 to 1 mapping - useless for encryption. Just take the n=0 case? M -- Mark "No Nickname" Murray Notable nebbish, extreme generalist.
From: James Kravitz on 22 Jul 2010 19:22 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.
From: JSH on 22 Jul 2010 19:42 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. I skimmed over but will review more closely later and more importantly mark for myself as a reference for when I might ponder this problem later. James Harris
From: MichaelW on 22 Jul 2010 22:09 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. > > I skimmed over but will review more closely later and more importantly > mark for myself as a reference for when I might ponder this problem > later. In the meantime some of your claims to having a new idea will be removed from your blog...? > > James Harris
From: Arte Atem on 22 Jul 2010 22:12
"Mark Murray" <w.h.oami(a)example.com> wrote in message news:4c48878a$0$28013$db0fefd9(a)news.zen.co.uk... > On 22/07/2010 18:54, Arte Atem wrote: >> you both are missing the bigger point. >> Mod functions have multiple solutions >> they are not a one to one mapping, >> therefore useless for encryption > > So far (except for some wild claims by JSH), crypto has not been > a functional part of the debate. doubt it would ever get to "functional" > > HOWEVER, DH and RSH /do/ use these mod functions; The result used > is the primary or "smallest" one. If the range is limited to this > primary value the the function /is/ one-to-one. .....fugley..... > > M > -- > Mark "No Nickname" Murray > Notable nebbish, extreme generalist. |