Кольцо вычетов по модулю m
Целочисленный тип компьютера в точности соответствует важнейшему понятию математики - понятию кольца вычетов по модулю m. В качестве m выступает число 232 = 4294967296. В математике кольцо Zm определяется следующим образом. Все множество целых чисел Z разбивается на m классов, которые называются классами эквивалентности. Каждый класс содержит числа, попарная разность которых делится на m. Первый класс содержит числа
{...,-2m,-m,0,m,2m, ...}
второй
{..., -2m+1, -m+1, 1, m+1, 2m+1, ...}
последний
{..., -m-1, -1, m-1, 2m-1, 3m-1, ...}
Элементами кольца Zm являются классы эквивалентности. Их ровно m, так что, в отличие от множества целых чисел Z, кольцо Zm содержит конечное число элементов. Операции с классами выполняются следующим образом: надо взять по одному представителю из каждого класса, произвести операцию и определить, в какой класс попадает результат. Этот класс и будет результатом операции. Легко показать, что он не зависит от выбора представителей.
Все числа, принадлежащие одному классу эквивалентности, имеют один и тот же остаток при делении на m. Таким образом, класс эквивалентности однозначно определяется остатком от деления на m. Традиционно остаток выбирается неотрицательным, в диапазоне от 0 до m -1. Остатки используют для обозначения классов, при этом используются квадратные скобки. Так, выражение [5] обозначает класс эквивалентности, состоящий из всех чисел, остатки которых при делении на m равны пяти. Все кольцо Zm состоит из элементов
[0],[1],[2], ...,[m-1],
например, кольцо Z5 состоит из элементов
[0],[1],[2],[3],[4].
В элементарной школьной математике результат операции остатка от деления традиционно считается неотрицательным. Операция нахождения остатка будет обозначаться знаком процента %, как в языке Си. Тогда, к примеру,
3%5 = 3, 17%5 = 2, (-3)%5 = 2, (-17)%5 = 3.
Отсюда видно, что в школьной математике не выполняется равенство
(-a)%b = -(a%b),
т.е. операции изменения знака и нахождения остатка не перестановочны (на математическом языке, не коммутируют друг с другом).
В компьютере операция нахождения остатка от деления для отрицательных чисел определяется иначе, ее результат может быть отрицательным. В приведенных примерах результаты будут следующими:
3%5 = 3, 17%5 = 2, (-3)%5 = -3, (-17)%5 = -2.
При делении на положительное число знак остатка совпадает со знаком делимого. При таком определении тождество
(-a)%b = a%(-b) = -(a%b)
справедливо. Это позволяет во многих алгоритмах не следить за знаками (так же, как в тригонометрии формулы, выведенные для углов, меньших 90 градусов, автоматически оказываются справедливыми для любых углов).
Вернемся к рассмотрению кольца Zm. Выберем по одному представителю из каждого класса эквивалентности, которые составляют множество Zm. Систему таких представителей называют системой остатков. Традиционно рассматривают две системы остатков: неотрицательную систему и симметричную систему. Неотрицательная система остатков состоит из элементов
0,1,2,3, ...m-1.
Очень удобна также симметричная система остатков, состоящая из отрицательных и неотрицательных чисел, не превосходящих m/2 по абсолютной величине. Пусть
k = целая часть(m/2)
тогда симметричная система остатков при нечетном m состоит из элементов
-k, -k+1, ..., -1, 0, 1, ..., k-1, k,
а при четном m - из элементов
-k, -k+1, ..., -1, 0, 1, ..., k-1.
Например, при m = 5 симметричная система остатков состоит из элементов
-2, -1, 0, 1, 2.
Кольцо Zm можно представлять состоящим из элементов, принадлежащих выбранной системе остатков. Арифметические операции определяются следующим образом: надо взять два остатка, произвести над ними операцию как над обычными целыми числами и выбрать тот остаток, которой лежит в том же классе эквивалентности, что и результат операции. Например, для симметричной системы остатков множества Z5 имеем:
1+1 = 2, 1+2 = -2, 1+(-2) = -1, 1+(-1) = 0, (-2)+2 = 0, (-2)+(-2) = 1.
