[The Vigenère cipher](https://en.wikipedia.org/wiki/Vigen%C3%A8re_cipher) is a classic cipher that was thought to be "unbreakable" for three centuries. We now know that this is not so and it can actually be broken pretty easily.

**How the Vigenère cipher works**:

The basic concept is that you have a `message` and a `key`, and each character in the `message` is encrypted using a character in the `key`, by applying a Caesar shift. The key is recycled as many times as needed.

You might want to try [this kata](https://www.codewars.com/kata/vigenere-cipher-helper) first, which focuses on the encryption and decryption processes.


## Well how do we break it?

The first thing we have to do is determine the **length of the key** that was used to encrypt the message.

Write a function that takes some cipher text and a maximum possible key length and returns the length of the key that was used in the encryption process.

**Note:** We don't care about what characters are in the key -- only how many of them there are.

---

Any feedback (and suggestions) would be much appreciated

*This kata is based on one of the programming assignments in [Prof. Jonathan Katz's course on cryptography](https://www.coursera.org/course/cryptography) given on Coursera*

Difficulty: interview

Starter code:

def get_key_length(text, max_key_length):
	

Solutions:
from collections import Counter

def get_key_length(cipher_text, max_key_length):
    avg_IC_by_keylen = {}
    
    for key_len in range(1, max_key_length+1):
        ICs = []
        
        for i in range(key_len):
            sub_str = cipher_text[i::key_len]
            freq = Counter(sub_str)
            IC = sum(v * (v-1) for k, v in freq.items()) / (len(sub_str) *  (len(sub_str)-1) )
            ICs.append(IC)
        
        avg_IC_by_keylen[key_len] = sum(ICs) / key_len
    
    return max(avg_IC_by_keylen, key=avg_IC_by_keylen.get)

from collections import defaultdict

def get_key_length(cipher_text,max_key_length):
    #Step 1: List of recurrent patterns of three signs
    d=defaultdict(list)
    for i in range(len(cipher_text)-3):
        d[cipher_text[i:i+3]].append(i)
    
    #Step 2: Compute distance between patterns
    e=defaultdict(int)
    for k,v in list(d.items()):
        for v0,v1 in zip(v,v[1:]):
            e[v1-v0]+=1

    #Step 3: Test of divisibility            
    lengths=[]
    total=sum(e.values())
    for length in range(2,max_key_length):
        score=[0,0]
        for k,n in list(e.items()):
            score[k%length==0]+=n
        # We put a threshold on 66% of completion            
        lengths.append((score[True]/total>0.66,length))  

    return max(lengths)[1]

            


def get_key_length(text, max_key_length):
    mx = s = 0 
    for i in range(2, max_key_length + 1):
        x = sum(index_of_coincidence(text[j::i]) for j in range(i)) / i
        if x > s: mx, s = i, x
    return mx

def index_of_coincidence(string):
    N = len(string)
    return sum(count * (count - 1) for count in map(string.count, set(string))) / (N * (N - 1))

def get_key_length(text, max_key_length):
    avgs = {}
    for i in range(2, max_key_length + 1):
        avgs[i] = sum(index_of_coincidence(text[j::i]) for j in range(i)) / i
    return max(avgs, key=avgs.get)

def index_of_coincidence(string):
    N = len(string)
    return sum(count * (count - 1) for count in map(string.count, set(string))) / (N * (N - 1))

def get_key_length(text, max_key_length):
    avgs = {}
    for i in range(2, max_key_length + 1):
        avgs[i] = sum(index_of_coincidence(text[j::i]) for j in range(i)) / i
    return max(avgs, key=avgs.get)


def index_of_coincidence(string):
    N = len(string)
    frequency_table = {char: string.count(char) for char in set(string)}
    return sum(count * (count - 1) for count in frequency_table.values()) / (N * (N - 1))

def get_key_length(text, max_key_length):
    N = len(text)
    avgs = {}
    for i in range(2, max_key_length + 1):
        avgs[i] = sum(index_of_coincidence(text[j::i]) for j in range(i)) / i
    return max(avgs, key=avgs.get)


def index_of_coincidence(string):
    string = string.upper().replace(' ', '')
    N = len(string)
    frequency_table = {char: string.count(char) for char in set(string)}
    return sum(count * (count - 1) for count in frequency_table.values()) / (N * (N - 1))

from functools import reduce
import itertools

def most_common(lst):
    return max(set(lst), key=lst.count)


def factors(n):    
    return list(set(reduce(list.__add__, 
                ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0))))

def gcd_list(alist):
    def gcd(a, b):
        while b > 0:
            a, b = b, a % b
        return a


    result = alist[0]
    for i in alist[1:]:
        result = gcd(result, i)

    return result



def common_subs(alist):
    to_return = []
    for i in alist:
        for j in alist:
            if i != j:
                to_return.append(abs(i-j))
    return to_return
    
#print(common_subs([100,3,4]))    


def get_key_length(cipher_text,max_key_length):
    dis = []
    for pos,char in enumerate(cipher_text):
        if pos == len(cipher_text)-1:
            pass
        else:
            dis.append([cipher_text[pos]+cipher_text[pos+1],pos])
            
    alls = []
    for di in dis:
        if [x[0] for x in dis].count(di[0]) != 1:
            a = [x[1] for x in dis if x[0] == di[0]]
            #print(a)
            #print(common_subs(a))
            #print(gcd_list(common_subs(a)))
            alls.append(gcd_list(common_subs(a)))
    print('a')
    return most_common([x for x in alls if x != 1])
            
            


from collections import defaultdict
def get_key_length(cipher_text,max_key_length):
    reverse_cipher = cipher_text[::-1]
    dict = {}
    for i in range(1,max_key_length+1):
        l = list(zip(reverse_cipher,reverse_cipher[i:]))
        c = 0
        for a,b in l:
            if a==b:
                c+=1
        dict[i] = c
    max_collisions = max(dict.values())
    for key, value in dict.items():  # for name, age in dictionary.iteritems():  (for Python 2.x)
        if value == max_collisions:
            return key

def get_ic(msg):
    frequency = {}
    ic = 0.0
    for c in msg:
        if c in msg.lower():
            frequency[c] = msg.count(c, 0, len(msg))
    #print(frequency)
    return sum(map(lambda x: x * (x - 1), frequency.values())) / (len(msg)*(len(msg) - 1))

def get_key_length(cipher_text,max_key_length):
    ics = [0.0]*max_key_length
    for i,ic in enumerate(ics):
        if i > 1:
            sum_ic = 0.0
            avg_ic = 0.0
            offset = 0
            for x in range(i):
                offset = x
                step = i
                sum_ic += get_ic(cipher_text[offset::step])
            avg_ic = sum_ic / i
            ics[i] = avg_ic
    #for ic in ics:
    #    print(ic)
    return ics.index(max(ics))

def get_key_length(cipher_text,max_key_length):
    IC=[]
    alphabet='abcdefghijklmnopqrstuvwxyz'
    for i in range(2,max_key_length+1):
        avg_ic=0
        for j in range(i):
            ic=0
            txt=cipher_text[j::i]
            l=len(txt)
            for k in alphabet:
                c=txt.count(k)
                n=(c*(c-1))/(l*(l-1))
                ic+=n
            avg_ic+=ic
            
        avg_ic/=i
        IC.append(avg_ic)
        
    return IC.index(max(IC))+2