/*
  Author:  Pate Williams (c) 1997

  Exercise
  "4.1 Use the Extended Euclidean algorithm to compute
       the following multiplicative inverses:
       (a) 17 ^ - 1 mod 101
       (b) 357 ^ - 1 mod 1234
       (c) 3125 ^ - 1 mod 9987."
  -Douglas R. Stinson-
  See "Cryptography: Theory and Practice" by
  Douglas R. Stinson page 157.
*/

#include <stdio.h>

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;
}

int main(void)
{
  long b[3] = {17, 357, 3125};
  long n[3] = {101, 1234, 9987};
  long i, x, y;

  for (i = 0; i < 3; i++) {
    x = Extended_Euclidean(b[i], n[i]);
    printf("the inverse of %4ld modulo %4ld = %4ld\n",
           b[i], n[i], x);
    y = (x * b[i]) % n[i];
    if (y != 1)
      printf("*error*\nin inverse calculation\n");
  }
  return 0;
}