Описание КТО III

Китайская теорема об остатках "третьей версии"

Третья версия теоремы [1] является расширением второй версии на системы модулей, не являющиеся взаимнопростыми, то есть на избыточную систему остаточных классов.

Система модулей $S = (m_1, m_2, \dots, m_n)$ не является взаимно простой, то есть является избыточной если $HOD(m_i, m_j) > 1$ для некоторых $i <> j$. Динамический диапазон для такой системы модулей равен $M = HOK(m_1, m_2, \dots, m_n)$.

Разделим набор $S$ на две части $(m_1, m_2, m_3, \dots, m_t)$ и $(m_{t+1}, m_{t+2}, m_{t+3}, \dots, m_n)$:

• $M_1 = HOK(m_1, m_2, \dots, m_t)$
• $M_2 = HOK(m_{t+1}, m_{t+2}, \dots, m_n)$

В этом случае число $X$ имеет следующее представление $(X_1, X_2)$, где $X_1 = X mod M_1$ и $X_2 = X mod M_2$. В таком случае восстановление числа X из остатков может быть представлено следующей формулой:

$X = X_1 + M_1\cdot|(M_1/d)^{-1}\cdot((X_2-X_1)/d)|_{M_2/d}$

где $d = HOD(M_1, M_2)$.

Можно заметить, что в случае если $d = 1$, то мы возвращаемся к формуле из КТО II.

Ссылки

[1] OPTIMIZATION OF NEW CHINESE REMAINDER THEOREMS USING SPECIAL MODULI SETS