Китайская теорема об остатках - Алгоритм Гаусса

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

Очевидный алгоритм получается, если вычислять 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