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

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

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

Пусть 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] единственное общее решение

х = 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

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

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 ₁ = 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).