Курс теории чисел и криптографии - Коблиц Н.
Скачать (прямая ссылка):
V2о2/' V707/' UOi)1 V 606 /' д) ^лож*ть вектор (g00j с любым из 11 векторов п. г) и привести по модулю 1111.
6. Воспользоваться методом математической индукции: сначала проверить, что утверждение верно при п = 1,2,...,6, а затем показать, что если оно верно при га, то оно верно при п + 6. А именно, убедиться в том, что
/„+6+1 fn+ь \ /і iv+6 /1 і\Vі 1
fn+b /„+6-і/ Vi о У Vi оУ Vi о
' fb+l /і \ / /п + 1 fn
fb fb-1 J V fn /п-1
с 0\ /fn + i fn
,0 с) V /„ /п-1
'с/п + 1 Cfn
Cfn Cfn _ 1
(mod а),
где с Є (Z/dZ)*, и воспользоваться предположением индукции. (Можно показать, что для любого целого а найдется такое 6, что a\fn ¦<=> b\n, и что если а = ра при простом р ф 5, то Ъ делит pQ_1(p2 — 1); доказательство использует некоторые сведения из алгебраической теории чисел для квадратичного расширения поля вещественных чисел, порожденного отношением «золотого сечения» (1 + у/Е)/2; заметим, что это число и сопряженное с ним число (1 — у/Е)/2 являются собственными значениями матрицы из определения чисел Фибоначчи.)
7. Л"1 = ( 23 7 V «SENATORTOOK.»
VlS 5 /
8. Д-! = (22 16V «МЕЕТ AT NOON.»
V 21 17/
/ 22 20 \ / 3 7 \
9. -4-1 = ( ), «WHY NO GO? MARIA»; A=I ),
V 28 8 / V 4 1 /
«JMLD W
EFWJV».
10. «СЛАВА КПСС».
11. Композиция криптосистем имеет матрицу шифрования A2A\.
/ 18 28 \
12. a) «?CVK». б) Применить матрицу ) к вектору шифртекста, дей-
V 19 20 /
/15 15\
ствуя в кольце вычетов по модулю 29, а к результату применить матрицу ( ),
V 22 3 /
238
ОТВЕТЫ К УПРАЖНЕНИЯМ
(4 9 \ ). Открытый текст «GIVE 25 28 /
действуя в кольце вычетов по модулю 26; «STOP».
13. В силу предложения III. 2.1 (а именно, если нарушается Ь), то нарушается и с)) существует ненулевой вектор, переводимый матрицей Ab Q). Такую биграмму-вектор можно прибавить к любой биграмме-вектору открытого текста без изменения соответствующего шифртекста.
/ 18 6 1 1 10 29 14 16 11 14 10 11 21 \
14. Шифртекст имеет вид ), а по-
426 13 8 3 10 25 11 8 12 20 27 24 /
I10 17 0 n
следние три столбца (10-й, 11-й и 12-й) открытого текста имеют вид ( ).
\ 0 11 27/
Определитель матрицы, образованной 10-м и 11-м столбцами открытого текста, равен 20 (mod 30), что не имеет обратного по модулю 30, но имеет обратное по модулю 3. Определитель матрицы, образованной 11-м и 12-м столбцами открытого текста, равен 9 (mod 30) и не обратим по модулю 30, но обратим по модулю 10. Производя в первом случае операции по модулю 3, получаем
/10 17\ /10 11 \ — 1 /1 2\ /1 2 n-i /1 on
A'1 (mod 3)= • = ¦ = . Аналогично,
40 11/ 420 27/ Vo 2> 42 0/ \>
во втором случае производя операции по модулю 10, получаем А = I ). По
4 5 8 /
китайской теореме об остатках имеется единственная матрица Д-1 (mod 30), удо-
9
THE PLANS ТО KARLA.».
/ 10 22 26 0 10 1 5 1 7 \
15. Шифртекст имеет вид ( ), а первые три столб-
421 27 19 28 9 27 21 26/ / 2 8 on
ца открытого текста имеют вид ( ). При использовании равенства
429 29 29 /
Л-1 = PC-1 учесть, что наибольший общий делитель определителя матрицы из первых двух столбцов шифртекста и 30 равен 6. Лучше использовать 1-й и 3-й
/ 10 26 \ '
столбцы: det = 4 и НОД (4, 30) = 2. Взяв эту матрицу в качестве С и опе-
4 21 19/
(2 2 n1 ) +15Аі, где А\ Є iW*2(Z/2Z). 8 4 /
, / 10 22 26 \ / 2 8 on _ .
Воспользовавшись тем, что А [ I= )> и TeMi 4tol3et^4 не-
4 21 27 19 / 4 29 29 29 / \
-1 /'172^ -1 Ґ 17 2 \ т,
четен, показать что либо A=I ), либо А = ( )• В первом вари-
n819/ 4 23 19/
анте получаем открытый текст «С.I.A. WILLLHTLA», а во втором — открытый текст «С.I.A. WILL HELP».
16. Использовать китайскую теорему об остатках.
17. (р2 - 1)(р2 -р).
18. Определитель взаимно прост с р° в том и только том случае, когда он взаимно прост с р; р4а_3(р2 — 1)(р — 1).
19- Up]NC1 - ^X1 - -рУ, 157248, 682080, 138240.
го. ^(t2)np|n((i- ^)(I -?)¦¦¦(! - і/*-»-
21- N6UpIN^ - ^)(1 - j2"); 106 299 648; 573629 280; 124416000.
22. a) (р2 - 1)(р2 - р). б) р2 - р.
/21 27n . ,i\ /
23. а) До = )¦ б) (.). в) Шесть матриц (ср. с ответом к упражнению
4 18 27/ 1
ОТВЕТЫ К УПРАЖНЕНИЯМ
239
226) при р = 3): А = J), где ф = (?, (21), Q, Q, (JJ)1Q.
24. а) НОД (det (А — /), JV) = I1 где det (Л - /) = (а - l)(d - 1) - 6с (применить утверждение об эквивалентности условий а) и с) в предложении III. 2. 1 с заменой
/a-l ь \
А на А — I = [ )). б) Пусть Fjv — поле Z/7VZ. Биграммы образуют дву-
ч с d — і /
мерное векторное пространство, а фиксированные биграммы — подпространство в нем. Любое подпространство, содержащее более одного вектора, либо одномерно (и содержит N векторов), либо содержит все биграммы (тогда А = I).
