Описание КТО 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)$

Ссылки

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