Описание КТО III — различия между версиями
Материал из Модулярная арифметики
Turbo (обсуждение | вклад) |
Turbo (обсуждение | вклад) |
||
| Строка 10: | Строка 10: | ||
* <math>M_2 = HOK(m_{t+1}, m_{t+2}, \dots, m_n)</math> | * <math>M_2 = HOK(m_{t+1}, m_{t+2}, \dots, m_n)</math> | ||
| + | В этом случае число <math>X</math> имеет следующее представление <math>(X_1, X_2)</math>, где <math>X_1 = X mod M_1</math> и <math>X_2 = X mod M_2</math>. В таком случае восстановление числа X из остатков может быть представлено следующей формулой: | ||
| + | <math>X = X_1 + M_1\cdot|(M_1/d)^{-1}\cdot((X_2-X_1)/d)|_{M_2/d}</math> | ||
| + | |||
| + | где <math>d = HOD(M_1, M_2)</math>. | ||
| + | |||
| + | Можно заметить, что в случае если <math>d = 1</math>, то мы возвращаемся к формуле из [[Описание КТО II|КТО II]]. | ||
== Ссылки == | == Ссылки == | ||
[1] OPTIMIZATION OF NEW CHINESE REMAINDER THEOREMS USING SPECIAL MODULI SETS | [1] OPTIMIZATION OF NEW CHINESE REMAINDER THEOREMS USING SPECIAL MODULI SETS | ||
Текущая версия на 06:59, 19 июня 2013
Китайская теорема об остатках "третьей версии"
Третья версия теоремы [1] является расширением второй версии на системы модулей, не являющиеся взаимнопростыми, то есть на избыточную систему остаточных классов.
Система модулей 
не является взаимно простой, то есть является избыточной если 
для некоторых 
. Динамический диапазон для такой системы модулей равен 
.
Разделим набор 
на две части 
и 
:
В этом случае число 
имеет следующее представление 
, где 
и 
. В таком случае восстановление числа X из остатков может быть представлено следующей формулой:
где 
.
Можно заметить, что в случае если 
, то мы возвращаемся к формуле из КТО II.
Ссылки
[1] OPTIMIZATION OF NEW CHINESE REMAINDER THEOREMS USING SPECIAL MODULI SETS
