/*
  Author:  Pate Williams (c) 1997

  Exercise 12.2
  "Suppose we have an RSA Generator with n = 36863,
  b = 229 and seed s_0 = 25. Compute the first 100
  bits produced by this generator."
  -Douglas R. Stinson-
  See "Cryptography: Theory and Practice" by
  Douglas R. Stinson page 385.
*/

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

int main(void)
{
  long b = 229, n = 36863l, s_0 = 25;
  long c_0 = 0, c_1 = 0, i, s, t;

  printf("b = %ld\n", b);
  printf("n = %ld\n", n);
  printf("s_0 = %ld\n", s_0);
  printf("the first 100 bits are:\n");
  for (i = 0; i < 100; i++) {
    s = exp_mod(s_0, b, n);
    s_0 = s;
    t = s & 1;
    if (!t) c_0++; else c_1++;
    printf("%ld", t);
    if ((i + 1) % 25 == 0) printf("\n");
  }
  printf("count of 0's = %ld\n", c_0);
  printf("count of 1's = %ld\n", c_1);
  return 0;
}