3 $[$ Cryptography $]$

Letters of the Russian alphabet are numbered according to the table:

$$
\begin{aligned}
& A^{*} \\
& 1
\end{aligned}
$$

For a message consisting of $p$ letters, a key $\mathrm{K}$ is chosen—a certain sequence of $\mathrm{n}$ letters from the above alphabet. The encryption of each letter of the message consists of adding its number in the table to the number of the corresponding letter of the key sequence and replacing the resulting sum with the letter of the alphabet whose number has the same remainder when divided by 30 as this sum. Read the encrypted message:

РБЬНПТСИТСРРЕЗОХ, if it is known that the encrypting sequence contained no letters other than

A, B and C. (Problem from the site www.cryptography.ru.)
There are three possible decodings for each letter. Decode each letter in three ways, and then search for a meaningful decoding.

## Solution

We will decode each letter of the encrypted message in three ways, assuming sequentially that the corresponding letter of the encrypting sequence is the letter A, B, or V:

encrypted message Р Б ь Н П Т С И Т С Р Р Е 3 О Х

variant A $\quad$ PA ShMO S R 3 S R PPDZHNF

variant B OY ShL N R PZHR POOGEM U

variant V NYU Ch MPOE PONNVDP L T

By selecting exactly one letter from each column of the resulting table, we find the meaningful message NASHKORRESPONDENT, which is the one we are looking for. In the solution, a significant part is devoted to finding a meaningful variant - the number of all different variants of the original messages without restrictions on meaningfulness is $3^{16}$ or 43046721, i.e., more than 40 million!