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?
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.
