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

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

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

Вычисление значения модифицированной диагональной функции от числа ${\displaystyle x=(x_{1},\ x_{2},\ \ldots ,\ x_{n})\in [0,M-1]}$, представленного в СОК с модулями ${\displaystyle m_{1},m_{2},\ldots ,m_{n}}$, где ${\displaystyle M=\prod _{i=1}^{n}m_{i}}$, осуществляется согласно формуле:

${\displaystyle MDF\left(x\right)=\left|\sum _{i=1}^{n}{k_{i}x_{i}}\right|_{2^{N}}}$.

Здесь

${\displaystyle 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 }$,

где ${\displaystyle \left|-m_{i}^{-1}\right|_{SQ}}$ – решение сравнения ${\displaystyle \alpha m_{i}\equiv -1\mod \ SQ}$ относительно ${\displaystyle \alpha }$, ${\displaystyle \lceil \,\rceil }$ – округление в бо́льшую сторону.

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

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

${\displaystyle SQ=\sum _{i=1}^{n}{\frac {M}{m_{i}}}=1232+528+336+231=2327}$,

${\displaystyle N=\left\lceil \log _{2}{(SQ\cdot (m_{n}-1))}\right\rceil =\left\lceil \log _{2}{(2327\cdot (16-1))}\right\rceil =16}$,

${\displaystyle \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}$,

${\displaystyle \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}$,

${\displaystyle k_{1}=\left\lceil {\frac {2^{N}\cdot \left|-m_{1}^{-1}\right|_{SQ}}{SQ}}\right\rceil =\left\lceil {\frac {2^{16}\cdot 1551}{2327}}\right\rceil =43682}$,

${\displaystyle k_{2}=\left\lceil {\frac {2^{N}\cdot \left|-m_{2}^{-1}\right|_{SQ}}{SQ}}\right\rceil =\left\lceil {\frac {2^{16}\cdot 1662}{2327}}\right\rceil =46808}$,

${\displaystyle k_{3}=\left\lceil {\frac {2^{N}\cdot \left|-m_{3}^{-1}\right|_{SQ}}{SQ}}\right\rceil =\left\lceil {\frac {2^{16}\cdot 423}{2327}}\right\rceil =11914}$,

${\displaystyle k_{4}=\left\lceil {\frac {2^{N}\cdot \left|-m_{4}^{-1}\right|_{SQ}}{SQ}}\right\rceil =\left\lceil {\frac {2^{16}\cdot 1018}{2327}}\right\rceil =28671}$.

Далее,

${\displaystyle MDF\left(x\right)=\left|43682\cdot 0+46808\cdot 3+11914\cdot 1+28671\cdot 3\right|_{2^{16}}=41743}$,

${\displaystyle MDF\left(y\right)=\left|43682\cdot 1+46808\cdot 4+11914\cdot 2+28671\cdot 4\right|_{2^{16}}=41746}$.

Так как ${\displaystyle MDF\left(x\right)<mdf\left(y\right)}$, то ${\displaystyle x<y}$.</mdf\left(y\right)<></math>

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