Курс теории чисел и криптографии - Коблиц Н.
Скачать (прямая ссылка):
а Ь с d
X обозначает вектор неизвестных (*), а В — вектор констант Q). Словесно эту систему уравнений можно интерпретировать как задачу поиска вектора, при «умножении» которого на заданную матрицу получается заданный вектор. Таким образом, эта система аналогична уравнению ах = Ь, которое решается умножением обеих частей на а 1 (если а ф 0). Аналогичный вид имеет один из способов решения матричного уравнения AX = В: находится обратная к матрице А матрица А 1, умножение на которую обеих частей уравнения дает единственное векторное решение X = A 1B.
Под обратной к матрице А понимается такая матрица, умножение которой на А дает единичную матрицу
1 0 0 1
(применение этой матрицы к любому вектору оставляет этот вектор неизменным). Но не все матрицы имеют обратные. Нетрудно показать, что матрица
а Ь с d
имеет обратную тогда и только тогда, когда отличен от нуля ее опре-
def
делитель D = ad — be. В этом случае обратная матрица равна 1 ( d -Ь\ ( D~ld -D~lb
76
ГЛ. iii. КРИПТОГРАФИЯ
Пусть имеется набор векторов Xx = ...,Xk= расположенных в столбцах 2 X /с-матрицы. Определим произведение матриц
Ах _ {а Ь\ Sx1...XЛ def (axi + byx ... ахк + ЬуЛ \с а)\у1...ук) XcX1-J-dyx ... схк-\-dy к)'
т.е. матрица А просто применяется поочередно к каждому столбцу, давая при этом очередной столбец произведения. Например, произведение 2 X 2-матриц вычисляется по формуле
fa b\ (a b' \ _ /аа + bc ab' + bd'\ [с d) \с d'J - [ca' + dc cb' + dd')'
Аналогичными свойствами обладают З X 3-матрицы, которые применяются к трехмерным векторам, и т. д. Однако формулы для определителя и обратной матрицы усложняются. На этом мы завершаем краткий обзор линейной алгебры над множеством вещественных чисел.
Линейная алгебра по модулю N. В §1, имея дело с отдельными символами и шифрующими отображениями Z/7VZ, мы обнаружили два удобных для использования класса отображений:
(a) «линейные» отображения С = аР, где а обратимо в Z/NZ,
(b) «аффинные» отображения С = аР + Ь, где а обратимо в Z/NZ. Аналогичная ситуация возникает, когда элементами сообщения
являются биграммы-векторы. Сначала рассмотрим линейные отображения. При работе с (Z/'AZ)2, в отличие от случая Z/NZ, вместо целого а мы используем 2 X 2-матрицу, которую будем обозначать через А. Сначала выясним, матрицы какого типа нам потребуются.
Пусть R — любое коммутативное кольцо, т. е. множество с умножением и сложением, удовлетворяющими тем же правилам, что и в поле, за исключением того, что допускается существование ненулевых элементов, не имеющих обратных по умножению. Например, Z/NZ — всегда кольцо, но оно не поле, если число N не является простым. Через R* обозначим подмножество обратимых элементов R. Например, (Z/NZ)* = {0 < j < N I НОД (j,N) = 1}.
Для коммутативного кольца R обозначим через M2(R) множество всех 2 X 2-матриц с элементами из A с обычными для матриц операциями сложения и умножения. Мы называем M2(R) кольцом матриц над R; M2(R) — кольцо, но некоммутативное, так как произведение матриц зависит от порядка сомножителей.
Ранее в этом разделе рассматривался случай, когда A = R есть кольцо (более того, поле) вещественных чисел. Напомним, что
§ 2. ШИФРУЮЩИЕ МАТРИЦЫ
77
матрица
a b с d
с вещественными элементами а, о, с, d имеет обратную тогда и только тогда, когда определитель D — ad — be отличен от нуля. В этом сл>чае обратная матрица имеет вид
D~ld -D~Xb -D~Xc D~la
Такая же ситуация имеет место для произвольного кольца R. Именно, пусть
a b с d
є M2[R)
и D = det Л d=f ad — be принадлежит R*. Пусть D 1 обозначает обратный по умножению элемент к D в R. Тогда.
D~ld -D~Xb\fa b\ = (D~\da - be) О
-0'1C D~\ J \c d)~{ о D~\-cb + ad)
1 0 0 1
Тот же результат
1 О О 1
мы получим, умножив матрицы в обратном порядке. Таким образом, обратная к Л матрица задается той же самой формулой, что и для матриц из вещественных чисел:
.-і ( D~ld -D~lb А -{-D~lc D~la
Пример 1. Найти обратную к матрице
A=(^1 g) GM2(Z/26Z).
Решение. Здесь ?) = 2- 8- 3- 7= -5 = 21 в Z/26Z. Так как НОД (21,26) = 1, то определитель D обратим, а именно, 21 1 = 5. Таким образом,
_1 /5-8 -5 -3\ [40 [14 11
Л 1 -5 • 7 5 - 2 / V -35 10 J V 17 10
78
ГЛ. III. КРИПТОГРАФИЯ
Проверим:
/14 11 \(2 ЗЛ / 105 130\ _ /1 0\ ^17 10 у V 7 8/ V104 131 у — \0 1/'
Здесь, поскольку операции проводятся в Z/26Z, знак « = » означает, что элементы матриц сравнимы по модулю 26.
Как и в случае вещественных чисел, 2 X 2-матрицу
С J)
с элементами из кольца R можно умножить на вектор-столбец (х) с х,у Є і? и получить новый вектор (ху, J:
(х'\ - ( а Ь\ fx\ _ fax + Ьу\
W) ~ Vе dJ\yJ~ \cx + dyj-Это отображение является линейным: оно переводит линейную комбинацию f^irit^2E2), где кл и к2 принадлежат R, в (1I11It1?2*?). Един-ственное отличие рассматриваемого случая от предыдущего состоит в том, что вместо вещественных чисел здесь мы имеем дело с элементами кольца R.
