Теорема С (Китайская теорема об остатках). Пусть mi, тг, ..., Шг -положительные целые попарно простые числа, т. е.

mj ± тк при j ф к. (5)

Пусть т = mim2...mr и пусть также а, ui, «г, щ-целые числа. Тогда существует ровно одно целое число и, удовлетворяющее условиям

а < и < а + т и и = Uj (по мод>лю mj) при 1 < j < г. (6)

Доказательство. Если и = v (по модулю mj) при 1 < j < г, то и - и кратно mj для всех j. Тогда из условия (5) следует, что u-v кратно m = mim2 ... т. Значит, уравнение (6) имеет не более одного решения. Для завершения доказательства необходимо показать, что существует по меньшей мере одно решение. Это можно сделать двумя простыми способами.

Способ 1 ("Неконструктивное" доказательство). Так как и принимает m различных значений а < и < а + т, наборы из г чисел (и mod mi,..., и mod m) также должны принимать m различных значений (поскольку уравнение (6) имеет не более одного решения). Но имеется ровно mim2 ... тг возможных г-наборов (vi,...,Vr), таких, что О < Vj < mj. Поэтому каждый г-набор должен встречаться точно один раз и должно существовать такое значение и, для которого (и mod mi,... ..., и mod тг) = (wi,..., Ur).

Способ 2 ("Конструктивное" доказательство). Можно найти числа Mj при 1 < j < г, такие, что

Mj = 1 (по модулю mj) и Mj =0 (по модулю тк) для fc Ф j. (7)

Действительно, из (5) следует, что mj и m/mj взаимно просты, а потому согласно теореме Эйлера (упр. 1.2.4-28) можно взять

Mj = {m/mj)("l (8)

Теперь число

и = а -(- ((wiMi + U2M2 Н----¥ UrMr - а) mod m) (9)

удовлетворяет всем условиям (6).

Частный случай этой теоремы был сформулирован китайским математиком Сунь Цу, который предложил правило, названное "тай-йен" ("большое обобщение"). Дата написания его работы точно не установлена; предположительно--между 280 и 473 г. н. э. Дальнейшее развитие эта задача получила в работах математиков средневековой Индии, предложивших методы куттака (kuttaka) (см. раздел 4.5.2). Однако в общем виде теорема С впервые была сформулирована и доказана Чин Чжу-Шао в работе Shu Shu Chiu Chang (1247), в которой рассмотрен также случай, когда модули могут иметь общие множители (как в упр. 3). [См. J. Needham, Science and Civilization in China 3 (Cambridge University Press, 1959), 33-34, 119-120; Y. Li and S. Du, Chinese Mathematics (Oxford: Clarendon, 1987), 92-94, 105, 161-166; K. Shen, Archive for History of Exact Sciences 38 (1988), 285-305.] Многочисленные исследования, посвященные этой теории, обобщены Л. Ю. Диксоном (L. Е. Dickson) в книге History of the Theory of Numbers 2 (Carnegie Inst, of Washington, 1920), 57-64.

Как следует из теоремы С, модулярное представление можно использовать для чисел в любом соответствующем интервале тп = тп1ТП2-..тПг целых чисел. Например, можно в (6) взять а = О и работать только с неотрицательными целыми числами и, меньшими тп. С другой стороны, при выполнении операций сложения и вычитания, так же, как и умножения, обычно удобнее всего предположить, что все модули mi, тп2, ..., тпг являются нечетными числами, так что и m = mim2 . ..тпг тоже нечетное, и работать с целыми числами из интервала

тп тп

-2-<«<у, (10)

симметричного относительно нуля.

Для выполнения основных операций, перечисленных в (2)-(4), необходимо вычислить (uj + Vj) mod Tnj, (uj - Vj) mod и UjVj mod mj при 0 < Uj, Vj < mj. Если Tnj - число однократной точности, то лучше всего формировать UjVj mod mj путем умножения и последующего деления. Что касается операций сложения и вычитания, то здесь ситуация проще, так как не требуется деление; удобно рассматривать следующие формулы:

[uj -f- Vj) mod mj = Uj + Vj - Tnj\uj -(- Vj > mj]. (11)

(uj - Vj) modmj = Uj -Vj+ mj[uj <Vj]. (12)

(Cm. раздел 3.2.1.1.) Поскольку желательно, чтобы w было как можно большим, проще всего принять mi наибольшим нечетным числом, соответствующим машинному слову, в качестве т2 принять наибольшее нечетное число < mi, взаимно простое с mi, а в качестве тз - наибольшее нечетное число < тг, взаимно простое как с mi, так и с тг, и т. д., пока не наберется столько mj, сколько будет достаточно для образования нужного тп. Способы эффективного определения, являются ли два числа взаимно простыми, рассматриваются в разделе 4.5.2.

В качестве простого примера предположим, чтб имеется десятичный компьютер со словом, содержащим две цифры, так что размер слова равен 100. Тогда в результате только что описанной процедуры получаем

mi =99, m2 = 97, тз = 95, m4 = 91, ms = 89, тб=83 (13)

и т. д.

При работе на двоичных компьютерах иногда желательно выбирать модули mj иным образом:

mj = Т - 1. (14)

Другими словами, значение каждого модуля на единицу меньше очередной степени 2. Такой выбор значения модуля mj зачастую упрощает выполнение основных арифметических операций, ибо выполнять вычисления с числами, представленными по модулю 2*> - 1, несколько проще, чем с числами, представленными в обратном коде. После того как значения модулей выбраны таким образом, полезно несколько ослабить условие О < < т и потребовать только, чтобы

О < < , Uj = u (по модулю 2«> - 1). (15)

Таким образом, значение Uj = mj = - 1 принимается в качестве оптимального вместо Uj = О, поскольку это, с одной стороны, не влияет на справедливость теоремы С, а с другой - означает, что Uj может быть любым -битовым двоичным

числом. При таком допущении операции сложения и вычитания по модулю rUj выполняются следующим образом:

Uj е Vj = {{uj + Vj) mod 2) + [uj + Vj > 2 ]. (16)

Uj (8 Vj = (ujVj mod 2) 0 \ujVjl2\. (17)

(Здесь Ф и (gl указывают на действия, которые с учетом условия (15) должны быть выполнены с отдельными компонентами (ui,...,и) и .. ,Vr) при сложении или умножении соответственно.) При вычитании можно пользоваться и соотношением (12). Можно также использовать условие

Uj е Vj = [{uj - Vj) mod 2) - [uj < Vj]. (18)

Эти операции могут быть эффективно выполнены, даже если 2* больше машинного слова компьютера, так как совсем просто вычислить остаток положительного числа по модулю степени 2 или разделить число на степень 2. В (17) имеем сумму "верхней половины" и "нижней половины" произведения, как в разделе 3.2.1.1-8.

Для работы с модулями вида 2 - 1 необходимо знать, при каких условиях число 2* - 1 является взаимно простым с числом 2- - 1. К счастью, для этого существует очень простое правило:

gcd(2 - 1, 2 - 1) = 2"-f - 1. (19)

Данная формула утверждает, в частности, что si 2* - 1 и 2- - 1 взаимно просты тогда и только тогда, когда взаимно просты ей/. Уравнение (19) сиедует из алгоритма Евклида и тождества

(2 - 1) mod (2 - 1) = 2 - 1. (20)

(См. упр. 6.) Поэтому на компьютере с длиной слова 2 можно выбрать mj = 22 - 1, m2 = 2-" - 1, тз = 2» - 1, m4 = 2 - 1, ms = 25 - 1, что обеспечивает эффективность сложения, вычитания и умножения целых чисел в интервале вплоть до mim2m3m4m5 > 2.

Как мы уже заметили, операции преобразования в модулярное представление и обратно очень важны. Модулярное представление (щ,...,Ur) для заданного числа и может быть получено посредством деления и на miтг с запоминанием остатков. В случае, когда и = (vmVm-i о)ь, возможно применение более подходящего способа, который состоит в том, чтобы, используя модулярную арифметику, вычислить полином

(. . . (Vmb + Vm~l)b+ )b + Vo.

Если Ь = 2 и модули tuj имеют специальный вид 2 - 1, оба подхода сводятся к совсем простому способу. Рассмотрим двоичное представление числа и с блоками Cj бит:

и = а«Л+а« 1Л~+ •••+ 01 + 00, (21)

где A = 2i viQ <ak < 2 при О < fc < t. Тогда

и = at + at-i -f- • • • -f- ai + Оо (no модулю 2 - 1), (22)

поскольку Л = 1. Поэтому Uj вычисляются, как и в (16), путем сложения е-би-товых чисел а< ф • • • ф oi ф oq. Этот процесс аналогичен уже знакомому процессу