Китайская теорема об остатках
Страница 3. Алгоритм Гарнера
Страница 3 из 3

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

Пусть все 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 - обратного элемента по модулю можно осуществить опять по алгоритму Евклида.

« Предыдущая страница - Следующая страница
 
« Предыдущая статья   Следующая статья »