Введение
Теорема о решении системы сравнений
В математике китайская теорема об остатках утверждает, что если известны остатки от деления целого числа n на несколько целых чисел, то можно однозначно определить остаток от деления n на произведение этих чисел, при условии, что делители взаимно просты (нет двух делителей, имеющих общий делитель, отличный от 1). Например, если известно, что остаток от деления n на 3 равен 2, остаток от деления n на 5 равен 3, а остаток от деления n на 7 равен 2, то, не зная значения n, можно определить, что остаток от деления n на 105 (произведение 3, 5 и 7) равен 23. Важно отметить, что это означает, что если n – натуральное число, меньшее 105, то 23 – единственное возможное значение n.
Самое раннее известное изложение теоремы принадлежит китайскому математику Сунь-цзы в трактате «Сунь-цзы Суаньцзин» в III–V веках нашей эры. Китайская теорема об остатках широко используется при вычислениях с большими целыми числами, поскольку она позволяет заменить вычисление, для которого известна граница размера результата, несколькими аналогичными вычислениями с небольшими целыми числами. Китайская теорема об остатках (выраженная в терминах сравнений) верна для любой области главных идеалов. Она была обобщена на произвольные кольца, с формулировкой, включающей двусторонние идеалы.
Доказательство
Существование и единственность решения могут быть доказаны независимо. Однако первое доказательство существования, представленное ниже, опирается на эту единственность.
Уникальность
Предположим, что x и y являются решениями всех конгруенций. Поскольку x и y дают один и тот же остаток при делении на ni, их разность x − y кратна каждому ni. Так как ni попарно взаимно просты, их произведение N также делит x − y, и, следовательно, x и y сравнимы по модулю N. Если x и y предполагаются неотрицательными и меньше N (как в первом утверждении теоремы), то их разность может быть кратна N только если x = y.
Существование (конструктивное доказательство)
Существование может быть установлено явным построением x. Это построение можно разбить на два шага: сначала решить задачу для двух модулей, а затем расширить это решение на общий случай посредством индукции по числу модулей.
Систематический поиск
Легко проверить, является ли значение x решением: достаточно вычислить остаток от деления x на каждое ni по алгоритму Евклида. Таким образом, для нахождения решения достаточно последовательно проверять целые числа от 0 до N, пока не будет найдено решение. Хотя этот метод очень прост, он крайне неэффективен. Для рассмотренного здесь простого примера необходимо проверить 40 целых чисел (включая 0), чтобы найти решение, равное 39. Это алгоритм с экспоненциальной сложностью, поскольку размер входных данных, с точностью до постоянного множителя, определяется количеством цифр в числе N, а среднее количество операций пропорционально N. Поэтому этот метод редко используется как при ручных вычислениях, так и на компьютерах.
Therefore, this method is rarely used, neither for hand written computation nor on computers.
Поиск путем просеивания
Поиск решения может быть значительно ускорен просеиванием. Для этого метода мы предполагаем, без потери общности, что (если бы это не было так, было бы достаточно заменить каждое на остаток от его деления на ). Это означает, что решение принадлежит арифметической прогрессии. Проверяя значения этих чисел по модулю , в конечном итоге можно найти решение первых двух сравнений. Затем решение принадлежит арифметической прогрессии. Проверка значений этих чисел по модулю и продолжение до тех пор, пока каждый модуль не будет проверен, в конечном итоге дает решение. Этот метод быстрее, если модули упорядочены по убыванию, то есть если . В качестве примера, это дает следующие вычисления. Сначала рассмотрим числа, сравнимые с 4 по модулю 5 (наибольший модуль), то есть 4, 9 = 4 + 5, 14 = 9 + 5, … Для каждого из них вычислим остаток по модулю 4 (второй по величине модуль), пока не получим число, сравнимое с 3 по модулю 4. Затем можно продолжить, добавляя 20 = 5 × 4 на каждом шаге и вычисляя только остатки по модулю 3. Это дает:
4 mod 4 → 0. Продолжаем.
4 + 5 = 9 mod 4 → 1. Продолжаем.
9 + 5 = 14 mod 4 → 2. Продолжаем.
14 + 5 = 19 mod 4 → 3. Хорошо, продолжаем, рассматривая остатки по модулю 3 и добавляя 5 × 4 = 20 каждый раз:
19 mod 3 → 1. Продолжаем.
19 + 20 = 39 mod 3 → 0. Хорошо, это результат. Этот метод хорошо подходит для ручных вычислений с произведением модулей, которое не слишком велико. Однако он гораздо медленнее, чем другие методы, для очень больших произведений модулей. Хотя этот метод значительно быстрее, чем систематический поиск, он также имеет экспоненциальную временную сложность и поэтому не используется на компьютерах.
By testing the values of these numbers modulo one eventually finds a solution of the two first congruences. Then the solution belongs to the arithmetic progression
Testing the values of these numbers modulo and continuing until every modulus has been tested eventually yields the solution. This method is faster if the moduli have been ordered by decreasing value, that is if For the example, this gives the following computation. We consider first the numbers that are congruent to 4 modulo 5 (the largest modulus), which are 4, 1=9 = 4 + 5, 1=14 = 9 + 5, For each of them, compute the remainder by 4 (the second largest modulus) until getting a number congruent to 3 modulo 4. Then one can proceed by adding 1=20 = 5 × 4 at each step, and computing only the remainders by 3. This gives
4 mod 4 → 0. Continue
4 + 5 = 9 mod 4 →1. Continue
9 + 5 = 14 mod 4 → 2. Continue
14 + 5 = 19 mod 4 → 3. OK, continue by considering remainders modulo 3 and adding 5 × 4 = 20 each time
19 mod 3 → 1. Continue
19 + 20 = 39 mod 3 → 0. OK, this is the result. This method works well for hand written computation with a product of moduli that is not too big. However, it is much slower than other methods, for very large products of moduli. Although dramatically faster than the systematic search, this method also has an exponential time complexity and is therefore not used on computers.
Сверх основных идеальных областей
В , китайская теорема об остатках была сформулирована тремя различными способами: в терминах остатков, в терминах сравнений по модулю и в терминах изоморфизма колец. Формулировка в терминах остатков, как правило, не применима к областям главных идеалов, поскольку остатки не определены в таких кольцах. Однако две другие формулировки имеют смысл для области главных идеалов R: достаточно заменить "целое число" на "элемент области" и на R. Эти две формулировки теоремы верны в этом контексте, поскольку доказательства (за исключением первого доказательства существования) основаны на лемме Евклида и тождестве Безу, которые верны для любой области главных идеалов. Однако, в общем случае, теорема является лишь теоремой о существовании и не предоставляет способа вычисления решения, если нет алгоритма для вычисления коэффициентов тождества Безу.
Номера последовательности
Китайская теорема об остатках была использована для построения нумерации Гёделя последовательностей, что играет роль в доказательстве теорем о неполноте Гёделя.
Быстрая трансформация Фурье
Алгоритм FFT с простым коэффициентом (также называемый алгоритмом Гуда — Томаса) использует китайскую теорему об остатках для сведения вычисления быстрого преобразования Фурье размера *N* к вычислению двух быстрых преобразований Фурье меньших размеров *N₁* и *N₂* (при условии, что *N₁* и *N₂* взаимно просты).
Шифрование
Большинство реализаций RSA используют китайскую теорему об остатках при подписании HTTPS-сертификатов и при дешифровании. Китайская теорема об остатках также может применяться в схемах разделения секрета, которые заключаются в распределении набора долей между группой людей, которые, действуя совместно (но не по отдельности), могут восстановить определенный секрет из заданного набора долей. Каждая доля представлена в виде сравнения, а решение системы сравнений с использованием китайской теоремы об остатках является искомым секретом. Схемы разделения секрета, использующие китайскую теорему об остатках, применяют, наряду с ней, специальные последовательности целых чисел, гарантирующие невозможность восстановления секрета из набора долей, размерность которого меньше определенного значения.
Резолюция неоднозначности диапазона
Техники разрешения неоднозначности дальности, используемые с радиолокационными станциями средней частоты повторения импульсов, можно рассматривать как частный случай китайской теоремы об остатках.