Complexity of breaking Vigenère cipher

Question

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?

Answer 1

Breaking Ceasar's shift is O(1), not 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.