0
$\begingroup$

Consider an alphabet with 26 letters. Then a substitution cipher has $26!$ possible ciphertexts (with every letter substituted). What about repetive substitutions on a 5 letter word for example? How many different ciphertexts will result? Like $\sigma(a)=b, \sigma(b)=c, \sigma(c)=a$, then $abc \rightarrow bca \rightarrow cab \rightarrow abc$ so two ciphertexts for $|A|=3$.But what about generally?

$\endgroup$
1
  • 1
    $\begingroup$ It's very hard to tell what you're trying to ask here. Two people have guessed and tried to answer below, but their answers are different because they're answering different questions. And it looks like you've accepted one of the answers, but I'm honestly not sure if that's because you understood it and it matches what you intended to ask, or because you didn't fully understand if but it just looked vaguely right. If the former, please edit your question to make it clearer now that you know the right terminology. Either way, I'd suggest this question should be closed until it's clarified. $\endgroup$ Mar 12 at 0:17
2
$\begingroup$

What you are asking is how many times do you have to apply the substitution on a plaintext to arrive back at the plain text. One observation is that it will depend on the order of the substitution as an element of $S_{26}$, the permutation group on 26 elements. If your permutation has order $n$, than applying it $n$ times is the same as the identity permutation. For a given substitution, it is not hard to determine its order.

Your question is a little different. For a given plaintext, it could take fewer iterations to return back. You are interested in the permutation's action on a subset of elements and not the full set. It is going to have to do with the orbits of each plaintext letter under the permutation. So for a plaintext "abcde", how long does it take each of a, b, c, d, and e to cycle back? The answer is the LCM of those lengths. In particular, notice that the answer might be totally different for plaintext "fghij".

$\endgroup$
0
$\begingroup$

The maximum possible cycle length of a permutation of $n$ elements is given by Landau's function. For $n=26$ the answer is 1260

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.