//  ============================================================
//
//  fastExp.cc
//
//  Copyright 2002, Dennis Meilicke and Rene Peralta
//
//  ============================================================
//
//  Description:
//
//  ln3-specific version of the FastExp method.  This is a
//  temporary implementation, and will be obsolete sometime
//  soon.  It will be replaced by the various Power( ) functions
//  in NTTL.
//
//  ============================================================


#include <lnv3/lnv3.h>


//
//  AIX: For declaration of exit( );
//
#include <stdlib.h>



//  ======================================================================


ln
ln::FastExp( const ln &Exponent, const ln &Modulus ) const
//
//  Date:        June 1993
//  Description: Compute *this^Exponent mod Modulus
//  Algorithm:   This is the Fast Exponentiation Algorithm.  See
//               Bressoud, or, of course, Knuth.
//  Notes:       This is an optimized form of FastExp.  Can this be
//               further optimized?  I think so.  We do not have to go
//               backwards through the exponent.  This gets rid of
//               mask, etc.
//
{
    static ln Result;
  
    if( this->IsZero( ) )   // *this == 0
    { 
        if( Exponent.IsZero( ) ) 
        { 
            cerr << "<ERROR-0020>. Fast Exponentation method ";
            cerr << "raise 0 to 0\n";
            exit( 0 );
        }

        Result = 0;

        return Result;
    }
    
    Result = 1;

    if ( Exponent.IsZero() ) 
        return Result;
    
    //
    //  The leading digit is a special case, since it (may) not have all
    //  of its bits used.
    //
    digit_t digit = Exponent.GetData( )->digit[ Exponent.GetData( )->size - 1 ];
    digit_t mask = 1;
    size_t i = ::NumBits( digit );
    if( i != 1 )
        mask = 1 << (i - 1);
    while( mask )
    {
        //Result = Result * Result % Modulus;
        Result = Result * Result;
        Result = Result % Modulus;
        if( mask & digit )
            Result = Result * *this % Modulus;
        mask = mask >> 1;
    }
    
    //
    //  Now the general case: all bits are significant:
    //
    for( i=Exponent.GetData( )->size-1 ; i>0 ; i-- )
    {
        mask = 0x80000000;
        digit = Exponent.GetData( )->digit[ i - 1 ];
        while( mask )
        {
            Result = Result * Result % Modulus;
            if( mask & digit )
                Result = Result * *this % Modulus;
            mask = mask >> 1;
        }
    }
    
    return Result; 
}