**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*/ }