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

Материал из Модулярная арифметики
(Различия между версиями)
Перейти к: навигация, поиск
(Новая страница: «== Китайская теорема об остатках "третьей версии"== Третья версия теоремы [1] является расш…»)
 
 
(не показаны 3 промежуточные версии 1 участника)
Строка 2: Строка 2:
  
 
Третья версия теоремы [1] является расширением [[Описание КТО II|второй версии]] на системы модулей, не являющиеся взаимнопростыми, то есть на избыточную систему остаточных классов.  
 
Третья версия теоремы [1] является расширением [[Описание КТО II|второй версии]] на системы модулей, не являющиеся взаимнопростыми, то есть на избыточную систему остаточных классов.  
 +
 +
Система модулей <math>S = (m_1, m_2, \dots, m_n)</math> не является взаимно простой, то есть является избыточной если <math>HOD(m_i, m_j) > 1</math> для некоторых <math>i <> j</math>. Динамический диапазон для такой системы модулей равен <math>M = HOK(m_1, m_2, \dots, m_n)</math>.
 +
 +
Разделим набор <math>S</math> на две части <math>(m_1, m_2, m_3, \dots, m_t)</math> и <math>(m_{t+1}, m_{t+2}, m_{t+3}, \dots, m_n)</math>:
 +
 +
* <math>M_1 = HOK(m_1, m_2, \dots, m_t)</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

Текущая версия на 09:59, 19 июня 2013

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

Третья версия теоремы [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


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

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