/*
  Author:  Pate Williams (c) 1997

  Exercise 12.3
  "A PRBG based on the Discrete Logarithm problem
  is given in Figure 12.11. Suppose p = 21383, the
  primitive element alpha = 5 and the seed
  s_0 = 15886. 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 alpha = 5, p = 21383, x_0 = 15886;
  long c_0 = 0, c_1 = 0, i, p2 = p / 2, x, z;

  printf("alpha = %ld\n", alpha);
  printf("p = %ld\n", p);
  printf("x_0 = %ld\n", x_0);
  printf("the first 100 bits are:\n");
  for (i = 0; i < 100; i++) {
    x = exp_mod(alpha, x_0, p);
    x_0 = x;
    z = (x > p2) ? 1 : 0;
    if (!z) c_0++; else c_1++;
    printf("%ld", z);
    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;
}