| Китайская теорема об остатках
Кантор И.А
e-mail: algolist@mail.ru
web: algolist.da.ru
Пусть m - натуральное число, m1, m2, ..., mt - взаимно простые натуральные числа, произведение которых больше либо равно m.
Теорема Любое число x: 0 <= x <= m может быть однозначно представлено в виде последовательности r(x) = (r1, r2, ..., rt), где ri = x(mod mi).
Для любых чисел r1 .. rt, таким образом, существует единственное число x(mod m), такое что
x = ri(mod mi), 1 <= i <= t
Более того, любое решение x набора такого сравнений имеет вид
x = r1*e1 + ... + rt*et (mod m), где
ei = m / mi * ( ( m/mi )-1 mod mi ), 1 <= i <= t.
Вышеприведенная формулировка - Китайская Теорема об Остатках в том виде, в котором ее сформулировал в 1247 году нашей эры китаец Jiushao Qin.
Заметим, что число m/mi = m1*...*mi-1*mi+1*...*mt взаимно просто с mi, а значит обратное число в формуле для ei всегда существует. Кроме того, имеют место равенства
ei*ei = ei (mod m)
ei * ej = 0 (mod m), i =/= j.
Знакомым с теорией колец: Zm = Zm1 + ... + Zmt, сумма прямая. ei, как следует из равенств выше - ортогональные идемпотенты в кольце Zm.
Иначе говоря, кольцо R = Zm разлагается в прямую сумму
R = R1 + R2 + ... + Rt ,
где Ri = Rei = {a*ei (mod m): a - целое} ~ Zmi , 1 <= i <= t.
Последовательность ( r1, ..., rt ) называется модульным представлением x. Набор модульных представлений для всех x: 0 <= x <= m называется системой вычетов.
Операции
Сумма представлений - последовательность wi = ri + ui mod mi
Произведение - последовательность zi = ri * ui mod mi.
Как восстановить число по системе вычетов?
Алгоритм Гаусса
Очевидный алгоритм получается, если вычислять x по формуле, данной в теореме:
На входе:
положительные взаимно простые m1, ..,mt
целые r1, .., rt
На выходе:
Целое число x:
x = ri (mod mi), 1 <= i <= t
0 <= x <= m, m = m1*..*mt
1. Вычислить m = m1*..*mt, положить x=0.
2. for i=1, 2, .., t do
вычислить yi = m/mi
вычислить расширенным алгоритмом Евклида si = yi-1 mod mi
ci = ri*si mod mi
x = x + ci*yi (mod m)
3. Возвратить x
Алгоритм Гарнера
Пусть все mi > 1, m = m1*..*mt. Тогда любое число 0 <= x < m может быть однозначным образом представлено в виде
x = x0 + x1m1 + x2m1m2 + ... + xt-1m1m2*...*mt-1 ,
где 0 <= xi < mi+1, i = 0, 1, .., t-1.
Для xi верно соотношение
| xi = |
ri+1 - ( x0 + x1m1 + .. + xi-1m1mi-1) |
(mod mi+1) |
|
| m1*..*mi |
Таким образом, xi могут быть вычеслены один за другим.
Получившийся алгоритм носит имя Гарнера(Garner). Он также пригоден для аналогичных операций с полиномами (в предыдущем алгоритме требуются некоторые изменения).
1. For i from 2 to t {
1.1 Ci := 1;
1.2 For j from 1 to (i-1) {
u := mj-1 mod mi;
Ci := u*Ci mod mi;
}
}
2. u := r1; x := u;
3. For i from 2 to t {
u := (ri-x)Ci mod mi;
x := x + u* [ Произведение mj от j=1 до i-1 ];
}
4. return (x);
Пример: пусть
m1=5, m2=7, m3=11, m4=13,
m = m1*m2*m3*m4 = 5*7*11*13 = 5005,
r(x) = (2, 1, 3, 8).
Константы Ci: C2=3, C3=6, C4=5.
Значения (i, u, x), вычисленные на шаге 3: (1, 2, 2); (2, 4, 22); (3, 7, 267) и (4, 5, 2192).
Таким образом модульное представление r(x) отвечает x = 2192.
Примечание Нахождение m-1 - обратного элемента по модулю можно осуществить опять по алгоритму Евклида.
| |
Главная 
