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

Материал из Модулярная арифметики
Версия от 12:05, 18 февраля 2015; Isaeva (обсуждение | вклад)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

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

Пусть операнды 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>


Персональные инструменты
Пространства имён

Варианты
Действия
Навигация