/* ECP: FILEname=fig11_10.c */
/* 1*/   /* Given A And B, Assume Gcd( A, B ) = 1 */
/* 2*/   /* Find X And Y Such That A X + B Y = 1 */

/* 3*/   void
/* 4*/   FullGcd( const HugeInt A, const HugeInt B,
                                         HugeInt *X, HugeInt *Y )
/* 5*/   {
/* 6*/       HugeInt X1, Y1;

/* 7*/       if( B == 0 )
/* 8*/       {
/* 9*/           *X = 1;     /* If A != 1, There Is No Inverse */
/*10*/           *Y = 0;     /* We Omit this Check */
/*11*/       }
/*12*/       else
/*13*/       {
/*14*/           FullGcd( B, A % B, &X1, &Y1 );
/*15*/           *X = Y1;
/*16*/           *Y = X1 - ( A / B ) * Y1;
/*17*/       }
/*18*/   }

/* 1*/   /* Solve A X == 1 ( Mod N ) */
/* 2*/   /* Assume That Gcd( A, N ) = 1 */

/* 3*/   HugeInt
/* 4*/   Inverse( const HugeInt A, const HugeInt N )
/* 5*/   {
/* 6*/       HugeInt X, Y;

/* 7*/       FullGcd( A, N, &X, &Y );
/* 8*/       return X > 0 ? X : X + N;
/* 9*/   }