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

Китайская теорема об остатках — несколько связанныхутверждений о решении линейной системы сравнений.

История


 Эта теорема в её арифметической формулировке была описана в трактатекитайского математика Сунь Цзы «Сунь Цзы Суань Цзин» ,предположительно датируемом третьим веком н. э. и затем была обобщенаЦинь Цзюшао в его книге «Математические рассуждения в 9 главах»датируемой 1247 годом, где было приведено точное решение.

Формулировка


 Если натуральные числа a1,a2,,ana1,a2,,an попарно взаимно просты, тодля любых целых r1,r2,,rnr1,r2,,rn таких, что0ri<ai0ri<ai при всех i{1,2,,n}, найдётсячисло N, которое при делении на ai даёт остаток ri при всехi{1,2,,n}. Более того, если найдутся два таких числаN1 и N2, тоN1N2(moda1a2an).

Доказательства


Индукция по числууравнений


 Воспользуемся методом математической индукции. При n=1 утверждениетеоремы очевидно. Пусть теорема справедлива при n=k1, тосуществует число m, дающее остаток ri при делении на ai приi{1,2,,k1}. Обозначим
d=a1a2ak1
 Выберем произвольное число ak, взаимно простое со всемиa1ak1 и рассмотрим числаM={m,m+d,m+2d,,m+(ak1)d}={m+td}0t<ak.Покажем, что все t{0,,ak1} являются остатками приделении каких-либо элементов из M на ak.
 Допустим это не так, то есть существует некоторое rk<ak, котороене принадлежит множеству всех остатков при делении элементов M наak. Поскольку количество этих элементов равно |M|=ak, авозможных остатков при делении элементов из M на ak может быть неболее чем ak1 (ведь ни одно число не даёт остаток rk), то срединих найдутся два числа, имеющих равные остатки (принцип ящиков Дирихле).Пусть это числа m+t1d и m+t2d при t1t2. Тогда ихразность (m+t1d)(m+t2d)=(t1t2)d делится на ak,что невозможно, так как t1<ak, t2<ak,0<|t1t2|<ak и d=a1a2ak1взаимно просто с ak, ибо числа a1,a2,,ak попарно взаимнопросты (по условию). Противоречие.
 Таким образом, среди рассматриваемых чисел найдётся числоN=m+td, которое при делении на ak даёт остаток rk. Вто же время при делении на a1,a2,,ak1 число N даётостатки r1,r2,,rk1 соответственно, так какm+tdm(modai).
 Докажем теперь, чтоN1N2(moda1a2an). В самом делеN1N2ri(modai), то естьN1N20(modai). Таким образом, число N1N2 делитбез остатка все ai, а также их произведение.

Конструктивный методдоказательства


 Описанное ниже доказательство теоремы помогает решить практически важнуюзадачу — поиск решения системы линейных уравнений по модулю.Рассмотрим систему уравнений:
{xr1(moda1),xr2(moda2),xrn(modan)

 Если наборы (r1,r2,,rn) и (a1,a2,,an)удовлетворяют условию теоремы, то решение системы (1) существует иединственно с точностью до операции взятия по модулю M, гдеM=ni=1ai, причем справедлива формула
x=ni=1riMiM1i, где Mi=Mai, аM1i — мультипликативно обратный к Mimodai элемент вкольце Zai. & (2)
 Покажем, что определенный таким образом x является решением —проверим, что для него выполняется i-е равенство в системе:xnj=1rjMjM1jriMiM1iri(modai)Второе равенство справедливо так какMjnkjak0(modai)при всех ij, третье так как M1i является обратным дляMi по модулю ai. Повторяя рассуждения для всех i, убедимся, чтоx, определенный формулой (2), является решением для (1).
 В силу выбранного числа M все числа xx(modM) будутудовлетворять системе.
 Покажем теперь, что среди чисел 0,1,,M1 (множество A) ненайдется другого решения, кроме найденного нами ранее. Проведёмдоказательство этого факта от противного. Предположим, что получилосьнайти хотя бы два решения x1,x2A для некоторого набораостатков r. Так как множество B всех допустимых наборов(r1,r2,,rn) является равномощным множеству A, то для¯Ax:=A{x1,x2} и¯Br:=B{r} выполнено|¯Ax|<|¯Br|. Однако по доказанному ранее, длялюбого набора из ¯Br существует решение из ¯Ax,следовательно, по принципу Дирихле, найдутся как минимум 2 набораостатков, которым соответствует одно и то же xA. Для такого xнайдется ai такое, что xr1,xr2(modai) иr1r2. Противоречие.

Замечания


 Из доказанного выше следует, что существует взаимно однозначноесоответствие между вектором остатков из B и числом из множества Aдля любого набора (a1,a2,,an), что означает, чтоотображение B в A, заданное (2), является биективным. Заметим, чтокроме соответствия
(x(modM))(r1(moda1),r2(moda2),,rn(modan))вернытакже(x_1 \pm x_2 \pmod{M})\leftrightarrow (r_{11} \pm r_{21}\pmod{a_1}, r_{12} \pm r_{22}\pmod{a_2}, \dots, r_{1n} \pm r_{2n}\pmod{a_n})$$
 $(x_1x_2\pmod{M})\leftrightarrow (r_{11}r_{21}\pmod{a_1}, r_{12}r_{22}\pmod{a_2}, \dots, r_{1n}r_{2n}\pmod{a_n})$.
 Временная сложность перехода от вектора остатков к числу оценивается как$O(k^2)$, где k — длина восстанавливаемого числа в битах.

Алгоритмы поискарешений


 Приведём ниже алгоритмы решения задачи, которая ставится в теореме —восстановление числа x по набору его остатков от деления на некоторыезаданные взаимно простые числа a1,a2,,an.

Элементарнаяалгебра


 Как пример рассмотрим систему
{x1(mod2),x2(mod3),x6(mod7)

 Для решения системы выпишем отдельно решения первого, второго и третьегоуравнений (достаточно выписать решения не превосходящие ):
x1{1,3,5,7,9,11,,39,41,43,}
x2{2,5,8,11,14,,38,41,44,}
x3{6,13,20,27,34,41,48,}
 Очевидно, что множество решений системы будет пересечение представленныхвыше множеств. По утверждению теоремы решение существует и единственно сточностью до операции взятия по модулю 42. В нашем случаеx{41,83,125,} или x41(mod42).
 Для того, чтобы продемонстрировать другой путь, переформулируем задачу.Найдем тройку чисел (u, v, w) таких, что:
{x1+2u,x2+3v,x6+7w

 Подставив x из первого уравнения во второе, получим1+2u2(mod3), тогда 2u1(mod3), или4u2(mod3), или u2(mod3), или u=2+3s;
 подставив затем x из первого уравнения в третье с учетомвыражения для u получим 1+2(2+3s)6(mod7) или6s1(mod7), тогда 36s6(mod7) и следовательноs6(mod7);
 тогда x=1+2(2+36)=41.

Алгоритм на основе китайской теоремы обостатках


 Алгоритм сводится к поиску решений по формуле, данной в теореме.
 Шаг 1. Вычисляем M=ni=1ai.
 Шаг 2. Для всех i{1,2,,n} находим Mi=Mai.
 Шаг 3. Находим M1i=1Mimodai (например, используярасширенный алгоритм Евклида).
 Шаг 4. Вычисляем искомое значение по формулеx=ni=1riMiM1imodM.

АлгоритмГарнера


 Рассмотрим набор модулей (a1,a2,,an), удовлетворяющихусловию теоремы. Другой теоремой из теории чисел утверждается, что любоечисло 0x<M=a1a2an однозначнопредставимо в виде
x=x1+x2a1+x3a1a2++xna1a2an1.
 Вычислив по порядку все коэффициенты xi дляi{1,2,,n} мы сможем подставить их в формулу и найтиискомое решение:
 Обозначим через rij=a1imodaj и рассмотрим выражениедля x по модулю ai, где i{2,,n}, получим:
x1=r1;
r2=(x1+x2a1)moda2;
x2=(r2x1)r12moda2;
r3=(x1+x2a1+x3a1a2)moda3;
x3=((r3x1)r13x2)r23moda3
 и так далее.
 Сложность вычисления коэффициентов xi для данного алгоритма O(n2).Такая же сложность и восстановления искомого числа по найденнымкоэффициентам.

Вариации иобобщения


Формулировка дляколец


 Пусть A,B1,,Bn — коммутативные кольца с единицей,φi:ABi — сюръективные гомоморфизмы, обладающиесвойством kerφi+kerφj=A для всехi,j{1,,n},ij. Тогда гомоморфизм
Φ:Ani=1Bi,
 заданный формулой
Φ(a)=(φ1(a),,φn(a)),
 является сюръективным. Более того, Φ определяет изоморфизм
A/(ni=1kerφi)ni=1Bi.
 Если положитьA=Z/(a1anZ),Bi=Z/aiZ (i=1,2,,n; aiZ)и определить гомоморфизмы следующим образом
φi(x)=xmodai,
 то мы получим арифметическую версию теоремы.
 Также часто встречается эквивалентная формулировка для колец, где Biимеют форму A/Ii для некоторого набора идеалов I1,,In,гомоморфизмы φi являются естественными проекциями на A/Ii итребуется, чтобы Ii+Ij=A для любыхi,j{1,,n},ij. Другими словами, если идеалыI1,,In попарно взаимно просты (то есть сумма двух различныхидеалов равна самому кольцу), то их произведение совпадает с ихпересечением, и факторкольцо по этому произведению изоморфнопроизведению факторов:
A/(I1I2In)A/I1×A/I2××A/In.

Доказательство для евклидовыхколец


 Пусть R — евклидово кольцо и m,n — взаимно простые числа. Тогдадокажем, что существует корректно заданный изоморфизм:
R/(mn)R/(m)×R/(n)
 Прямое отображение [x]mn([x]m, [x]n) очевидно.
 Для доказательства существования обратного отображения рассмотрим классыэквивалентности [1] и [0].
([1]m, [0]n)[u]mn
([0]m, [1]n)[v]mn
 Найдём [u]mn, решив следующую систему уравнений:
{u1 (modm)u0 (modn)
yZ: u=ny, ny1(modm)
 Аналогично найдём [v]mn:
xZ: u=mx, mx1(modm)
 Покажем, что в общем виде выполняется:
([a]m, [b]n)[au+bv]mn
au+bva(modm), так как v0(modm) иu1(modm)
au+bvb(modn), так как u0(modn) иv1(modn)
 Проверим корректность отображения, то есть что при взятии разныхэлементов из классов [a]m, [b]n результат не меняется.
{aa(modm)bb(modn)
 Значит au+bvau+bv(modmn), отображение корректно.
 Можно проверить, что построенное отображение действительно обратное .

Применения


 Китайская теорема об остатках широко применяется в теории чисел,криптографии и других дисциплинах.

  • Взаимно однозначное соответствие между некоторым числом и набором его остатков, определяемым набором взаимно простых чисел, существование которого утверждается в теореме, на практике помогает работать не с длинными числами, а с наборами их коротких по длине остатков. Кроме того, вычисления по каждому из модулей можно выполнять параллельно. Если в качестве базиса взять, к примеру, первые 500 простых чисел, длина каждого из которых не превосходит 12 бит, то этого хватит для представления десятичных чисел длиной до 1519 знаков. (Откуда взялось число 1519 понять очень просто: сумма десятичных логарифмов первых 500 простых чисел равна 1519,746...).

 Например, в алгоритме RSA вычисления производятся по модулю оченьбольшого числа n, представимого в виде произведения двух большихпростых чисел. Теорема позволяет перейти к вычислениям по модулю этихпростых делителей, которые по величине уже порядка корня из n, азначит имеют в два раза меньшую битовую длину.
 Отметим также, что применение вычислений согласно китайской теореме обостатках делает алгоритм RSA восприимчивым к атакам по времени.

  • На теореме основаны схема Асмута — Блума и схема Миньотта — пороговые схемы разделения секрета в группе участников. Секрет могут узнать только k из n участников, объединив свои ключи.
  • Одним из применений является быстрое преобразование Фурье на основе простых чисел.
  • Теорема лежит в основе принципа Хассе поиска целочисленных корней уравнения.
  • Из теоремы следует мультипликативность функции Эйлера.
  • На теореме основывается алгоритм Полига — Хеллмана нахождения дискретного логарифма за полиномиальное время для чисел, имеющих специальный вид.
  • Теорема имеет множество применений в шифровании и дешифровании в криптографических системах, например, в криптосистеме Рабина или в шифре Виженера.