Файл: Учебник издание шестое Рекомендовано Министерством образования и науки Российской Федерации в качестве учебника для студентов высших технических учебных заведений.pdf

3.8. ЛИНЕЙНЫЕ УРАВНЕНИЯ ПО МОДУЛЮ m
105
Пример 3.8.4. Решим систему уравнений
x ≡ 1 (mod 2), x ≡ 2 (mod 5), x ≡ 5 (mod 7).
Из первого уравнения следует, что x = 1+2q. Чтобы вычислить q, подста- вим x во второе уравнение: 1 + 2q ≡ 2 (mod 5) или 2q ≡ (2 − 1) (mod 5). Так как 2
−1
≡ 3 (mod 5), то q ≡ 2
−1
(2 − 1) (mod 5) ≡ 3 (mod 5) или q = 3 + 5r
для некоторого r. Следовательно, решением первых двух уравнений явля- ется x = 1 + 2(3 + 5r) = 7 + 2 · 5r, т. е. x ≡ 7 (mod 2 · 5).
Осталось решить систему уравнений x ≡ 7 (mod 2 · 5) и x ≡ 5 (mod 7).
Имеем x = 7 + 2 · 5q ≡ 5 (mod 7) или 2 · 5q ≡ (5 − 7) ≡ −2 ≡ 5 (mod 7). Так как 10
−1
≡ 3
−1
≡ 5 (mod 7), то q ≡ 5 · 5 (mod 7) ≡ 4 (mod 7) или q = 4 + 7r
для некоторого r. Следовательно, решением трех уравнений является число
x = 7 + 2 · 5(4 + 7r) или x ≡ 47 (mod 2 · 5 · 7).
Отметим, что 47 = 1 + 3 · (2) + 4 · (2 · 5), где коэффициенты 3 и 4 являются значениями q. Заметим также, что при изоморфизме Z
2·5·7
∼
= Z
2
× Z
5
× Z
7
число 47 соответствует данной тройке (1, 2, 5). ¤
В общем случае решение системы k уравнений
x ≡ a
1
(mod m
1
), x ≡ a
2
(mod m
2
), . . . , x ≡ a
k
(mod m
k
)
представляется в виде
x = q
1
+ q
2
· m
1
+ q
3
· (m
1
· m
2
) + . . . + q
k
· (m
1
· m
2
· . . . · m
k−1
),
где 0 6 q
i
< |m
i
|, q
1
— остаток от деления a
1
на m
1
Опишем применение китайского алгоритма к задаче о безопасном хране-
нии ключа. Пусть K ∈ Z — ключ, который необходимо сохранить. При этом требуется, чтобы любые L человек из тех k (k > L), которые получили ин- формацию о ключе, могли бы вместе восстановить ключ, но ни одна группа из L − 1 человек или менее не могла этого сделать.
Для решения этой задачи выберем такое множество целых чисел
{p, d
1
, d
2
, . . . , d
k
}, что:
1) p > K;
2) d
1
< d
2
< . . . < d
k
;
3) числа p, d
1
, d
2
, . . . , d
k
попарно взаимно просты;
4) d
1
· d
2
· . . . · d
k
> p · d
k−L+2
· d
k−L+3
· . . . · d
k
Пункт 4 означает, что произведение L наименьших чисел d
i
больше, чем произведение p и L − 1 наибольших чисел d
i
. Положим D ­ d
1
· d
2
· . . . · d

106
Глава 3. ЧИСЛОВЫЕ СИСТЕМЫ
Тогда D/p больше, чем произведение любых L − 1 чисел d
i
. Выберем теперь целое число r ∈ [0, (D/p) − 1] так, чтобы число K
0
= K + r · p попало в интервал [D/p, D − 1]. Между разными людьми распределяются числа
K
i
≡ K
0
(mod d
i
), i = 1, 2, . . . , k.
Пример 3.8.5. Предположим, что требуется закодировать ключ K = 5
и при этом L = 2, k = 3, p = 7, d
1
= 11, d
2
= 13, d
3
= 17. Имеем
D = d
1
· d
2
= 11 · 13 = 143 > 119 = 7 · 17 = p · d
3
, как и требуется. Выберем число r ∈ [0, (143/7) − 1] = [0, 19] так, что K
0
= K + r · p ∈ [D/p, D− 1],
т. е. 5+ 7r ∈ [20, 142]. Возьмем, например, r = 3, тогда K
0
= 26. Распре- деляемые числа равны
K
1
= 26 (mod 11) = 4,
K
2
= 26 (mod 13) = 0,
K
3
= 26 (mod 17) = 9. По любым двум из этих чисел можно восстановить K.
Например, для K
1
и K
3
имеем K
0
≡ 4 (mod 11), K
0
≡ 9 (mod 17). Используя китайский алгоритм, находим K
0
= 26, откуда K = K
0
− r · p = 5. ¤
§ 3.9.
Точные вычисления,
использующие модулярную арифметику
Используя результаты предыдущих параграфов, опишем способ выпол- нения точных арифметических действий с (большими) целыми числами, при котором целые числа представляются в виде кортежей остатков от деления данных чисел на попарно взаимно простые модули, а выполнение арифме- тических операций сводится к выполнению соответствующих операций над остатками.
Рассмотрим сначала случай одного модуля. Пусть дано выражение
f (x
1
, x
2
, . . . , x
h
), являющееся термом сигнатуры Σ = {+
(2)
, −
(1)
, ·
(2)
, (()
−1
)
(1)
},
и требуется вычислить значение f (i
1
, i
2
, . . . , i
h
), где i
1
, i
2
, . . . , i
h
∈ Z. Три- виальный подход состоит в непосредственном вычислении значения терма.
Однако промежуточные результаты могут не быть целыми числами (напри- мер, 1/3 = 0.333 . . . = 0.(3)), и отбрасывание цифр или округление может привести к неточности окончательного результата. Во избежание этого со- поставим вычислению значения f (i
1
, i
2
, . . . , i
h
) над Z соответствующее вы- числение значения f (i
0
1
, i
0
2
, . . . , i
0
h
) в поле Z
m
по обходному пути, показанному на рис. 3.2.
Вместо вычисления f (i
1
, i
2
, . . . , i
h
) над Z мы сначала получаем эквива- лентное выражение f
m
= f (i
0
1
, i
0
2
, . . . , i
0
h
) над Z
m
для некоторого простого m,
где i
0
j
≡ i
j
(mod m), j = 1, 2, . . . , h. Затем вычисляем выражение f
m
над Z
m

3.9. ТОЧНЫЕ ВЫЧИСЛЕНИЯ
107
Z
Выражение (f )
−−−−→
Z
m
Эквивалентное выражение (f
m
)


y
Вычисление над Z


y
Вычисление над Z
m
Результат (res) ←−−−− Эквивалентный результат (res
m
)
Рис. 3.2
и получаем эквивалентный результат res
m
, где res
m
≡ res (mod m). В за- ключение отображаем res
m
обратно в множество целых чисел.
Отметим, что отношение res ≡ res
m
(mod m) не определяет однозначно окончательный результат res. Например, условие x ≡ 7 (mod 13) означает,
что x может быть равным 7, 20 и т. д. Однако если мы знаем, что 0 < x < 13,
то x может быть равным только 7. Для того чтобы однозначно определить res, нужно иметь априорную оценку его величины. Эта оценка используется в качестве модуля m, и все операции выполняются в кольце Z
m
. Если име- ется оценка на величину res, то ищем наименьшее неотрицательное решение уравнения res ≡ res
m
(mod m). Если же мы имеем оценку на |res|, то ищем наименьшее по абсолютной величине решение.
Сложности с данным методом возникают при выполнении операции деле- ния. Как уже отмечалось, в случае, когда p — простое число, кольцо hZ; +, ·i
является конечным полем. Поскольку обратный элемент к любому ненуле- вому элементу всегда существует, деление по модулю p определяется следу- ющим образом:
a
b
(mod p) = a · (b
−1
(mod p)) (mod p),
где b
−1
(mod p) — элемент, обратный к элементу b по модулю p, который будет также обозначаться просто через b
−1
. Частное двух целых чисел в Z
p
также является целым числом, даже если b не делит a в Z.
Пример 3.9.1. 3/4 (mod 11) ≡ 3 · 4
−1
(mod 11) ≡ 3 · 3 (mod 11) ≡ 9.
Таким образом, 3/4 ≡ 9 (mod 11). Число, полученное в этом примере и рас- сматриваемое как промежуточный результат, имеет смысл для дальнейших вычислений, поскольку (3/4) · 4 (mod 11) ≡ 9 · 4 (mod 11) ≡ 3 (mod 11). ¤
Предположим теперь, что модуль p ограничивает окончательный результат res. Если res не является целым числом, принадлежащим Z
p
,

108
Глава 3. ЧИСЛОВЫЕ СИСТЕМЫ
то res
p
6= res, и для того чтобы получить последнее число, требуется допол- нительная информация (которую мы проиллюстрируем ниже двумя при- мерами). Если res лежит в Z
p
, то res
p
= res. Таким образом, арифметика одного модуля может быть использована для выполнения последователь- ности точных арифметических операций над целыми числами в Z
p
, даже если эта последовательность включает операции деления. Трудности могут возникнуть лишь при интерпретации результатов.
Если вычисляемое выражение может быть положительным или отри- цательным, необходимо использовать симметричную систему с носителем
{−
p−1 2
, . . . , −2, −1, 0, 1, 2, . . . ,
p−1 2
}, которая изоморфна неотрицательной си-
стеме с носителем {0, 1, . . . , p − 1}. Изоморфизм ϕ между этими системами осуществляется по формуле
ϕ(k) =
(
k,
если 0 6 k 6
p−1 2
,
k + p, если −
p−1 2
6 k < 0.
Пример 3.9.2. На рис. 3.3 показано отображение ϕ при p = 11. Урав- нение x ≡ 17 (mod 11) имеет наименьшее неотрицательное решение x = 6
и наименьшее по абсолютной величине решение x = −5. ¤
При выполнении арифметических операций удобно сначала отобразить данные в неотрицательное множество, выполнить в нем все операции, а за- тем отобразить обратно в симметричное множество.
¡
¡
¡
¡
¡
¡
¡
¡
¡
¡
¡
¡
¡
¡
¡
¡
¡
¡
¡
¡
¡
¡
¡
¡
¡
¡
¡
¡
¡
¡
¡
¡
¡
¡
¡
¡
¡
¡
¡
¡
¡
¡
¡
¡
¡
¡
¡
¡
¡
¡
¡
¡
¡
¡
¡
¡
¡
¡
¡
¡
¡
¡
¡
¡
¡
¡
¡
¡
¡
¡
0 1 2 3 4 5 6 7 8 9 10
-5 -4 -3 -2 -1 0 1 2 3 4 5
Неотрицательное множество множество
Симметричное
Рис. 3.3

3.9. ТОЧНЫЕ ВЫЧИСЛЕНИЯ
109
Пример 3.9.3. Выполним точные арифметические операции в Z
11
для вычисления x = 1/3 − 4/3.
В этом примере априорная информация состоит в том, что результат ищется в симметричном множестве. Имеем x (mod 11) ≡ (1/3 + (−4)/3)
(mod 11) ≡ (1/3 + 7/3) (mod 11) ≡ (1 · 3
−1
+ 7 · 3
−1
) (mod 11) ≡ (1 · 4+
+ 7·4) (mod 11) ≡ 32 (mod 11). Отображая результат обратно в симметрич- ное множество, получаем правильный ответ x = −1. В приведенном примере res
p
= res, поскольку с самого начала известно, что res лежит в симметрич- ном множестве для Z
11
. ¤
Пример 3.9.4. Вычислим x = 1/2 − 2/3, пользуясь той же априорной информацией, что и в предыдущем примере.
Имеем x (mod 11) ≡ (1/2 + (−2)/3) (mod 11) ≡ (1/2 + 9/3) (mod 11) ≡
≡ (1 · 2
−1
+ 9 · 3
−1
) (mod 11) ≡ (1 · 6 + 9 · 4) (mod 11) ≡ 42 (mod 11) ≡ 9. Ес- ли мы отобразим результат в симметричное множество, то получим непра- вильный ответ: x = −2. Поэтому требуется дополнительная информация о том, что мы ищем рациональное число x (mod 11) ≡ (a/b) (mod 11), где
b =НОК(2, 3). Тогда a = xb (mod 11) ≡ 9 · 6 (mod 11) ≡ 10 (mod 11) ≡ −1.
Следовательно, x = (−1)/6, что является правильным ответом. ¤
Перейдем теперь к арифметике нескольких модулей. Использование этой арифметики позволяет естественно решать проблему компьютерного представления и работы с большими целыми числами, с которой мы сталки- ваемся в арифметике одного модуля: как мы видели, модуль m должен быть достаточно большим, чтобы результат res определялся однозначно по его остатку res
m
(m > res). Поэтому при работе с большим m мы используем несколько модулей, кодирующих целые числа x (0 6 x 6 m − 1) в соответ- ствии с китайской теоремой об остатках.
Для вычисления заданного выражения f (i
1
, i
2
, . . . , i
h
), зависящего от це- лочисленных аргументов i
1
, i
2
, . . . , i
h
, сначала вычисляем f
m
k
(i
1k
, i
2k
, . . . , i
hk
),
где i
jk
— остаток от деления i
j
на m
k
(j = 1, 2, . . . , h, k = 1, 2, . . . , n) для ко- ротких модулей m
k
. При условии, что выражения f
m
k
определены над Z
m
k
,
вычисляем их над Z
m
k
и получаем эквивалентные результаты res
m
k
,
k = 1, 2, . . . , n. В завершение, пользуясь китайским алгоритмом, получаем окончательный результат res. Модули m
k
выбираются таким образом, чтобы
m
1
· m
2
· . . . · m
n
> res. Если дана положительная оценка на res, то ищет- ся наименьшее неотрицательное решение системы уравнений по китайскому алгоритму, если же оценивается |res|, то ищется наименьшее по абсолютной

110
Глава 3. ЧИСЛОВЫЕ СИСТЕМЫ
Z
Выражение (f )
−−−−→
Z
m
k
Эквивалентное выражение (f
m
k
)


y
Вычисление над Z


y
Вычисление над Z
m
k
Результат (res) ←−−−− Эквивалентный результат (res
m
k
)
Рис. 3.4
величине решение. На рис. 3.4 представлена диаграмма, иллюстрирующая приведенный алгоритм.
Рассмотрим более подробно арифметику нескольких модулей. Описанные в § 3.2 системы счисления являются линейными, позиционными и весовыми.
Это означает, что всем позициям соответствуют веса, зависящие от одного основания P : P
0
, P
1
, P
2
и т. д. Вместо этого многомодульная система счис- ления использует взаимно простые позиционные основания, m
1
, m
2
, . . . , m
n
Это позволяет однозначно представлять m
1
· m
2
· . . . · m
n
различных чисел x
в виде вектора остатков [a
1
, a
2
, . . . , a
n
] относительно вектора оснований
β = [m
1
, m
2
, . . . , m
n
], где x ≡ a
i
(mod m
i
), i = 1, 2, . . . , n. Как и в случае одного модуля, мы можем определить наименьшую неотрицательную чис-
ловую систему (которую будем называть стандартным набором остат-
ков) и при условии, что все модули нечетные, наименьшую по абсолютной
величине числовую систему или симметричную систему остатков относи- тельно данного вектора оснований β. Если [a
1
, a
2
, . . . , a
n
] — стандартный на- бор остатков числа x относительно вектора оснований β = [m
1
, m
2
, . . . , m
n
],
то запишем
x (mod β) = [a
1
, a
2
, . . . , a
n
].
Пример 3.9.5. Если n = 3, m
1
= 3, m
2
= 5, m
3
= 7, то в этой системе с помощью остатков можно представить 3· 5 · 7 = 105 различных чисел. Век- тор [2, 3, 1] однозначно определяет десятичное число 8 в неотрицательной системе остатков относительно вектора оснований β = [3, 5, 7]. В симмет- ричной системе число 8 представляется вектором [−1, −2, 1]. Имеем
8 (mod β) = [2, 3, 1]. ¤
Из китайской теоремы об остатках вытекает
Теорема 3.9.1. Два целых числа n
1
и n
2
имеют одинаковые стандарт-
ные наборы остатков относительно вектора оснований β = [m
1
, m
2
, . . . , m
n
]
тогда и только тогда, когда n
1
≡ n
2
(mod m
1
m
2
. . . m
n
). ¤