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

Методы, основанные на переводе чисел из СОК в позиционную (например, десятичную) систему счисления и последующим их сравнением, являются наиболее очевидными и наименее производительными. С целью повышения производительности разработаны методы, основанные на вычислении позиционных характеристик, таких как диагональная функция (Dimauro. 1993), функция Пирло и Импедово (Mohan. 2016). Все вышеперечисленные позиционные характеристики являются монотонными, при этом возможна ситуация, когда разные числа имеют одинаковую позиционную характеристику. В этом случае требуется выполнение дополнительных действий для сравнения чисел, представленных в СОК. Кроме того, для получения значений указанных позиционных характеристик используется ресурсозатратная операция вычисления остатка от деления на большой модуль. Для устранения этих недостатков была разработана модифицированная диагональная функция (RNS Number Comparator ... 2020). Модифицированная диагональная функция (англ. Modified Diagonal Function, MDF) представляет собой строго возрастающую позиционную характеристику чисел, представленных в СОК, сочетающую преимущества диагональной функции и приближённого метода. Строгая монотонность MDF обеспечивает взаимно однозначное соответствие числа и его позиционной характеристики, поэтому не возникает ситуаций, когда требуется выполнение дополнительных действий для сравнения чисел. Кроме того, вместо операции нахождения остатка от деления на большое число при вычислении MDF используются значительно более простые в реализации вычисления по модулю $2^k,$ где $k$ – натуральное число.

Вычисление значения модифицированной диагональной функции от числа $x=(x_1,\ x_2,\ \ldots,\ x_n)\in[0,M-1],$ представленного в СОК с модулями $m_1,m_2,\ldots,m_n,$ где $M=\prod_{i=1}^{n}m_i,$ осуществляется согласно формуле: $$MDF\left(x\right)=\left|\sum_{i=1}^{n}{k_ix_i}\right|_{2^N}.$$Здесь $$k_i=\left\lceil\frac{2^N\cdot\left|-m_i^{-1}\right|_{SQ}}{SQ}\right\rceil,\quad SQ=\sum_{i=1}^{n}\frac{M}{m_i},\quad N=\left\lceil\log_2{(SQ\cdot(m_n-1))}\right\rceil,$$
где $\left|-m_i^{-1}\right|_{SQ}$ – решение сравнения $\alpha m_i\equiv-1\mod\ SQ$ относительно $\alpha,$ $\lceil\,\rceil$ – округление в бо́льшую сторону.

Пример. Пусть задана СОК с модулями $m_1=3,$ $m_2=7,$ $m_3=11,$ $m_4=16,$ $M=\prod_{i=1}^{n}m_i=3696.$ Требуется сравнить числа $x=(0,\ 3,\ 1,\ 3)$ и $y=(1,\ 4,\ 2,\ 4),$ представленные в данной СОК (и равные в десятичной позиционной системе счисления $2355$ и $2356$ соответственно).

Значения констант, необходимых для модифицированной диагональной функции, равны:

$$SQ=\sum_{i=1}^{n}\frac{M}{m_i}=1232+528+336+231=2327,$$$$N=\left\lceil\log_2{(SQ\cdot(m_n-1))}\right\rceil=\left\lceil\log_2{(2327\cdot(16-1))}\right\rceil=16,$$$$\left|-m_1^{-1}\right|_{SQ}=\left|-\frac{1}{3}\right|_{2327}=1551,\quad \left|-m_2^{-1}\right|_{SQ}=\left|-\frac{1}{7}\right|_{2327}=1662,$$$$\left|-m_3^{-1}\right|_{SQ}=\left|-\frac{1}{11}\right|_{2327}=423,\quad \left|-m_4^{-1}\right|_{SQ}=\left|-\frac{1}{16}\right|_{2327}=1018,$$$$k_1=\left\lceil\frac{2^N\cdot\left|-m_1^{-1}\right|_{SQ}}{SQ}\right\rceil=\left\lceil\frac{2^{16}\cdot1551}{2327}\right\rceil=43682,$$$$k_2=\left\lceil\frac{2^N\cdot\left|-m_2^{-1}\right|_{SQ}}{SQ}\right\rceil=\left\lceil\frac{2^{16}\cdot1662}{2327}\right\rceil=46808,$$$$k_3=\left\lceil\frac{2^N\cdot\left|-m_3^{-1}\right|_{SQ}}{SQ}\right\rceil=\left\lceil\frac{2^{16}\cdot423}{2327}\right\rceil=11914,$$$$k_4=\left\lceil\frac{2^N\cdot\left|-m_4^{-1}\right|_{SQ}}{SQ}\right\rceil=\left\lceil\frac{2^{16}\cdot1018}{2327}\right\rceil=28671.$$

Далее, $$MDF\left(x\right)=\left|43682\cdot0+46808\cdot3+11914\cdot1+28671\cdot3\right|_{2^{16}}=41743,$$$$MDF\left(y\right)=\left|43682\cdot1+46808\cdot4+11914\cdot2+28671\cdot4\right|_{2^{16}}=41746.$$Так как $MDF\left(x\right)<MDF\left(y\right),$ то $x<y.$

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