/*
  Author:  Pate Williams (c) 1997

  Exercise 7.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>
#include "lip.h"

int main(void)
{
  long alpha = 11, n = 603241, n1 = n - 1;
  long x1 = 1294755, x2 = 80115359, x3 = 52738737;
  long s1 = (x1 - x2) / 2, s2 = (x1 - x3) / 2;
  verylong za = 0, zb = 0, zc = 0, zd = 0, zn = 0;
  verylong zalpha = 0;
  verylong zn1 = 0, zs1 = 0, zs2 = 0;
  verylong zx1 = 0, zx2 = 0, zx3 = 0;

  zintoz(alpha, &zalpha);
  zintoz(n, &zn);
  zintoz(n1, &zn1);
  zintoz(s1, &zs1);
  zintoz(s2, &zs2);
  zintoz(x1, &zx1);
  zintoz(x2, &zx2);
  zintoz(x3, &zx3);
  printf("n = ");
  zwriteln(zn);
  zexpmod(zalpha, zx1, zn, &za);
  printf("h(x1) = h(%8ld) = ", x1);
  zwriteln(za);
  zexpmod(zalpha, zx2, zn, &zb);
  printf("h(x2) = h(%8ld) = ", x2);
  zwriteln(zb);
  zexpmod(zalpha, zx3, zn, &zc);
  printf("h(x3) = h(%8ld) = ", x3);
  zwriteln(zc);
  zgcd(zs1, zs2, &za);
  printf("gcd((x1 - x2) / 2, (x1 - x3) / 2) = ");
  zwriteln(za);
  zlshift(za, 2l, &zb);
  zsub(zn, zb, &zc);
  zsadd(zc, 1l, &za);
  zsq(za, &zb);
  zlshift(zn, 2l, &zc);
  zsub(zb, zc, &zd);
  zsqrt(zd, &zb, &zc);
  zadd(za, zb, &zd);
  zrshift(zd, 1l, &zx1);
  zsub(za, zb, &zd);
  zrshift(zd, 1l, &zx2);
  printf("p = ");
  zwriteln(zx1);
  printf("q = ");
  zwriteln(zx2);
  printf("p * q = ");
  zmul(zx1, zx2, &za);
  zwriteln(za);
  zfree(&za);
  zfree(&zb);
  zfree(&zc);
  zfree(&zd);
  zfree(&zn);
  zfree(&zn1);
  zfree(&zs1);
  zfree(&zs2);
  zfree(&zx1);
  zfree(&zx2);
  zfree(&zx3);
  zfree(&zalpha);
  return 0;
}