Просмотр исходного текста страницы Модульные операции

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

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

:<math>A=({\alpha}_1, {\alpha}_2, \ldots, {\alpha}_n)</math>,
:<math>A=({\beta}_1, {\beta}_2, \ldots, {\beta}_n)</math>,
:<math>A=({\gamma}_1, {\gamma}_2, \ldots, {\gamma}_n)</math>,
:<math>A=({\delta}_1, {\delta}_2, \ldots, {\delta}_n)</math>

и

:<math>0 \le A <P, 0 \le B <P, 0 \le A+B <P, 0 \le A\cdot B <P</math>.


<to be continued>