/*==============================================================================
| 
|  File Name:     
|
|     Primpoly.cpp
|
|  Description:   
|
|     Compute primitive polynomials of degree n modulo p.
| 
|  Functions:
|
|     main      Main driving routine.
|
|  Legal:
|
|
|     Primpoly Version 7.7 - 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. 
|
==============================================================================*/

/*------------------------------------------------------------------------------
|                                Include Files                                 |
------------------------------------------------------------------------------*/

#include <cstdlib>      // abort()
#include <iostream>     // Basic stream I/O.
#include <new>          // set_new_handler()
#include <cmath>        // Basic math functions e.g. sqrt()
#include <limits>       // Numeric limits.
#include <complex>      // Complex data type and operations.
#include <fstream>      // File stream I/O.
#include <sstream>      // String stream I/O.
#include <vector>       // STL vector class.
#include <string>       // STL string class.
#include <algorithm>    // Iterators.
#include <stdexcept>    // Exceptions.
#include <cassert>      // assert()

#ifdef _MSC_VER
#include <new.h> // new_handler()
#endif

using namespace std ;   // So we don't need to use the std:: prefix everywhere.

#include "ctype.h"      // C string functions.



/*------------------------------------------------------------------------------
|                                PP Include Files                              |
------------------------------------------------------------------------------*/

#include "Primpoly.h"		  // Global functions.
#include "ppArith.h"		  // Basic arithmetic functions.
#include "ppBigInt.h"       // Arbitrary precision integer arithmetic.
#include "ppFactor.h"       // Prime factorization and Euler Phi.
#include "ppParser.h"	       // Parsing of polynomials and I/O services.
#include "ppPolynomial.h"	  // Polynomial operations and mod polynomial operations.
#include "ppUnitTest.h"     // Complete unit test.


/*------------------------------------------------------------------------------
|                      Remap new and unexpected handlers                       |
------------------------------------------------------------------------------*/

// Patch Microsoft VC++ so new() throws bad_alloc.
#ifdef _MSC_VER
int MyNewHandler( size_t size )
{
    cout << "Throwing bad_alloc() exception from the new handler" << endl ;
    throw bad_alloc() ;
    return 0 ; // Allocation failed.
}
#endif // _MSC_VER

// Violating an exception specification (throwing a type of exception 
// from within a function which does not match its exception specification)
// normally causes a call to unexpected() which calls terminate() which 
// in turn calls abort().  We don't want to abruptly stop like this, so
// we remap unexpected() so that it throws the exception bad_exception.
// The drawback is that now all functions need to include bad_exception in
// their exception specifiations list.
void MyUnexpectedHandler()
{
    cout << "Throwing runtime_error() exception from the unexpected() handler" << endl ;
    throw bad_exception() ;
    return ;
}




enum ReturnStatus
{
    Success       = 0,
    AskForHelp    = 1,
    PNotPrime     = 2,
    InternalError = 3
   
} ;

/*==============================================================================
|                                    main                                      |
================================================================================

DESCRIPTION

     Program for finding a primitive polynomial of degree n modulo p for use in
     generating PN sequences and finite fields for error control coding.

INPUT 

     Run the program by typing

         $ Primpoly p n

OUTPUT

     You will get an nth degree primitive polynomial modulo p.

EXAMPLE CALLING SEQUENCE

    Let's find a primitive polynomial of degree 18, modulo the prime 11.
    After a few seconds, even on a slow PC, we get:

        $ primpoly -s 5 20

        Primpoly Version 7.7 - A Program for Computing Primitive Polynomials.
        Copyright (C) 1999-2008 by Sean Erik O'Connor.  All Rights Reserved.

        Primpoly comes with ABSOLUTELY NO WARRANTY; for details see the
        GNU General Public License.  This is free software, and you are welcome
        to redistribute it under certain conditions; see the GNU General Public License
        for details.


        Factoring r = 23841857910156 into
            2^2 3 11 13 41 71 521 9161

        Total number of primitive polynomials = 1280348160000.  Begin testing...

        abcabcaaaaaaaaabaaaababcdef



        Primitive polynomial modulo 5 of degree 20

         x ^ 20   +    x ^  2   +    2 x   +    3


        +--------- Statistics ----------------------------
        |
        | Total num. degree 20 polynomials mod  5 :    95367431640625
        |
        | Actually tested :                             39
        | a. Const. coeff. was primitive root :         16
        | b. Free of linear factors :                    5
        | c. Irreducible or irred. to power :            3
        | d. Had order r (x^r = integer) :               1
        | e. Passed const. coeff. test :                 1
        | f. Had order m (x^m != integer) :              1
        |
        +-------------------------------------------------


METHOD

     Described in detail in my web page at
     http://seanerikoconnor.freeservers.com/Mathematics/AbstractAlgebra/PrimitivePolynomials/overview.html

BUGS

--------------------------------------------------------------------------------
|                                Function Call                                 |
-----------------------------------------------------------------------------*/

int main( int argc, char * argv[] )
{

// Violating an exception specification causes a call to unexpected()
// which calls terminate() which calls abort().
// Intercept calls to unexpected() and convert to a throw.
set_unexpected( MyUnexpectedHandler ) ;

// Patch Microsoft VC++ so new() throws bad_alloc.
#ifdef _MSC_VER
    _set_new_handler( MyNewHandler ) ;
#endif

try
{
    //  Show the legal notice first.
    cout << legalNotice ;  

    bool unitTestStatus = unitTest() ;
    if (!unitTestStatus) 
        cout << "Unit test failed!  Look at the unitTest.log file" << endl ;
    else
        cout << "Self-check passes..." << endl ;

    Parser parser ;

    // Read the parameters p and n from the command line.
    // Throw a parsing exception if there is a problem.
    parser.parseCommandLine( argc, argv ) ;

    // Did user ask for help?
    if (parser.printHelp == true)
    {
        cout << help ;
        return AskForHelp ;
    }

    //  Check to see if p is a prime.
    if (!is_almost_surely_prime( static_cast<uint>( parser.p )))
        throw ParserError( "ERROR:  p must be a prime number.\n\n" ) ;

    findPrimitivePolynomial( parser.p, parser.n ) ;

return 0 ;

#if 0
//  Confirm f(x) is primitive using a different, but extremely slow test for 
//  primitivity.
if (parser.selfCheck)
{
    printf( "\nConfirming polynomial is primitive with an independent check.\n"
            "Warning:  You may wait an impossibly long time!\n\n" ) ;

    if (f.maximal_order())
        printf( "    -Polynomial is confirmed to be primitive.\n\n" ) ;
    else
    {
        cerr << "Internal error:  \n"
                "Primitive polynomial confirmation test failed.\n"
                "Please write to the author at artifex@seanerikoconnor.freeservers.com\n\n" ;
        return InternalError ;
    }
}
#endif

}
// Catch all exceptions and report what happened to the user.
catch ( bad_alloc & e )
{
    cerr << "Error allocating memory:  " << e.what() << endl ;
    cerr << "Try again with smaller p and n" << endl ;
    cerr << "or try on a computer with more RAM or virtual memory." << endl ;
    system( "PAUSE" ) ;
    return InternalError ;
}
catch ( bad_exception & e )
{
    cerr << "Bad exception violation:  " << e.what() << endl ;
    //    cerr << "p = " << parser.p << "n = " << parser.n << endl ;
    cerr << "Please write to the author at artifex@seanerikoconnor.freeservers.com\n\n" ;
    system( "PAUSE" ) ;
    return InternalError ;
}
catch ( BigIntMathError & e )
{
    cerr << "Error in multiple precision arithmetic:  " << e.what() << endl ;
    //    cerr << "p = " << parser.p << "n = " << parser.n << endl ;
    cerr << "Please write to the author at artifex@seanerikoconnor.freeservers.com\n\n" ;
    system( "PAUSE" ) ;
    return InternalError ;
}
catch ( PolynomialError & e )
{
    cerr << "Error in polynomial arithmetic:  " << e.what() << endl ;
    //    cerr << "p = " << parser.p << "n = " << parser.n << endl ;
    cerr << "Please write to the author at artifex@seanerikoconnor.freeservers.com\n\n" ;
    system( "PAUSE" ) ;
    return InternalError ;
}
catch( ParserError & e )
{
    cerr << "Parsing error: " << e.what() << endl ;
    //    cerr << "p = " << parser.p << "n = " << parser.n << endl ;
    cerr << "Enter the correct inputs.\n\n" ;
    system( "PAUSE" ) ;
    return InternalError ;
}
//  Standard library exceptions.
catch( exception & e )
{
    cerr << "Standard library error: " << e.what() << endl ;
    //    cerr << "p = " << parser.p << "n = " << parser.n << endl ;
    cerr << "Enter the correct inputs.\n\n" ;
    system( "PAUSE" ) ;
    return InternalError ;
}
// Catch all uncaught exceptions, which would otherwise call terminate()
// which would call abort() 
// Can't catch those thrown by initializing or
// destructing global variables.
// Also terminate() will be called if exception mechanism finds a corrupt
// stack or catches a destructor throwing an exception.
catch( ... )
{
    cerr << "Unexpected exception: " << endl ;
    //    cerr << "p = " << parser.p << "n = " << parser.n << endl ;
    cerr << "Please write to the author at artifex@seanerikoconnor.freeservers.com\n\n" ;
    system( "PAUSE" ) ;
    return InternalError ;
}
    //   message if there are an incorrect number of inputs on the command line,
    //   or if p and n are out of bounds.

system( "PAUSE" ) ;

return Success ;

} /* ========================== end of function main ======================== */