Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
Доказательство. Введем обозначение k — gcd(d, n). Тогда из п \ (ad—bd) следует, что (п/к) | (d/k)(a — b). Поскольку gcd(d/k, п/к) = 1, из (п/к) \ (к/к)(а — Ь) следует, что (п/к) \ (а — Ь). о
Итак, арифметические операции в фактор-группе Zn полностью сохраняют свойства сравнимости арифметических операций в поле Z.
Следствие 6-1. Если функция f(x) является полиномом над полем Z и a=b(mod п) для п > 1, то f(a) = /(fc)(modn). ?
6.2.2 Решение линейного уравнения в фактор-группе Жп
В теореме 4.2 (раздел 4.3.2.5) дано определение мультипликативной инверсии по модулю п. Как следует из этой теоремы, для того, чтобы существовало число, обратное к целому числу а по модулю п, т.е. единственное число х < п, удовлетворяющее условию ах=l(mod п), необходимо и достаточно, чтобы выполнялось условие gcd(a, п) = 1.
Теорема 6.5. Для того чтобы при п > 1 уравнение
ах = fc(mod п) (6.2.7)
имело решение, необходимо и достаточно, чтобы выполнялось условие gcd(o,n) | Ъ.
Глава 6. Теория чисел
219
Доказательство. По определению 4.4 (раздел 4.3.2.5) уравнение (6.2.7) можно переписать в виде линейного уравнения
ах+ кп = Ь, (6.2.8)
где к — некоторое целое число.
{=>) Пусть выполняется условие (6.2.8). Поскольку число gcd(a, ri) является делителем левой части уравнения, оно должно быть также делителем его правой части.
(<=) Используя обобщенный алгоритм Евклида (алгоритм 4.2) для чисел а и п, можно вычислить
аА + рп = gcd(a, ri).
Поскольку число Ь/ gcd(a, ri) является целым, умножая на него обе части уравнения, получаем формулы (6.2.8) или (6.2.7), где х = gCd(a п) (m°d п) — °Дно 113 решений. ?
Легко проверить, что при заданном решении х уравнения (6.2.7) уравнение
х Н--—--(modri) для г = 0.1.2,...,gcd(a,п) — 1
gcd(a, ri)
имеет gcd(a, ri) разных решений, которые меньше числа п. Очевидно, что условие gcd(a,n) = 1 является достаточным для того, чтобы уравнение (6.2.8) имело единственное решение, которое меньше числа п.
Пример 6.1. Уравнение
2х = 5(mod 10)
не имеет решения, поскольку gcd(2,10) = 2 { 5. Фактически левая часть уравнения, 2х, должна быть четным числом, поскольку правая часть, 10к + 5, может быть только нечетным числом. Следовательно, пытаясь решить это уравнение, мы ищем число, которое одновременно было бы четным и нечетным, что, разумеется, невозможно.
С другой стороны, уравнение
6a;=18(mod36)
является разрешимым, поскольку gcd(6,36) | 18. Это уравнение имеет шесть решений: 3, 9, 15, 21, 27 и 33. ?
Теорема 6.6. Если для всех чисел п > 1 выполняется условие gcd(a, ri) = 1, то ai + b ^aj + 6(mod ri) для всех чисел b, г, j, удовлетворяющих условию 0 ^ г < 3 < п-
220
Часть II. Математические основы
Доказательство. Допустим противоположное: ai + b = aj + b(modn). Тогда по теореме 6.4 г = j(modn), что противоречит условию 0 < г < j < п. ?
Из этого свойства следует, что для целых чисел ним, удовлетворяющих условию gcd(a, п) = 1, числа аг + fc(modn), где г = 0,1,..., п — 1, образуют полную систему вычетов (complete residue system) по модулю п, т.е. значение выражения ai+b(modn) пробегает всю фактор-группу Z^, когда число г принимает значения из этой же фактор-группы.
6.2.3 Китайская теорема об остатках
Итак, нам известно условие разрешимости линейного уравнения (6.2.7). Однако довольно часто возникает необходимость решать систему таких уравнений по разным модулям.
а\х = 6i(modni), G2a; = b2(modn2),
(6.2.9)
arx = br (mod nr),
где Gj, bi € Z, a,j Ф 0 при г — 1,2,..., г.
Очевидно, система уравнений имеет решение, только если каждое из уравнений разрешимо. Введем обозначение
а\ = gcd(ai, гц),
где г = 1,2,..., г. Тогда по теореме 6.5 для разрешимости уравнений необходимо, чтобы выполнялось условие а\ \ fcj. В этом случае свойства умножения (теорема 6.3) и деления (теорема 6.4) по модулю п позволяют переписать систему (6.2.9) в эквивалентном, но более простом виде.
х = Ci(modmi), х = С2 (mod тг),
(6.2.10)
х = cr(modmr), m-i = TLi/di
где г = 1,2,..., г,
Ci = {bildi){ai/di) 1 (mod mj).
Заметим, что число (aj/di)-1(modmj) существует, поскольку gcd(aj/dj,mi) = 1 (теорема 4.2 из раздела 4.3.2.5).
Глава 6. Теория чисел
221
Из курса линейной алгебры известно, что систему (6.2.10) можно представить в матрично-векторном виде
АХ = С, (6.2.11)
где
(1
А =
\
Lm2
(6.2.12)
(х\
х
Х =
(6.2.13)
V7 /сЛ
С2
(6.2.14)
\сг;
Заметим, что, поскольку г-е уравнение (г = 1,2,...,г) в системе (6.2.10) представляет собой сравнение по модулю тщ, диагональные элементы матрицы А обозначают классы вычетов единицы по модулю mi, т.е.
lm, = farm + 1
(6.2.15)
для некоторого целого числа fa(i = 1,2,..., г). Остальные элементы матрицы А равны нулю по соответствующему модулю (т.е. нули в г-й строке являются нулями
ПО МОДУЛЮ ТПг).
Итак, при заданном r-мерном векторе С решение системы уравнений (6.2.10) сводится к идентификации диагональной матрицы А. Иначе говоря, решить систему (6.2.10) значит найти класс вычетов единицы по модулям mi, где г — 1,2,..., г, как показано в выражении (6.2.15). Из курса линейной алгебры известно, что если такая матрица А существует, то, поскольку все ее диагональные элементы не
