Определения
Два целых числа a и b сравнимы по модулю натурального числа n (или равноостаточны при делении на n ), если при делении на n они дают одинаковые остатки.
Эквивалентные формулировки: a и b сравнимы по модулю n , если их разность a — b делится на n , или если a может быть представлено в виде a = b + kn , где k — некоторое целое число. Например: 32 и −10 сравнимы по модулю 7, так как
Утверждение « a и b сравнимы по модулю n » записывается в виде:
Прямое преобразование
Прямое преобразование из позиционной системы счисления (обычно в двоичном виде) в систему счисления в остатках заключается в нахождении остатков от деления по каждому из модулей системы.
Пример: Пусть требуется найти представление числа X = 25 по системе модулей (3, 5, 7). X = (25%3, 25%5, 25%7) = (1, 0, 4).
Реализация нахождения вычета в микроэлектронике по заданному модулю строится на следующих свойствах вычетов:
(a+b) % p = (a%p + b%p)%p
(a*b) % p = (a%p * b%p)%p
Любое число X можно записать в виде X%p = (xn-1*2 n-1 + xn-2*2 n-2 + x*2 0 )%p = ((xn-1)%p*2 n-1 %p) + ((xn-2)%p*2 n-2 %p) + … + x%p)%p. Поскольку в данном случае xn-1, … x равны 0 или 1, то фактически нам требуется сложить вычеты вида (2 i %p).
Пример: пусть задано число 25 или в двоичной системе счисления 11001 и требуется найти остаток по модулю 7.
25%7 = (1*2 4 + 1*2 3 + 0*2 2 + 0* 1 + 1*2 0 )%7 = (2 4 %7 + 2 3 %7 + 1%7)%7 = (2 + 1 + 1)%7 = 4
Систему используемых модулей подбирают под конкретную задачу. Например, для представления 32-х битных чисел достаточно следующей системы модулей: (7, 11, 13, 17, 19, 23, 29, 31) – все они взаимнопросты друг с другом, их произведение равно 6685349671 > 4294967296. Каждый из модулей не превышает 5 бит, то есть операции сложения и умножения будут производиться над 5-битными числами.
Особое значение так же имеет система модулей вида: (2 n -1, 2 n , 2 n +1) в связи с тем, что прямое и обратное преобразование для них выполняется простейшим образом. Что бы получить остаток от деления на 2 n достаточно взять последние n цифр двоичного представления числа.