/*
  Author:  Pate Williams (c) 1997

  Exercise
  "4.13 Write a program that computes the number
  of Euler pseudo-primes to the bases 837, 851,
  and 1189." -Douglas R. Stinson-
  See "Cryptography: Theory and Practice" by
  Douglas R. Stinson page 160.
*/

#include <stdio.h>

int JACOBI(long a, long n)
{
  int s;
  long a1, b = a, e = 0, m, n1;

  if (a == 0) return 0;
  if (a == 1) return 1;
  while ((b & 1) == 0)
    b >>= 1, e++;
  a1 = b;
  m = n % 8;
  if (!(e & 1)) s = 1;
  else if (m == 1 || m == 7) s = + 1;
  else if (m == 3 || m == 5) s = - 1;
  if (n % 4 == 3 && a1 % 4 == 3) s = - s;
  if (a1 != 1) n1 = n % a1; else n1 = 1;
  return s * JACOBI(n1, a1);
}

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)
{
  int j;
  long a, c, i, n[3] = {837l, 851l, 1189l};
  long n1, n2, ni, x;

  for (i = 0; i < 3; i++) {
    c = 0;
    ni = n[i];
    n1 = ni - 1;
    n2 = n1 >> 1;
    for (a = 2l; a < ni; a++) {
      x = exp_mod(a, n2, ni);
      j = JACOBI(a, ni);
      if (j == - 1 && x == n1) c++;
      else if (j == x) c++;
    }
    printf("%ld Euler pseudo-prime(s) base %4ld\n", c, ni);
  }
  return 0;
}