Baby Step Giant Step Algorithm Python Code 

#Baby Step Giant Step DLP problem y = a**x mod n


#Example 70 = 2**x mod 131

y = 70
a = 2
n = 131

s = floor(sqrt(n))

A = []
B = []

for r in range(0,s):
    value = y*(a^r) % n
    A.append(value)

for t in range(1,s+1):
    value = a^(t*s) % n
    B.append(value)

print A
print B

x1,x2 =0,0
 
for r in A:
    for t in B:
        if r == t:
            x1 = A.index(r)            
            x2 = B.index(t)
            print x1,x2
            break
            

print 'the value of x is ', ((x2+1)*s - x1) % n # Answer

Comments

  1. UnknownJune 11, 2015 at 3:28 AM

    This comment has been removed by the author.

    ReplyDelete
  2. UnknownJune 11, 2015 at 3:31 AM

    There is no need to store list B, you also have some python mistakes: ^ should be **, s needs to be cast to int

    I'd write it like this:

    def baby_step_giant_step(y, a, n):
    ...s = int(ceil(sqrt(n)))
    ...A = [y * pow(a, r, n) % n for r in xrange(s)]
    ...for t in xrange(1,s+1):
    ......value = pow(a, t*s, n)
    ......if value in A:
    ......return (t * s - A.index(value)) % n

    ReplyDelete

Post a Comment

Popular posts from this blog

Berlekamp–Massey algorithm

The Berlekamp–Massey algorithm is an algorithm that will find the shortest linear feedback shift register for a given binary output sequence. The algorithm will also find the minimal polynomial of a linearly recurrent sequence in an arbitrary field. I have used sage for computing this program. # Berlekamp-Massey Algorithm #from __future__ import print_function s = [GF(2)(0), 0, 1, 0, 0, 0, 0, 0, 1, 1, 0] #input sequence n = len(s) C = [GF(2)(1)] B = [GF(2)(1)] temp = [] T = [] L = 0 N = 0 m = -1 print '----- n',n print '-----------------------------------------------------------------------' while N < n: temp = B d = s[N] for i in range(1,L+1): d = d + C[i]*s[N-i] print '----- d ',d if d == 1: T = C temp = [ 0 for i in range(int(N-m))] + temp if len(C) < len(temp): C = C + [0 for i in range(len(temp)-len(C))] else: temp = temp +...
Read more

Simple Automation using Python - Atomac in Mac OS X

Image
The Product Automation in MAC OS X is quite easy if we have enough knowledge in the following languages and tools  Bash Scripts  Apple Scripts  Python especially ATOMac Knowledge in Accessibility. For more understanding of the LDTP: http://download.freedesktop.org/ldtp/doc/ldtp-tutorial.pdf LDTP - Tutorial is written by  Nagappan Alagappan. He has given the clear idea and architecture of the LDTP and its working. I have used the contents from the tutorial for knowledge sharing. Following are the few information and contents from  the LDTP - Tutorial. Few interesting key points, Linux Desktop Testing Project (LDTP) i s aimed at producing high quality test automation framework and cutting-edge tools that can be used to test GNU/Linux Desktop and improve it.  It uses the Accessibility libraries to poke through the application's user interface.  This idea has been extended to Microsoft Windows as Cobra , Mac OS X as ATOMa...
Read more