So I want to know what is the time complexity of deciphering a text of n words encrypted bt Vigenère.
Vigenère is just applying different Caesar shifts for each letter. I know that for a Caesar Cipher it is just O(n) Because we simply try all different 25 shifts. But what about Vigenère?Answer1:
Breaking Ceasar's shift is
O(n). The size of the alphabet is constant. You only need to decode a short stretch of the ciphertext under a given key to know if you are on track.
For Vigenere's cipher you have sequence of repeating shifts. The brute-force way to break it without statistical analysis depends on the key space, which is
O(26^k) for a key of length
k. Because statistical analysis is highly effective on Vigenere's cipher, its actual strength is much lower than would be suggested by this time bound.