# Is the complexity of Caesar (shift) ciphers “n * n!”?

Can we say that any shift cipher to be decrypted needs an algorithm of complexity “n * n!”? (where n is number of possible values. 26 in case of English language).

My reasoning related to reaching n * n! was as follows:

Take the word BRAZIL for example. We have 26 possibilities for B, 25 for R, 24 forA, etc. ThusO(n!). We also can have this 26 times, B was A now, but is a G in the next time, thus 26 which isO(n)henceO(n * n!)`.

• Probably not. What's $n$ anyway? – fkraiem Feb 11 '15 at 20:37
• @fkraiem see updated question – tony9099 Feb 11 '15 at 20:42
• Please note that "decryption" usually means an algorithm which knows the key. And knowing the key, you should be able to decrypt a text in O(length of text). – Paŭlo Ebermann Feb 12 '15 at 19:13
• @PaŭloEbermann good point ! – tony9099 Feb 13 '15 at 15:02

How on earth did you arrive at that formula?

You can break a Caesar cipher by calculating the result of applying all of the $n-1$ (i.e., 25) possible shifts to the ciphertext and picking the one that makes sense. The computational complexity is just $\mathcal{O}(n)$.

If you want to automate the process based on frequency analysis, the correlation step where you pick the most likely offset would perhaps have $\mathcal{O}(n^2)$ complexity, but in practice you could probably achieve this by only considering a small subset of the most common letters. (For the English alphabet, E, T, A, I, O and N should suffice).

• Thanks. I updated my answer and included my reasoning. Can you please check and let me know where/how I got it wrong ? – tony9099 Feb 11 '15 at 21:46
• @tony9099 In a Caesar shift cipher, every letter is shifted by the same offset. So there are just 25 possible keys to test. That's all. You appear to be thinking of a monoalphabetic substitution cipher, where any letter can be mapped to any other. Although this has a larger keyspace (26 factorial), the code can still be broken by frequency analysis with O(n^2) complexity. (Actually I don't understand the last bit where you say we "have this 26 times". What does that mean?) – r3mainer Feb 11 '15 at 22:01
• Strictly speaking, wouldn't brute-force be $O(2^n)$ just like it is on every other scheme (because $n$ is the length of the key, not number of possible keys)? – cpast Feb 11 '15 at 22:53
• @cpast No. A 26-bit key would give you a keyspace of 2^26 (64M) permutations. But a key that consists of a single number from 1 to 25 can only give you 25 permutations. – r3mainer Feb 11 '15 at 23:10
• @squeamishossifrage EDIT: Never mind, I didn't notice the questions quirky definition of $n$. – cpast Feb 11 '15 at 23:19

If you consider arbitrary permutations, you have $\frac{n(n+1)}{2}$ possibilities. That means, $O(n^2)$ is the correct complexity in big-O notation, but I don't understand why you need that at all, if you can provide the result as exact formula.

Caesar cipher contains just a subset of $n$ possibilities, and therefore obviously $O(n)$.

Anyway, this doesn't cover algorithms like frequency analysis, which works both for the Caesar cipher and the general simple substitution cipher.