Система остаточных классов

Систе́ма оста́точных кла́ссов (СОК), непозиционная система счисления, числа в которой представлены наборами остатков от деления на попарно взаимно простые натуральные числа.

СОК задаётся набором попарно взаимно простых натуральных чисел (модулей системы) ${\displaystyle \{m_{1},m_{2},\ldots ,m_{n}\},}$ ${\displaystyle M=\prod _{i=1}^{n}m_{i}}$ – диапазон СОК. Целое число ${\displaystyle x\geq 0}$ в СОК представляется в виде набора остатков от деления числа ${\displaystyle x}$ на модули системы ${\displaystyle m_{i}}$. Каждому числу ставится в соответствие единственный набор ${\displaystyle \left(x_{1},x_{2},\ldots ,x_{n}\right),}$ где ${\displaystyle x_{i}=x\mod {m_{i}}}$ (Ananda Mohan. 2016^[1]).

Например, число ${\displaystyle 104}$ в СОК с модулями ${\displaystyle \{3,\ 5,\ 8\}}$ имеет вид ${\displaystyle 104=(2,\ 4,\ 0)}$. Диапазон СОК равен ${\displaystyle 120}$.

Для вычисления остатка от деления разработаны алгоритмы (Nazarov. 2020.^[2] P. 10–13) более эффективные, чем, например, известное со школы «деление углом».

На рисунке представлено сложение в позиционной десятичной системе счисления и в СОК с модулями ${\displaystyle \{3,5,8\}}$. При сложении в СОК складываются остатки по соответствующим модулям, поэтому, например, ${\displaystyle (4+4)\mod 5=8\mod 5=3}$. Вычислив соответствующие остатки от деления, легко убедиться, что действительно ${\displaystyle 113=(2,\ 3,\ 1)}$.

В десятичной системе счисления для вычисления второй цифры, соответствующей количеству десятков в сумме, необходимо дождаться вычисления третьей цифры, соответствующей единицам, потому что возможен перенос в старший разряд. В СОК же вычисления по каждому из модулей происходят независимо без межразрядных переносов, кроме того операнды имеют ме́ньшую разрядность (маленькие числа складывать проще). Если необходимо сложить очень большие числа, задержка, связанная с ожиданием возможных переносов из единиц в десятки, из десятков в сотни и т. д. будет очень большой, тогда как для СОК всё останется по-прежнему. Аналогично обстоит дело с вычитанием (когда необходимо «занимать» у старшего разряда) и умножением. Арифметические операции сложения, вычитания и умножения чисел в СОК называются модульными и выполняются покомпонентно (Акушский. 1968^[3]).

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

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

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