/*
  Author:  Pate Williams (c) 1997

  Exercise
  "4.19 Factor 262063 and 9420457 using the p - 1
  method. How big does B have to be each case to
  be successful." -Douglas R. Stinson-
  See "Cryptography: Theory and Practice" by
  Douglas R. Stinson page 161.
*/

#include <stdio.h>

#define B_MAX 10000l

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 p_1(long B, long n, long *d)
{
  long a = 2, j;

  for (j = 2; j <= B; j++)
    a = exp_mod(a, j, n);
  *d = gcd(a - 1, n);
  if (*d > 1 && *d < n) return 1;
  return 0;
}

int main(void)
{
  int found;
  long B, d, e, i, ni;
  long n[2] = {262063l, 9420457l};

  for (i = 0; i < 2; i++) {
    ni = n[i];
    found = 0;
    for (B = 2; !found && B <= B_MAX; B++)
      found = p_1(B, ni, &d);
    if (found) {
      e = ni / d;
      if (d * e != ni)
        printf("*error*\in p_1\n");
      else {
        printf("%7ld = %4ld * %4ld ", ni, d, e);
        printf("B = %3ld\n", B);
      }
    }
    else
      printf("%ld not factored in %ld attempts\n",
             ni, B_MAX - 1);
  }
  return 0;
}