Поиск по сайту.

Математика: Теория чисел.

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

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

Теорема. любое число x: 0 <= x <= B может быть однозначно представлено в виде последовательности v(x) = (v₁, v₂, ..., v_t), где v_i = x(mod m_i).

Эта последовательность называется модульным представлением x. Набор модульныых представлений для всех x: 0 <= x <= B называется системой вычетов.

Операции.

Сумма - последовательность w_i = v_i + u_i mod m_i
Произведение - аналогично z_i = v_i * u_i mod m_i.

Знакомым с теорией колец: теорема <=> Z_B = Zm₁ + ... + Zm_t, сумма прямая.Из этого все операции определяются очевидным образом.

Восстановление: алгоритм Гарнера.

Даю псевдокод

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 := v₁; x := u; 
3. For i from 2 to t {
       u := (v_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_i=5*7*11*13=5005,
v(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).

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

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

Вверх по странице, к оглавлению и навигации.