/*
  Author:  Pate Williams (c) 1997

  Exercise
  "4.2 Solve the following system of congruences:
       x = 12 (mod 25)
       x =  9 (mod 26)
       x = 23 (mod 27)." -Douglas R. Sinson-
  See "Cryptography: Theory and Practice" by
  Douglas R. Stinson page 157.
*/

#include <stdio.h>

#define SIZE 256l

long Extended_Euclidean(long b, long n)
{
  long b0 = b, n0 = n, t = 1, t0 = 0, temp, q, r;

  q = n0 / b0;
  r = n0 - q * b0;
  while (r > 0) {
    temp = t0 - q * t;
    if (temp >= 0) temp = temp % n;
    else temp = n - (- temp % n);
    t0 = t;
    t = temp;
    n0 = b0;
    b0 = r;
    q = n0 / b0;
    r = n0 - q * b0;
  }
  if (b0 != 1) return 0;
  else return t % n;
}

long Chinese_Remainder(long r, long *a, long *m)
{
  long i, N = 1, M[SIZE], y[SIZE], x = 0;

  for (i = 0; i < r; i++) N *= m[i];
  for (i = 0; i < r; i++) {
    M[i] = N / m[i];
    y[i] = Extended_Euclidean(M[i], m[i]);
    x += (a[i] * M[i] * y[i]) % N;
  }
  return x;
}

int main(void)
{
  long a[3] = {12, 9, 23};
  long m[3] = {25, 26, 27};
  long i, r = 3, x;

  x = Chinese_Remainder(r, a, m);
  for (i = 0; i < 3; i++) {
    printf("x = %2ld mod %2ld\n", a[i], m[i]);
    if (x % m[i] != a[i])
      printf("*error\nin CRT calculation\n");
  }
  printf("x = %ld\n", x);
  return 0;
}