/*
  Author:  Pate Williams (c) 1997

  Exercise I.3.11
  "Find the smallest nonnegative solution of each
  of the following systems of congruences:
  (a) x = 2 mod 3  (b) x = 12 mod 31
      x = 3 mod 5      x = 87 mod 127
      x = 4 mod 11     x = 91 mod 255
      x = 5 mod 16
  (c) 19x = 103 mod 900
      10x = 511 mod 841" -Neal Koblitz-
  See "A Course in Number Theory and Cryptography"
  by Neal Koblitz second edition page 25.
*/

#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 % N;
}

int main(void)
{
  long a[3][4] = {{2, 3, 4, 5}, {12, 87, 91}, {103, 511}};
  long m[3][4] = {{3, 5, 11, 16}, {31, 127, 255}, {900, 841}};
  long b[2] = {19, 10}, i, j, r[3] = {4, 3, 2}, x;

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