Китайская теорема об остатках

Любое неотрицательное целое число, не превосходящее произведения модулей, можно однозначно восстановить, если известны его вычеты по этим модулям. Этот результат был известен еще в древнем Китае и носит название китайской теоремы об остатках. Теорема была предложена китайским математиком первого века Сун Це. Китайская теорема об остатках является мощным криптографическим инструментом.

Она формулируется следующим образом.

Пусть m₁, m₂, … , m _t – модули (целые числа, большие 1), которые являются попарно взаимно простыми, т.е. НОД (m_i, m_j,) = 1 при i ¹ j.

Пусть а₁, а₂, … , а _t– тоже целые числа, такие, что 0 ≤ а _i≤ m _i.

Пусть М = m₁• m₂• … • 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] единственное общее решение

х = Китайская теорема об остатках - student2.ru a _i• N _i • М _i(mod M).

Рассмотрим частный случай. Пусть М = m₁• m₂, где m₁и m₂– взаимно простые числа. Тогда для произвольных целых а₁< m ₁ и
а ₂< m ₂существует единственное число х, х < М, такое, что

х º а ₁(mod m ₁) и х º а ₂(mod m ₂).

Чтобы найти значение решения х, сначала используют алгоритм Евклида для вычисления значений N ₁и N ₂, таких, что

М ₁• N ₁º 1 (mod m ₁) и М ₂• N ₂º 1 (mod m ₂).

Здесь M m ₁• m ₂ M

Китайская теорема об остатках - student2.ru M ₁ = = = m ₂; M ₂ = = m ₁.

m ₁ m ₁m ₂

Затем вычисляют значение

х = (a ₁• N ₁ • М ₁+ a ₂• N ₂ • М ₂) (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 _imod 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 ₁= 5; m ₂= 11; M = m ₁• m ₂= 5 • 11 = 55;

а ₁= 1; а ₂= 10; M ₁ = М / m ₁= m ₂= 11; M ₂ = М / m ₂= m ₂= 5.

Найдем значения N ₁ и N ₂, обратные к M ₁ и M ₂сответственно по mod m ₁ и mod m ₂:

М ₁• N ₁º 1 (mod m ₁), 11 • N ₁º 1 (mod 5) Þ N ₁= 1,

М ₂• N ₂º 1 (mod m ₂), 5 • N ₂º 1 (mod 11) Þ N ₂= 9.

Вычислим общее значение

х = (a ₁• N ₁ • М ₁+ a ₂• N ₂ • М ₂) (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, т.е. выполняется сравнение х² º а (mod p), тогда а называют квадратичным вычетом по модулю p. В противном случае а называют квадратичным невычетом по модулю p.

Если а – квадратичный вычет, сравнение х² º а (mod p) имеет два решения: +х и –х, т.е. а имеет два квадратных корня по модулю р.

Все квадратичные вычеты находят возведением в квадрат элементов 1, 2, 3, … , (р – 1) /2.

Не все значения а < р являются квадратичными вычетами.

Пример. При р = 7 квадратичные вычеты это 1, 2, 4:

1² = 1 º 1 (mod 7),

2² = 4 º 4 (mod 7),

3² = 9 º 2 (mod 7),

4² = 16 º 2 (mod 7),

5² = 25 º 4 (mod 7),

6² = 36 º 1 (mod 7).

Каждый квадратичный вычет появляется в этом списке дважды.

Не существует никаких значений х, которые удовлетворяли бы любому из следующих уравнений:

х² º 3 (mod 7),

х² º 5 (mod 7),

х² º 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