// ----------------------------------------------------------------------
// 
//  Module:          fast_exp.cc
//  Description:     fast_exponentiation
//  Contributed by:  Rene Peralta
//  Date:            2001
//  
// ----------------------------------------------------------------------
#include <lnv3/lnv3.h>
#include <nttl/traits.h>

ln fast_exp(ln a, ln b, ln n);

int
main( int argc, char *argv[ ] )
{
    ln a,b,n;

    while( 1 )
    {
        cout << "a b n (0 to exit):  will return a^b mod n" << endl;
        cin >> a ;
	if (a.IsZero()) exit(0);
        cin >> b;
	cin >> n;
        cout << fast_exp(a,b,n) << endl << endl;
    }
    return 0;
}

ln fast_exp(ln a, ln b, ln n)
{
  if ( a.IsZero() ) return (0);
  if ( b.IsZero() ) return(1);
  if ( b == 1 ) return(a%n);
  ln x = a*a % n;
  if (b.IsOdd()) return( a*fast_exp(x,b/2,n) % n );
  return(fast_exp(x,b/2,n));
}