Последовательности, функции и их кодирование на Верченко
Ошибка.
Попробуйте повторить позже
Целое число 
может быть преобразовано следующим образом. Пусть, например, 
Представим его в двоичной системе
счисления пятизначным числом: 
Теперь выберем какое-нибудь целое число 
и сдвинем получившуюся
строку 
циклически на 
позиций влево. Например, при 
получится строка 10010, представляющая собой
двоичную запись числа 18. Значит, сдвигом на одну позицию из числа 9 получается число 
будем это записывать так:
(Если 
сдвинуть влево на две позиции, то получится 
то есть 
)
Итак, 
— это число, получившееся сдвигом числа 
на 
позиций влево.
Для зашифрования осмысленного слова выбирается секретный ключ — набор из 
чисел
Затем с каждой буквой слова (по отдельности) проделывается следующее.
Букву заменяют числом 
по таблице
и последовательно вычисляют
Исходную букву затем заменяют на букву, соответствующую числу 
(Если в процессе вычислений получается число, превышающее 
то оно заменяется остатком от деления на 
Так, сумму 
следует заменить на 
)
В результате зашифрования получился набор букв ЯГКЫНИ.
Найдите исходное слово, если известно, что при зашифровании на этом ключе буква Ъ переходит в букву Ь, а буква П — в Е.
Источники:
Подсказка 1
В таких задачах, где идёт сложный процесс, хорошей идеей будет посмотреть на первые несколько шагов. Вдруг обнаружится цикличность, или можно будет заметить явную закономерность и вывести общую формулу. Попробуйте посмотреть, как меняется для чисел, которые записываются в виде пяти знаков (может быть с нулями в начале) в двоичной системе счисления, значение при операции левого циклического сдвига (то есть при с=1).
Подсказка 2
Заметим, что s « 1 = 2s (mod 31) (для этого надо разобрать два случая, чему равна первая цифра в двоичной системе счисления). Тогда s « c = 2^c * s (mod 31). А это значит, что мы стали чуть больше понимать, как работает процесс. Однако, все ещё не представляется возможным решить задачу, потому что даже сейчас непонятно, как явным образом ввести ограничения на k_i и c_i. Каким свойством обладает преобразование s « c? А что будет, если сделать не s « c, а (k + n) « c? Чему равно такое выражение?
Подсказка 3
Преобразование линейно, а значит и композиция преобразований тоже линейна. Значит оно записывается в виде kx + b. Что тогда можно сказать про k и b, если у нас есть значения на двух разных аргументах?
Покажем, что
Заметим, что достаточно доказать для 
Пусть 
Если 
, то равенство ( 
очевидно. Если 
то
Тогда
и равенство 
доказано. Следовательно,
То есть, на одном шаге шифрования — линейное преобразование числа 
Так как композиция линейных преобразований есть линейное
преобразование, то 
, где 
и 
— неизвестные.
Воспользуемся тем, что на этом ключе буква Ъ переходит в букву Ь, а буква П — в Е:
Вычитая из первого равенства второе, получим: 
Отсюда 
Тогда
и, следовательно, 
Окончательно получили:
Тогда
Последовательно подставляя буквы шифрованного текста ЯГКЫНИ, получим исходное слово МОСКВА.
МОСКВА
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
