(************************************************************)
(*
** 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;
(*---------------------------------------------------------*)