/*==============================================================================
|
|  File Name:
|
|     ppPolynomial.h
|
|  Description:
|
|     Header file for polynomial routines.
|
|  Legal:
|
|     Primpoly Version 8.0 - A Program for Computing Primitive Polynomials.
|     Copyright (C) 1999-2008 by Sean Erik O'Connor.  All Rights Reserved.
|
|     This program is free software; you can redistribute it and/or
|     modify it under the terms of the GNU General Public License
|     as published by the Free Software Foundation;  version 2
|     of the License.
|
|     This program is distributed in the hope that it will be useful,
|     but WITHOUT ANY WARRANTY; without even the implied warranty of
|     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
|     GNU General Public License for more details.
|
|     You should have received a copy of the GNU General Public License
|     along with this program; if not, write to the Free Software
|     Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307,
|     USA.
|
|     The author's address is artifex@seanerikoconnor.freeservers.com
|
==============================================================================*/

// Wrap this header file to prevent duplication if it is included
// accidentally more than once.
#ifndef __POLYNOMIAL_H__
#define __POLYNOMIAL_H__

/*=============================================================================
|
| NAME
|
|     PolynomialError
|     PolynomialRangeError
|
| DESCRIPTION
|
|     Exception classes for classes Polynomial and PolyMod
|     derived from the STL exception class runtime_error.
|
| BUGS
|
+============================================================================*/

class PolynomialError : public runtime_error
{
    public:
        // Throw with an error message.
        PolynomialError( const string & description )
            : runtime_error( description )
        {
        } ;

        // Default throw with no error message.
        PolynomialError()
            : runtime_error( "Polynomial error:  " )
        {
        } ;

} ; // end class PolynomialError

class PolynomialRangeError : public PolynomialError
{
    public:
        // Throw with an error message.
        PolynomialRangeError( const string & description )
            : PolynomialError( description )
        {
        } ;

        // Default throw with no error message.
        PolynomialRangeError()
            : PolynomialError( "Polynomial range error:  " )
        {
        } ;

} ; // end class PolynomialRangeError



/*=============================================================================
|
| NAME
|
|     Polynomial
|
| DESCRIPTION
|
|     Represents the monic polynomial f( x ) of degree n, with
|     coefficients in GF( p ).  Precisely,
|
|                   n         n-1
|         f( x ) = x  +  a   x    + ... a x + a     0 <= a  < p
|                         n-1            1     0          i
|
|     The constant polynomial is of degree 0.
|
|     We support these basic operations:
|
|         Polynomial f ;                Construct f(x) = 0 mod 2.
|         <destructor>
|         Polynomial f( f2 ) ;          Copy, f(x) = f2(x)
|         Polynomial f = f2 ;           Overwrite, f(x) = f2(x)
|         Polynomial f( "x^2+1, 3" ) ;  Polynomial from string.
|         String s = f ;                Poly to string.
|         stream << p                   Read the poly.
|         p >> stream                   Print the poly.
|         f[ i ] = coeff                Set poly coefficient.
|         f.deg()                       Return the degree of f(x).
|         f.modulus()                   Return the modulus p of f(x).
|         int coeff = f[ i ]            Get poly coefficient.
|         f(x) + g(x)                   Add poly mod p.
|         f(x)                          Evaluate f(x) for integer x
|         f.hasLinearFactor()           Check if f(x) has any linear factors.
|         f.isInteger()                 Is f(x) = constant?
|         f.firstTrialPoly()            Set f(x) = x^n - 1
|         f.nextTrialPoly()             Set f(x) = next poly in sequence.
|
|     Exceptions:  throw PolynomialError or one of its subclasses such as 
|     PolynomialRangeError.  Assume we've mapped unexpected() in main() to 
|     throw bad_exception whenever an exception specification is violated.
|
| NOTES
|
|     The member functions and friends are documented in ppPolynomial.cpp
|
| BUGS
|
+============================================================================*/

class Polynomial
{
    public:
        // Default constructor.  
        // Set f(x) = 0 mod 2.
        Polynomial()
            throw( PolynomialError, bad_exception ) ;

        // Destructor.
        virtual ~Polynomial() ;

        // Copy constructor.
        Polynomial( const Polynomial & g )
                       throw( PolynomialError, bad_exception ) ;

        // Assignment.
        virtual Polynomial & operator=( const Polynomial & g )
                                  throw( PolynomialError, bad_exception ) ;
        // TODO operator=( string )
        // Construct from string:
        // Polynomial p( "x^2 + 2 x + 1, 3" ) ;
		// If modulus isn't specified, use the one in specified in the
		// polynomial string.
        Polynomial( string s, uint p = 0 )
                       throw( PolynomialRangeError, bad_exception ) ;
		
        // Operator casting to string type.
        operator string()
                 const
                 throw( PolynomialRangeError, bad_exception ) ;
		// TODO handle exceptions.
		void printPolynomial()
		{ 		
		    try 
			{
		        cout << static_cast<string>( *this ) ; 
			}
			catch (...)
			{
				//do nothing
			}
		}

        // cout << p and cin >> p
        friend ostream & operator<<( ostream &          out,
                                     const Polynomial & p )
                         throw( PolynomialRangeError, bad_exception ) ;

        friend istream & operator>>( istream &          in,
                                     Polynomial &       p )
                      throw( PolynomialRangeError, bad_exception ) ;

        // Bounds checked indexing operator which allows an lvalue:
        //  p[ i ] = coeff ;
        int & operator[]( int i )
                      throw( PolynomialRangeError, bad_exception ) ;

        // Bounds checked indexing operator for read only access:
        // coeff = p[ i ] ;
        const int operator[]( int i ) const
                          throw( PolynomialRangeError, bad_exception ) ;

        // Return the degree n of f(x).
        int deg() const
                  throw() ;

        // Return the modulus p of f(x).
        int modulus() const
                  throw() ;
				  
        // Set the modulus p of f(x).
        void setModulus( const int p )
			throw( PolynomialRangeError, bad_exception ) ;

        // Addition modulo p:  f(x) + g(x) mod p
        friend const Polynomial
               operator+( const Polynomial & f,
                          const Polynomial & g )
                      throw( PolynomialRangeError, bad_exception ) ;

        // Addition.
        Polynomial & operator+=( const Polynomial & g )
                      throw( PolynomialRangeError, bad_exception ) ;
					  
        // Scalar multiple.
		friend const Polynomial
		   operator*( const Polynomial & f, const uint k )
		       throw( bad_exception ) ;
			   
        Polynomial & operator*=( const uint k )
                      throw( bad_exception ) ;

        // Evaluation:  f( x ) mod p
        int operator()( int x )
                   throw( PolynomialRangeError, bad_exception ) ;

        // Does f(x) have any linear factor?
        bool hasLinearFactor()
                   throw( PolynomialRangeError, bad_exception ) ;

        // Is f(x) an integer?
        bool isInteger() const
                   throw( PolynomialRangeError, bad_exception ) ;

        // First trial polynomial.  Set
        //                 n
        //       f( x ) = x  - 1
        void initial_trial_poly( const uint n, const uint p )
                  throw( PolynomialRangeError, bad_exception ) ;

        // Update f( x ) := next polynomial in sequence.
        void next_trial_poly()
                  throw( PolynomialRangeError, bad_exception ) ;
        
    // Private data accessible by member functions only, and
    // derived classes for convenience.
    protected:
        vector<int> f_ ;  //  Polynomial coefficients:  
                          //  f_[0] = const coeff ... f_[n] = nth degree coeff.
                          //  then f_.size() = n+1
        int         n_ ;  //  Degree of the polynomial.
        int         p_ ;  //  Coefficients are in GF( p ).
        ModP        mod ; //  modulo p functionoid.
} ;



/*=============================================================================
|
| NAME
|
|     PolyMod
|
| DESCRIPTION
|
|     Represents the monic polynomial g( x ) of degree m with coefficients in GF( p ),
|
|                   m         m-1
|         g( x ) = x  +  a   x  + ... + a    0 <= a  < p
|                         m-1            0         i
|
|     modulo f( x ) for monic polynomial f( x ) of degree n over GF( p ),
|
|                   n         n-1
|         f( x ) = x  +  a   x  + ... + a    0 <= a  < p
|                         n-1            0         i
|
|     We support these basic operations:
|     
|         PolyMod p() ;             Set g(x)=0 and f(x) = 0 mod 2
|                                   Destructor.   
|         PolyMod p( g, f )         Constructor from polynomials g(x) and f(x)
|         PolyMod p( p2 )           Copy p(x) = p2(x).
|         PolyMod p = p2            Assign p(x) = p2(x).
|         p.timesX() ;              p(x) := x p( x ) (mod f( x ), p)
|                                            2
|         p.square() ;              p(x) := p( x ) (mod f( x ), p)
|         p *= p2                   Do p(x) = p(x) * p2(x) (mod f( x ), p)
|         p1 * p2                   Do p1(x) * p2(x) (mod f( x ), p)
|                                           m 
|         p.power( m )              p(x) = x  (mod f(x), p)
|     
|     Exceptions:  throw PolynomialError or one of its subclasses such as 
|     PolynomialRangeError.  Assume we've mapped unexpected() in main() to 
|     throw bad_exception whenever an exception specification is violated.
|
| NOTES
|
|     The member functions and friends are documented in ppPolynomial.h
|
| BUGS
|
+============================================================================*/

class PolyMod
{
    public:
        // Set g( x ) = 0 modulo f(x) = 0 and p = 2
        PolyMod()
               throw( PolynomialRangeError, bad_exception ) ;

        // Destructor.
        virtual ~PolyMod() ;

        // Construct from polynomials g(x) and f(x).
        PolyMod( const Polynomial & g, const Polynomial & f )
                 throw( PolynomialRangeError, bad_exception ) ;

        // Construct from string g and polynomial f(x).
        PolyMod( const string & g, const Polynomial & f )
                 throw( PolynomialRangeError, bad_exception ) ;
                         
		// Operator casting g(x) to string type.
        operator string()
                 const
                 throw( PolynomialRangeError, bad_exception ) ;
				 
         // cout << p prints g(x) to output stream
        friend ostream & operator<<( ostream &          out,
                                     const PolyMod & p )
                         throw( PolynomialRangeError, bad_exception ) ;

        // Copy g( x ) = g2( x ).
        PolyMod( const PolyMod & g2 )
                  throw( PolynomialRangeError, bad_exception ) ;

        // Assign g( x ) = g2( x ) 
        virtual PolyMod & operator=( const PolyMod & g2 )
                             throw( PolynomialRangeError, bad_exception ) ;

        // Bounds checked indexing operator for read only access:
        // coeff = p[ i ] ;
        const int operator[]( int i ) const
                          throw( PolynomialRangeError, bad_exception ) ;

        // Multiply by x:  g(x) := g(x) x (mod f( x ), p)
        void timesX()
                   throw( PolynomialRangeError, bad_exception ) ;

        // Squaring:             2
        //           g(x) := g(x) (mod f( x ), p)
        void square()
                   throw( PolynomialRangeError, bad_exception ) ;

        // Multiplication:  g(x) := g(x) g2(x) (mod f( x ), p)
        PolyMod & operator*=( const PolyMod & g2 )
                   throw( PolynomialRangeError, bad_exception ) ;

        // Multiplication:  g(x) := s(x) t(x) (mod f( x ), p)
        friend const PolyMod operator*( const PolyMod & s,
                                                const PolyMod & t )
                               throw( PolynomialRangeError, bad_exception ) ;

        // Special exponentiation:  g(x) ^ m (mod f(x), p)
		// for g(x) = x only for now!
        friend const PolyMod power( const PolyMod & g, const BigInt & m )
                  throw( PolynomialRangeError, bad_exception ) ;

        bool isInteger() const ;
		
        //-----------------< Helper functions >-------------------------------
		const Polynomial getf() const ;
		
		const int getModulus() const ;
		
       
    private:
        // Polynomial g(x).
        Polynomial g_ ;

        // Modulus polynomial f(x) and modulus p.
        Polynomial f_ ;

        // Two dimensional precomputed power table.
        //
        //  Precompute the n-1 polynomials
        //
        //       n      2n-2
        //      x  ... x     (mod f(x), p)
        //
        //                          n+i
        //      powerTable_[ i ] = x   (mod f(x), p)
        //
        vector< Polynomial > powerTable_ ;

        ModP        mod ; //  modulo p functionoid.

    // Helper functions.  Note the friend functions are really public due to C++ rules.
    protected:
	    // Offset into powerTable.
	    int inline offset( const int i ) const { return i - f_.deg() ; }
		
        // Power table of the polynomial.
        void constructPowerTable() ;
		
        // Reduce g( x ) mod f( x ) and p
		void modf() throw( PolynomialRangeError, bad_exception ) ;

        // Autoconvolution product.
        friend int autoConvolve( const Polynomial & t, const int k, const int lower, const int upper ) ;

        // Convolution product.
        friend int convolve( const Polynomial & s, const Polynomial & t, 
                             const int k, const int lower, const int upper ) ;

        //               2
        // kth coeff of g (x) for degree n.
        friend int coeffOfSquare( const Polynomial & g, const int k, const int n ) ;

        // Coeff of s(x) t(x) for degree n.
        friend int coeffOfProduct( const Polynomial & s, const Polynomial & t, const int k, const int n ) ;
} ;



/*=============================================================================
|
| NAME
|
|     PolyOrder
|
| DESCRIPTION
|
|     Represents tests on the monic polynomial f( x ) of degree n,
|     with coefficients in GF( p ).
|
|                   n         n-1
|         f( x ) = x  +  a   x  + ... + a    0 <= a  < p
|                         n-1            0         i
|
|     We support these basic operations:
|     
|     
|     Exceptions:  throw PolynomialError or one of its subclasses such as 
|     PolynomialRangeError.  Assume we've mapped unexpected() in main() to 
|     throw bad_exception whenever an exception specification is violated.
|
| NOTES
|
|     The member functions and friends are documented in ppPolynomial.h
|
| BUGS
|
+============================================================================*/


class PolyOrder
{
    public:
        // Do tests on the nth degree polynomial f(x) modulo p.
        PolyOrder( const Polynomial & f )
                  throw( PolynomialRangeError, bad_exception ) ;
         
        void newPolynomial( const Polynomial &f )
                  throw( PolynomialRangeError, bad_exception ) ;

        //             m                                          r
        // Check that x  (mod f(x), p) is not an integer for m = ---
        //                                                        p
        //                                                         i
        // but skip this test if p  | (p-1).
        //                        i
        bool order_m()
                  throw( PolynomialRangeError, bad_exception ) ;

       //           r
	   // Check if x  (mod f(x), p) = a, for integer a.
       // If a is not an integer, return 0.
       uint order_r()
                  throw( PolynomialRangeError, bad_exception ) ;

        //           k                                 n
        // Check if x  = 1 (mod f(x), p) only for k = p - 1
		// Note this is O( p^n ); very expensive.
        bool maximal_order()
                  throw( PolynomialRangeError, bad_exception ) ;
				  
        // Check if the monic polynomial f( x ) has 2 or more distinct factors.
        // Uses x_to_power().
        bool hasMultipleDistinctFactors()
                  throw( PolynomialRangeError, bad_exception ) ;
           

        // --- Stand alone functions, here for neatness.

        // Find a single "random" primitive polynomial.
        friend bool findPrimitivePolynomial( uint p, uint n )
                  throw( PolynomialRangeError, bad_exception ) ;

        // Test if a given polynomial f(x) is primitive.
        bool isPrimitive()
                  throw( PolynomialRangeError, bad_exception ) ;
			  
        // Test function.
	    string printQMatrix() const ;
		
		inline int getNullity() const { return nullity_ ; } ;

    protected:
        // Polynomial f(x) modulo p of degree n which is to be tested.
        Polynomial f_ ;
		uint n_ ;
		uint p_ ;
		ModP mod ;
        
        //           n
        //          p  - 1 
        //   r =   --------
        //          p - 1
        BigInt r_ ;
 
        // Constant factor a (see notes).
        uint a_ ;
        
        // Factorization of r.
        Factor<BigInt> factor_ ;

        // Two dimensional Q matrix for irreducibility testing.
        vector< vector<int> > Q_ ;
		
		int nullity_ ;

        typedef struct
        {
            bool freeOfLinearFactors ;
            bool constantCoefficientIsPrimitiveRoot ;
            bool passesConstantCoefficientTest ;
            bool irreducibleToAPower ;
            bool orderM ;
            bool orderR ;

        } PrimitivityStatus ;

        PrimitivityStatus primitivityStatus ;
                
    // Helper functions. 
    protected:
        void generate_Q_matrix()
                  throw( PolynomialRangeError, bad_exception ) ;

        void findNullity()
                  throw( PolynomialRangeError, bad_exception ) ;

} ;

#endif // __POLYNOMIAL_H__ --- End of wrapper for header file.