/*****************************************************************************/
/*									     */
/*  COUNT PAIRS OF CONSECUTIVE ROOTS OF x**((p-1)/n)=y(mod p), y**n=1(mod p) */
/*  06/01/07 (dkc)							     */
/*									     */
/*****************************************************************************/
#include <stdio.h>
#include <math.h>
#include "input.h"               // primes and primitive roots
int main () {
unsigned int n=2;		 // n value
unsigned int maxprime=5000;	// maximum allowable prime (less than 100000)
unsigned int j[100000],i[32];
unsigned int h,k,k1,l,l1,l2;
FILE *Outfp;
Outfp = fopen("output.dat","w");
for (h=0; h<insize; h++) {
   k=input[2*h];		 // load prime
   if (k>maxprime)		 // reduce execution time
      break;
   j[0]=input[2*h+1];		 // load primitive root
   k1=k-1;
   if (k1!=(k1/n)*n)		 // continue if n does not divide prime minus 1
      continue;
   for (l=0; l<n; l++)		 // clear count array
      i[l]=0;
   for (l=1; l<k1; l++) 	 // compute powers of primitive root
      j[l]=j[0]*j[l-1]-((j[0]*j[l-1])/k)*k;
   if (j[k1-1]!=1)		 // return if last power is not equal to 1
      printf(" error \n");
   for (l=0; l<n; l++) {	 // compute roots of x**((p-1)/n)=y(mod p)
      for (l1=l; l1<k1; l1+=n) {
	 for (l2=l; l2<k1; l2+=n) {
	    if ((j[l1]-j[l2])==1)
	       i[l]=i[l]+1;
	    }
	 }
      }
   fprintf(Outfp," p=%d",k);     // prime
   printf(" p=%d",k);
   for (l=0; l<n; l++) {	 // numbers of pairs of consecutive roots
      fprintf(Outfp," %d",i[l]);
      printf(" %d",i[l]);
      }
   fprintf(Outfp,"\n");
   printf("\n");
   }
fclose(Outfp);
return(0);
}