How can one calculate the key-space for a restricted substitution cipher? A restricted substitution cipher is one where no letter is assigned to itself. For an alphabet with 26 letters how many keys are there for a restricted substitution cipher? What is the correct way to approach this question? I have been adviced to look into cycle notations, Markov chains and the structure of the symmetric group and its conjugacy classes.

  • $\begingroup$ isn't it 25!. Simply you have 25 for the first position, then 24 for the second, and so on. $\endgroup$ – kelalaka Sep 9 '18 at 20:23
  • $\begingroup$ @kelalaka Alright, let's say that 'a' can be assigned in 25 ways because we can't fix 'a' with 'A', and 'b' can be assigned in 24 ways because 'a' is already assigned with one and 'b' can't be assigned with 'B'. But, what if 'a' was assigned with 'B', this would make the number of options to be 25. $\endgroup$ – Rai Sep 9 '18 at 23:01

It is called derangement, see Wikipedia. Also, in Mathematics Stack Exchange 1, 2

Number of derangements of n elements $=\sum\limits_{k = 0}^{n}(-1)^k\frac{n!}{k!}$

When n = 26 the result is 148362637348470135821287825 $\approx 2^{87} $

| improve this answer | |
  • $\begingroup$ That seems a bit too much. The derangement can be approximated as !n = (n!/e), and for n = 26, that's of the order of 26, not 87 as you said. $\endgroup$ – Rai Sep 10 '18 at 23:44
  • $\begingroup$ $\mathcal{O}(2^n) \in \mathcal{O}(n!)$ but $\mathcal{O}(n!) \notin \mathcal{O}(2^n)$ $\endgroup$ – kelalaka Sep 11 '18 at 5:15

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.