**fig10_62.txt**

/* 1*/	enum Test_Result { Probably_Prime, Definitely_Composite };

/* 2*/	// Compute Result = A^P mod N.
/* 3*/	// If at any point X^2 ==1 ( mod N ) is detected,
/* 4*/	// With X != 1 and X != N-1,
/* 5*/	// Then set What_N_Is to Definitely_Composite.

/* 6*/	void
/* 7*/	Power( const Huge_Int & A, const Huge_Int & P, const Huge_Int & N,
/* 8*/	        Huge_Int & Result, Test_Result & What_N_Is )
/* 9*/	{
/*10*/	    Huge_Int X;

/*11*/	    if( P == 0 )	// Base case.
/*12*/	        Result = 1;
/*13*/	    else
/*14*/	    {
/*15*/	        Power( A, P/2, N, X, What_N_Is );
/*16*/	        Result = ( X * X ) % N;

/*17*/	        // Check whether X^2 == 1 ( mod N ), with X != 1 or  N-1.
/*18*/	        if( ( Result == 1 ) && ( X != 1 ) && ( X != N-1 ) )
/*19*/	            What_N_Is = Definitely_Composite;

/*20*/	        // If P is odd, we need one more A.
/*21*/	        if(  ( P % 2 ) == 1 )
/*22*/	            Result = ( Result * A ) % N;
/*23*/	    }
/*24*/	}


/* 1*/	// Test whether N >=3 is prime using one value of A.
/* 2*/	// Repeat as many times as needed for desired error rate.

/* 3*/	Test_Result
/* 4*/	Test_Prime( const Huge_Int & N )
/* 5*/	{
/* 6*/	    Huge_Int A, Result;
/* 7*/	    Test_Result What_N_Is;

/* 8*/	    A = Rand_Int( 2, N - 2 );
/* 9*/	    What_N_Is = Probably_Prime;
/*10*/	    Power( A, N-1, N, Result, What_N_Is );
/*11*/	    if( ( Result != 1 ) || ( What_N_Is == Definitely_Composite ) )
/*12*/	        return Definitely_Composite;
/*13*/	    else
/*14*/	        return Probably_Prime;
/*15*/	}