[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: MEDIUM_HARD

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):
	d = defaultdict(list)
	for i in range(len(cipher_text) - 3):
		d[cipher_text[i:i + 3]].append(i)
	e = defaultdict(int)
	for (k, v) in list(d.items()):
		for (v0, v1) in zip(v, v[1:]):
			e[v1 - v0] += 1
	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
		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):
	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

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]]
			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():
		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))
	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
	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