(************************************************************) (* ** ARIBAS Code ** zur Vorlesung ** O. Forster: Algorithmische Zahlentheorie ** SS 2009 LMU Muenchen ** ** Chap. 3. The residue class ring Z/mZ ** ** Functions concerning the Chinese Remainder Theorem *) (*---------------------------------------------------------*) (* ** M is an array of integers, which are supposed to be ** positive and pairwise coprime ** The function maps x to an array with ** coefficients x mod M[i] *) function chin_arr(x: integer; M: array): array; var X: array[length(M)]; i: integer; begin for i := 0 to length(M)-1 do X[i] := x mod M[i]; end; return X; end; (*---------------------------------------------------------*) (* ** Inverse function of chin_arr ** The components of the array M are supposed to ** be positive and pairwise coprime *) function chin_inv(X, M: array): integer; var m, m1, i, z: integer; begin m := product(M); z := 0; for i := 0 to length(M)-1 do m1 := m div M[i]; z := z + X[i] * m1 * mod_inverse(m1,M[i]); end; return z mod m; end; (*---------------------------------------------------------*) (* ** Componentwise addition of two arrays X,Y modulo M *) function arr_add(X,Y,M: array): array; var i: integer; begin for i := 0 to length(X)-1 do X[i] := (X[i] + Y[i]) mod M[i]; end; return X; end; (*---------------------------------------------------------*) (* ** Componentwise multiplication of two arrays X,Y modulo M *) function arr_mult(X,Y,M: array): array; var i: integer; begin for i := 0 to length(X)-1 do X[i] := (X[i] * Y[i]) mod M[i]; end; return X; end; (*---------------------------------------------------------*)