Модульные операции — различия между версиями

Текущая версия на 09:05, 18 февраля 2015

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

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