/* ECP: FILEname=fig11_8.c */
/* 1*/   /* If Witness Does Not return 1, N Is Definitely Composite */
/* 2*/   /* Do This By Computing A^i ( Mod N ) And Look For */
/* 3*/   /* Non-Trivial Square Roots Of 1 Along The Way */

/* 4*/   HugeInt
/* 5*/   Witness( const HugeInt A, const HugeInt i, const HugeInt N )
/* 6*/   {
/* 7*/       HugeInt X, Y;

/* 8*/       if( i == 0 )
/* 9*/           return 1;

/*10*/       X = Witness( A, i / 2, N );
/*11*/       if( X == 0 )  /* If N Is Recursively Composite, Stop */
/*12*/           return 0;

/*13*/       /* N Is Not Prime if We Find A Non-Trivial Root Of 1 */
/*14*/       Y = ( X * X ) % N;
/*15*/       if( Y == 1 && X != 1 && X != N - 1 )
/*16*/           return 0;

/*17*/       if( i % 2 )
/*18*/           Y = ( A * Y ) % N;

/*19*/       return Y;
/*20*/   }


/* 1*/   /* Make NumTrials Call To Witness To Check if N Is Prime */

/* 2*/   int
/* 3*/   IsPrime( const HugeInt N )
/* 4*/   {
/* 5*/       const int NumTrials = 5;
/* 6*/       int Counter;

/* 7*/       for( Counter = 0; Counter < NumTrials; Counter++ )
/* 8*/           if( Witness( RandInt( 2, N - 2 ), N - 1, N ) != 1 )
/* 9*/               return 0;

/*10*/       return 1;
/*11*/   }