Rambler's Top100 Service
Поиск   
 
Обратите внимание!   Обратите внимание!
 
  Наука | Задачи
 Написать комментарий  Добавить новое сообщение
 См. также

Книги"Введение в криптографию" под редакцией В.В.Ященко: pr8.3.

зашифрование дат рождения
23.05.2002 15:23 | МЦНМО

    Сообщение, подлежащее зашифрованию, представляет собой цифровую последовательность, составленную из дат рождения 6 членов оргкомитета олимпиады. Каждая дата представлена в виде последовательности из 8 цифр, первые две из которых обозначают день,следующие две - месяц, а остальные - год. Например, дата рождения великого математика Л.Эйлера 4 апреля 1707 года представляется в виде последовательности 04041707. Для зашифрования сообщения строится ключевая последовательность длины 48. Для ее построения все нечетные простые числа, меньшие 100, выписываются через запятую в таком порядке, что модуль разности любых двух соседних чисел есть та или иная степень числа 2. При этом каждое простое число выписано ровно один раз, а числа 3, 5 и 7 записаны в виде 03, 05 и 07 соответственно. Удалив запятые из записи этой последовательности, получим искомую ключевую последовательность.
При зашифровании цифровой последовательности, представляющей сообщение, ее цифры почленно складываются с соответствующими цифрами ключевой последовательности, при этом каждая полученная сумма заменяется ее остатком от деления на 10. В результате зашифрования сообщения получена последовательность: 150220454213266744305682533362327363924975709849
Определите даты рождения членов оргкомитета олимпиады.
(Задача с сайта www.cryptography.ru.)
  • Хочу подсказку


  •     Решение:
    Естественно предположить, что все члены оргкомитета родились в ХХ веке. Отсюда сразу замечаем, что на 3, 7, 11, 15, 19 и 23 местах последовательности простых чисел расположены числа 11, 17, 47, 53, 83 и 89 соответственно.

    Выясним, какие числа являются соседними с указанными шестью числами. Для этого составим таблицу их возможных "соседей". В соответствии с условием имеем:

    \begin{tabular}{|c|c|} \hline число & соседи \\ \hline 11 & 13, 19, 43, 7, 3 \\ \hline 17 & 13, 19 \\ \hline 47 & 79, 43, 31 \\ \hline 53 & 61, 37 \\ \hline 83 & 79, 67, 19 \\ \hline 89 & 97, 73 \\ \hline \end{tabular}
    Учитывая, что первая цифра в номере месяца принимает значения только 0 или 1, построим следующую таблицу:
    \begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|} \hline 15 & 02 & 20 & 45 & 42 & 13 & 26 & 67 & 44 & 30 & 56 & 82 \\ \hline & & 19 & & & & 19 & & & & 19 & \\ \hline & & 11 & & & & 17 & & & 31 & 47 & \\ \hline & 03 & & 03 & & 13 & & 13 & & & & 43 \\ \hline & 07 & & 07 & & 19 & & 19 & & & & 79 \\ \hline & & & 13 & & & & & & & & \\ \hline & & & 19 & & & & & & & & \\ \hline & & & 43 & & & & & & & & \\ \hline \end{tabular}
    \begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|} \hline 53 & 33 & 62 & 32 & 73 & 63 & 92 & 49 & 75 & 70 & 98 & 49 \\ \hline & & 19 & & & & 19 & & & & 19 & \\ \hline & 37 & 53 & 61 & & 67 & 83 & & & 73 & 89 & 97 \\ \hline & & & & & & & 19 & & & & \\ \hline & & & & & & & 79 & & & & \\ \hline & & & & & & & & & & & \\ \hline & & & & & & & & & & & \\ \hline & & & & & & & & & & & \\ \hline \end{tabular}
    где в первой строке расположено шифрованное сообщение, во второй строке - известные участки исходного сообщения, в третьей строке - ставшие известными участки ключевой последовательности, в остальных строках - возможные варианты ключевой последовательности в соответствующих позициях. При составлении таблицы учитывалось, что каждое число должно встретиться ровно один раз. Позиции чисел 31, 37, 67, 73 определяются однозначно. Их расположение однозначно определяет места для простых чисел 61 и 97.

    Снова выпишем известные числа последовательности простых чисел и варианты для их соседей (первые две строки таблицы на этом шаге не понадобятся):
    \begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|} \hline & & 11 & & & & 17 & & & 31 & 47 & \\ \hline & 03 & & 03 & & 13 & & 13 & & & & 43 \\ \hline & 07 & & 07 & & 19 & & 19 & & & & 79 \\ \hline & & & 13 & & & & & & & & \\ \hline & & & 19 & & & & & & & & \\ \hline & & & 43 & & & & & & & & \\ \hline \end{tabular}
    \begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|} \hline & 37 & 53 & 61 & & 67 & 83 & & & 73 & 89 & 97 \\ \hline & & & & & & & 19 & & & & \\ \hline & & & & & & & 79 & & & & \\ \hline & & & & & & & & & & & \\ \hline & & & & & & & & & & & \\ \hline & & & & & & & & & & & \\ \hline \end{tabular}
    Возможные соседи для числа 61 - лишь 59 и 29, а для 67 - лишь 59 и 3. Поэтому между 61 и 67 может находиться только число 59. Возможными соседями для числа 73 являются 89, 71 и 41. Ни одно из этих чисел не может быть соседом для 19, а для 79 может быть только 71. Таким образом, однозначно определяется расположение чисел 71 и 79. Для числа 47 остался только один кандидат в соседи справа - число 43. Общим соседом для 43 и 37 может быть только 41. Скорректируем таблицу с учетом сделанных выводов:
    \begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|} \hline & & 11 & & & & 17 & & & 31 & 47 & 43 \\ \hline & 03 & & 03 & & 13 & & 13 & 29 & & & \\ \hline & 07 & & 07 & & 19 & & 19 & 23 & & & \\ \hline & & & 13 & & & & & & & & \\ \hline & & & 19 & & & & & & & & \\ \hline \end{tabular}
    \begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|} \hline 41 & 37 & 53 & 61 & 59 & 67 & 83 & 79 & 71 & 73 & 89 & 97 \\ \hline & & & & & & & & & & & \\ \hline & & & & & & & & & & & \\ \hline & & & & & & & & & & & \\ \hline & & & & & & & & & & & \\ \hline \end{tabular}

    Участок последовательности 17 * * 31 имеет только два варианта доопределения: (а) 17-19-23-31 и (б) 17-13-29-31. Рассмотрим оба случая.

    а) Выпишем фрагмент таблицы для первого случая:
    \begin{tabular}{|c|c|c|c|c|c|c|c|c|c|} \hline & & 11 & & & 13 & 17 & 19 & 23 & 31 \\ \hline & 03 & & 03 & & & & & & \\ \hline & 07 & & 07 & & & & & & \\ \hline \end{tabular}
    Очевидно, что числа 3 и 7 должны обязательно быть соседними с числом 11. Число 29 еще не встречалось, значит оно должно располагаться либо на первом месте, либо на пятом. И то и другое невозможно, так как в обоих позициях оно является соседом либо для числа 3, либо для числа 7, что не соответствует условию (отличие соседних чисел на степень двойки). Следовательно, рассматриваемый случай невозможен.

    б) Выпишем фрагмент таблицы для второго случая:
    \begin{tabular}{|c|c|c|c|c|c|c|c|c|c|} \hline 05 & & 11 & & 23 & 19 & 17 & 13 & 29 & 31 \\ \hline & 03 & & 03 & & & & & & \\ \hline & 07 & & 07 & & & & & & \\ \hline \end{tabular}

    Очевидно, что числа 3 и 7 должны обязательно быть соседями для числа 11. Число 5 может попасть только на первую позицию (т.к. оно не может находиться рядом с 19). Значит, в пятой позиции должно быть число 23. Ясно, что числа 3 и 7 теперь расставляются однозначно.
    Таким образом, приходим к выводу, что возможен всего один вариант ключевой последовательности. Получим окончательный вариант таблицы и найдем ответ (вторая строка):
    \begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|} \hline 15 & 02 & 20 & 45 & 42 & 13 & 26 & 67 & 44 & 30 & 56 & 82 \\ \hline 10 & 09 & 19 & 48 & 29 & 04 & 19 & 54 & 25 & 09 & 19 & 49 \\ \hline 05 & 03 & 11 & 07 & 23 & 19 & 17 & 13 & 29 & 31 & 47 & 43 \\ \hline \end{tabular}
    \begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline 53 & 33 & 62 & 32 & 73 & 63 & 92 & 49 & 75 & 70 & 98 & 49 \\ \hline 12 & 06 & 19 & 71 & 24 & 06 & 19 & 70 & 04 & 07 & 19 & 52 \\ \hline 41 & 37 & 53 & 61 & 59 & 67 & 83 & 79 & 71 & 73 & 89 & 97 \\ \hline \end{tabular}

    Ответ: 10.09.1948 29.04.1954 25.09.1949 12.06.1971 24.06.1970 04.07.1952


    Написать комментарий
     Copyright © 2000-2015, РОО "Мир Науки и Культуры". ISSN 1684-9876 Rambler's Top100 Яндекс цитирования