
Number Theory Number Theory Math Forum 
 LinkBack  Thread Tools  Display Modes 
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(x1) (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^x1= (a1) 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 
Click on a term to search for related topics.

Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
trying to make a solution (liquid solution...) problem...  TreeTruffle  Algebra  2  March 27th, 2010 01:22 AM 