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.
2
-
$\begingroup$ isn't it 25!. Simply you have 25 for the first position, then 24 for the second, and so on. $\endgroup$– kelalakaCommented Sep 9, 2018 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$– RaiCommented Sep 9, 2018 at 23:01
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
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} $
answered Sep 10, 2018 at 6:30
-
$\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$– RaiCommented Sep 10, 2018 at 23:44
-
$\begingroup$ $\mathcal{O}(2^n) \in \mathcal{O}(n!)$ but $\mathcal{O}(n!) \notin \mathcal{O}(2^n)$ $\endgroup$– kelalakaCommented Sep 11, 2018 at 5:15