8.4. МОДУЛЬНАЯ АРИФМЕТИКА

В некоторых приложениях удобно выполнять арифметические операции над целыми числами в "модульном" представлении (т. е. в системе классов вычетов). Это значит, что вместо того, чтобы представлять целое число в системе счисления с фиксированным основанием, его представляют вычетами по модулям из множества попарно взаимно простых чисел. Если попарно взаимно простые числа и то любое целое число можно однозначно представить множеством его вычетов где по модулю Когда фиксированы, пишут

Сложение, вычитание и умножение легко выполняются, если их результаты заключены между и (другими словами, если эти вычисления можно рассматривать как вычисления по модулю Пусть

Тогда

Пример 8.4. Пусть Тогда , поскольку Аналогично . Заметим, что в силу , а это — представление числа 28. Первая компонента произведения равна т. е. 3; вторая компонента равна т. е. 1; третья равна т. е. 0. Кроме того,

(представление числа ), (представление числа 3).

Однако неясно, как в модульной арифметике экономно выполнять деление. Заметим, что отношение может не быть целым числом, а если бы и было, то в общем случае нельзя найти его модульное представление, вычисляя по модулю для каждого Действительно, если не является простым числом, то между и может оказаться несколько целых чисел равных по модулю в том смысле, что Например, если то в качестве можно было бы взять 1, 3 или 5, поскольку Поэтому может не иметь смысла.

Преимущество модульного представления в основном в том, что арифметические операции можно реализовать с меньшими аппаратными затратами, чем при обычном представлении, поскольку вычисления выполняются независимо для каждого модуля. В отличие от обычного (позиционного) представления чисел, здесь не нужны никакие переносы. К сожалению, проблемы эффективного деления и контроля переполнений (т. е. выхода результата за пределы области, заключенной между и оказываются непреодолимыми, и поэтому такие системы редко реализуются в машинных блоках общего назначения.

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

Первая часть доказательства состоит в том, чтобы доказать, что соотношения (8.17) — (8.19) выполняются. Эти соотношения очевидны, и мы оставляем их в качестве упражнения. Вторая часть доказательства — показать, что соответствие взаимно однозначно (т. е. является изоморфизмом). Хотя этот результат несложен, сформулируем его в виде леммы.

Лемма 8.1. Пусть попарно взаимно простые целые числа, Тогда соответствие между целыми числами и в интервале и наборами вида

взаимно однозначно.

Доказательство. Очевидно, что для каждого и найдется соответствующий -членный кортеж. Так как в интервале

заключено ровно значений переменной и допустимых -членных кортежей также ровно достаточно показать, что каждый такой кортеж соответствует не более одному целому числу и. Допустим, что два числа и соответствуют кортежу Тогда разность должна делиться на каждое число Поскольку все попарно взаимно просты, разность должна делиться и на Но делится на так что должны разниться не менее чем на значит, не могут оба лежать между и

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

Допустим, что каждое из чисел содержит разрядов в двоичном представлении. Тогда для представления

требуется, грубо говоря, битов (двоичных разрядов), а деление и на каждое из чисел где могло бы потребовать делений -битового числа на -битовое число. Разбив каждое деление на делений -битовых чисел на -битовые, можно перейти к модульному представлению за время Об где время деления целых чисел (не превосходящее Об в силу следствия теоремы 8.5).

Однако можно проделать эту работу за значительно меньшее время, если применить метод, напоминающий метод деления полиномов из разд. 7.2. Вместо того чтобы делить число и на каждый из модулей сначала вычисляем произведения затем Далее вычисляем вычеты с помощью приема "разделяй и властвуй". Деля, получаем вычеты числа и по модулям соответственно. Теперь задача вычисления и сведена к двум подзадачам половинного размера, а именно и для для

Алгоритм 8.4. Вычисление вычетов

Вход. Модули и такое целое число и, что

Выход. Числа такие, что

Метод. Допустим, что степень числа 2, скажем

(Если нужно, добавим ко входу лишние модули, равные 1, чтобы сделать степенью числа 2.) Начинаем с вычисления определенных произведений модулей, аналогичных полиномам из разд. 7.2.

Пусть число кратно числу и положим

Таким образом,

Сначала вычисляем числа затем находим остатки от деления и на каждое из чисел Искомым ответом будут числа Детали приведены в программе на рис. 8.3.

Теорема 8.8. Алгоритм 8.4 правильно вычисляет числа

Доказательство. Доказательство следует плану доказательства теоремы 7.3, где вычислялись значения полинома в корнях степени из единицы. Легко показать индукцией по что строка 4 правильно вычисляет числа Затем возвратной индукцией по в строке 6 доказываем, что Строки 8 и 9 позволяют сделать это легко. Полагая получаем Детали оставляем в качестве упражнения.

Теорема 8.9. Алгоритм 8.4 тратит времени, если для представления каждого из чисел достаточно битов.

Доказательство. Легко видеть, что больше всего времени требуют циклы в строках 3, 4 и 7—9. Каждый из них занимает

Рис. 8.3. Вычисление вычетов.

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

Следствие. Если для представления каждого из модулей требуется битов, то вычеты по этим модулям можно вычислить за время Об