Learn _ Play _

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 +

""" TRAIL and DIVISION METHOD with PRIME_SIEVE """ def primes_sieve(limit): a = [True] * limit # Initialize the primality list a[0] = a[1] = False for (i, isprime) in enumerate(a): if isprime: yield i for n in xrange(i*i, limit, i): # Mark factors non-prime a[n] = False def trial_division(n): """Return a list of the prime factors for a natural number.""" if n == 1: return [1] primes = primes_sieve(int(pow(n,0.5)) + 1) # Prime factor is always less than SQRT(n)+1 prime_factors = [] for p in primes: if p*p > n: break while n % p == 0: prime_factors.append(p) n //= p if n > 1: prime_factors.append(n) return prime_factors t = trial_division(600851475143) print t Fermat Theorem import math def gcd(a, b): while a != b: if a > b:

#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

## using SAGE RSA n = 80646413 p = floor(sqrt(80646413)) ### Finding Factor p*q = n while(true): if (n%p == 0): print p break p=p+1 q = n / p print q #### phi(n) n1 = (p-1) * (q-1) print n1 e =5 d = e^-1 % n1 print d ### got private key ###Fast Exponentiation Algorithms def expo(c,d,n): if (d==1): return c%n if (d==2): return c*c % n if (d%2==0): return expo(expo(c,d/2,n),2,n) else: return c*expo(expo(c,(d-1)/2,n),2,n) cipher = [72895864,15633602,38820479,60303684,7458706,60299530,20682371,54642689,26066811,32615038,35349196,76400140,38820479,56463813,80491201,76400140,35349196,69567074,26066811,76400140,74270178,76127647,76127647,15633602,76400140,60303684,38820479,56463813,60303684,76400140,72844764,76127647,69302434,15633602,80491201,76400140,6809712,26066811,76400140,42498798,60299530,76127647,69302434,80491201,33234011] flag = '' for c in cipher: flag = flag+ chr(ex