Архив задач олимпиады по математике и криптографии

Циклический сдвиг, 8-11 класс.

Целое число s ∈ {0,…,30} может быть преобразовано следующим образом. Пусть, например, s = 9. Представим его в двоичной системе счисления пятизначным числом: s = 9 = 010012. Теперь выберем какое-нибудь целое число c ≥ 0 и сдвинем получившуюся строку 01001 циклически на c позиций влево. Например, при c = 1 получится строка 10010, представляющая собой двоичную запись числа 18. Значит, сдвигом на одну позицию из числа 9 получается число 18; будем это записывать так: 9 ⋘ 1 = 18. (Если 01001 сдвинуть влево на две позиции, то получится 00101, то есть 9 ⋘ 2 = 5.) Итак, sc – это число, получившееся сдвигом числа s на c позиций влево. Для зашифрования осмысленного слова выбирается секретный ключ – набор из 64 чисел k1,…,k32 ∈ {0,…,30} и c1, … , c32 ∈ {0,1,2,3}. Затем с каждой буквой слова (по отдельности) проделывается следующее. Букву заменяют числом a по таблице и последовательно вычисляют a1 = (a + k1 ) ⋘ c1, a2 = (a1k2) ⋘ c2, … , a32 = (a31 + k32 ) ⋘ c32. Исходную букву затем заменяют на букву, соответствующую числу a32. (Если в процессе вычислений получается число, превышающее 30, то оно заменяется остатком от деления на 31. Так, сумму 20 + 17 следует заменить на 6.) 
В результате зашифрования получился набор букв ЯГКЫНИ. Найдите исходное слово, если известно, что при зашифровании на этом ключе буква Ъ переходит в букву Ь, а буква П – в Е.