Китайская теорема об остатках
Страница 2. Алгоритм Гаусса
|
|
Страница 2 из 3
Алгоритм Гаусса Очевидный алгоритм получается, если вычислять 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
|