Китайская теорема об остатках
Любое неотрицательное целое число, не превосходящее произведения модулей, можно однозначно восстановить, если известны его вычеты по этим модулям. Этот результат был известен еще в древнем Китае и носит название китайской теоремы об остатках. Теорема была предложена китайским математиком первого века Сун Це. Китайская теорема об остатках является мощным криптографическим инструментом.
Она формулируется следующим образом.
Пусть 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
fori : = 1 tot do
N i : = inv (M i mod m i, m j);
x : = 0;
fori : = 1 tot 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.