/*
  Author:  Pate Williams (c) 1997

  Exercise
  "5.4 Suppose n = pq, where p and q are two (secret)
  distinct large primes such that p = 2p_1 + 1 and
  q = 2q_1 + 1, where p_1 and q_1 are prime. Suppose
  that alpha is an element of order 2p_1q_1 in Z_n*
  (this is the largest order of any element in Z_n*).
  Define a hash function h : {1,...,n * n} -> Z_n*
  by the rule h(x) = alpha ^ x mod n. Now suppose
  that n = 603241 and alpha = 11 are used to define
  a hash function of this type. Suppose we are given
  three collisions h(1294755) = h(80115359) =
  h(52738737). Use this information to factor n."
  -Douglas R. Stinson-
  See "Cryptogrpahy: Theory and Practice" by Douglas
  R. Stinson page 257.
*/

#include <stdio.h>

long exp_mod(long x, long b, long n)
/* returns x ^ b mod n */
{
  long a = 1l, s = x;

  if (b == 0) return 1;
  while (b != 0) {
    if (b & 1l) a = (a * s) % n;
    b >>= 1;
    if (b != 0) s = (s * s) % n;
  }
  return a;
}

long gcd(long a, long b)
{
  long r;

  while (b > 0)
    r = a % b, a = b, b = r;
  return a;
}

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)