Модулярная арифметика

Модулярное исчисление состоит в осуществлении нескольких малых вычислений по модулям простых чисел и получении необходимого результата с помощью теоремы об остатках.

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

Пусть n₁ ,n₂, …, n_r - попарно взаимно простые числа. Пусть а₁ ,а₂, …, а_r произвольно целые числа. Тогда система

имеет по крайней мере одно решение. Кроме того, если х' – другое решение этой системы, то хºх'(mod n₁·n₂· …·n_r ).

Смешанная система счисления.

Идея, принадлежавшая Л.Гарнеру и представленная у Д.Кнута, состоит в том, чтобы связать с модулярным представлением еще одно представление, называемое смешанной системой счисления.

Основанием смешанной системы счисления называется множество из r³2 целых чисел n₁,n₂,…,n_r, не обязательно взаимно простых. Если положим и n=n₁·n₂·…·n_r, то имеется биекция (взаимно однозначное соответствие):

Обратное отображение определяется при помощи евклидовых делений:

x=q₁n₁+z₁, q₁= q₂n₂+z₂, … , q_r-1= q_rn_r+z_r.

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

Формулы определения цифр.

Пусть n₁,n₂,…,n_r – попарно взаимно простые числа. Пусть и C_i – обратные к N_i по модулю n_i.

Рассмотрим целое число x, модулярные компоненты которого x₁,x₂,…,x_r тогда цифры x в системе со смешанным основанием n_i обозначим через z_i ; они находятся по формулам:

z₁= x₁mod n₁,

z₂= C₂(x₂-z₁) mod n₂,

z₃= C₃(x₃-(N₂z₂+z₂)) mod n₃,

……………

z_r= C_r(x_r-(N_r-1z_r-1+…+ N₂z₂+z₁)) mod n_r.

Чтобы осуществить обратный переход от системы со смешанным основанием к модулярному представлению, достаточно провести следующие вычисления:

x₁=z₁,

x₂=(z₁+z₂n₁)mod n₂,

x₃=(z₁+z₂n₁+z₃n₁n₂)mod n₃,

…

x_r=(z₁+z₂n₁+…+z_rn₁n₂…n_r-1)mod n_r.

Сравнение чисел, определение цифр в позиционной системе счисления.

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