Problem 5 - An Introduction to Mathematical Cryptography

Question

Suppose that you have an alphabet of 26 letters. (a) How many possible simple substitution ciphers are there? (b) A letter in the alphabet is said to be fixed if the encryption of the letter is the letter itself. How many simple substitution ciphers are there that leave: (i) no letters fixed? (ii) at least one letter fixed? (iii) exactly one letter fixed? (iv) at least two letters fixed? (Part (b) is quite challenging! You might try doing the problem first with an alphabet of four or five letters to get an idea of what is going on.)

Step-by-Step Solution

Answer

(a) 26!, (b)(i) !26, (ii) 26! - !26, (iii) \( \binom{26}{1} \times !25 \), (iv) \( 26! - !26 - (\binom{26}{1} \times !25) \)

Step 1: Understanding Simple Substitution Ciphers

A simple substitution cipher is a method where each letter in the alphabet corresponds to a unique letter from the same alphabet. Therefore, any arrangement (permutation) of 26 letters will give us a unique cipher.

Step 2: Calculate Number of Simple Substitution Ciphers

The number of possible simple substitution ciphers is the number of different permutations of 26 letters. This can be calculated as \( 26! \) (26 factorial).

Step 3: Calculate Ciphers with No Fixed Letters (Derangement)

A permutation where no element appears in its original position is called a derangement. The number of derangements \( !n \) for 26 letters can be calculated using the formula:\[ !n = n! \, \sum_{i=0}^{n} \frac{(-1)^i}{i!} \]Substitute \( n = 26 \) to find \( !26 \).

Step 4: Calculate Ciphers with At Least One Fixed Letter

To find the number of ciphers with at least one fixed letter, subtract the number of derangements from the total permutations: \( 26! - !26 \).

Step 5: Calculate Ciphers with Exactly One Fixed Letter

Choose 1 out of 26 letters to be fixed and derange the remaining 25 letters. The calculation is: \( \binom{26}{1} \times !25 \).

Step 6: Calculate Ciphers with At Least Two Fixed Letters

Find the ciphers with at least two fixed letters by subtracting the ciphers with no fixed letters and exactly one fixed letter from those with at least one fixed letter:\[ 26! - !26 - \left( \binom{26}{1} \times !25 \right) \].

Key Concepts

Permutations

In mathematics, permutations refer to the different ways in which a set of items can be organized or arranged. When we talk about arrangements of letters, each distinct order in which the letters can occur is a permutation. For example, with an alphabet of 26 letters, any arrangement of these letters constitutes a permutation of the alphabet. The formula to find the number of permutations of 'n' distinct items is given by the factorial of 'n', represented as \( n! \). This means for an alphabet with 26 letters, the number of permutations is \( 26! \), which represents all possible arrangements of these letters. Permutations are fundamental in understanding how substitution ciphers work since each cipher is a unique permutation of the alphabet.

Derangements

A derangement is a type of permutation where none of the elements appear in their original positions. In the context of the alphabet and simple substitution ciphers, this means creating a cipher where no letter encrypts to itself. Calculating derangements can be trickier than standard permutations. For 'n' items, the number of derangements, denoted as \( !n \), is given by the formula:

• \[ !n = n! \, \sum_{i=0}^{n} \frac{(-1)^i}{i!} \]

This formula uses the concept of inclusion-exclusion principle from combinatorics, alternating between adding and subtracting permutations that have certain letters in fixed positions. Applying this to our 26-letter alphabet gives us the number of derangements, denoted as \( !26 \). Understanding derangements helps us solve problems where no letters in the cipher retain their original positions.

Fixed Letters

The idea of a fixed letter is straightforward – it’s a letter that remains unchanged after encryption in a substitution cipher. When working with substitution ciphers, analyzing fixed letters helps us understand how the structure of the cipher affects the message. For example, when examining a cipher with no fixed letters, we’re looking at a derangement. In contrast, if at least one letter is fixed, we subtract the number of derangements from the total permutations. Calculating the exact number of ciphers with exactly one fixed letter involves choosing one letter to stay in its place and deranging the remaining 25 letters. Thus, fixing one letter significantly changes the calculation and structure of the cipher permutations.

Factorial

The factorial function, typically denoted by an exclamation point (\(!\)), is a mathematical operation that multiplies a series of descending natural numbers. For a non-negative integer \(n\), \(n!\) is the product of all positive integers less than or equal to \(n\). For instance, \( 5! \) equals \( 5 \times 4 \times 3 \times 2 \times 1 = 120 \). Factorials grow rapidly with larger values of \(n\), which makes them suitable for counting permutations. In the context of substitution ciphers, \( 26! \) calculates how many ways we can permute an entire alphabet, generating all possible simple substitution ciphers. This concept is foundational in combinatorics and crucial for understanding the extent of permutation possibilities as well as calculating large combinations.