Документ взят из кэша поисковой машины. Адрес оригинального документа : http://phys.web.ru/db/msg.html?mid=1161235&uri=node92.html
Дата изменения: Unknown
Дата индексирования: Sun Apr 10 14:56:46 2016
Кодировка: koi8-r
"Введение в криптографию" под редакцией В.В.Ященко - Все о Геологии (geo.web.ru)
Все о геологии :: на главную страницу! Геовикипедия 
wiki.web.ru 
Поиск  
   Rambler's Top100 Service
 Главная страница  Конференции: Календарь / Материалы  Каталог ссылок    Словарь       Форумы        В помощь студенту     Последние поступления
   Геология | Книги
 Обсудить в форуме  Добавить новое сообщение
Next: ...к задачам второй олимпиады Up: 7.6. Указания и решения Previous: 7.6. Указания и решения Contents: Содержание

...к задачам первой олимпиады

1.1. Все клетки квадрата размера $ n\times n$ разобьем на непересекающиеся группы по четыре клетки в каждой.

1 2 3 4 5 1
5 6 7 8 6 2
4 8 9 9 7 3
3 7 9 9 8 4
2 6 8 7 6 5
1 5 4 3 2 1

Отнесем клетки к одной и той же группе, если при каждом повороте квадрата до его самосовмещения они перемещаются на места клеток этой же группы. На рисунке показано такое разбиение на группы всех клеток квадрата $ 6\times 6$, причем клетки одной группы помечены одной и той же цифрой. Всего таких групп будет $ n^2/4$ (целое, так как $ n$ - четное число). При наложении трафарета на квадрат ровно одна клетка из каждой группы окажется под его вырезами. Каждому трафарету поставим в соответствие упорядоченный набор всех клеток из таких групп, оказавшихся под вырезами трафарета при наложении его на квадрат помеченной стороной вверх. Такое соответствие является взаимнооднозначным, поскольку каждому ключу будет однозначно соответствовать упорядоченный набор из $ n^2/4$ клеток (по одной из каждой группы), вырезанных в трафарете, и наоборот. Всего таких наборов $ 4^{n^2/4}$. В самом деле, существует ровно четыре различных варианта выбора клетки из каждой группы независимо от выбранных клеток из других таких групп. Таким образом, число различных ключей шифра ``поворотная решетка'' при четных значениях $ n$ равно $ 4^{n^2/4}$.

1.2. Легко видеть, что $ f(x)=(x^2+3x+1)(x^4+x+1)+2$. Отсюда $ f(x_1)=f(x_2)=2$, где $ x_1, x_2$ - корни многочлена $ x^2+3x+1$. Получаем

Буква ш.с. Ф В М Е Ж Т И В Ф Ю
Номер 22 3 14 7 8 20 10 3 22 32

Номер 20 1 12 5 6 18 8 1 20 30
Буква о.с. Т А К Д Е Р Ж А Т Ь

Ответ: ТАКДЕРЖАТЬ

1.3. Ответ: начиная с 54.

1.4. Разложим числа $ m$ и $ d$ на простые множители: $ d=6=2\cdot3$; $ m=6930=2\cdot3\cdot3\cdot5\cdot7\cdot11$. Обозначим буквой $ t$ число $ m/d$, равное произведению $ 3\cdot5\cdot7\cdot11 $. Найдем все его делители $ q$ вида: $ q=3^x5^y7^z11^u$, где числа $ x$, $ y$, $ z$ и $ u$ принимают только значения 0 и 1. Тогда, как нетрудно видеть, числа $ q$ и $ t/q$ окажутся взаимно простыми. Полагая $ а=dq$ и $ b=dt/q$, получим все искомые пары $ (a,b)$. В самом деле, в указанных выше условиях наибольший общий делитель такой пары равен $ d$, а ее наименьшее общее кратное равно $ dqt/q=dt=dm/d=m$. Таким образом, искомое число упорядоченных пар совпадает с числом всех делителей $ q$ вида: $ 3^x5^y7^z11^u$, которое равно числу всех упорядоченных наборов длины 4 и состоящих только из 0 и 1. Число всех таких наборов равно $ 2^4=16$, так как для каждого места в наборах существует ровно 2 варианта его значений независимо от значений на других местах. В общем случае число $ m/d$ представляется в виде $ m/d=p^ir^j\dots s^h$, где $ p$,$ r$,...,$ s$ - различные простые числа, а $ i$,$ j$,...,$ h$ - натуральные числа. Число всех делителей вида: $ q=p^xr^y\dots s^z$, где числа $ x$,$ y$,...,$ z$ принимают только по два значения (0 и соответствующий натуральный показатель степени в представлении числа $ m/d$), равно $ 2^k$, где $ k$ - число всех простых делителей числа $ m/d$. Если число различных простых множителей в каноническом разложении числа $ m/d$ равно $ k$, то число различных упорядоченных пар $ (a,b)$ равно $ 2^k$.

Ответ: 16 пар (пары $ (a,b)$ и $ (b,a)$ разные). В общем случае число упорядоченных пар равно $ 2^k$, где $ k$ - число всех простых делителей $ m/d$.

1.5. Из последней строчки легко заметить, что Ш=0. Тогда из первого столбца находим, что И=1. Затем из последнего столбца находим Ф=2. Итак,

\begin{displaymath} \begin{array}{ccccc} \texttt{2Н} & \times & \texttt{Ы} & ... ...ttt{10А}& + & \texttt{МР} & = & \texttt{1МН} \end{array} \end{displaymath}

Из средней строки ясно, что Н$ >$Е. Из первого столбца находим Е=7. Из средней строки можно вычислить значения Н и З: Н=8 и З=4. Получим

\begin{displaymath} \begin{array}{ccccc} \texttt{28} & \times & \texttt{Ы} & ... ...ttt{10А}& + & \texttt{МР} & = & \texttt{1М8} \end{array} \end{displaymath}

Далее, последовательно вычисляем значения: А=5,Ы=9, М=6, Р=3. Расставим буквы в порядке возрастания их цифровых значений и получим текст ШИФРЗАМЕНЫ

Ответ: ШИФРЗАМЕНЫ

1.6. Ответ: например, $ cbcacbc$.

Обозначим $ \overline{\ph(P)}$ - набор $ \ph(P)$, выписанный в обратном порядке.
\begin{align*} \ph(cbcacbc)=&\overline{\phi(bcacbc)}= \overline{\ph(cacbc)a\ph(... ...rline{\overline{cbc}a\overline{cbc}}= \overline{cbcacbc}=cbcacbc. \end{align*}

В общем случае можно показать, что множество искомых наборов состоит из слов вида:

\begin{displaymath} P=\left\{ \begin{array}{ll} cb\underbrace{c\dots c}_{\text... ...tsize $k$ раз}}& \text{$k$ - четное.} \end{array} \right. \end{displaymath}

Next: ...к задачам второй олимпиады Up: 7.6. Указания и решения Previous: 7.6. Указания и решения Contents: Содержание

Проект осуществляется при поддержке:
 Геологического факультета МГУ,
РФФИ
    
TopList Rambler's Top100