/*
  Author:  Pate Williams (c) 1997

  Exercise
  "7.3 Suppose p = 15083, alpha = 154, beta = 2307
  in the Chaum-van Heijst-Piftmann Hash Function.
  Given the collision
  alpha ^ 7431 * beta ^ 5564 =
  alpha ^ 1459 * beta ^ 954 (mod p),
  compute log(alpha, beta)." -Douglas R. Stinson-
  See "Cryptography: Theory and Practice" by
  Douglas R. Stinson page 257.
*/

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

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

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

int main(void)
{
  long alpha = 154, beta = 2307, p = 15083;
  long x1 = 7431, x2 = 5564, x3 = 1459, x4 = 954;
  long d, log, p1 = p - 1, q = (p - 1) >> 1, x, y;

  x = x4 - x2;
  if (x < 0) x += p1;
  d = gcd(x, p1);
  if (d == 1) {
    y = Extended_Euclidean(x, p1);
    log = ((x1 - x3) * y) % p1;
  }
  else if (d == 2) {
    x = x4 - x2;
    if (x < 0) x += q;
    y = Extended_Euclidean(x, q);
    x = (x1 - x3) * y;
    log = x % p1;
    if (beta != exp_mod(alpha, log, p))
      log = (x + q) % p1;
  }
  if (beta != exp_mod(alpha, log, p))
    printf("error in log calculation\n");
  printf("alpha = %ld\n", alpha);
  printf("beta = %ld\n", beta);
  printf("p = %ld\n", p);
  printf("q = %ld\n", q);
  printf("x1 = %ld\n", x1);
  printf("x2 = %ld\n", x2);
  printf("x3 = %ld\n", x3);
  printf("x4 = %ld\n", x4);
  printf("d = %ld\n", d);
  printf("log = %ld\n", log);
  return 0;
}