/*==============================================================================
|
|  NAME
|
|     ppFactor.cpp
|
|  Description:
|
|     Classes for factoring integers.
|
|  Legal:
|
|     Primpoly Version 9.1 - 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 <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()

using namespace std ;

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

#include "Primpoly.h"		// Global functions.
#include "ppArith.h"		// Basic arithmetic functions.
#include "ppBigInt.h"       // Arbitrary precision integer arithmetic.
#include "ppStatistics.h"   // Statistics collection for factoring and poly finding.
#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.

/*------------------------------------------------------------------------------
|                                Local Functions                               |
------------------------------------------------------------------------------*/

// Generic function.
template <typename IntType>
bool Factor<IntType>::factorTable() 
{
    return false ;
}


// Specialization for unsigned integer.
template<>
bool Factor<uint>::factorTable()
{
    if (n_ == 0u)
    {
	    PrimeFactor<uint> f( 0u, 1u ) ;
        factor_.push_back( f ) ;
        
        numFactors_ = 1u ;
        return true ;
    }
    else if (n_ == 1u)
    {
	    PrimeFactor<uint> f( 1u, 1u ) ;
        factor_.push_back( f ) ;
        
        numFactors_ = 1u ;
        return true ;
    }
    
    return false ;
}



// Specialization for BigInt.
template<>
bool Factor<BigInt>::factorTable() 
{
    if (n_ == static_cast<BigInt>(0u))
    {
	    PrimeFactor<BigInt> f( 0u, 1u ) ;
        factor_.push_back( f ) ;
        
        numFactors_ = 1u ;
        return true ;
    }
    else if (n_ == static_cast<BigInt>(1u))
    {
	    PrimeFactor<BigInt> f( 1u, 1u ) ;
        factor_.push_back( f ) ;
        
        numFactors_ = 1u ;
        return true ;
    }
    else if (n_ == static_cast<BigInt>("4611686018427387903"))  // (2^62-1) / (2-1)
    {
        PrimeFactor<BigInt>f1(static_cast<BigInt>("3"), 1u) ;
        factor_.push_back(f1) ;
        n_ /= static_cast<BigInt>("3") ;

        PrimeFactor<BigInt>f2(static_cast<BigInt>("715827883"), 1u) ;
        factor_.push_back(f2) ;
        n_ /= static_cast<BigInt>("715827883") ;

        PrimeFactor<BigInt>f3(static_cast<BigInt>("2147483647"), 1u) ;
        factor_.push_back(f3) ;
        n_ /= static_cast<BigInt>("2147483647") ;

        numFactors_ = 3u;

        return true;
    }
    else if (n_ == static_cast<BigInt>("9223372036854775807"))  // 2^63/ (2-1)
    {
        PrimeFactor<BigInt>f1(static_cast<BigInt>("7"), 2u) ;
        factor_.push_back(f1) ;
        n_ /= static_cast<BigInt>("7") ;
        n_ /= static_cast<BigInt>("7") ;

        PrimeFactor<BigInt>f2(static_cast<BigInt>("73"), 1u) ;
        factor_.push_back(f2) ;
        n_ /= static_cast<BigInt>("73") ;

        PrimeFactor<BigInt>f3(static_cast<BigInt>("127"), 1u) ;
        factor_.push_back(f3) ;
        n_ /= static_cast<BigInt>("127") ;

        PrimeFactor<BigInt>f4(static_cast<BigInt>("337"), 1u) ;
        factor_.push_back(f4) ;
        n_ /= static_cast<BigInt>("337") ;

        PrimeFactor<BigInt>f5(static_cast<BigInt>("92737"), 1u) ;
        factor_.push_back(f5) ;
        n_ /= static_cast<BigInt>("92737") ;

        PrimeFactor<BigInt>f6(static_cast<BigInt>("649657"), 1u) ;
        factor_.push_back(f6) ;
        n_ /= static_cast<BigInt>("649657") ;

        numFactors_ = 6u;

        return true;
    }
    else if (n_ == static_cast<BigInt>("18446744073709551615"))  // 2^64/ (2-1)
    {
        PrimeFactor<BigInt>f1(static_cast<BigInt>("3"), 1u) ;
        factor_.push_back(f1) ;
        n_ /= static_cast<BigInt>("3") ;

        PrimeFactor<BigInt>f2(static_cast<BigInt>("5"), 1u) ;
        factor_.push_back(f2) ;
        n_ /= static_cast<BigInt>("5") ;

        PrimeFactor<BigInt>f3(static_cast<BigInt>("17"), 1u) ;
        factor_.push_back(f3) ;
        n_ /= static_cast<BigInt>("17") ;

        PrimeFactor<BigInt>f4(static_cast<BigInt>("257"), 1u) ;
        factor_.push_back(f4) ;
        n_ /= static_cast<BigInt>("257") ;

        PrimeFactor<BigInt>f5(static_cast<BigInt>("641"), 1u) ;
        factor_.push_back(f5) ;
        n_ /= static_cast<BigInt>("641") ;

        PrimeFactor<BigInt>f6(static_cast<BigInt>("65537"), 1u) ;
        factor_.push_back(f6) ;
        n_ /= static_cast<BigInt>("65537") ;

        PrimeFactor<BigInt>f7(static_cast<BigInt>("6700417"), 1u) ;
        factor_.push_back(f7) ;
        n_ /= static_cast<BigInt>("6700417") ;

        numFactors_ = 7u;

        return true;
    }
    else if (n_ == static_cast<BigInt>("147573952589676412927"))  // 2^67/ (2-1)
    {
        PrimeFactor<BigInt>f1(static_cast<BigInt>("193707721"), 1u) ;
        factor_.push_back(f1) ;
        n_ /= static_cast<BigInt>("193707721") ;

        PrimeFactor<BigInt>f2(static_cast<BigInt>("761838257287"), 1u) ;
        factor_.push_back(f2) ;
        n_ /= static_cast<BigInt>("761838257287") ;

        numFactors_ = 2u;

        return true;
    }
    else if (n_ == static_cast<BigInt>("590295810358705651711"))  // 2^69/ (2-1)
    {
        PrimeFactor<BigInt>f1(static_cast<BigInt>("7"), 1u) ;
        factor_.push_back(f1) ;
        n_ /= static_cast<BigInt>("7") ;

        PrimeFactor<BigInt>f2(static_cast<BigInt>("47"), 1u) ;
        factor_.push_back(f2) ;
        n_ /= static_cast<BigInt>("47") ;

        PrimeFactor<BigInt>f3(static_cast<BigInt>("178481"), 1u) ;
        factor_.push_back(f3) ;
        n_ /= static_cast<BigInt>("178481") ;

        PrimeFactor<BigInt>f4(static_cast<BigInt>("10052678938039"), 1u) ;
        factor_.push_back(f4) ;
        n_ /= static_cast<BigInt>("10052678938039") ;

        numFactors_ = 4u;

        return true;
    }
    else if (n_ == static_cast<BigInt>("2361183241434822606847"))  // 2^71/ (2-1)
    {
        PrimeFactor<BigInt>f1(static_cast<BigInt>("228479"), 1u) ;
        factor_.push_back(f1) ;
        n_ /= static_cast<BigInt>("228479") ;

        PrimeFactor<BigInt>f2(static_cast<BigInt>("48544121"), 1u) ;
        factor_.push_back(f2) ;
        n_ /= static_cast<BigInt>("48544121") ;

        PrimeFactor<BigInt>f3(static_cast<BigInt>("212885833"), 1u) ;
        factor_.push_back(f3) ;
        n_ /= static_cast<BigInt>("212885833") ;

        numFactors_ = 3u;

        return true;
    }
    else if (n_ == static_cast<BigInt>("9444732965739290427391"))  // 2^73/ (2-1)
    {
        PrimeFactor<BigInt>f1(static_cast<BigInt>("439"), 1u) ;
        factor_.push_back(f1) ;
        n_ /= static_cast<BigInt>("439") ;

        PrimeFactor<BigInt>f2(static_cast<BigInt>("2298041"), 1u) ;
        factor_.push_back(f2) ;
        n_ /= static_cast<BigInt>("2298041") ;

        PrimeFactor<BigInt>f3(static_cast<BigInt>("9361973132609"), 1u) ;
        factor_.push_back(f3) ;
        n_ /= static_cast<BigInt>("9361973132609") ;

        numFactors_ = 3u;

        return true;
    }
    else if (n_ == static_cast<BigInt>("18889465931478580854783"))  // 2^74/ (2-1)
    {
        PrimeFactor<BigInt>f1(static_cast<BigInt>("3"), 1u) ;
        factor_.push_back(f1) ;
        n_ /= static_cast<BigInt>("3") ;

        PrimeFactor<BigInt>f2(static_cast<BigInt>("223"), 1u) ;
        factor_.push_back(f2) ;
        n_ /= static_cast<BigInt>("223") ;

        PrimeFactor<BigInt>f3(static_cast<BigInt>("1777"), 1u) ;
        factor_.push_back(f3) ;
        n_ /= static_cast<BigInt>("1777") ;

        PrimeFactor<BigInt>f4(static_cast<BigInt>("25781083"), 1u) ;
        factor_.push_back(f4) ;
        n_ /= static_cast<BigInt>("25781083") ;

        PrimeFactor<BigInt>f5(static_cast<BigInt>("616318177"), 1u) ;
        factor_.push_back(f5) ;
        n_ /= static_cast<BigInt>("616318177") ;

        numFactors_ = 5u;

        return true;
    }
    else if (n_ == static_cast<BigInt>("604462909807314587353087"))  // 2^79/ (2-1)
    {
        PrimeFactor<BigInt>f1(static_cast<BigInt>("2687"), 1u) ;
        factor_.push_back(f1) ;
        n_ /= static_cast<BigInt>("2687") ;

        PrimeFactor<BigInt>f2(static_cast<BigInt>("202029703"), 1u) ;
        factor_.push_back(f2) ;
        n_ /= static_cast<BigInt>("202029703") ;

        PrimeFactor<BigInt>f3(static_cast<BigInt>("1113491139767"), 1u) ;
        factor_.push_back(f3) ;
        n_ /= static_cast<BigInt>("1113491139767") ;

        numFactors_ = 3u;

        return true;
    }
    else if (n_ == static_cast<BigInt>("4835703278458516698824703"))  // 2^82/ (2-1)
    {
        PrimeFactor<BigInt>f1(static_cast<BigInt>("3"), 1u) ;
        factor_.push_back(f1) ;
        n_ /= static_cast<BigInt>("3") ;

        PrimeFactor<BigInt>f2(static_cast<BigInt>("83"), 1u) ;
        factor_.push_back(f2) ;
        n_ /= static_cast<BigInt>("83") ;

        PrimeFactor<BigInt>f3(static_cast<BigInt>("13367"), 1u) ;
        factor_.push_back(f3) ;
        n_ /= static_cast<BigInt>("13367") ;

        PrimeFactor<BigInt>f4(static_cast<BigInt>("164511353"), 1u) ;
        factor_.push_back(f4) ;
        n_ /= static_cast<BigInt>("164511353") ;

        PrimeFactor<BigInt>f5(static_cast<BigInt>("8831418697"), 1u) ;
        factor_.push_back(f5) ;
        n_ /= static_cast<BigInt>("8831418697") ;

        numFactors_ = 5u;

        return true;
    }
    else if (n_ == static_cast<BigInt>("2475880078570760549798248447"))  // 2^91/ (2-1)
    {
        PrimeFactor<BigInt>f1(static_cast<BigInt>("127"), 1u) ;
        factor_.push_back(f1) ;
        n_ /= static_cast<BigInt>("127") ;

        PrimeFactor<BigInt>f2(static_cast<BigInt>("911"), 1u) ;
        factor_.push_back(f2) ;
        n_ /= static_cast<BigInt>("911") ;

        PrimeFactor<BigInt>f3(static_cast<BigInt>("8191"), 1u) ;
        factor_.push_back(f3) ;
        n_ /= static_cast<BigInt>("8191") ;

        PrimeFactor<BigInt>f4(static_cast<BigInt>("112901153"), 1u) ;
        factor_.push_back(f4) ;
        n_ /= static_cast<BigInt>("112901153") ;

        PrimeFactor<BigInt>f5(static_cast<BigInt>("23140471537"), 1u) ;
        factor_.push_back(f5) ;
        n_ /= static_cast<BigInt>("23140471537") ;

        numFactors_ = 5u;

        return true;
    }
    else if (n_ == static_cast<BigInt>("9903520314283042199192993791"))  // 2^93/ (2-1)
    {
        PrimeFactor<BigInt>f1(static_cast<BigInt>("7"), 1u) ;
        factor_.push_back(f1) ;
        n_ /= static_cast<BigInt>("7") ;

        PrimeFactor<BigInt>f2(static_cast<BigInt>("2147483647"), 1u) ;
        factor_.push_back(f2) ;
        n_ /= static_cast<BigInt>("2147483647") ;

        PrimeFactor<BigInt>f3(static_cast<BigInt>("658812288653553079"), 1u) ;
        factor_.push_back(f3) ;
        n_ /= static_cast<BigInt>("658812288653553079") ;

        numFactors_ = 3u;

        return true;
    }
    else if (n_ == static_cast<BigInt>("19807040628566084398385987583"))  // 2^94/ (2-1)
    {
        PrimeFactor<BigInt>f1(static_cast<BigInt>("3"), 1u) ;
        factor_.push_back(f1) ;
        n_ /= static_cast<BigInt>("3") ;

        PrimeFactor<BigInt>f2(static_cast<BigInt>("283"), 1u) ;
        factor_.push_back(f2) ;
        n_ /= static_cast<BigInt>("283") ;

        PrimeFactor<BigInt>f3(static_cast<BigInt>("2351"), 1u) ;
        factor_.push_back(f3) ;
        n_ /= static_cast<BigInt>("2351") ;

        PrimeFactor<BigInt>f4(static_cast<BigInt>("4513"), 1u) ;
        factor_.push_back(f4) ;
        n_ /= static_cast<BigInt>("4513") ;

        PrimeFactor<BigInt>f5(static_cast<BigInt>("13264529"), 1u) ;
        factor_.push_back(f5) ;
        n_ /= static_cast<BigInt>("13264529") ;

        PrimeFactor<BigInt>f6(static_cast<BigInt>("165768537521"), 1u) ;
        factor_.push_back(f6) ;
        n_ /= static_cast<BigInt>("165768537521") ;

        numFactors_ = 6u;

        return true;
    }
    else if (n_ == static_cast<BigInt>("39614081257132168796771975167"))  // 2^95/ (2-1)
    {
        PrimeFactor<BigInt>f1(static_cast<BigInt>("31"), 1u) ;
        factor_.push_back(f1) ;
        n_ /= static_cast<BigInt>("31") ;

        PrimeFactor<BigInt>f2(static_cast<BigInt>("191"), 1u) ;
        factor_.push_back(f2) ;
        n_ /= static_cast<BigInt>("191") ;

        PrimeFactor<BigInt>f3(static_cast<BigInt>("524287"), 1u) ;
        factor_.push_back(f3) ;
        n_ /= static_cast<BigInt>("524287") ;

        PrimeFactor<BigInt>f4(static_cast<BigInt>("420778751"), 1u) ;
        factor_.push_back(f4) ;
        n_ /= static_cast<BigInt>("420778751") ;

        PrimeFactor<BigInt>f5(static_cast<BigInt>("30327152671"), 1u) ;
        factor_.push_back(f5) ;
        n_ /= static_cast<BigInt>("30327152671") ;

        numFactors_ = 5u;

        return true;
    }
    else if (n_ == static_cast<BigInt>("316912650057057350374175801343"))  // 2^98/ (2-1)
    {
        PrimeFactor<BigInt>f1(static_cast<BigInt>("3"), 1u) ;
        factor_.push_back(f1) ;
        n_ /= static_cast<BigInt>("3") ;

        PrimeFactor<BigInt>f2(static_cast<BigInt>("43"), 1u) ;
        factor_.push_back(f2) ;
        n_ /= static_cast<BigInt>("43") ;

        PrimeFactor<BigInt>f3(static_cast<BigInt>("127"), 1u) ;
        factor_.push_back(f3) ;
        n_ /= static_cast<BigInt>("127") ;

        PrimeFactor<BigInt>f4(static_cast<BigInt>("4363953127297"), 1u) ;
        factor_.push_back(f4) ;
        n_ /= static_cast<BigInt>("4363953127297") ;

        PrimeFactor<BigInt>f5(static_cast<BigInt>("4432676798593"), 1u) ;
        factor_.push_back(f5) ;
        n_ /= static_cast<BigInt>("4432676798593") ;

        numFactors_ = 5u;

        return true;
    }
    else if (n_ == static_cast<BigInt>("2535301200456458802993406410751"))  // 2^101/ (2-1)
    {
        PrimeFactor<BigInt>f1(static_cast<BigInt>("7432339208719"), 1u) ;
        factor_.push_back(f1) ;
        n_ /= static_cast<BigInt>("7432339208719") ;

        PrimeFactor<BigInt>f2(static_cast<BigInt>("341117531003194129"), 1u) ;
        factor_.push_back(f2) ;
        n_ /= static_cast<BigInt>("341117531003194129") ;

        numFactors_ = 2u;

        return true;
    }
    else if (n_ == static_cast<BigInt>("10141204801825835211973625643007"))  // 2^103/ (2-1)
    {
        PrimeFactor<BigInt>f1(static_cast<BigInt>("2550183799"), 1u) ;
        factor_.push_back(f1) ;
        n_ /= static_cast<BigInt>("2550183799") ;

        PrimeFactor<BigInt>f2(static_cast<BigInt>("3976656429941438590393"), 1u) ;
        factor_.push_back(f2) ;
        n_ /= static_cast<BigInt>("3976656429941438590393") ;

        numFactors_ = 2u;

        return true;
    }
    else if (n_ == static_cast<BigInt>("649037107316853453566312041152511"))  // 2^109/ (2-1)
    {
        PrimeFactor<BigInt>f1(static_cast<BigInt>("745988807"), 1u) ;
        factor_.push_back(f1) ;
        n_ /= static_cast<BigInt>("745988807") ;

        PrimeFactor<BigInt>f2(static_cast<BigInt>("870035986098720987332873"), 1u) ;
        factor_.push_back(f2) ;
        n_ /= static_cast<BigInt>("870035986098720987332873") ;

        numFactors_ = 2u;

        return true;
    }
    else if (n_ == static_cast<BigInt>("2596148429267413814265248164610047"))  // 2^111/ (2-1)
    {
        PrimeFactor<BigInt>f1(static_cast<BigInt>("7"), 1u) ;
        factor_.push_back(f1) ;
        n_ /= static_cast<BigInt>("7") ;

        PrimeFactor<BigInt>f2(static_cast<BigInt>("223"), 1u) ;
        factor_.push_back(f2) ;
        n_ /= static_cast<BigInt>("223") ;

        PrimeFactor<BigInt>f3(static_cast<BigInt>("321679"), 1u) ;
        factor_.push_back(f3) ;
        n_ /= static_cast<BigInt>("321679") ;

        PrimeFactor<BigInt>f4(static_cast<BigInt>("26295457"), 1u) ;
        factor_.push_back(f4) ;
        n_ /= static_cast<BigInt>("26295457") ;

        PrimeFactor<BigInt>f5(static_cast<BigInt>("319020217"), 1u) ;
        factor_.push_back(f5) ;
        n_ /= static_cast<BigInt>("319020217") ;

        PrimeFactor<BigInt>f6(static_cast<BigInt>("616318177"), 1u) ;
        factor_.push_back(f6) ;
        n_ /= static_cast<BigInt>("616318177") ;

        numFactors_ = 6u;

        return true;
    }
    else if (n_ == static_cast<BigInt>("332306998946228968225951765070086143"))  // 2^118/ (2-1)
    {
        PrimeFactor<BigInt>f1(static_cast<BigInt>("3"), 1u) ;
        factor_.push_back(f1) ;
        n_ /= static_cast<BigInt>("3") ;

        PrimeFactor<BigInt>f2(static_cast<BigInt>("2833"), 1u) ;
        factor_.push_back(f2) ;
        n_ /= static_cast<BigInt>("2833") ;

        PrimeFactor<BigInt>f3(static_cast<BigInt>("37171"), 1u) ;
        factor_.push_back(f3) ;
        n_ /= static_cast<BigInt>("37171") ;

        PrimeFactor<BigInt>f4(static_cast<BigInt>("179951"), 1u) ;
        factor_.push_back(f4) ;
        n_ /= static_cast<BigInt>("179951") ;

        PrimeFactor<BigInt>f5(static_cast<BigInt>("1824726041"), 1u) ;
        factor_.push_back(f5) ;
        n_ /= static_cast<BigInt>("1824726041") ;

        PrimeFactor<BigInt>f6(static_cast<BigInt>("3203431780337"), 1u) ;
        factor_.push_back(f6) ;
        n_ /= static_cast<BigInt>("3203431780337") ;

        numFactors_ = 6u;

        return true;
    }
    else if (n_ == static_cast<BigInt>("664613997892457936451903530140172287"))  // 2^119/ (2-1)
    {
        PrimeFactor<BigInt>f1(static_cast<BigInt>("127"), 1u) ;
        factor_.push_back(f1) ;
        n_ /= static_cast<BigInt>("127") ;

        PrimeFactor<BigInt>f2(static_cast<BigInt>("239"), 1u) ;
        factor_.push_back(f2) ;
        n_ /= static_cast<BigInt>("239") ;

        PrimeFactor<BigInt>f3(static_cast<BigInt>("20231"), 1u) ;
        factor_.push_back(f3) ;
        n_ /= static_cast<BigInt>("20231") ;

        PrimeFactor<BigInt>f4(static_cast<BigInt>("131071"), 1u) ;
        factor_.push_back(f4) ;
        n_ /= static_cast<BigInt>("131071") ;

        PrimeFactor<BigInt>f5(static_cast<BigInt>("62983048367"), 1u) ;
        factor_.push_back(f5) ;
        n_ /= static_cast<BigInt>("62983048367") ;

        PrimeFactor<BigInt>f6(static_cast<BigInt>("131105292137"), 1u) ;
        factor_.push_back(f6) ;
        n_ /= static_cast<BigInt>("131105292137") ;

        numFactors_ = 6u;

        return true;
    }
    else if (n_ == static_cast<BigInt>("5316911983139663491615228241121378303"))  // 2^122/ (2-1)
    {
        PrimeFactor<BigInt>f1(static_cast<BigInt>("3"), 1u) ;
        factor_.push_back(f1) ;
        n_ /= static_cast<BigInt>("3") ;

        PrimeFactor<BigInt>f2(static_cast<BigInt>("768614336404564651"), 1u) ;
        factor_.push_back(f2) ;
        n_ /= static_cast<BigInt>("768614336404564651") ;

        PrimeFactor<BigInt>f3(static_cast<BigInt>("2305843009213693951"), 1u) ;
        factor_.push_back(f3) ;
        n_ /= static_cast<BigInt>("2305843009213693951") ;

        numFactors_ = 3u;

        return true;
    }
    else if (n_ == static_cast<BigInt>("42535295865117307932921825928971026431"))  // 2^125/ (2-1)
    {
        PrimeFactor<BigInt>f1(static_cast<BigInt>("31"), 1u) ;
        factor_.push_back(f1) ;
        n_ /= static_cast<BigInt>("31") ;

        PrimeFactor<BigInt>f2(static_cast<BigInt>("601"), 1u) ;
        factor_.push_back(f2) ;
        n_ /= static_cast<BigInt>("601") ;

        PrimeFactor<BigInt>f3(static_cast<BigInt>("1801"), 1u) ;
        factor_.push_back(f3) ;
        n_ /= static_cast<BigInt>("1801") ;

        PrimeFactor<BigInt>f4(static_cast<BigInt>("269089806001"), 1u) ;
        factor_.push_back(f4) ;
        n_ /= static_cast<BigInt>("269089806001") ;

        PrimeFactor<BigInt>f5(static_cast<BigInt>("4710883168879506001"), 1u) ;
        factor_.push_back(f5) ;
        n_ /= static_cast<BigInt>("4710883168879506001") ;

        numFactors_ = 5u;

        return true;
    }
    else if (n_ == static_cast<BigInt>("21778071482940061661655974875633165533183"))  // 2^134/ (2-1)
    {
        PrimeFactor<BigInt>f1(static_cast<BigInt>("3"), 1u) ;
        factor_.push_back(f1) ;
        n_ /= static_cast<BigInt>("3") ;

        PrimeFactor<BigInt>f2(static_cast<BigInt>("7327657"), 1u) ;
        factor_.push_back(f2) ;
        n_ /= static_cast<BigInt>("7327657") ;

        PrimeFactor<BigInt>f3(static_cast<BigInt>("193707721"), 1u) ;
        factor_.push_back(f3) ;
        n_ /= static_cast<BigInt>("193707721") ;

        PrimeFactor<BigInt>f4(static_cast<BigInt>("761838257287"), 1u) ;
        factor_.push_back(f4) ;
        n_ /= static_cast<BigInt>("761838257287") ;

        PrimeFactor<BigInt>f5(static_cast<BigInt>("6713103182899"), 1u) ;
        factor_.push_back(f5) ;
        n_ /= static_cast<BigInt>("6713103182899") ;

        numFactors_ = 5u;

        return true;
    }
    else if (n_ == static_cast<BigInt>("174224571863520493293247799005065324265471"))  // 2^137/ (2-1)
    {
        PrimeFactor<BigInt>f1(static_cast<BigInt>("32032215596496435569"), 1u) ;
        factor_.push_back(f1) ;
        n_ /= static_cast<BigInt>("32032215596496435569") ;

        PrimeFactor<BigInt>f2(static_cast<BigInt>("5439042183600204290159"), 1u) ;
        factor_.push_back(f2) ;
        n_ /= static_cast<BigInt>("5439042183600204290159") ;

        numFactors_ = 2u;

        return true;
    }
    else if (n_ == static_cast<BigInt>("348449143727040986586495598010130648530943"))  // 2^138/ (2-1)
    {
        PrimeFactor<BigInt>f1(static_cast<BigInt>("3"), 2u) ;
        factor_.push_back(f1) ;
        n_ /= static_cast<BigInt>("3") ;

        PrimeFactor<BigInt>f2(static_cast<BigInt>("7"), 1u) ;
        factor_.push_back(f2) ;
        n_ /= static_cast<BigInt>("7") ;

        PrimeFactor<BigInt>f3(static_cast<BigInt>("47"), 1u) ;
        factor_.push_back(f3) ;
        n_ /= static_cast<BigInt>("47") ;

        PrimeFactor<BigInt>f4(static_cast<BigInt>("139"), 1u) ;
        factor_.push_back(f4) ;
        n_ /= static_cast<BigInt>("139") ;

        PrimeFactor<BigInt>f5(static_cast<BigInt>("178481"), 1u) ;
        factor_.push_back(f5) ;
        n_ /= static_cast<BigInt>("178481") ;

        PrimeFactor<BigInt>f6(static_cast<BigInt>("2796203"), 1u) ;
        factor_.push_back(f6) ;
        n_ /= static_cast<BigInt>("2796203") ;

        PrimeFactor<BigInt>f7(static_cast<BigInt>("168749965921"), 1u) ;
        factor_.push_back(f7) ;
        n_ /= static_cast<BigInt>("168749965921") ;

        PrimeFactor<BigInt>f8(static_cast<BigInt>("10052678938039"), 1u) ;
        factor_.push_back(f8) ;
        n_ /= static_cast<BigInt>("10052678938039") ;

        numFactors_ = 8u;

        return true;
    }
    else if (n_ == static_cast<BigInt>("696898287454081973172991196020261297061887"))  // 2^139/ (2-1)
    {
        PrimeFactor<BigInt>f1(static_cast<BigInt>("5625767248687"), 1u) ;
        factor_.push_back(f1) ;
        n_ /= static_cast<BigInt>("5625767248687") ;

        PrimeFactor<BigInt>f2(static_cast<BigInt>("123876132205208335762278423601"), 1u) ;
        factor_.push_back(f2) ;
        n_ /= static_cast<BigInt>("123876132205208335762278423601") ;

        numFactors_ = 2u;

        return true;
    }
    else if (n_ == static_cast<BigInt>("11150372599265311570767859136324180752990207"))  // 2^143/ (2-1)
    {
        PrimeFactor<BigInt>f1(static_cast<BigInt>("23"), 1u) ;
        factor_.push_back(f1) ;
        n_ /= static_cast<BigInt>("23") ;

        PrimeFactor<BigInt>f2(static_cast<BigInt>("89"), 1u) ;
        factor_.push_back(f2) ;
        n_ /= static_cast<BigInt>("89") ;

        PrimeFactor<BigInt>f3(static_cast<BigInt>("8191"), 1u) ;
        factor_.push_back(f3) ;
        n_ /= static_cast<BigInt>("8191") ;

        PrimeFactor<BigInt>f4(static_cast<BigInt>("724153"), 1u) ;
        factor_.push_back(f4) ;
        n_ /= static_cast<BigInt>("724153") ;

        PrimeFactor<BigInt>f5(static_cast<BigInt>("158822951431"), 1u) ;
        factor_.push_back(f5) ;
        n_ /= static_cast<BigInt>("158822951431") ;

        PrimeFactor<BigInt>f6(static_cast<BigInt>("5782172113400990737"), 1u) ;
        factor_.push_back(f6) ;
        n_ /= static_cast<BigInt>("5782172113400990737") ;

        numFactors_ = 6u;

        return true;
    }
    else if (n_ == static_cast<BigInt>("89202980794122492566142873090593446023921663"))  // 2^146/ (2-1)
    {
        PrimeFactor<BigInt>f1(static_cast<BigInt>("3"), 1u) ;
        factor_.push_back(f1) ;
        n_ /= static_cast<BigInt>("3") ;

        PrimeFactor<BigInt>f2(static_cast<BigInt>("439"), 1u) ;
        factor_.push_back(f2) ;
        n_ /= static_cast<BigInt>("439") ;

        PrimeFactor<BigInt>f3(static_cast<BigInt>("1753"), 1u) ;
        factor_.push_back(f3) ;
        n_ /= static_cast<BigInt>("1753") ;

        PrimeFactor<BigInt>f4(static_cast<BigInt>("2298041"), 1u) ;
        factor_.push_back(f4) ;
        n_ /= static_cast<BigInt>("2298041") ;

        PrimeFactor<BigInt>f5(static_cast<BigInt>("9361973132609"), 1u) ;
        factor_.push_back(f5) ;
        n_ /= static_cast<BigInt>("9361973132609") ;

        PrimeFactor<BigInt>f6(static_cast<BigInt>("1795918038741070627"), 1u) ;
        factor_.push_back(f6) ;
        n_ /= static_cast<BigInt>("1795918038741070627") ;

        numFactors_ = 6u;

        return true;
    }
    else if (n_ == static_cast<BigInt>("178405961588244985132285746181186892047843327"))  // 2^147/ (2-1)
    {
        PrimeFactor<BigInt>f1(static_cast<BigInt>("7"), 3u) ;
        factor_.push_back(f1) ;
        n_ /= static_cast<BigInt>("7") ;

        PrimeFactor<BigInt>f2(static_cast<BigInt>("127"), 1u) ;
        factor_.push_back(f2) ;
        n_ /= static_cast<BigInt>("127") ;

        PrimeFactor<BigInt>f3(static_cast<BigInt>("337"), 1u) ;
        factor_.push_back(f3) ;
        n_ /= static_cast<BigInt>("337") ;

        PrimeFactor<BigInt>f4(static_cast<BigInt>("4432676798593"), 1u) ;
        factor_.push_back(f4) ;
        n_ /= static_cast<BigInt>("4432676798593") ;

        PrimeFactor<BigInt>f5(static_cast<BigInt>("2741672362528725535068727"), 1u) ;
        factor_.push_back(f5) ;
        n_ /= static_cast<BigInt>("2741672362528725535068727") ;

        numFactors_ = 5u;

        return true;
    }
    else if (n_ == static_cast<BigInt>("713623846352979940529142984724747568191373311"))  // 2^149/ (2-1)
    {
        PrimeFactor<BigInt>f1(static_cast<BigInt>("86656268566282183151"), 1u) ;
        factor_.push_back(f1) ;
        n_ /= static_cast<BigInt>("86656268566282183151") ;

        PrimeFactor<BigInt>f2(static_cast<BigInt>("8235109336690846723986161"), 1u) ;
        factor_.push_back(f2) ;
        n_ /= static_cast<BigInt>("8235109336690846723986161") ;

        numFactors_ = 2u;

        return true;
    }
    else if (n_ == static_cast<BigInt>("182687704666362864775460604089535377456991567871"))  // 2^157/ (2-1)
    {
        PrimeFactor<BigInt>f1(static_cast<BigInt>("852133201"), 1u) ;
        factor_.push_back(f1) ;
        n_ /= static_cast<BigInt>("852133201") ;

        PrimeFactor<BigInt>f2(static_cast<BigInt>("60726444167"), 1u) ;
        factor_.push_back(f2) ;
        n_ /= static_cast<BigInt>("60726444167") ;

        PrimeFactor<BigInt>f3(static_cast<BigInt>("1654058017289"), 1u) ;
        factor_.push_back(f3) ;
        n_ /= static_cast<BigInt>("1654058017289") ;

        PrimeFactor<BigInt>f4(static_cast<BigInt>("2134387368610417"), 1u) ;
        factor_.push_back(f4) ;
        n_ /= static_cast<BigInt>("2134387368610417") ;

        numFactors_ = 4u;

        return true;
    }
    else if (n_ == static_cast<BigInt>("365375409332725729550921208179070754913983135743"))  // 2^158/ (2-1)
    {
        PrimeFactor<BigInt>f1(static_cast<BigInt>("3"), 1u) ;
        factor_.push_back(f1) ;
        n_ /= static_cast<BigInt>("3") ;

        PrimeFactor<BigInt>f2(static_cast<BigInt>("2687"), 1u) ;
        factor_.push_back(f2) ;
        n_ /= static_cast<BigInt>("2687") ;

        PrimeFactor<BigInt>f3(static_cast<BigInt>("202029703"), 1u) ;
        factor_.push_back(f3) ;
        n_ /= static_cast<BigInt>("202029703") ;

        PrimeFactor<BigInt>f4(static_cast<BigInt>("1113491139767"), 1u) ;
        factor_.push_back(f4) ;
        n_ /= static_cast<BigInt>("1113491139767") ;

        PrimeFactor<BigInt>f5(static_cast<BigInt>("201487636602438195784363"), 1u) ;
        factor_.push_back(f5) ;
        n_ /= static_cast<BigInt>("201487636602438195784363") ;

        numFactors_ = 5u;

        return true;
    }
    else if (n_ == static_cast<BigInt>("748288838313422294120286634350736906063837462003711"))  // 2^169/ (2-1)
    {
        PrimeFactor<BigInt>f1(static_cast<BigInt>("4057"), 1u) ;
        factor_.push_back(f1) ;
        n_ /= static_cast<BigInt>("4057") ;

        PrimeFactor<BigInt>f2(static_cast<BigInt>("8191"), 1u) ;
        factor_.push_back(f2) ;
        n_ /= static_cast<BigInt>("8191") ;

        PrimeFactor<BigInt>f3(static_cast<BigInt>("6740339310641"), 1u) ;
        factor_.push_back(f3) ;
        n_ /= static_cast<BigInt>("6740339310641") ;

        PrimeFactor<BigInt>f4(static_cast<BigInt>("3340762283952395329506327023033"), 1u) ;
        factor_.push_back(f4) ;
        n_ /= static_cast<BigInt>("3340762283952395329506327023033") ;

        numFactors_ = 4u;

        return true;
    }
    else if (n_ == static_cast<BigInt>("1496577676626844588240573268701473812127674924007423"))  // 2^170/ (2-1)
    {
        PrimeFactor<BigInt>f1(static_cast<BigInt>("3"), 1u) ;
        factor_.push_back(f1) ;
        n_ /= static_cast<BigInt>("3") ;

        PrimeFactor<BigInt>f2(static_cast<BigInt>("11"), 1u) ;
        factor_.push_back(f2) ;
        n_ /= static_cast<BigInt>("11") ;

        PrimeFactor<BigInt>f3(static_cast<BigInt>("31"), 1u) ;
        factor_.push_back(f3) ;
        n_ /= static_cast<BigInt>("31") ;

        PrimeFactor<BigInt>f4(static_cast<BigInt>("43691"), 1u) ;
        factor_.push_back(f4) ;
        n_ /= static_cast<BigInt>("43691") ;

        PrimeFactor<BigInt>f5(static_cast<BigInt>("131071"), 1u) ;
        factor_.push_back(f5) ;
        n_ /= static_cast<BigInt>("131071") ;

        PrimeFactor<BigInt>f6(static_cast<BigInt>("9520972806333758431"), 1u) ;
        factor_.push_back(f6) ;
        n_ /= static_cast<BigInt>("9520972806333758431") ;

        PrimeFactor<BigInt>f7(static_cast<BigInt>("26831423036065352611"), 1u) ;
        factor_.push_back(f7) ;
        n_ /= static_cast<BigInt>("26831423036065352611") ;

        numFactors_ = 7u;

        return true;
    }
    else if (n_ == static_cast<BigInt>("11972621413014756705924586149611790497021399392059391"))  // 2^173/ (2-1)
    {
        PrimeFactor<BigInt>f1(static_cast<BigInt>("730753"), 1u) ;
        factor_.push_back(f1) ;
        n_ /= static_cast<BigInt>("730753") ;

        PrimeFactor<BigInt>f2(static_cast<BigInt>("1505447"), 1u) ;
        factor_.push_back(f2) ;
        n_ /= static_cast<BigInt>("1505447") ;

        PrimeFactor<BigInt>f3(static_cast<BigInt>("70084436712553223"), 1u) ;
        factor_.push_back(f3) ;
        n_ /= static_cast<BigInt>("70084436712553223") ;

        PrimeFactor<BigInt>f4(static_cast<BigInt>("155285743288572277679887"), 1u) ;
        factor_.push_back(f4) ;
        n_ /= static_cast<BigInt>("155285743288572277679887") ;

        numFactors_ = 4u;

        return true;
    }
    else if (n_ == static_cast<BigInt>("383123885216472214589586756787577295904684780545900543"))  // 2^178/ (2-1)
    {
        PrimeFactor<BigInt>f1(static_cast<BigInt>("3"), 1u) ;
        factor_.push_back(f1) ;
        n_ /= static_cast<BigInt>("3") ;

        PrimeFactor<BigInt>f2(static_cast<BigInt>("179"), 1u) ;
        factor_.push_back(f2) ;
        n_ /= static_cast<BigInt>("179") ;

        PrimeFactor<BigInt>f3(static_cast<BigInt>("62020897"), 1u) ;
        factor_.push_back(f3) ;
        n_ /= static_cast<BigInt>("62020897") ;

        PrimeFactor<BigInt>f4(static_cast<BigInt>("18584774046020617"), 1u) ;
        factor_.push_back(f4) ;
        n_ /= static_cast<BigInt>("18584774046020617") ;

        PrimeFactor<BigInt>f5(static_cast<BigInt>("618970019642690137449562111"), 1u) ;
        factor_.push_back(f5) ;
        n_ /= static_cast<BigInt>("618970019642690137449562111") ;

        numFactors_ = 5u;

        return true;
    }
    else if (n_ == static_cast<BigInt>("12259964326927110866866776217202473468949912977468817407"))  // 2^183/ (2-1)
    {
        PrimeFactor<BigInt>f1(static_cast<BigInt>("7"), 1u) ;
        factor_.push_back(f1) ;
        n_ /= static_cast<BigInt>("7") ;

        PrimeFactor<BigInt>f2(static_cast<BigInt>("367"), 1u) ;
        factor_.push_back(f2) ;
        n_ /= static_cast<BigInt>("367") ;

        PrimeFactor<BigInt>f3(static_cast<BigInt>("55633"), 1u) ;
        factor_.push_back(f3) ;
        n_ /= static_cast<BigInt>("55633") ;

        PrimeFactor<BigInt>f4(static_cast<BigInt>("2305843009213693951"), 1u) ;
        factor_.push_back(f4) ;
        n_ /= static_cast<BigInt>("2305843009213693951") ;

        PrimeFactor<BigInt>f5(static_cast<BigInt>("37201708625305146303973352041"), 1u) ;
        factor_.push_back(f5) ;
        n_ /= static_cast<BigInt>("37201708625305146303973352041") ;

        numFactors_ = 5u;

        return true;
    }
    else if (n_ == static_cast<BigInt>("49039857307708443467467104868809893875799651909875269631"))  // 2^185/ (2-1)
    {
        PrimeFactor<BigInt>f1(static_cast<BigInt>("31"), 1u) ;
        factor_.push_back(f1) ;
        n_ /= static_cast<BigInt>("31") ;

        PrimeFactor<BigInt>f2(static_cast<BigInt>("223"), 1u) ;
        factor_.push_back(f2) ;
        n_ /= static_cast<BigInt>("223") ;

        PrimeFactor<BigInt>f3(static_cast<BigInt>("616318177"), 1u) ;
        factor_.push_back(f3) ;
        n_ /= static_cast<BigInt>("616318177") ;

        PrimeFactor<BigInt>f4(static_cast<BigInt>("1587855697992791"), 1u) ;
        factor_.push_back(f4) ;
        n_ /= static_cast<BigInt>("1587855697992791") ;

        PrimeFactor<BigInt>f5(static_cast<BigInt>("7248808599285760001152755641"), 1u) ;
        factor_.push_back(f5) ;
        n_ /= static_cast<BigInt>("7248808599285760001152755641") ;

        numFactors_ = 5u;

        return true;
    }
    else if (n_ == static_cast<BigInt>("46354731573948918542880962705293"))  // 3^67/ (3-1)
    {
        PrimeFactor<BigInt>f1(static_cast<BigInt>("221101"), 1u) ;
        factor_.push_back(f1) ;
        n_ /= static_cast<BigInt>("221101") ;

        PrimeFactor<BigInt>f2(static_cast<BigInt>("441019876741"), 1u) ;
        factor_.push_back(f2) ;
        n_ /= static_cast<BigInt>("441019876741") ;

        PrimeFactor<BigInt>f3(static_cast<BigInt>("475384700124973"), 1u) ;
        factor_.push_back(f3) ;
        n_ /= static_cast<BigInt>("475384700124973") ;

        numFactors_ = 3u;

        return true;
    }
    else if (n_ == static_cast<BigInt>("417192584165540266885928664347641"))  // 3^69/ (3-1)
    {
        PrimeFactor<BigInt>f1(static_cast<BigInt>("13"), 1u) ;
        factor_.push_back(f1) ;
        n_ /= static_cast<BigInt>("13") ;

        PrimeFactor<BigInt>f2(static_cast<BigInt>("47"), 1u) ;
        factor_.push_back(f2) ;
        n_ /= static_cast<BigInt>("47") ;

        PrimeFactor<BigInt>f3(static_cast<BigInt>("277"), 1u) ;
        factor_.push_back(f3) ;
        n_ /= static_cast<BigInt>("277") ;

        PrimeFactor<BigInt>f4(static_cast<BigInt>("1001523179"), 1u) ;
        factor_.push_back(f4) ;
        n_ /= static_cast<BigInt>("1001523179") ;

        PrimeFactor<BigInt>f5(static_cast<BigInt>("2461243576713869557"), 1u) ;
        factor_.push_back(f5) ;
        n_ /= static_cast<BigInt>("2461243576713869557") ;

        numFactors_ = 5u;

        return true;
    }
    else if (n_ == static_cast<BigInt>("1251577752496620800657785993042924"))  // 3^70/ (3-1)
    {
        PrimeFactor<BigInt>f1(static_cast<BigInt>("2"), 2u) ;
        factor_.push_back(f1) ;
        n_ /= static_cast<BigInt>("2") ;
        n_ /= static_cast<BigInt>("2") ;

        PrimeFactor<BigInt>f2(static_cast<BigInt>("11"), 2u) ;
        factor_.push_back(f2) ;
        n_ /= static_cast<BigInt>("11") ;
        n_ /= static_cast<BigInt>("11") ;

        PrimeFactor<BigInt>f3(static_cast<BigInt>("61"), 1u) ;
        factor_.push_back(f3) ;
        n_ /= static_cast<BigInt>("61") ;

        PrimeFactor<BigInt>f4(static_cast<BigInt>("71"), 1u) ;
        factor_.push_back(f4) ;
        n_ /= static_cast<BigInt>("71") ;

        PrimeFactor<BigInt>f5(static_cast<BigInt>("547"), 1u) ;
        factor_.push_back(f5) ;
        n_ /= static_cast<BigInt>("547") ;

        PrimeFactor<BigInt>f6(static_cast<BigInt>("1093"), 1u) ;
        factor_.push_back(f6) ;
        n_ /= static_cast<BigInt>("1093") ;

        PrimeFactor<BigInt>f7(static_cast<BigInt>("2664097031"), 1u) ;
        factor_.push_back(f7) ;
        n_ /= static_cast<BigInt>("2664097031") ;

        PrimeFactor<BigInt>f8(static_cast<BigInt>("374857981681"), 1u) ;
        factor_.push_back(f8) ;
        n_ /= static_cast<BigInt>("374857981681") ;

        numFactors_ = 8u;

        return true;
    }
    else if (n_ == static_cast<BigInt>("33792599317408761617760221812158961"))  // 3^73/ (3-1)
    {
        PrimeFactor<BigInt>f1(static_cast<BigInt>("11243"), 1u) ;
        factor_.push_back(f1) ;
        n_ /= static_cast<BigInt>("11243") ;

        PrimeFactor<BigInt>f2(static_cast<BigInt>("20149"), 1u) ;
        factor_.push_back(f2) ;
        n_ /= static_cast<BigInt>("20149") ;

        PrimeFactor<BigInt>f3(static_cast<BigInt>("15768033143"), 1u) ;
        factor_.push_back(f3) ;
        n_ /= static_cast<BigInt>("15768033143") ;

        PrimeFactor<BigInt>f4(static_cast<BigInt>("9460375336977361"), 1u) ;
        factor_.push_back(f4) ;
        n_ /= static_cast<BigInt>("9460375336977361") ;

        numFactors_ = 4u;

        return true;
    }
    else if (n_ == static_cast<BigInt>("2737200544710109691038577966784875881"))  // 3^77/ (3-1)
    {
        PrimeFactor<BigInt>f1(static_cast<BigInt>("23"), 1u) ;
        factor_.push_back(f1) ;
        n_ /= static_cast<BigInt>("23") ;

        PrimeFactor<BigInt>f2(static_cast<BigInt>("1093"), 1u) ;
        factor_.push_back(f2) ;
        n_ /= static_cast<BigInt>("1093") ;

        PrimeFactor<BigInt>f3(static_cast<BigInt>("3851"), 1u) ;
        factor_.push_back(f3) ;
        n_ /= static_cast<BigInt>("3851") ;

        PrimeFactor<BigInt>f4(static_cast<BigInt>("51457561"), 1u) ;
        factor_.push_back(f4) ;
        n_ /= static_cast<BigInt>("51457561") ;

        PrimeFactor<BigInt>f5(static_cast<BigInt>("7151459701"), 1u) ;
        factor_.push_back(f5) ;
        n_ /= static_cast<BigInt>("7151459701") ;

        PrimeFactor<BigInt>f6(static_cast<BigInt>("76831835389"), 1u) ;
        factor_.push_back(f6) ;
        n_ /= static_cast<BigInt>("76831835389") ;

        numFactors_ = 6u;

        return true;
    }
    else if (n_ == static_cast<BigInt>("24634804902390987219347201701063882933"))  // 3^79/ (3-1)
    {
        PrimeFactor<BigInt>f1(static_cast<BigInt>("432853009"), 1u) ;
        factor_.push_back(f1) ;
        n_ /= static_cast<BigInt>("432853009") ;

        PrimeFactor<BigInt>f2(static_cast<BigInt>("392038110671"), 1u) ;
        factor_.push_back(f2) ;
        n_ /= static_cast<BigInt>("392038110671") ;

        PrimeFactor<BigInt>f3(static_cast<BigInt>("145171177264407947"), 1u) ;
        factor_.push_back(f3) ;
        n_ /= static_cast<BigInt>("145171177264407947") ;

        numFactors_ = 3u;

        return true;
    }
    else if (n_ == static_cast<BigInt>("665139732364556654922374445928724839204"))  // 3^82/ (3-1)
    {
        PrimeFactor<BigInt>f1(static_cast<BigInt>("2"), 2u) ;
        factor_.push_back(f1) ;
        n_ /= static_cast<BigInt>("2") ;
        n_ /= static_cast<BigInt>("2") ;

        PrimeFactor<BigInt>f2(static_cast<BigInt>("83"), 1u) ;
        factor_.push_back(f2) ;
        n_ /= static_cast<BigInt>("83") ;

        PrimeFactor<BigInt>f3(static_cast<BigInt>("33703"), 1u) ;
        factor_.push_back(f3) ;
        n_ /= static_cast<BigInt>("33703") ;

        PrimeFactor<BigInt>f4(static_cast<BigInt>("2526913"), 1u) ;
        factor_.push_back(f4) ;
        n_ /= static_cast<BigInt>("2526913") ;

        PrimeFactor<BigInt>f5(static_cast<BigInt>("86950696619"), 1u) ;
        factor_.push_back(f5) ;
        n_ /= static_cast<BigInt>("86950696619") ;

        PrimeFactor<BigInt>f6(static_cast<BigInt>("270547105429567"), 1u) ;
        factor_.push_back(f6) ;
        n_ /= static_cast<BigInt>("270547105429567") ;

        numFactors_ = 6u;

        return true;
    }
    else if (n_ == static_cast<BigInt>("17958772773843029682904110040075570658521"))  // 3^85/ (3-1)
    {
        PrimeFactor<BigInt>f1(static_cast<BigInt>("11"), 2u) ;
        factor_.push_back(f1) ;
        n_ /= static_cast<BigInt>("11") ;
        n_ /= static_cast<BigInt>("11") ;

        PrimeFactor<BigInt>f2(static_cast<BigInt>("1871"), 1u) ;
        factor_.push_back(f2) ;
        n_ /= static_cast<BigInt>("1871") ;

        PrimeFactor<BigInt>f3(static_cast<BigInt>("34511"), 1u) ;
        factor_.push_back(f3) ;
        n_ /= static_cast<BigInt>("34511") ;

        PrimeFactor<BigInt>f4(static_cast<BigInt>("2663568851051"), 1u) ;
        factor_.push_back(f4) ;
        n_ /= static_cast<BigInt>("2663568851051") ;

        PrimeFactor<BigInt>f5(static_cast<BigInt>("862970652262943171"), 1u) ;
        factor_.push_back(f5) ;
        n_ /= static_cast<BigInt>("862970652262943171") ;

        numFactors_ = 5u;

        return true;
    }
    else if (n_ == static_cast<BigInt>("53876318321529089048712330120226711975564"))  // 3^86/ (3-1)
    {
        PrimeFactor<BigInt>f1(static_cast<BigInt>("2"), 2u) ;
        factor_.push_back(f1) ;
        n_ /= static_cast<BigInt>("2") ;
        n_ /= static_cast<BigInt>("2") ;

        PrimeFactor<BigInt>f2(static_cast<BigInt>("431"), 1u) ;
        factor_.push_back(f2) ;
        n_ /= static_cast<BigInt>("431") ;

        PrimeFactor<BigInt>f3(static_cast<BigInt>("380808546861411923"), 1u) ;
        factor_.push_back(f3) ;
        n_ /= static_cast<BigInt>("380808546861411923") ;

        PrimeFactor<BigInt>f4(static_cast<BigInt>("82064241848634269407"), 1u) ;
        factor_.push_back(f4) ;
        n_ /= static_cast<BigInt>("82064241848634269407") ;

        numFactors_ = 4u;

        return true;
    }
    else if (n_ == static_cast<BigInt>("1454660594681285404315232913246121223340241"))  // 3^89/ (3-1)
    {
        PrimeFactor<BigInt>f1(static_cast<BigInt>("179"), 1u) ;
        factor_.push_back(f1) ;
        n_ /= static_cast<BigInt>("179") ;

        PrimeFactor<BigInt>f2(static_cast<BigInt>("1611479891519807"), 1u) ;
        factor_.push_back(f2) ;
        n_ /= static_cast<BigInt>("1611479891519807") ;

        PrimeFactor<BigInt>f3(static_cast<BigInt>("5042939439565996049162197"), 1u) ;
        factor_.push_back(f3) ;
        n_ /= static_cast<BigInt>("5042939439565996049162197") ;

        numFactors_ = 3u;

        return true;
    }
    else if (n_ == static_cast<BigInt>("9544028161703913537712243143807801346335324481"))  // 3^97/ (3-1)
    {
        PrimeFactor<BigInt>f1(static_cast<BigInt>("76631"), 1u) ;
        factor_.push_back(f1) ;
        n_ /= static_cast<BigInt>("76631") ;

        PrimeFactor<BigInt>f2(static_cast<BigInt>("2549755542947"), 1u) ;
        factor_.push_back(f2) ;
        n_ /= static_cast<BigInt>("2549755542947") ;

        PrimeFactor<BigInt>f3(static_cast<BigInt>("48845962828028421155731228333"), 1u) ;
        factor_.push_back(f3) ;
        n_ /= static_cast<BigInt>("48845962828028421155731228333") ;

        numFactors_ = 3u;

        return true;
    }
    else if (n_ == static_cast<BigInt>("187855106306818130162790081799568953899918191769364"))  // 3^106/ (3-1)
    {
        PrimeFactor<BigInt>f1(static_cast<BigInt>("2"), 2u) ;
        factor_.push_back(f1) ;
        n_ /= static_cast<BigInt>("2") ;
        n_ /= static_cast<BigInt>("2") ;

        PrimeFactor<BigInt>f2(static_cast<BigInt>("107"), 1u) ;
        factor_.push_back(f2) ;
        n_ /= static_cast<BigInt>("107") ;

        PrimeFactor<BigInt>f3(static_cast<BigInt>("24169"), 1u) ;
        factor_.push_back(f3) ;
        n_ /= static_cast<BigInt>("24169") ;

        PrimeFactor<BigInt>f4(static_cast<BigInt>("78719947"), 1u) ;
        factor_.push_back(f4) ;
        n_ /= static_cast<BigInt>("78719947") ;

        PrimeFactor<BigInt>f5(static_cast<BigInt>("61557605176233223"), 1u) ;
        factor_.push_back(f5) ;
        n_ /= static_cast<BigInt>("61557605176233223") ;

        PrimeFactor<BigInt>f6(static_cast<BigInt>("3747607031112307667"), 1u) ;
        factor_.push_back(f6) ;
        n_ /= static_cast<BigInt>("3747607031112307667") ;

        numFactors_ = 6u;

        return true;
    }
    else if (n_ == static_cast<BigInt>("15216263610852268543185996625765085265893373533318524"))  // 3^110/ (3-1)
    {
        PrimeFactor<BigInt>f1(static_cast<BigInt>("2"), 2u) ;
        factor_.push_back(f1) ;
        n_ /= static_cast<BigInt>("2") ;
        n_ /= static_cast<BigInt>("2") ;

        PrimeFactor<BigInt>f2(static_cast<BigInt>("11"), 3u) ;
        factor_.push_back(f2) ;
        n_ /= static_cast<BigInt>("11") ;
        n_ /= static_cast<BigInt>("11") ;
        n_ /= static_cast<BigInt>("11") ;

        PrimeFactor<BigInt>f3(static_cast<BigInt>("23"), 1u) ;
        factor_.push_back(f3) ;
        n_ /= static_cast<BigInt>("23") ;

        PrimeFactor<BigInt>f4(static_cast<BigInt>("61"), 1u) ;
        factor_.push_back(f4) ;
        n_ /= static_cast<BigInt>("61") ;

        PrimeFactor<BigInt>f5(static_cast<BigInt>("67"), 1u) ;
        factor_.push_back(f5) ;
        n_ /= static_cast<BigInt>("67") ;

        PrimeFactor<BigInt>f6(static_cast<BigInt>("661"), 1u) ;
        factor_.push_back(f6) ;
        n_ /= static_cast<BigInt>("661") ;

        PrimeFactor<BigInt>f7(static_cast<BigInt>("1321"), 1u) ;
        factor_.push_back(f7) ;
        n_ /= static_cast<BigInt>("1321") ;

        PrimeFactor<BigInt>f8(static_cast<BigInt>("3851"), 1u) ;
        factor_.push_back(f8) ;
        n_ /= static_cast<BigInt>("3851") ;

        PrimeFactor<BigInt>f9(static_cast<BigInt>("659671"), 1u) ;
        factor_.push_back(f9) ;
        n_ /= static_cast<BigInt>("659671") ;

        PrimeFactor<BigInt>f10(static_cast<BigInt>("24472341743191"), 1u) ;
        factor_.push_back(f10) ;
        n_ /= static_cast<BigInt>("24472341743191") ;

        PrimeFactor<BigInt>f11(static_cast<BigInt>("560088668384411"), 1u) ;
        factor_.push_back(f11) ;
        n_ /= static_cast<BigInt>("560088668384411") ;

        numFactors_ = 11u;

        return true;
    }
    else if (n_ == static_cast<BigInt>("99833905550801733911843323861644724429526423752102839244"))  // 3^118/ (3-1)
    {
        PrimeFactor<BigInt>f1(static_cast<BigInt>("2"), 2u) ;
        factor_.push_back(f1) ;
        n_ /= static_cast<BigInt>("2") ;
        n_ /= static_cast<BigInt>("2") ;

        PrimeFactor<BigInt>f2(static_cast<BigInt>("3187"), 1u) ;
        factor_.push_back(f2) ;
        n_ /= static_cast<BigInt>("3187") ;

        PrimeFactor<BigInt>f3(static_cast<BigInt>("14425532687"), 1u) ;
        factor_.push_back(f3) ;
        n_ /= static_cast<BigInt>("14425532687") ;

        PrimeFactor<BigInt>f4(static_cast<BigInt>("489769993189671059"), 1u) ;
        factor_.push_back(f4) ;
        n_ /= static_cast<BigInt>("489769993189671059") ;

        PrimeFactor<BigInt>f5(static_cast<BigInt>("1108439448677340328268341"), 1u) ;
        factor_.push_back(f5) ;
        n_ /= static_cast<BigInt>("1108439448677340328268341") ;

        numFactors_ = 5u;

        return true;
    }
    else if (n_ == static_cast<BigInt>("299501716652405201735529971584934173288579271256308517733"))  // 3^119/ (3-1)
    {
        PrimeFactor<BigInt>f1(static_cast<BigInt>("239"), 1u) ;
        factor_.push_back(f1) ;
        n_ /= static_cast<BigInt>("239") ;

        PrimeFactor<BigInt>f2(static_cast<BigInt>("1093"), 1u) ;
        factor_.push_back(f2) ;
        n_ /= static_cast<BigInt>("1093") ;

        PrimeFactor<BigInt>f3(static_cast<BigInt>("1871"), 1u) ;
        factor_.push_back(f3) ;
        n_ /= static_cast<BigInt>("1871") ;

        PrimeFactor<BigInt>f4(static_cast<BigInt>("34511"), 1u) ;
        factor_.push_back(f4) ;
        n_ /= static_cast<BigInt>("34511") ;

        PrimeFactor<BigInt>f5(static_cast<BigInt>("44626806191326911791"), 1u) ;
        factor_.push_back(f5) ;
        n_ /= static_cast<BigInt>("44626806191326911791") ;

        PrimeFactor<BigInt>f6(static_cast<BigInt>("397881837642577477902049"), 1u) ;
        factor_.push_back(f6) ;
        n_ /= static_cast<BigInt>("397881837642577477902049") ;

        numFactors_ = 6u;

        return true;
    }
    else if (n_ == static_cast<BigInt>("1084202172485504434007452800869941711425781"))  // 5^61/ (5-1)
    {
        PrimeFactor<BigInt>f1(static_cast<BigInt>("8419"), 1u) ;
        factor_.push_back(f1) ;
        n_ /= static_cast<BigInt>("8419") ;

        PrimeFactor<BigInt>f2(static_cast<BigInt>("918585913061"), 1u) ;
        factor_.push_back(f2) ;
        n_ /= static_cast<BigInt>("918585913061") ;

        PrimeFactor<BigInt>f3(static_cast<BigInt>("140194179307171898833699259"), 1u) ;
        factor_.push_back(f3) ;
        n_ /= static_cast<BigInt>("140194179307171898833699259") ;

        numFactors_ = 3u;

        return true;
    }
    else if (n_ == static_cast<BigInt>("677626357803440271254658000543713569641113281"))  // 5^65/ (5-1)
    {
        PrimeFactor<BigInt>f1(static_cast<BigInt>("11"), 1u) ;
        factor_.push_back(f1) ;
        n_ /= static_cast<BigInt>("11") ;

        PrimeFactor<BigInt>f2(static_cast<BigInt>("71"), 1u) ;
        factor_.push_back(f2) ;
        n_ /= static_cast<BigInt>("71") ;

        PrimeFactor<BigInt>f3(static_cast<BigInt>("131"), 1u) ;
        factor_.push_back(f3) ;
        n_ /= static_cast<BigInt>("131") ;

        PrimeFactor<BigInt>f4(static_cast<BigInt>("305175781"), 1u) ;
        factor_.push_back(f4) ;
        n_ /= static_cast<BigInt>("305175781") ;

        PrimeFactor<BigInt>f5(static_cast<BigInt>("1034150930241911"), 1u) ;
        factor_.push_back(f5) ;
        n_ /= static_cast<BigInt>("1034150930241911") ;

        PrimeFactor<BigInt>f6(static_cast<BigInt>("20986207825565581"), 1u) ;
        factor_.push_back(f6) ;
        n_ /= static_cast<BigInt>("20986207825565581") ;

        numFactors_ = 6u;

        return true;
    }
    else if (n_ == static_cast<BigInt>("16940658945086006781366450013592839241027832031"))  // 5^67/ (5-1)
    {
        PrimeFactor<BigInt>f1(static_cast<BigInt>("269"), 1u) ;
        factor_.push_back(f1) ;
        n_ /= static_cast<BigInt>("269") ;

        PrimeFactor<BigInt>f2(static_cast<BigInt>("1609"), 1u) ;
        factor_.push_back(f2) ;
        n_ /= static_cast<BigInt>("1609") ;

        PrimeFactor<BigInt>f3(static_cast<BigInt>("26399"), 1u) ;
        factor_.push_back(f3) ;
        n_ /= static_cast<BigInt>("26399") ;

        PrimeFactor<BigInt>f4(static_cast<BigInt>("2454335007529"), 1u) ;
        factor_.push_back(f4) ;
        n_ /= static_cast<BigInt>("2454335007529") ;

        PrimeFactor<BigInt>f5(static_cast<BigInt>("604088623657497125653141"), 1u) ;
        factor_.push_back(f5) ;
        n_ /= static_cast<BigInt>("604088623657497125653141") ;

        numFactors_ = 5u;

        return true;
    }
    else if (n_ == static_cast<BigInt>("1323488980084844279794253907311940565705299377441406"))  // 5^74/ (5-1)
    {
        PrimeFactor<BigInt>f1(static_cast<BigInt>("2"), 1u) ;
        factor_.push_back(f1) ;
        n_ /= static_cast<BigInt>("2") ;

        PrimeFactor<BigInt>f2(static_cast<BigInt>("3"), 1u) ;
        factor_.push_back(f2) ;
        n_ /= static_cast<BigInt>("3") ;

        PrimeFactor<BigInt>f3(static_cast<BigInt>("149"), 1u) ;
        factor_.push_back(f3) ;
        n_ /= static_cast<BigInt>("149") ;

        PrimeFactor<BigInt>f4(static_cast<BigInt>("9103"), 1u) ;
        factor_.push_back(f4) ;
        n_ /= static_cast<BigInt>("9103") ;

        PrimeFactor<BigInt>f5(static_cast<BigInt>("29010221"), 1u) ;
        factor_.push_back(f5) ;
        n_ /= static_cast<BigInt>("29010221") ;

        PrimeFactor<BigInt>f6(static_cast<BigInt>("13971969971"), 1u) ;
        factor_.push_back(f6) ;
        n_ /= static_cast<BigInt>("13971969971") ;

        PrimeFactor<BigInt>f7(static_cast<BigInt>("8737481256739"), 1u) ;
        factor_.push_back(f7) ;
        n_ /= static_cast<BigInt>("8737481256739") ;

        PrimeFactor<BigInt>f8(static_cast<BigInt>("45920153384867"), 1u) ;
        factor_.push_back(f8) ;
        n_ /= static_cast<BigInt>("45920153384867") ;

        numFactors_ = 8u;

        return true;
    }
    else if (n_ == static_cast<BigInt>("4135903062765138374357043460349814267829060554504394531"))  // 5^79/ (5-1)
    {
        PrimeFactor<BigInt>f1(static_cast<BigInt>("205367807127911"), 1u) ;
        factor_.push_back(f1) ;
        n_ /= static_cast<BigInt>("205367807127911") ;

        PrimeFactor<BigInt>f2(static_cast<BigInt>("58523123221688392679"), 1u) ;
        factor_.push_back(f2) ;
        n_ /= static_cast<BigInt>("58523123221688392679") ;

        PrimeFactor<BigInt>f3(static_cast<BigInt>("344120456368919234899"), 1u) ;
        factor_.push_back(f3) ;
        n_ /= static_cast<BigInt>("344120456368919234899") ;

        numFactors_ = 3u;

        return true;
    }
    else if (n_ == static_cast<BigInt>("516987882845642296794630432543726783478632569313049316406"))  // 5^82/ (5-1)
    {
        PrimeFactor<BigInt>f1(static_cast<BigInt>("2"), 1u) ;
        factor_.push_back(f1) ;
        n_ /= static_cast<BigInt>("2") ;

        PrimeFactor<BigInt>f2(static_cast<BigInt>("3"), 1u) ;
        factor_.push_back(f2) ;
        n_ /= static_cast<BigInt>("3") ;

        PrimeFactor<BigInt>f3(static_cast<BigInt>("83"), 1u) ;
        factor_.push_back(f3) ;
        n_ /= static_cast<BigInt>("83") ;

        PrimeFactor<BigInt>f4(static_cast<BigInt>("43543"), 1u) ;
        factor_.push_back(f4) ;
        n_ /= static_cast<BigInt>("43543") ;

        PrimeFactor<BigInt>f5(static_cast<BigInt>("221401"), 1u) ;
        factor_.push_back(f5) ;
        n_ /= static_cast<BigInt>("221401") ;

        PrimeFactor<BigInt>f6(static_cast<BigInt>("2238236249"), 1u) ;
        factor_.push_back(f6) ;
        n_ /= static_cast<BigInt>("2238236249") ;

        PrimeFactor<BigInt>f7(static_cast<BigInt>("9472026608675509"), 1u) ;
        factor_.push_back(f7) ;
        n_ /= static_cast<BigInt>("9472026608675509") ;

        PrimeFactor<BigInt>f8(static_cast<BigInt>("5079304643216687969"), 1u) ;
        factor_.push_back(f8) ;
        n_ /= static_cast<BigInt>("5079304643216687969") ;

        numFactors_ = 8u;

        return true;
    }
    else if (n_ == static_cast<BigInt>("4148845196040257483464536947493101431141548619494008"))  // 7^62/ (7-1)
    {
        PrimeFactor<BigInt>f1(static_cast<BigInt>("2"), 3u) ;
        factor_.push_back(f1) ;
        n_ /= static_cast<BigInt>("2") ;
        n_ /= static_cast<BigInt>("2") ;
        n_ /= static_cast<BigInt>("2") ;

        PrimeFactor<BigInt>f2(static_cast<BigInt>("311"), 1u) ;
        factor_.push_back(f2) ;
        n_ /= static_cast<BigInt>("311") ;

        PrimeFactor<BigInt>f3(static_cast<BigInt>("373"), 1u) ;
        factor_.push_back(f3) ;
        n_ /= static_cast<BigInt>("373") ;

        PrimeFactor<BigInt>f4(static_cast<BigInt>("21143"), 1u) ;
        factor_.push_back(f4) ;
        n_ /= static_cast<BigInt>("21143") ;

        PrimeFactor<BigInt>f5(static_cast<BigInt>("9754399"), 1u) ;
        factor_.push_back(f5) ;
        n_ /= static_cast<BigInt>("9754399") ;

        PrimeFactor<BigInt>f6(static_cast<BigInt>("5420506947192709"), 1u) ;
        factor_.push_back(f6) ;
        n_ /= static_cast<BigInt>("5420506947192709") ;

        PrimeFactor<BigInt>f7(static_cast<BigInt>("3999088279399464409"), 1u) ;
        factor_.push_back(f7) ;
        n_ /= static_cast<BigInt>("3999088279399464409") ;

        numFactors_ = 7u;

        return true;
    }

    return false ;
}


// TODO
//                                       ---          1/2
//    Trial division takes max( p    , \/ p  )  = O( N   )
//                               t-1       t
//                                       ---          1/4
//    Pollard rho takes                \/ p       = O( N  )
//                                         t-1
//
template <typename IntType>
Factor<IntType>::Factor( const IntType n, FactoringAlgorithm type )
    : n_()
    , numFactors_()
    , factor_()
    , statistics_()
             
{
    factor_.clear() ;

    // Initialize the unfactored remainder.
    n_ = n ;

    //  Handle special cases for speed.
    //  These are cases where r = (p^n - 1)/(p-1) has large prime factors.
    if (factorTable())
        return ;
    // Table lookup failed, but return anyway (for unit testing).
    else if (type == FactorTable)
        return ;
    // Else continue to trial division or Pollard rho methods.

    // TODO pull out small factors first with trial division?

    //  If the number is fairly small, use trial division.
    //  TODO this is largest uint type. Need 2^60 instead.
    const IntType crossoverPoint = 13693952u ;  

    // For unit testing only, specify the type of algorithm.
    if (type == TrialDivisionAlgorithm)
    {
        #ifdef DEBUG_PP_FACTOR
        cout << "Trial division factoring on n = " << n_ << endl ;
        #endif

        trialDivision() ;
    }
    else if (type == PollardRhoAlgorithm)
    {
        #ifdef DEBUG_PP_FACTOR
        cout << "Pollard Rho factoring on n = " << n_ << endl ;
        #endif

        PollardRho() ;
    }
    // Factor small integers with trial division.
    else if (n_ < crossoverPoint)
    {
        #ifdef DEBUG_PP_FACTOR
        cout << "Trial division factoring on n = " << n_ << endl ;
        #endif

        trialDivision() ;
    }
    else
    {
        // Try Pollard's method first.  If it fails, keep the
        // factors found so far, and retry on the unfactored
        // remainder.
        if (!PollardRho())
        {
            #ifdef DEBUG_PP_FACTOR
            cout << "Pollard Rho failed on n =" << n_ << endl ;
            cout << "Try again" << endl ;
            #endif

            // Try again with random c, but avoid using c in { 0, 1, -2 }
            if (!PollardRho( 5u ))
            {
                #ifdef DEBUG_PP_FACTOR
                cout << "Pollard Rho failed again on n =" << n_ << endl ;
                cout << "switching to trial division" << endl ;
                #endif
             
                // Still fails?  Fall back onto trial division.
                trialDivision() ;
            }
        }
     }
	 
	#ifdef DEBUG_PP_FACTOR
    cout << "     Unsorted prime factors." << endl ;
    for( typename vector< PrimeFactor<IntType> >::const_iterator i = 
         factor_.begin() ;  i < factor_.end() ;  ++i)
    {
        PrimeFactor<IntType> e = *i ;
        cout << e.prime_ << " " << e.count_ << endl ;
    }
    #endif

    // Sort primes into ascending order.
    sort( factor_.begin(), factor_.end(), CompareFactor<IntType>() ) ;

    // Merge duplicated prime factors into unique primes to powers.
    for (int i = 1 ;  i < factor_.size() ;  ++i)
    {
        // This prime factor is a duplicate of the last.
        if (factor_[ i ].prime_ == factor_[ i-1 ].prime_)
        {
            // Merge into existing prime power.
            factor_[ i ].count_ += factor_[ i-1 ].count_ ;
            factor_[ i-1 ].count_ = static_cast<IntType>( 0u ) ;
        }
    }

    // Remove factors of 1.
    typename vector< PrimeFactor<IntType> >::iterator last =
        remove_if( factor_.begin(), factor_.end(), Unit<IntType>() ) ;
    factor_.erase( last, factor_.end() ) ;
    numFactors_ = factor_.size() ;

    #ifdef DEBUG_PP_FACTOR
    numFactors_ = factor_.size() ;
    cout << numFactors_ << " sorted unique factors" << endl ;
    for (int i = 0 ;  i < numFactors_ ;  ++i)
        cout << factor_[ i ].prime_ << " ^ " << factor_[ i ].count_ << endl ;
    #endif
 }



/*=============================================================================
|
| NAME
|
|    template <typename IntType> Factor<IntType>::Factor( const IntType n_arg )
|
| DESCRIPTION
|
     Factor n into primes.  Record all the distinct prime factors and how
     many times each occurs.  Return the number of primes - 1.
|    where n_arg >= 1
|
| EXAMPLE CALLING SEQUENCE
|
|    Factor<BigInt> f ;


     primes (bigint *)   List of distinct prime factors.
     count  (uint *)     List of how many times each factor occurred.

     When n = 1, t = 0, and primes[ 0 ] = count[ 0 ] = 1.

RETURNS

     t (int)             Number of prime factors - 1.
	                     Prime factors and their multiplicites are in locations 0 to t.

EXAMPLE
                   2
    For n = 156 = 2  * 3 * 13 we have

    k   primes[ k ]   count[ k ]
    ----------------------------
    0        2            2
    1        3            1
    2       13            1

METHOD

    Method described by D.E. Knuth, ART OF COMPUTER PROGRAMMING, vol. 2, 2nd ed.,
	                                                            -----
	in Algorithm A, pgs. 364-365.  The running time is O( max \/ p   , p  )
                                                                  t-1   t
    where p  is the largest prime divisor of n and p    is the next largest.
	       t                                        t-1

    (1)  First divide out all multiples of 2 and 3 and count them.

	(2)  Next, divide n by all integers d >= 5 except multiples of 2 and 3.

    (3)  Halt either when all prime factors have been divided out (leaving n = 1)
	     or when the current value of n is prime.  The stopping test

          (d > | n/d | AND r != 0)
               --   --
         detects when n is prime.

    In the example above, we divided out 2's and 3's first, leaving
    n = 13.  We continued with trial divisor d = 3.  But now the stopping
    test was activated because 5 > | 13/5 | = 2, and remainder = 3 (non-zero).
                                   --    --
    n = 13 itself is the last prime factor of 156.  We return t = 2.  There
    are 2 + 1 = 3 distinct primes.


    If we start with d = 5, and add 2 and 4 in succession, we will run through all
	the integers except multiples of 2 and 3.  To see this, observe the pattern:

    Integers:     1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17
	Mult. of 2:      x     x     x     x     x     x     x     x
	Mult. of 3:         x        x        x        x        x
	d:                        x     x           x     x          x
	Separation:                  2       4         2       4

    The sequence of divisors d, includes all the primes, so is safe to use for
	factorization testing.

    Theorem.  Suppose no divisor d in the sequence divides n.  Suppose at some point,
	q < d with r != 0.  Then n must be prime.

    Proof.  We begin with an integer n which has all powers of 2 and 3 removed.
    Assume, to the contrary, that n is composite:  n = p ... p
	      t                                             1     t
    n >= p    since p  is the smallest prime factor.
	      1          1

	      2
    n >= p    since n is composite, so has at least 2 prime factors.
	      1
		        2
	  >= (d + 1)   since p  > d implies p >= (d + 1).  p > d because we assumed
                          1              1              1
      that no d in the sequence divided n, so d couldn't be any of the prime divisors
	  p
	   i
         2            2               2
	  = d + 2d + 1 = d + d + d + 1 > d + d
         2
      > d + n mod d   since n mod d < d
                                                                              2
      > | n / d | d + n mod d  because our test said q < d, so | n / d | d < d
	    --     --                                              --     --

      = n.  So we get the contradiction n > n.  Thus n must be prime.
	                                               ---
    Note that this is sharper than the bound d > \/ n

    Theorem.  Conversely, if n is a prime, no d will divide it, so at some point,
	d will be large enough that q = | n / d | < d.  r != 0 since n is prime.
	                                --     --

    Theorem.  The factoring algorithm works.

	Proof.  If n == 1 we exit immediately.  If n is composite, we divide out all powers
	of 2 and 3 (if any).  Since d runs through all possible prime divisors, we divide
	these out also.  Composite trial d causes no problem;  prime factors of d are divided
	out of n before we try to divide by d, so such a d cannot divide n.

    We end in one of two ways (1) All divisors of n have been divided out in which case n = 1.
	(2) n is a prime, so the stopping test is activiated and n != 1 is recorded as a prime
	divisor.


TODO

    Can be slow when n is a prime.  We could do a probabilistic test for
    the primality of n at the statement, "n_is_prime = (r != 0 && q < d) ;"
    which would speed up the test.

+============================================================================*/

template <typename IntType>
void Factor<IntType>::trialDivision()
{
#ifdef DEBUG_PP_FACTOR
    cout << "trial division on n =" << n_ << endl ;
#endif

// Remove factors of 2.
uint cnt = 0u ;
while( n_ % 2u == 0u )
{
    n_ /= 2u ;
    ++cnt ;
    ++statistics_.num_trial_divides ;
}

if (cnt != 0u)
{
    PrimeFactor<IntType> f( 2u, cnt ) ;
    factor_.push_back( f ) ;
}

#ifdef DEBUG_PP_FACTOR
    cout << "after removing powers of 2, n =" << n_ << endl ;
#endif

// Remove factors of 3.
cnt = 0 ;
while( n_ % 3u == 0u )
{
    n_ /= 3 ;
    ++cnt ;
    ++statistics_.num_trial_divides ;
}

if (cnt != 0)
{
    PrimeFactor<IntType> f( 3u, cnt ) ;
	factor_.push_back( f ) ;
}

#ifdef DEBUG_PP_FACTOR
cout << "after removing powers of 3, n =" << n_ << endl ;
#endif


//  Factor the rest of n.  Continue until n = 1 (all factors divided out)
//  or until n is prime (so n itself is the last prime factor).

bool new_d = true ;       //  true if current divisor is different from
                          //  the previous one.
bool n_is_prime = false ; //  true if current value of n is prime.
bool flag = true ;        //  Alternately true and false.

IntType d = 5u ;  // First trial divisor.
do {
	/*  Integer divide to get quotient and remainder:  n = qd + r */
    // TODO:  speed this up using divMod.
    IntType q = n_ / d ;
    IntType r = n_ % d ;
    ++statistics_.num_trial_divides ;

    #ifdef DEBUG_PP_FACTOR
    cout << "n = " ; printNumber( n_ ) ;
    cout << "d = " ; printNumber( d ) ;
    cout << "q = " ; printNumber( q ) ;
    cout << "r = " ; printNumber( r ) ;
    #endif

    // Stopping test.
    n_is_prime = (r != 0u && q < d) ;

    // d | n.
    if (r == 0u)
    {
        n_ = q ;     /*  Divide d out of n. */

        if (new_d)  /*  New prime factor. */
        {
		    PrimeFactor<IntType> f( d, 1u ) ;
			factor_.push_back( f ) ;

            new_d = false ;
            #ifdef DEBUG_PP_FACTOR
                cout << "after dividing out new prime divisor d = " << d << " n =" << n_ << endl ;
            #endif
         }
         else
         {
             ++factor_[ factor_.size() - 1 ].count_ ; //  Same divisor again.  Increment its count.

            #ifdef DEBUG_PP_FACTOR
                cout << "after dividing out repeated factor d = " << d << " n =" << n_ << endl ;
            #endif
         }
    }
    else {
        d += (flag ? 2u : 4u) ;  /* d did not divide n.  Try a new divisor. */
        flag = !flag ;
        new_d = true ;

        #ifdef DEBUG_PP_FACTOR
            cout << "next trial divisor d  = " << d << endl ;
        #endif
    }

} while ( !n_is_prime && (n_ != 1u)) ;

if (n_ == 1u)       /*  All factors were divided out. */
{
    numFactors_ = factor_.size() ;
    return ;
}
else
{  //  Current value of n is prime.  It is the last prime factor.
    PrimeFactor<IntType> f( n_, 1u ) ;
    factor_.push_back( f ) ;
    numFactors_ = factor_.size() ;
    return ;
}

} /* ========================= end of function factor ======================= */




template <typename IntType>
Factor<IntType>::~Factor()
{
   // Do nothing.
}


template <typename IntType>
Factor<IntType>::Factor( const Factor<IntType> & f )
        : n_( f.n_ )
		, factor_( f.factor_ )
		, numFactors_( f.numFactors_ )
        , statistics_( f.statistics_ )
{
}

// Assignment operator.
template <typename IntType>
Factor<IntType> & Factor<IntType>::operator=( const Factor<IntType> & g )
{
	// If assigned to itself, return the object g.
    if (this == &g)
        return *this ;
		
	// TODO make a safe copy.
    n_          = g.n_ ;
	factor_     = g.factor_ ;
	numFactors_ = g.numFactors_ ;
    statistics_ = g.statistics_ ;
	
    // Return a reference to assigned object to make chaining possible.
    return *this ;
}


template <typename IntType>
IntType Factor<IntType>::operator[]( uint i ) const
{
    return factor_[ i ].prime_ ;
}


// Return the number of distinct factors.
template <typename IntType>
uint Factor<IntType>::num() const
{
    return numFactors_ ;
}


// Return the count for the ith prime factor.
// TODO range check.
template <typename IntType>
IntType Factor<IntType>::count( uint i ) const
{
    return factor_[ i ].count_ ;
}



/*
      4
Phi[ 5  - 1 ]

   4              4
  5  - 1 = 624 = 2  3  13

  Phi = 624 (1 - 1/2) (1 - 1/3)(1 - 1/13) = 192



  Handle special cases.

  Warning: can take a long time due to factorization.
  */

template <typename IntType>
IntType Factor<IntType>::EulerPhi()
{
	// Compute Euler phi[ n ] =
	//
	//      num prime factors
	//        -------
	//     n   |  |   (1 - 1/p )
	//         i = 1          i
    //
    IntType phi = 1u ;
	for (uint i = 0u ;  i < numFactors_ ; ++i)
        for (uint j = 0u ;  j < factor_[ i ].count_ ; ++j)
		    phi *= factor_[ i ].prime_ ;

	for (uint i = 0u ;  i < numFactors_ ; ++i)
	{
		phi *= (factor_[ i ].prime_ - static_cast<IntType>( 1u )) ;
        phi /=  factor_[ i ].prime_ ;
	}

	return phi ;
}


/*==============================================================================
|                             is_probably_prime                                |
================================================================================

DESCRIPTION

     Test whether the number n is probably prime.  If n is composite
     we are correct always.  If n is prime, we will be wrong no more
     than about 1/4 of the time on average, probably less for
     any x and n.

INPUT

     n      (int, n >= 0)    Number to test for primality.
     x      (int, 1 < x < n for n > 6) A random integer.

RETURNS

     true    If n is probably prime.

     false   If n is definitely not prime or n < 0,
             or x is out of range.


METHOD

     Miller-Rabin probabilistic primality test, described by Knuth.

     If
                   k
         n = 1 + 2  q

     is prime and
           q
          x  mod n != 1

     the sequence
                                         k
            q          2q               2 q
         { x  mod n, x    mod n, ..., x     mod n}

     will end with 1 and the element in the sequence just before
     1 first appears = n-1, since

          2
         y = 1 (mod p)

     satisfies y = +1 or y = -1 only. The probability the algorithm fails is
     bounded above by about 1/4 for all n.

EXAMPLE

     If k = 5, q = 3 then n = 1 + 2^5 3 = 97, which is prime.  
     
     For x = 10, we get                    For x = 9, we get

      q                                   q  
     x      =   30                       x     =  50

         1                                   1
      q 2                                 q 2
     x      =   27                       x     = 75

         2                                   2
      q 2                                 q 2
     x      =   50                       x     =  96

         3                                   3
      q 2                                 q 2
     x      =   75                       x     = 1

         4                                   4
      q 2                                 q 2
     x      =   96                       x     = 1

         5                                   5
      q 2                                 q 2
     x      =    1                       x     =  1


     If k = 4, q = 3 then n = 1 + 2^4 3 = 49, which is composite.  
     
     For x = 10, we get

      q
     x      =   20

         1
      q 2
     x      =   8

         2
      q 2
     x      =   15

         3       
      q 2       
     x      =  29

         4      
      q 2      
     x      =  8
     

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

template <typename IntType>
bool is_probably_prime( const IntType & n, const IntType & x )
{
//  Not prime if input is out of range.
if (n < static_cast<IntType>( 0u ))
    return false ;

// Small composite numbers.
if (n == static_cast<IntType>( 0u ) || n == static_cast<IntType>( 1u ) || n == static_cast<IntType>( 4u ))
    return false ;

// Small primes.
if (n == static_cast<IntType>( 2u ) || n == static_cast<IntType>( 3u ) || n == static_cast<IntType>( 5u ))
    return true ;

// Composites aren't prime.
if (n % static_cast<IntType>( 2u ) == static_cast<IntType>( 0u ) ||
    n % static_cast<IntType>( 3u ) == static_cast<IntType>( 0u ) ||
    n % static_cast<IntType>( 5u ) == static_cast<IntType>( 0u ))
    return false ;

// Return not prime if x is out of range. 
if (x <= static_cast<IntType>( 1u ) || x >= n)
    return false ;

// Factor out powers of 2 to get n = 1 + 2^k q, q odd.
IntType nm1 = n - static_cast<IntType>( 1u ) ;
IntType k   = static_cast<IntType>( 0u ) ;

while( nm1 % static_cast<IntType>( 2u ) == static_cast<IntType>( 0u ))
{
	nm1 /= static_cast<IntType>( 2u ) ;
	++k ;
}

IntType q = nm1 ;

#ifdef PP_PRIMALITY_DEBUG
cout << "Miller-Rabin primality test" << endl ;
cout << "    q = " << q << endl ;
#endif

//  y = x^q (mod n)
PowerMod<IntType> power_mod( n ) ;
IntType y = power_mod( x, q ) ;

#ifdef PP_PRIMALITY_DEBUG
cout << "    x^q = " << y << endl ;
#endif

for (IntType j = 0u ;  j < k ;  ++j)
{
    if ( (j == static_cast<IntType>( 0u ) && y == static_cast<IntType>( 1u )) || (y == n - static_cast<IntType>( 1u )))
		return true ;
	else if (j > static_cast<IntType>( 0u ) && y == static_cast<IntType>( 1 ))
		return false ;

	// Compute y^2 (mod n)
    y = power_mod( y, static_cast<IntType>( 2u ) ) ;

    #ifdef PP_PRIMALITY_DEBUG
    cout << "    x ^ (2^ " << j << " j q) = " << y << endl ;
    #endif
}

/*  Shouldn't get here, but do it anyway for safety. */
return false ;

} /* =============== end of function is_probably_prime ===================== */



/*==============================================================================
|                           is_almost_surely_prime                             |
================================================================================

DESCRIPTION

     Test whether the number n is almost surely prime.  If n is
     composite, we always return NO.  If n is prime, the
     probability of returning YES successfully is

                 NUM_PRIME_TEST_TRIALS
        1 - (1/4)

INPUT

     n      (int, n >= 0)

RETURNS


     YES    If n is probably prime with a very high degree of
            probability.
     NO     If n is definitely not prime.
	 -1     If inputs are out of range.

EXAMPLE

METHOD

    Use the Miller-Rabin probabilitic primality test for lots of
    random integers x.  If the test shows n is composite for any
    given x, is is non-prime for sure.

    But if n is prime, P( failure | n=prime ) <= 1/4, on each
    trial, so if the random numbers are independent,

                                   NUM_PRIME_TEST_TRIALS 
    P( failure | n=prime ) <= (1/4)

    for 25 trials, P <= 0.8817841970012523e-16
    and for 14 trials, P <= 3.7252902984619141e-09

TODO

    The system pseudorandom number generator needs to be a good one
    (i.e. passes the spectral test and other statistical tests).

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

template <typename IntType>
bool is_almost_surely_prime( const IntType & n )
{

/*------------------------------------------------------------------------------
|                               Local Variables                                |
------------------------------------------------------------------------------*/

IntType
    trial = 0u,
    x     = 3u ;

const uint NUM_PRIME_TEST_TRIALS = 14u ; 

/*------------------------------------------------------------------------------
|                                Function Body                                 |
------------------------------------------------------------------------------*/

/* Seed the random-number generator. */
srand( 314159u );

for (trial = static_cast<IntType>( 1u ) ;  trial <= static_cast<IntType>( NUM_PRIME_TEST_TRIALS ) ;  ++trial)
{
    /*  Generate a new random integer such that 1 < x < n. */
    x = static_cast<IntType>( rand() ) % n ;
	
	// Clip away from 1.
    if (x <= static_cast<IntType>( 1u )) 
	    x = static_cast<IntType>( 3u ) ;

	/* Definitely not prime. */
	if (is_probably_prime( n, x ) == false)
		return false ;
}

/* Almost surely prime because it passed the probably prime test
 * above many times.
 */
return true ;

} // ============== end of function is_almost_surely_prime ================





/*==============================================================================
|                                    skip_test                                 |
================================================================================

DESCRIPTION

     Make the test p  | (p - 1).
                    i

INPUT

    i      (int)       ith prime divisor of r.

    primes (bigint *)  Array of distict prime factors of r.  primes[ i ] = p
                                                                            i
    p      (int)        p >= 2.

RETURNS

    true    if the test succeeds for some i.
    false   otherwise

EXAMPLE

    Suppose i = 0, primes[ 0 ] = 2 and p = 5.  Return true since 2 | 5-1.

METHOD

    Test if (p - 1) mod p = 0 for all i.
                         i
--------------------------------------------------------------------------------
|                                Function Call                                 |
------------------------------------------------------------------------------*/
template <typename IntType>
bool Factor<IntType>::skip_test( int p, int i ) const
{

// p  cannot divide the smaller number (p-1)
//  i
if ( static_cast<IntType>( p-1 ) < static_cast<IntType>( factor_[ i ].prime_ ) )
    return false ;
else
    return( ( static_cast<IntType>(p - 1) % static_cast<IntType>( factor_[ i ].prime_ ) == static_cast<IntType>( 0u )) ? true : false ) ;

} // ====================== end of function skip_test =======================


template <typename IntType>
bool Factor<IntType>::PollardRho( const IntType & c )
{
    IntType x  = static_cast<IntType>( 5u ) ;
    IntType xp = static_cast<IntType>( 2u ) ;
    IntType k  = static_cast<IntType>( 1u ) ;
    IntType l  = static_cast<IntType>( 1u ) ;
    IntType g  = static_cast<IntType>( 0u ) ;

    bool status = true ;

#ifdef DEBUG_PP_FACTOR
	cout << "Pollard rho n = " << n_ << " c = " << c << endl ;
#endif

    // Seed 1 as a factor and early out if n == 1.
    PrimeFactor<IntType>f( 1u, 1u ) ;
    factor_.push_back( f ) ;
    numFactors_ = 1u ;

    if (n_ == 1u)
        return status ;

    while( true )
    {
        if (is_almost_surely_prime( n_ ))
        {
#ifdef DEBUG_PP_FACTOR
            cout << "    >>>>>prime factor n_ = " << n_ << endl ;
#endif
            PrimeFactor<IntType>f( n_, 1u ) ;
            factor_.push_back( f ) ;
            ++numFactors_ ;

            status = true ;
            ++statistics_.num_prime_tests ;
            goto Exit ;
        }

        while (true)
        {
            // TODO don't check gcd when k > l/2
            //if (k > l/2u)
            //    continue ;

            // TODO accumulate gcd products.

            IntType absDiff = (xp > x) ? (xp - x) : (x - xp) ;
            g = gcd( absDiff, n_ ) ;
            ++statistics_.num_gcds ;

#ifdef DEBUG_PP_FACTOR
            cout << "    inner while loop, gcd = g = " << g << " |x -xp| = " << absDiff << " n_ = " << n_
                 << " k = " << k << " l = " << l << endl ;
#endif
            if  (g == 1u)
            {
                --k ;
                if (k == 0u)
                {
                    xp = x ;
                    l = l * 2u ;
                    k = l ;
                }
                x = (x * x + c) % n_ ;
                ++statistics_.num_squarings ;
            } 
            else if (g == n_)
            {
#ifdef DEBUG_PP_FACTOR
                cout << "    failure:  g equals non-prime n_ = " << n_ << endl ;
#endif
                status = false ;
                goto Exit ;
            }
            else if (is_almost_surely_prime( g ))
            {
#ifdef DEBUG_PP_FACTOR
                cout << "    >>>>>prime factor g = " << g << endl ;
#endif
                PrimeFactor<IntType> f( g, 1u ) ;
                factor_.push_back( f ) ;
                ++numFactors_ ;

                ++statistics_.num_prime_tests ;
            }
            else
            {
#ifdef DEBUG_PP_FACTOR
                cout << "    g = " << g << " isn't prime " << endl ;
#endif
                status = false ;
                goto Exit ;
            }

            n_ /= g ;
            x = x % n_ ;
            xp = xp % n_ ;

#ifdef DEBUG_PP_FACTOR
            cout << "    after division, n_ = " << n_ << " x = " << x << " xp = " << xp << endl ;
#endif
            break ;
        } // end gcd loop
    }


Exit:	
    return status ;
}

/*==============================================================================
|                     Forced Template Instantiations                           |
==============================================================================*/

// C++ doesn't automatically generate templated classes or functions unless
// we USE them on particular data types.

template Factor<uint>::Factor( const uint, FactoringAlgorithm ) ;
template Factor<BigInt>::Factor( const BigInt, FactoringAlgorithm ) ;

template Factor<uint>::~Factor() ;
template Factor<BigInt>::~Factor() ;

template Factor<uint>::Factor( const Factor<uint> & f ) ;
template Factor<BigInt>::Factor( const Factor<BigInt> & f ) ;
		
template Factor<uint> & Factor<uint>::operator=( const Factor<uint> & g ) ;
template Factor<BigInt> & Factor<BigInt>::operator=( const Factor<BigInt> & g ) ;

// We already specialized bool Factor<uint>::factorTable() and bool Factor<BigInt>::factorTable().

template void Factor<uint>::trialDivision() ;
template void Factor<BigInt>::trialDivision() ;

template bool Factor<uint>::PollardRho( const uint & c ) ;
template bool Factor<BigInt>::PollardRho( const BigInt & c ) ;

template uint Factor<uint>::num() const ;
template uint Factor<BigInt>::num() const ;

template uint Factor<uint>::operator[]( uint ) const ;
template BigInt Factor<BigInt>::operator[]( uint ) const ;

template uint Factor<uint>::count( uint ) const ;
template BigInt Factor<BigInt>::count( uint ) const ;

template uint Factor<uint>::EulerPhi() ;
template BigInt Factor<BigInt>::EulerPhi() ;

template bool is_probably_prime( const uint &, const uint & ) ;
template bool is_probably_prime( const BigInt &, const BigInt & ) ;

template bool is_almost_surely_prime( const uint & ) ;
template bool is_almost_surely_prime( const BigInt & ) ;

template bool Factor<int>::skip_test( int p, int i ) const ;
template bool Factor<BigInt>::skip_test( int p, int i ) const ;