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

СОК задаётся набором попарно взаимно простых натуральных чисел (модулей системы) $\{m_1,m_2,\ldots,m_n\},$ $M=\prod_{i=1}^{n}m_i$ – диапазон СОК. Целое число $x\ge 0$ в СОК представляется в виде набора остатков от деления числа $x$ на модули системы $m_i.$ Каждому числу ставится в соответствие единственный набор $\left(x_1,x_2,\ldots,x_n\right),$ где $x_i=x\mod{m_i}$ (Ananda Mohan. 2016).

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

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

Сложение чисел в позиционной системе счисления и в СОК.Сложение чисел в позиционной системе счисления и в СОК.

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

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

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

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

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