Любое неотрицательное целое число, не превосходящее произведения модулей, можно однозначно восстановить, если известны его вычеты по этим модулям. Этот результат был известен еще в древнем Китае и носит название китайской теоремы об остатках. Теорема была предложена китайским математиком первого века Сун Це. Китайская теорема об остатках является мощным криптографическим инструментом.
Она формулируется следующим образом.
Пусть m1, m2, …, m t – модули (целые числа, большие 1), которые являются попарно взаимно простыми, т.е. НОД (mi, mj,) = 1 при i ¹ j.
Пусть а1, а2, …, а t – тоже целые числа, такие, что 0 ≤ а i ≤ m i.
Пусть М = m1 • m2 • … • m t – произведение всех m i. Обозначим
М i = M / m i.
И пусть N i будет обратным к М i (mod m i), i = 1, 2, …, t, т.е.
М i • N i º 1 (mod m i).
Так как НОД (М i , m i) = 1, то обратный элемент N i существует и легко находится по алгоритму Евклида из соотношения
М i • N i + m i • n i = 1, i = 1, 2, …, t.
Сравнения х º а i (mod m i), i = 1, 2, …, t, имеют в интервале
[0, M – 1] единственное общее решение
х = 
a i • N i • М i (mod M).
Рассмотрим частный случай. Пусть М = m1 • m2 , где m1 и m2 – взаимно простые числа. Тогда для произвольных целых а1 < m 1 и
а 2 < m 2 существует единственное число х, х < М, такое, что
х º а 1 (mod m 1) и х º а 2 (mod m 2).
Чтобы найти значение решения х, сначала используют алгоритм Евклида для вычисления значений N 1 и N 2 , таких, что
М 1 • N 1 º 1 (mod m 1) и М 2 • N 2 º 1 (mod m 2).
Здесь M m 1 • m 2 M
M 1 = = = m 2 ; M 2 = = m 1.
m 1 m 1 m 2
Затем вычисляют значение
х = (a 1 • N 1 • М 1 + a 2 • N 2 • М 2 ) (mod M).
Алгоритм 1.6.1 – Нахождение решения системы сравнений, использующий Китайскую теорему об остатках
{возврат х Î [0, M – 1], такого что х mod m i = a i (1 ≤ i ≤ t)}
Begin
for i: = 1 to t do
N i : = inv (M i mod m i, m j);
x: = 0;
for i: = 1 to t do
x: = [x + M i • N i • a i ] mod n;
crt: = x {crt - результат}
End
Пример. Решить систему из двух сравнений
х º 1 (mod 5),
х º 10 (mod 11)
и найти общее решение х по модулю 55.
Здесь: m 1 = 5; m 2 = 11; M = m 1 • m 2 = 5 • 11 = 55;
а 1 = 1; а 2 = 10; M 1 = М / m 1 = m 2 = 11; M 2 = М / m 2 = m 2 = 5.
Найдем значения N 1 и N 2, обратные к M 1 и M 2 сответственно по mod m 1 и mod m 2 :
М 1 • N 1 º 1 (mod m 1), 11 • N 1 º 1 (mod 5) Þ N 1 = 1,
М 2 • N 2 º 1 (mod m 2), 5 • N 2 º 1 (mod 11) Þ N 2 = 9.
Вычислим общее значение
х = (a 1 • N 1 • М 1 + a 2 • N 2 • М 2 ) (mod M) =
= (1 • 11 • 1 + 10 • 5 • 9) (mod 55) = (11 + 450) (mod 55) =
= 461 (mod 55) = 21 (mod 55).
Итак, х = 21 (mod 55).
Квадратичные вычеты
Рассмотрим некотрое простое p < q и число a < p. Если число а сравнимо с квадратом некоторого числа х по модулю p, т.е. выполняется сравнение х2 º а (mod p), тогда а называют квадратичным вычетом по модулю p. В противном случае а называют квадратичным невычетом по модулю p.
Если а – квадратичный вычет, сравнение х2 º а (mod p) имеет два решения: +х и –х, т.е. а имеет два квадратных корня по модулю р.
Все квадратичные вычеты находят возведением в квадрат элементов 1, 2, 3, …, (р – 1) /2.
Не все значения а < р являются квадратичными вычетами.
Пример. При р = 7 квадратичные вычеты это 1, 2, 4:
12 = 1 º 1 (mod 7),
22 = 4 º 4 (mod 7),
32 = 9 º 2 (mod 7),
42 = 16 º 2 (mod 7),
52 = 25 º 4 (mod 7),
62 = 36 º 1 (mod 7).
Каждый квадратичный вычет появляется в этом списке дважды.
Не существует никаких значений х, которые удовлетворяли бы любому из следующих уравнений:
х2 º 3 (mod 7),
х2 º 5 (mod 7),
х2 º 6 (mod 7).
Числа 3, 5 и 6 – квадратичные невычеты по модулю 7.
Можно доказать, что существует точно (р – 1) / 2 квадратичных вычетов по модулю р и (р – 1) / 2 квадратичных невычетов по модулю р.
Если а – квадратичный вычет по модулю р, то а имеет точно два квадратных корня: один корень между 0 и (р – 1) / 2, другой корень между (р – 1) / 2 и (р – 1).
Один из этих квадратных корней также является квадратичным вычетом по модулю р. Он называется главным квадратичным корнем.
Вычисление квадратных корней при р = 7 представлено в таблице 1.7.1.
Таблица 1.7.1 Вычисление квадратных корней при р = 7
| х2 º а (mod 7) | Корни | |
| х 1 | х 2 | |
| 12 º 1 (mod 7) 22 º 4 (mod 7) 32 º 2 (mod 7) | +1 +2 +3 | -1 = -1 + 7 = 6 -2 = -2 + 7 = 5 -3 = -3 + 7 = 4 |
Если n – призведение двух простых р и q, т.е. n = p • q, то существует точно
(p – 1) • (q – 1) / 4
квадратичных вычетов по модулю n, взаимно простых n.
Пример. По модулю 35 (р = 5, q = 7, n = 5 • 7 = 35) существуют
(5 – 1) • (7 – 1) 4 • 6
= = 6
4 4
квадратичных вычетов: 1, 4, 9, 11, 16, 29, взаимно простых с 35.
