Система нумерации остатков

Система счисления с вычетом ( RNS ) — это система счисления, представляющая целые числа по их значениям по модулю нескольких попарно взаимно простых целых чисел, называемых модулями. Это представление допускается китайской теоремой об остатках , которая утверждает, что, если M является произведением модулей, в интервале длины M существует ровно одно целое число, имеющее любой заданный набор модульных значений. Использование системы счисления вычета для арифметических операций также называется мультимодульной арифметикой .

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

Определение

Система счисления остатка определяется набором из k целых чисел

$\{m_{1},m_{2},m_{3},\ldots ,m_{k}\},$

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

Целое число x представляется в системе счисления вычетов набором его остатков

$\{x_{1},x_{2},x_{3},\ldots ,x_{k}\}$

при евклидовом делении по модулям. То есть

$x_{i}=x\operatorname {mod} m_{i},$

и

$0\leq x_{i}<m_{i}$

для каждого я

Пусть М — произведение всех $m_{i}$. Два целых числа, разность которых кратна M, имеют одинаковое представление в системе счисления остатка, определяемой m i _s . Точнее, китайская теорема об остатках что каждый из M различных наборов возможных остатков представляет ровно один класс вычетов по модулю M. утверждает , То есть каждый набор остатков представляет ровно одно целое число. $X$ в интервале $0,\dots ,M-1$. Для чисел со знаком динамический диапазон равен ${\textstyle {-\lfloor M/2\rfloor }\leq X\leq \lfloor (M-1)/2\rfloor }$(когда $M$ четно, обычно отображается дополнительное отрицательное значение).

Арифметические операции

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

$[m_{1},\ldots ,m_{k}]$

список модулей, сумма целых чисел x и y , соответственно представленных остатками $[x_{1},\ldots ,x_{k}]$ и $[y_{1},\ldots ,y_{k}],$ целое число z, представленное $[z_{1},\ldots ,z_{k}],$ такой, что

$z_{i}=(x_{i}+y_{i})\operatorname {mod} m_{i},$

для i = 1, ..., k (как обычно, mod обозначает операцию по модулю , состоящую в взятии остатка евклидова деления правым операндом). Аналогично определяются вычитание и умножение.

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

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

Сравнение

Если два целых числа равны, то все их остатки равны. И наоборот, если все остатки равны, то два целых числа равны или их разность кратна M . Отсюда следует, что проверить равенство легко.

Напротив, проверка неравенств ( x < y ) сложна и обычно требует преобразования целых чисел к стандартному представлению. Как следствие, такое представление чисел не подходит для алгоритмов, использующих тесты на неравенства, таких как деление Евклида и алгоритм Евклида .

Разделение

Деление в остаточных системах счисления проблематично. С другой стороны, если $B$ является взаимно простым с $M$ (то есть $b_{i}\not =0$) затем

$C=A\cdot B^{-1}\mod M$

можно легко вычислить по

$c_{i}=a_{i}\cdot b_{i}^{-1}\mod m_{i},$

где $B^{-1}$ является мультипликативным обратным $B$ модуль $M$, и $b_{i}^{-1}$ является мультипликативным обратным $b_{i}$ модуль $m_{i}$.

Приложения

RNS имеют применение в области цифровой компьютерной арифметики . Разложив при этом большое целое число на набор меньших целых чисел, можно выполнить большое вычисление как серию меньших вычислений, которые можно выполнять независимо и параллельно.

См. также

• Система покрытия
• Система пониженного остатка

Дальнейшее чтение

• Сабо, Николас С.; Танака, Ричард И. (1967). Остаточная арифметика и ее приложения к компьютерным технологиям (1-е изд.). Нью-Йорк, США: МакГроу-Хилл .
• Сондерстранд, Майкл А.; Дженкинс, В. Кеннет; Жюльен, Грэм А.; Тейлор, Фред Дж., ред. (1986). Арифметика системы счисления остатков: современные приложения в цифровой обработке сигналов . Серия переизданий IEEE Press (1-е изд.). Нью-Йорк, США: Общество схем и систем IEEE , IEEE Press . ISBN  0-87942-205-Х . LCCN   86-10516 . Код заказа IEEE PC01982. (viii+418+6 страниц)
• Червяков Н.И.; Молахоссейни, AS; Ляхов, П.А. (2017). Преобразование вычета в двоичный код для общих наборов модулей на основе приближенной китайской теоремы об остатках . Международный журнал компьютерной математики , 94:9, 1833–1849, doi: 10.1080/00207160.2016.1247439.
• Финько [Финько], Олег Анатольевич [Олег Анатольевич] (июнь 2004 г.). «Большие системы булевых функций: реализация методами модульной арифметики» . Автоматизация и дистанционное управление . 65 (6): 871–892. дои : 10.1023/B:AURC.0000030901.74901.44 . ISSN   0005-1179 . LCCN   56038628 . S2CID   123623780 . КОДЕН   АУРКАТ . Ми   в 1588 .
• Червяков Н.И.; Ляхов, П.А.; Дерябин, М.А. (2020). Решение на основе системы остаточных чисел для снижения стоимости оборудования сверточной нейронной сети . Нейрокомпьютинг , 407, 439-453, doi: 10.1016/j.neucom.2020.04.018.
• Бажар, Жан-Клод; Мелони, Николя; Плантар, Томас (6 октября 2006 г.) [июль 2005 г.]. «Эффективные основы RNS для криптографии» (PDF) . IMACS'05: Всемирный конгресс: Научные вычисления, прикладная математика и моделирование . Париж, Франция. Идентификатор HAL: lirmm-00106470. Архивировано (PDF) из оригинала 23 января 2021 г. Проверено 23 января 2021 г. (1+7 страниц)
• Омонди, Амос; Премкумар, Бенджамин (2007). Системы счисления остатков: теория и реализация . Лондон, Великобритания: Издательство Имперского колледжа . ISBN  978-1-86094-866-4 . (296 страниц)
• Мохан, П.В. Ананда (2016). Системы счисления остатков: теория и приложения (1-е изд.). Биркхойзер / Springer International Publishing, Швейцария . дои : 10.1007/978-3-319-41385-3 . ISBN  978-3-319-41383-9 . LCCN   2016947081 . (351 страница)
• Амир Саббаг, Молахосейни; де Соуза, Леонель Сибра; Чип-Хонг Чанг, ред. (21 марта 2017 г.). Проектирование встраиваемых систем с использованием специальной арифметики и систем счисления (1-е изд.). Спрингер Интернэшнл Паблишинг АГ . дои : 10.1007/978-3-319-49742-6 . ISBN  978-3-319-49741-9 . LCCN   2017934074 . (389 страниц)
• «Алгоритмы деления» . Архивировано из оригинала 17 февраля 2005 г. Проверено 24 августа 2023 г.
• Кнут, Дональд Эрвин . Искусство компьютерного программирования . Эддисон Уэсли .
• Харви, Дэвид (2010). «Многомодульный алгоритм вычисления чисел Бернулли» . Математика вычислений . 79 (272): 2361–2370. arXiv : 0807.1347 . дои : 10.1090/S0025-5718-2010-02367-1 . S2CID   11329343 .
• Лесерф, Грегуар; Шост, Эрик (2003). «Быстрое умножение многомерного степенного ряда по нулевой характеристике». Электронный журнал SADIO по информатике и исследованию операций . 5 (1): 1–10.
• Оранж, Себастьен; Рено, Генель; Ёкояма, Казухиро (2012). «Эффективная арифметика в последовательных алгебраических полях расширения с использованием симметрий». Математика в информатике . 6 (3): 217–233. дои : 10.1007/s11786-012-0112-y . S2CID   14360845 .
• Ёкояма, Кадзухиро (сентябрь 2012 г.). «Использование модульных методов для эффективного расчета идеальных операций». Международный семинар по компьютерной алгебре в научных вычислениях . Берлин / Гейдельберг, Германия: Springer. стр. 361–362.
• Хладик, Якуб; Шимечек, Иван (январь 2012 г.). «Модульная арифметика для решения линейных уравнений на графическом процессоре». Семинар по численному анализу . стр. 68–70.
• Перне, Клеман (июнь 2015 г.). «Точная алгоритмика линейной алгебры: теория и практика». Материалы Международного симпозиума по символьным и алгебраическим вычислениям 2015 года . Ассоциация вычислительной техники . стр. 17–18.
• Лесерф, Грегуар (2018). «О сложности алгоритма промежуточного результата Ликтейга – Роя». Журнал символических вычислений .
• Ёкояма, Кадзухиро; Норо, Масаюки; Такэсима, Таку (1994). «Многомодульный подход к полиномиальной факторизации двумерных целых полиномов» . Журнал символических вычислений . 17 (6): 545–563. дои : 10.1006/jsco.1994.1034 .
• Исупов, Константин (2021). «Высокопроизводительные вычисления в системе счисления остатков с использованием арифметики с плавающей запятой». Вычисление . 9 (2): 9. doi:10.3390/computation9020009 . ISSN 2079-3197.