/*
  Author:  Pate Williams (c) 1997

  Exercise I.4.6
  "Factor 3 ^ 15 - 1 and 3 ^ 24 - 1." -Neal Koblitz-
  See "A Course in Number Theory and Cryptography"
  by Neal Koblitz second edition page 29.
*/

#include <stdio.h>
#include "lip.h"

int main(void)
{
  long e = 0;
  verylong za = 0, zb = 0, zc = 0;

  zintoz(3, &za);
  zsexp(za, 15, &zb);
  zsadd(zb, - 1, &zc);
  printf("3 ^ 15 - 1 = ");
  zwriteln(zc);
  /*
     15 = 3 * 5, hence, by Proposition I.4.3
     3 ^ 15 - 1 is divisible by
     3 ^ 3 - 1 = 26 = 2 * 13 and
     3 ^ 5 - 1 = 242 = 2 * 121 = 2 * 11 ^ 2
  */
  zsdiv(zc, 2, &za);
  zsdiv(za, 13, &zc);
  zsdiv(zc, 121, &za);
  printf("factors:\n");
  printf("2\n");
  printf("11 ^ 2\n");
  printf("13\n");
  if (zsmod(za, 30) == 1) zwriteln(za);
  zintoz(3, &za);
  zsexp(za, 24, &zb);
  zsadd(zb, - 1, &zc);
  printf("3 ^ 24 - 1 = ");
  zwriteln(zc);
  /*
     24 = 2 * 3 * 4, hence, by Proposition I.4.3
     3 ^ 24 - 1 is divisible by
     3 ^ 2 - 1 = 8 = 2 ^ 3
     3 ^ 3 - 1 = 26 = 2 * 13
     3 ^ 4 - 1 = 80 = 2 ^ 4 * 5
     (3 ^ 3 - 1) * (3 ^ 3 + 1)
     (3 ^ 4 - 1) * (3 ^ 4 + 1)
     (3 ^ 6 - 1) * (3 ^ 6 + 1)
     3 ^ 3 + 1 = 28 = 2 ^ 2 * 7
     3 ^ 4 + 1 = 82 = 2 * 41
     3 ^ 6 - 1 = 728 = 2 ^ 3 * 7 * 13
     3 ^ 6 + 1 = 730 = 2 * 5 * 73
  */
  while (zsmod(zc, 2) == 0) {
    e++;
    zsdiv(zc, 2, &za);
    zcopy(za, &zc);
  }
  printf("factors:\n");
  printf("2 ^ %ld\n", e);
  printf("5\n");
  printf("7\n");
  printf("13\n");
  printf("41\n");
  printf("73\n");
  zsdiv(zc, 5, &za);
  zsdiv(za, 7, &zc);
  zsdiv(zc, 13, &za);
  zsdiv(za, 41, &zc);
  zsdiv(zc, 73, &za);
  if (zsmod(za, 24) == 1) zwriteln(za);
  return 0;
}