My Math Forum  

Go Back   My Math Forum > College Math Forum > Number Theory

Number Theory Number Theory Math Forum


Reply
 
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(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.
mobel is offline  
 
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?
1ucid is offline  
Reply

  My Math Forum > College Math Forum > Number Theory

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





Copyright © 2019 My Math Forum. All rights reserved.