//  ============================================================
//
//  isPrime.h
//
//  Copyright 2002, Dennis Meilicke and Rene Peralta
//
//  ============================================================
//
//  Description:
//
//  NTTL Implementation of:
//      IsPrime
//
//  ============================================================
#ifndef __nttlHeader_isPrime__
#define __nttlHeader_isPrime__


#include <nttl/traits.h>


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


template< class T >
bool
IsPrime( const T &X, size_t security = 30 )
//
//  Description
//
//  Returns TRUE if X is a prime number.  The algorithm is
//  probabilistic, with an error determined by the 'security'
//  parameter.
//
{
    static nttlTraits<T> t;


    if( X %  2 == 0) return ( X == 2  ? true : false );
    if( X %  3 == 0) return ( X == 3  ? true : false );
    if( X %  5 == 0) return ( X == 5  ? true : false );
    if( X %  7 == 0) return ( X == 7  ? true : false );
    if( X % 11 == 0) return ( X == 11 ? true : false );
    if( X % 13 == 0) return ( X == 13 ? true : false );
    
    T a = t.Abs( X );

    if( a == 1 ) return true;
    
    T e = ( a - 1 ) / 2;
    bool seeMinus1 = false;
    T minusOne = a - 1;
    
    T b, r;
    
    for( size_t i = 0 ; i < security ; i++ )
    {
        while( 1 )
        {
            r = t.Random( 10 ) % a;
            if( r != 0 )
                break;
        }

        b = t.Power( r, e, a );
        
        if( b == minusOne )
        {
            seeMinus1 = true;
            continue;
        }
        
        if( b != 1 )
            return false;
    }

    return seeMinus1; 
}


#endif // __nttlHeader_isPrime__