My Math Forum To Charles GH : solution of the discrete logarithm

 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

### charles math puzzle solutions

Click on a term to search for related topics.
 Thread Tools Display Modes Linear 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