Модульные операции

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

Пусть операнды $A$ и $B$, а также результаты операций сложения и умножения $A+B$ и $A \cdot B$ представлены соответственно остатками ${\alpha}_i, {\beta}_i, {\gamma}_i, {\delta}_i$ по основаниям $p_i (i=1, \ldots, n)$, причём оба числа и результаты находятся в диапазоне $[0, P)$, то есть

$A=({\alpha}_1, {\alpha}_2, \ldots, {\alpha}_n)$,

$A=({\beta}_1, {\beta}_2, \ldots, {\beta}_n)$,

$A=({\gamma}_1, {\gamma}_2, \ldots, {\gamma}_n)$,

$A=({\delta}_1, {\delta}_2, \ldots, {\delta}_n)$

и

$0 \le A <P, 0 \le B <P, 0 \le A+B <P, 0 \le A\cdot B <P$.

<to be continued>