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

Путь: Математика » Теория чисел » Китайская теорема об остатках

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

Кантор И.А
e-mail: algolist@mail.ru
web: iliakan@gmail.com

Пусть m - натуральное число, m₁, m₂, ..., m_t - взаимно простые натуральные числа, произведение которых больше либо равно m.

Теорема

Любое число x: 0 <= x <= m может быть однозначно представлено в виде последовательности r(x) = (r₁, r₂, ..., r_t), где r_i = x(mod m_i).

Для любых чисел r₁ .. r_t, таким образом, существует единственное число x(mod m), такое что

x = r_i(mod m_i), 1 <= i <= t

Более того, любое решение x набора такого сравнений имеет вид

x = r₁*e₁ + ... + r_t*e_t (mod m), где e_i = m / m_i * ( ( m/m_i )^-1 mod m_i ), 1 <= i <= t.

Вышеприведенная формулировка - Китайская Теорема об Остатках в том виде, в котором ее сформулировал в 1247 году нашей эры китаец Jiushao Qin.

Заметим, что число m/m_i = m₁*...*m_i-1*m_i+1*...*m_t взаимно просто с m_i, а значит обратное число в формуле для e_i всегда существует. Кроме того, имеют место равенства

e_i*e_i = e_i (mod m)
e_i * e_j = 0 (mod m), i =/= j.

Знакомым с теорией колец: Z_m = Zm₁ + ... + Zm_t, сумма прямая. e_i, как следует из равенств выше - ортогональные идемпотенты в кольце Zm.

Иначе говоря, кольцо R = Zm разлагается в прямую сумму

R = R₁ + R₂ + ... + R_t ,

где R_i = Re_i = {a*e_i (mod m): a - целое} ~ Zm_i , 1 <= i <= t.

Последовательность ( r₁, ..., r_t ) называется модульным представлением x. Набор модульных представлений для всех x: 0 <= x <= m называется системой вычетов.

Операции

Сумма представлений - последовательность w_i = r_i + u_i mod m_i

Произведение - последовательность z_i = r_i * u_i mod m_i.

Как восстановить число по системе вычетов?

Алгоритм Гаусса

Очевидный алгоритм получается, если вычислять x по формуле, данной в теореме:

На входе: 
положительные взаимно простые m₁, ..,m_t
целые r₁, .., r_t

На выходе:
Целое число x:
x = r_i (mod m_i), 1 <= i <= t
0 <= x <= m, m = m₁*..*m_t

1. Вычислить m = m₁*..*m_t, положить x=0.
2. for i=1, 2, .., t do
	вычислить y_i = m/m_i
	вычислить расширенным алгоритмом Евклида s_i = y_i^-1 mod m_i
    c_i = r_i*s_i mod m_i
    x = x + c_i*y_i (mod m)
3. Возвратить x

Алгоритм Гарнера

Пусть все m_i > 1, m = m₁*..*m_t. Тогда любое число 0 <= x < m может быть однозначным образом представлено в виде

x = x₀ + x₁m₁ + x₂m₁m₂ + ... + x_t-1m₁m₂*...*m_t-1 ,

где 0 <= x_i < m_i+1, i = 0, 1, .., t-1.

Для x_i верно соотношение

x_i = r_i+1 - ( x₀ + x₁m₁ + .. + x_i-1m₁m_i-1) (mod m_i+1)

m₁*..*m_i

Таким образом, x_i могут быть вычеслены один за другим. Получившийся алгоритм носит имя Гарнера(Garner). Он также пригоден для аналогичных операций с полиномами (в предыдущем алгоритме требуются некоторые изменения).

1. For i from 2 to t {
    1.1 C_i := 1; 
    1.2 For j from 1 to (i-1) {
           u := m_j^-1 mod m_i; 
           C_i := u*C_i mod m_i; 
        }
    }
2. u := r₁; x := u; 
3. For i from 2 to t {
       u := (r_i-x)C_i mod m_i;
	   x := x + u* [ Произведение m_j от j=1 до i-1 ]; 
    }
4. return (x);

Пример: пусть
m₁=5, m₂=7, m₃=11, m₄=13,
m = m₁*m₂*m₃*m₄ = 5*7*11*13 = 5005,
r(x) = (2, 1, 3, 8).

Константы C_i: C₂=3, C₃=6, C₄=5.

Значения (i, u, x), вычисленные на шаге 3: (1, 2, 2); (2, 4, 22); (3, 7, 267) и (4, 5, 2192).

Таким образом модульное представление r(x) отвечает x = 2192.

Примечание Нахождение m^-1 - обратного элемента по модулю можно осуществить опять по алгоритму Евклида.