 My Math Forum To Charles GH : solution of the discrete logarithm
 User Name Remember Me? Password

 Number Theory Number Theory Math Forum

 September 16th, 2016, 06:53 AM #1 Banned Camp   Joined: Dec 2013 Posts: 1,117 Thanks: 41 To Charles GH : solution of the discrete logarithm Hi Charles! If you read me then good luck! Solving 2^x=a mod b (with b prime) Here is an example : We want to solve 2^x = 11 mod 101 The first job to do is to write the left part as sum : (2^x)-1=1+2+4+8+...+2(x-1) (2^x)-1=10 mod 101 Now let us write 101 is base 2 : 101=64+32+4+1 1+0+4+0+0+32+64 Why doing this? The goal is to cut (2^x) in intervals of the same length : First interval of length 7 : 1+2+4+8+16+32+64 (as 101 is equal to 1+0+4+0+0+32+64 we remove the positive values because of modulo 101) we will have then : 0+2+0+8+16+0+0 = 26 (26+101=127=(2^6)-1) We have then (2^7)-1= 26 mod 101 Second interval same length : 128+256+512+1024+2048+4096+8192=128(1+2+4+8+16+32+ 64) If we remove the part modulo we will have then 128*26 As 128>101 then 128=27 mod 101 27*26 + 26 = 21 mod 101 (2^14)-1= 21 mod 101 (2^14)= 22 mod 101 as 22 is divisble by 11 then 2^13=11 mod 101 x=13 I gave an example without trying to formalize all this stuff : Step 1 : rewriting the left part as 2^x-1= (a-1) mod b Step 2 : the goal of the algorithm is first to define the interval length starting from the value of b in base 2. Step 3 : we write using modular arithmetic each interval Step 4 : we will have to solve interval 1 mod b then interval 2 mod b etc...(this step need lot of calculations because there is a window for many simplifications Step 5 : we will obtain a closed formula Keep in mind that what I exposed above is the principle of solutions knowing that there many hurdles ahead to fix to reach a workable algorihm. Good luck to those who are going to try to follow my idea. They will solve once for all the discrete logarithm. I have another complex solution leading to close formula anyway. In fact I solved the problem long time ago I gave hints to Charles without details but I do not know if he get them. September 17th, 2016, 05:00 AM #2 Member   Joined: Aug 2015 From: Montenegro (Podgorica) Posts: 37 Thanks: 4 this is nice! but does it work for any example? Tags charles, discrete, logarithm, solution Search tags for this page

### charles math puzzle solutions

Click on a term to search for related topics.
 Thread Tools Show Printable Version Email this Page Display Modes Linear Mode Switch to Hybrid Mode Switch to Threaded Mode Similar Threads Thread Thread Starter Forum Replies Last Post TreeTruffle Algebra 2 March 27th, 2010 01:22 AM

 Contact - Home - Forums - Cryptocurrency Forum - Top

Copyright © 2019 My Math Forum. All rights reserved.      