/*
  Author:  Pate Williams (c) 1997

  Exercise
  "4.16 Suppose Bob has carelessly revealed his
  decryption exponent to be a = 14039 in an RSA
  Cryptosystem with public key n = 36581 and
  b = 4679.  Implement the probabilistic algorithm
  to factor n given this information. Test your
  algorithm  with the "random" choices w = 9983 and
  w = 13641. Show all computations."
  -Douglas R. Stinson-
  See "Cryptography: Theory and Practice by
  Douglas R. Stinson page 161.
*/

#include <stdio.h>

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)
/* Euclid's algorithm */
{
  long r;

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

int factor(long a, long b, long n, long w, long *x)
{
  long r = a * b - 1, s = 0, v, v0;

  *x = gcd(w, n);
  printf("x = %ld\n", *x);
  if (*x > 1 && *x < n) return 1;
  while (!(r & 1)) r >>= 1, s++;
  v = exp_mod(w, r, n);
  printf("w = %ld\n", w);
  printf("r = %ld\n", r);
  printf("s = %ld\n", s);
  printf("v = %ld\n", v);
  if (v == 1) return 0;
  while (v != 1) {
    v0 = v;
    v = (v * v) % n;
    printf("v0 = %ld\n", v0);
    printf("v  = %ld\n", v);
  }
  if (v0 == n - 1) return 0;
  *x = gcd(v0 + 1, n);
  printf("x = %ld\n", *x);
  return 1;
}

int main(void)
{
  long a = 14039l, b = 4679l, n = 36581l;
  long w1 = 9983l, w2 = 13461l, x;

  printf("success = %d\n", factor(a, b, n, w1, &x));
  printf("success = %d\n", factor(a, b, n, w2, &x));
  return 0;
}