Loading...
Searching...
No Matches
fac_univar.cc
Go to the documentation of this file.
/* emacs edit mode for this file is -*- C++ -*- */
#include "config.h"
#include "cf_assert.h"
#include "debug.h"
#include "timing.h"
#include "cf_defs.h"
#include "cf_algorithm.h"
#include "fac_util.h"
#include "fac_univar.h"
#include "fac_cantzass.h"
#include "fac_berlekamp.h"
#include "cf_iter.h"
#include "cf_primes.h"
#include "fac_sqrfree.h"
#include "cfUnivarGcd.h"
#ifdef HAVE_FLINT
#include "FLINTconvert.h" // for __FLINT_RELEASE
#endif
#if !defined(HAVE_NTL)
TIMING_DEFINE_PRINT(fac_choosePrimes)
TIMING_DEFINE_PRINT(fac_facModPrimes)
TIMING_DEFINE_PRINT(fac_liftFactors)
TIMING_DEFINE_PRINT(fac_combineFactors)
const int max_fp_fac = 3;
STATIC_INST_VAR modpk theModulus;
#ifdef DEBUGOUTPUT
#define DEBOUTHPRINT(stream, msg, hg) \
{std::stream << deb_level_msg << msg, std::stream.flush(); hprint( hg ); std::stream << std::endl;}
static void
hprint ( int * a )
{
int n = a[0];
std::cerr << "( " << n << ": ";
int i = 1;
while ( i < n ) {
if ( a[i] != 0 )
std::cerr << i << " ";
i++;
}
std::cerr << ")";
}
#else /* DEBUGOUTPUT */
#define DEBOUTHPRINT(stream, msg, hg)
#endif /* DEBUGOUTPUT */
static void
hgroup ( int * a )
{
int n = a[0];
int i, j, k;
for ( i = 1; i < n; i++ )
if ( a[i] != 0 )
for ( j = 1; j <= i; j++ )
if ( a[j] != 0 )
for ( k = i; k < n; k += j )
a[k] = 1;
}
static void
hintersect( int * a, const int * const b )
{
int i, n, na = a[0], nb = b[0];
if ( nb < na )
n = nb;
else
n = na;
for ( i = 1; i < n; i++ )
if ( b[i] == 0 )
a[i] = 0;
a[0] = n;
}
/*
static int
hcount ( const int * const a )
{
int n = a[0], sum = 0, i;
for ( i = 1; i < n; i++ )
if ( a[i] != 0 ) sum++;
return sum;
}
*/
static void
initHG ( int * a, const CFFList & F )
{
ListIterator<CFFactor> i;
int n = a[0], k;
for ( int j = 1; j < n; j++ ) a[j] = 0;
for ( i = F; i.hasItem(); i++ )
if ( (k = i.getItem().factor().degree()) < n )
{
if ( k == -1 ) {
STICKYWARN( k == -1, "there occured an error. factory was not able to factorize\n"
"correctly mod p. Please send the example which caused\n"
"this error to the authors. Nonetheless we will go on with the\n"
"calculations hoping the result will be correct. Thank you." );
}
else if ( k != 0 )
a[k] = 1;
}
}
static void
initHG ( int * a, const Array<CanonicalForm> & F )
{
int i, n = a[0], m = F.size(), k;
for ( i = 1; i < n; i++ ) a[i] = 0;
for ( i = 1; i < m; i++ )
if ( (k = F[i].degree()) < n )
{
if ( k == -1 )
{
STICKYWARN( k == -1, "there occured an error. factory was not able to factorize\n"
"correctly mod p. Please send the example which caused\n"
"this error to the authors. Nonetheless we will go on with the\n"
"calculations hoping the result will be correct. Thank you." );
}
else if ( k != 0 )
a[k] = 1;
}
}
static int cmpFactor( const CFFactor & a, const CFFactor & b )
{
CFFactor A( a ), B( b );
return degree( A.factor() ) > degree( B.factor() );
}
//static double cf2double ( const CanonicalForm & f )
//{
// CanonicalForm a = f, q, r;
// double m = 1, res = 0;
// if ( a.sign() < 0 ) a = -a;
// while ( ! a.isZero() ) {
// divrem( a, 10, q, r );
// res += m * (double)(r.intval());
// m *= 10;
// a = q;
// }
// if ( f.sign() < 0 ) res = -res;
// return res;
//}
//{{{ static int kBound ( const CanonicalForm & f, int p )
//{{{ docu
//
// kBound() - return bound of coefficients of factors of f.
//
// The bound is returned as an integer k such that p^k is larger
// than all coefficients of all possible factors of f. f should
// be an univariate polynomial over Z.
//
// For a discussion of the formula, see the article Mignotte -
// 'Some Usefull Bounds' in Buchberger, Collins, Loos (eds.) -
// 'Computer Algebra: Symbolic and Algebraic Computation', 2nd
// ed.
//
// Use by ZFactorizeUnivariate().
//
//}}}
static int
kBound ( const CanonicalForm & f, int p )
{
return (int)(f.degree() + (double)(ilog2( euclideanNorm(f)+1 ) + 1) / (double)ilog2(p)) + 1;
}
//}}}
modpk
getZFacModulus()
{
return theModulus;
}
static bool
liftDegreeFactRec( CFArray & theFactors, CanonicalForm & F, const CanonicalForm & recip_lf, const CanonicalForm & f, const modpk & pk, int i, int d, CFFList & ZF, int exp )
{
if ( i >= theFactors.size() )
return false;
else if ( degree( f ) + degree( theFactors[i] ) == d ) {
DEBOUTLN( cerr, "ldfr (f) = " << f );
DEBOUTLN( cerr, "ldfr (g) = " << theFactors[i] );
CanonicalForm g = pp( pk( recip_lf * f * theFactors[i] ) );
DEBOUTLN( cerr, "ldfr (pk(f*g)) = " << g );
CanonicalForm gg, hh;
DEBOUTLN( cerr, "F = " << F );
DEBOUTLN( cerr, "g = " << g );
if ( divremt( F, g, gg, hh ) && hh.isZero() ) {
ZF.append( CFFactor( g, exp ) );
F = gg;
theFactors[i] = 1;
return true;
}
else {
return liftDegreeFactRec( theFactors, F, recip_lf, f, pk, i+1, d, ZF, exp );
}
}
else if ( degree( f ) + degree( theFactors[i] ) > d )
return false;
else {
bool ok = liftDegreeFactRec( theFactors, F, recip_lf, pk( recip_lf * f * theFactors[i] ), pk, i+1, d, ZF, exp );
if ( ok )
theFactors[i] = 1;
else
ok = liftDegreeFactRec( theFactors, F, recip_lf, f, pk, i+1, d, ZF, exp );
return ok;
}
}
bool isSqrFreeZ ( const CanonicalForm & f )
{
return gcd( f, f.deriv() ).degree() == 0;
}
bool isSqrFreeFp( const CanonicalForm & f )
{
CFFList F = sqrFreeFp( f );
return ( F.length() == 1 && F.getFirst().exp() == 1 );
}
bool isSqrFree ( const CanonicalForm & f )
{
// ASSERT( f.isUnivariate(), "multivariate factorization not implemented" );
if ( getCharacteristic() == 0 )
return isSqrFreeZ( f );
else
return isSqrFreeFp( f );
}
static int choosePrimes ( int * p, const CanonicalForm & f )
{
int ptr = 0;
int i = 0;
int maxp = cf_getNumPrimes();
int prime;
while ( ptr < maxp && i < max_fp_fac )
{
prime = cf_getPrime( ptr );
if ( mod( lc( f ), prime ) != 0 )
{
setCharacteristic( prime );
if ( isSqrFree( mapinto( f ) ) )
{
p[i] = prime;
i++;
}
setCharacteristic( 0 );
}
ptr++;
}
return ( i == max_fp_fac );
}
static int
UnivariateQuadraticLift ( const CanonicalForm &F, const CanonicalForm & G, const CanonicalForm &H, const modpk & pk, const CanonicalForm & /*Gamma*/, CanonicalForm & gk, CanonicalForm & hk )
{
CanonicalForm lf, f, gamma;
CanonicalForm a, b, aa, bb, c, g, h, g1, h1, e, modulus, tmp, q, r;
int i, j, save;
int p = pk.getp(), k = pk.getk();
int no_iter = SI_LOG2(k)+2;
int * kvals = new int[no_iter];
DEBOUTLN( cerr, "quadratic lift called with p = " << p << " and k = " << k );
for ( j = 0, i = k; i > 1; i = ( i+1 ) / 2, j++ ) kvals[j] = i;
kvals[j] = 1;
save = getCharacteristic(); setCharacteristic( 0 );
lf = lc( F );
f = lf * F;
{
setCharacteristic( p );
g1 = mapinto( lf ) / lc( G ) * G;
h1 = mapinto( lf ) / lc( H ) * H;
(void)extgcd( g1, h1, a, b );
setCharacteristic( 0 );
}
a = mapinto( a ); b = mapinto( b );
g = mapinto( g1 ); h = mapinto( h1 );
g = replaceLc( g, lf ); h = replaceLc( h, lf );
e = f - g * h;
modulus = p;
i = 1;
while ( ! e.isZero() && j > 0 ) {
c = e / modulus;
{
j--;
setCharacteristic( p, kvals[j+1]);
DEBOUTLN( cerr, "lifting from p^" << kvals[j+1] << " to p^" << kvals[j] );
c = mapinto( c );
DEBOUTLN( cerr, " !!! g = " << mapinto( g ) );
g1 = mapinto( lf ) / mapinto( lc( g ) ) * mapinto( g );
h1 = mapinto( lf ) / mapinto( lc( h ) ) * mapinto( h );
// (void)extgcd( g1, h1, a, b );
// DEBOUTLN( cerr, " a = " << aa );
// DEBOUTLN( cerr, " b = " << bb );
a = mapinto( a ); b = mapinto( b );
a += ( ( 1 - a * g1 ) * a ) % h1;
b += ( ( 1 - b * h1 ) * b ) % g1;
DEBOUTLN( cerr, " a = " << a );
DEBOUTLN( cerr, " b = " << b );
divrem( a * c, h1, q, r );
tmp = b * c + q * g1;
setCharacteristic( 0 );
}
a = mapinto( a ); b = mapinto( b );
g += mapinto( tmp ) * modulus;
h += mapinto( r ) * modulus;
// g = replaceLc( g, lf ); h = replaceLc( h, lf );
e = f - g * h;
modulus = power( CanonicalForm(p), kvals[j] );
if ( mod( f - g * h, modulus ) != 0 ) {
DEBOUTLN( cerr, "error at lift stage " << i );
}
i++;
}
if ( e.isZero() ) {
tmp = content( g );
gk = g / tmp; hk = h / ( lf / tmp );
}
else {
gk = pk(g); hk = pk(h);
}
setCharacteristic( save );
delete [] kvals;
return e.isZero();
}
static int
UnivariateLinearLift ( const CanonicalForm &F, const CanonicalForm & G, const CanonicalForm &H, const modpk & pk, const CanonicalForm & /*Gamma*/, CanonicalForm & gk, CanonicalForm & hk )
{
CanonicalForm lf, f, gamma;
CanonicalForm a, b, c, g, h, g1, h1, e, modulus, tmp, q, r;
int i, save;
int p = pk.getp(), k = pk.getk();
save = getCharacteristic(); setCharacteristic( 0 );
lf = lc( F );
f = lf * F;
{
setCharacteristic( p );
g1 = mapinto( lf ) / lc( G ) * G;
h1 = mapinto( lf ) / lc( H ) * H;
(void)extgcd( g1, h1, a, b );
setCharacteristic( 0 );
}
g = mapinto( g1 ); h = mapinto( h1 );
g = replaceLc( g, lf ); h = replaceLc( h, lf );
e = f - g * h;
modulus = p;
i = 1;
while ( ! e.isZero() && i <= k ) {
c = e / modulus;
{
setCharacteristic( p );
c = mapinto( c );
divrem( a * c, h1, q, r );
tmp = b * c + q * g1;
setCharacteristic( 0 );
}
g += mapinto( tmp ) * modulus;
h += mapinto( r ) * modulus;
// g = replaceLc( g, lf ); h = replaceLc( h, lf );
e = f - g * h;
modulus *= p;
ASSERT( mod( f - g * h, modulus ) == 0, "error at lift stage" );
i++;
}
if ( e.isZero() ) {
tmp = content( g );
gk = g / tmp; hk = h / ( lf / tmp );
}
else {
gk = pk(g); hk = pk(h);
}
setCharacteristic( save );
// return e.isZero();
return (F-gk*hk).isZero();
}
CFFList
ZFactorizeUnivariate( const CanonicalForm& ff, bool issqrfree )
{
bool symmsave = isOn( SW_SYMMETRIC_FF );
CanonicalForm cont = content( ff );
CanonicalForm lf, recip_lf, fp, f, g = ff / cont, dummy1, dummy2;
int i, k, exp, n;
bool ok;
CFFList H, F[max_fp_fac];
CFFList ZF;
int * p = new int [max_fp_fac];
int * D = 0;
int * Dh = 0;
ListIterator<CFFactor> J, I;
DEBINCLEVEL( cerr, "ZFactorizeUnivariate" );
On( SW_SYMMETRIC_FF );
// get squarefree decomposition of f
if ( issqrfree )
H.append( CFFactor( g, 1 ) );
else
H = sqrFree( g );
DEBOUTLN( cerr, "H = " << H );
// cycle through squarefree factors of f
for ( J = H; J.hasItem(); ++J ) {
f = J.getItem().factor();
if ( f.inCoeffDomain() ) continue;
n = f.degree() / 2 + 1;
delete [] D;
delete [] Dh;
D = new int [n]; D[0] = n;
Dh = new int [n]; Dh[0] = n;
exp = J.getItem().exp();
// choose primes to factor f
TIMING_START(fac_choosePrimes);
ok = choosePrimes( p, f );
TIMING_END_AND_PRINT(fac_choosePrimes, "time to choose the primes: ");
if ( ! ok ) {
DEBOUTLN( cerr, "warning: no good prime found to factorize " << f );
STICKYWARN( ok, "there occured an error. We went out of primes p\n"
"to factorize mod p. Please send the example which caused\n"
"this error to the authors. Nonetheless we will go on with the\n"
"calculations hoping the result will be correct. Thank you.");
ZF.append( CFFactor( f, exp ) );
continue;
}
// factorize f modulo certain primes
TIMING_START(fac_facModPrimes);
for ( i = 0; i < max_fp_fac; i++ ) {
setCharacteristic( p[i] );
fp = mapinto( f );
F[i] = FpFactorizeUnivariateCZ( fp, true, 0, Variable(), Variable() );
// if ( p[i] < 23 && fp.degree() < 10 )
// F[i] = FpFactorizeUnivariateB( fp, true );
// else
// F[i] = FpFactorizeUnivariateCZ( fp, true, 0, Variable, Variable() );
DEBOUTLN( cerr, "F[i] = " << F[i] << ", p = " << p[i] );
}
TIMING_END_AND_PRINT(fac_facModPrimes, "time to factorize mod primes: ");
setCharacteristic( 0 );
// do some strange things with the D's
initHG( D, F[0] );
hgroup( D );
DEBOUTHPRINT( cerr, "D = ", D );
for ( i = 1; i < max_fp_fac; i++ ) {
initHG( Dh, F[i] );
hgroup( Dh );
DEBOUTHPRINT( cerr, "Dh = ", Dh );
hintersect( D, Dh );
DEBOUTHPRINT( cerr, "D = ", D );
}
// look which p gives the shortest factorization of f mod p
// j: index of that p in p[]
int min, j;
min = F[0].length(), j = 0;
for ( i = 1; i < max_fp_fac; i++ ) {
if ( min >= F[i].length() ) {
j = i; min = F[i].length();
}
}
k = kBound( f, p[j] );
CFArray theFactors( F[j].length() );
// pk = power( CanonicalForm( p[j] ), k );
// pkhalf = pk / 2;
modpk pk( p[j], k );
DEBOUTLN( cerr, "coeff bound = " << pk.getpk() );
theModulus = pk;
setCharacteristic( p[j] );
fp = mapinto( f );
F[j].sort( cmpFactor );
I = F[j]; i = 0;
TIMING_START(fac_liftFactors);
while ( I.hasItem() ) {
DEBOUTLN( cerr, "factor to lift = " << I.getItem().factor() );
if ( isOn( SW_FAC_QUADRATICLIFT ) )
ok = UnivariateQuadraticLift( f, I.getItem().factor(), fp / I.getItem().factor(), pk, lc( f ), dummy1, dummy2 );
else
ok = UnivariateLinearLift( f, I.getItem().factor(), fp / I.getItem().factor(), pk, lc( f ), dummy1, dummy2 );
if ( ok ) {
// should be done in a more efficient way
DEBOUTLN( cerr, "dummy1 = " << dummy1 );
DEBOUTLN( cerr, "dummy2 = " << dummy2 );
f = dummy2;
fp /= I.getItem().factor();
ZF.append( CFFactor( dummy1, exp ) );
I.remove( 0 );
I = F[j];
i = 0;
DEBOUTLN( cerr, "F[j] = " << F[j] );
}
else {
DEBOUTLN( cerr, "i = " << i );
DEBOUTLN( cerr, "dummy1 = " << dummy1 );
setCharacteristic( 0 );
// theFactors[i] = pk( dummy1 * pk.inverse( lc( dummy1 ) ) );
theFactors[i] = pk( dummy1 );
setCharacteristic( p[j] );
i++;
I++;
}
}
TIMING_END_AND_PRINT(fac_liftFactors, "time to lift the factors: ");
DEBOUTLN( cerr, "ZF = " << ZF );
initHG( Dh, theFactors );
hgroup( Dh );
DEBOUTHPRINT( cerr, "Dh = ", Dh );
hintersect( D, Dh );
setCharacteristic( 0 );
for ( int l = i; l < F[j].length(); l++ )
theFactors[l] = 1;
DEBOUTLN( cerr, "theFactors = " << theFactors );
DEBOUTLN( cerr, "f = " << f );
DEBOUTLN( cerr, "p = " << pk.getp() << ", k = " << pk.getk() );
DEBOUTHPRINT( cerr, "D = ", D );
lf = lc( f );
(void)bextgcd( pk.getpk(), lf, dummy1, recip_lf );
DEBOUTLN( cerr, "recip_lf = " << recip_lf );
TIMING_START(fac_combineFactors);
for ( i = 1; i < D[0]; i++ )
if ( D[i] != 0 )
while ( liftDegreeFactRec( theFactors, f, recip_lf, lf, pk, 0, i, ZF, exp ) );
if ( degree( f ) > 0 )
ZF.append( CFFactor( f, exp ) );
TIMING_END_AND_PRINT(fac_combineFactors, "time to combine the factors: ");
}
// brush up our result
if ( ZF.getFirst().factor().inCoeffDomain() )
ZF.removeFirst();
if ( lc( ff ).sign() < 0 )
ZF.insert( CFFactor( -cont, 1 ) );
else
ZF.insert( CFFactor( cont, 1 ) );
delete [] D;
delete [] Dh;
delete [] p;
if ( ! symmsave )
Off( SW_SYMMETRIC_FF );
DEBDECLEVEL( cerr, "ZFactorizeUnivariate" );
return ZF;
}
#endif
FLINTconvert.h
This file defines functions for conversion to FLINT (www.flintlib.org) and back.
divrem
void divrem(const CanonicalForm &f, const CanonicalForm &g, CanonicalForm &q, CanonicalForm &r)
Definition canonicalform.cc:1032
isOn
bool isOn(int sw)
switches
Definition canonicalform.cc:1971
On
void On(int sw)
switches
Definition canonicalform.cc:1957
divremt
bool divremt(const CanonicalForm &f, const CanonicalForm &g, CanonicalForm &q, CanonicalForm &r)
Definition canonicalform.cc:1066
Off
void Off(int sw)
switches
Definition canonicalform.cc:1964
bextgcd
CanonicalForm bextgcd(const CanonicalForm &f, const CanonicalForm &g, CanonicalForm &a, CanonicalForm &b)
CanonicalForm bextgcd ( const CanonicalForm & f, const CanonicalForm & g, CanonicalForm & a,...
Definition canonicalform.cc:1722
power
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
Definition canonicalform.cc:1896
content
CanonicalForm FACTORY_PUBLIC content(const CanonicalForm &)
CanonicalForm content ( const CanonicalForm & f ).
Definition cf_gcd.cc:603
mapinto
CanonicalForm mapinto(const CanonicalForm &f)
Definition canonicalform.h:355
lc
CanonicalForm lc(const CanonicalForm &f)
Definition canonicalform.h:304
ilog2
int ilog2(const CanonicalForm &a)
Definition canonicalform.h:352
mod
CF_NO_INLINE FACTORY_PUBLIC CanonicalForm mod(const CanonicalForm &, const CanonicalForm &)
degree
int degree(const CanonicalForm &f)
Definition canonicalform.h:316
pp
CanonicalForm FACTORY_PUBLIC pp(const CanonicalForm &)
CanonicalForm pp ( const CanonicalForm & f ).
Definition cf_gcd.cc:676
CFArray
Array< CanonicalForm > CFArray
Definition canonicalform.h:397
setCharacteristic
void FACTORY_PUBLIC setCharacteristic(int c)
Definition cf_char.cc:28
CFFList
List< CFFactor > CFFList
Definition canonicalform.h:393
CFFactor
Factor< CanonicalForm > CFFactor
Definition canonicalform.h:392
getCharacteristic
int FACTORY_PUBLIC getCharacteristic()
Definition cf_char.cc:70
l
int l
Definition cfEzgcd.cc:100
m
int m
Definition cfEzgcd.cc:128
i
int i
Definition cfEzgcd.cc:132
k
int k
Definition cfEzgcd.cc:99
p
int p
Definition cfModGcd.cc:4086
g
g
Definition cfModGcd.cc:4098
fp
CanonicalForm fp
Definition cfModGcd.cc:4110
b
CanonicalForm b
Definition cfModGcd.cc:4111
extgcd
CanonicalForm extgcd(const CanonicalForm &f, const CanonicalForm &g, CanonicalForm &a, CanonicalForm &b)
CanonicalForm extgcd ( const CanonicalForm & f, const CanonicalForm & g, CanonicalForm & a,...
Definition cfUnivarGcd.cc:174
cfUnivarGcd.h
univariate Gcd over finite fields and Z, extended GCD over finite fields and Q
cf_algorithm.h
declarations of higher level algorithms.
sqrFree
CFFList FACTORY_PUBLIC sqrFree(const CanonicalForm &f, bool sort=false)
squarefree factorization
Definition cf_factor.cc:961
euclideanNorm
CanonicalForm euclideanNorm(const CanonicalForm &f)
cf_assert.h
assertions for Factory
STICKYWARN
#define STICKYWARN(expression, message)
Definition cf_assert.h:72
ASSERT
#define ASSERT(expression, message)
Definition cf_assert.h:99
cf_defs.h
factory switches.
SW_SYMMETRIC_FF
static const int SW_SYMMETRIC_FF
set to 1 for symmetric representation over F_q
Definition cf_defs.h:33
SW_FAC_QUADRATICLIFT
static const int SW_FAC_QUADRATICLIFT
Definition cf_defs.h:53
cf_iter.h
Iterators for CanonicalForm's.
cf_getPrime
int cf_getPrime(int i)
Definition cf_primes.cc:14
cf_getNumPrimes
int cf_getNumPrimes()
Definition cf_primes.cc:23
cf_primes.h
access to prime tables
f
FILE * f
Definition checklibs.c:9
Array
Definition ftmpl_array.h:18
Array::size
int size() const
Definition ftmpl_array.cc:92
CanonicalForm
factory's main class
Definition canonicalform.h:86
CanonicalForm::isZero
CF_NO_INLINE bool isZero() const
CanonicalForm::inCoeffDomain
bool inCoeffDomain() const
Definition canonicalform.cc:122
Factor::exp
int exp() const
Definition ftmpl_factor.h:31
Factor::factor
T factor() const
Definition ftmpl_factor.h:30
ListIterator
Definition ftmpl_list.h:87
ListIterator::remove
void remove(int moveright)
Definition ftmpl_list.cc:526
ListIterator::hasItem
int hasItem()
Definition ftmpl_list.cc:439
ListIterator::getItem
T & getItem() const
Definition ftmpl_list.cc:431
List::getFirst
T getFirst() const
Definition ftmpl_list.cc:279
List::removeFirst
void removeFirst()
Definition ftmpl_list.cc:287
List::sort
void sort(int(*)(const T &, const T &))
Definition ftmpl_list.cc:339
List::length
int length() const
Definition ftmpl_list.cc:273
List::append
void append(const T &)
Definition ftmpl_list.cc:256
List::insert
void insert(const T &)
Definition ftmpl_list.cc:193
Variable
factory's class for variables
Definition factory.h:127
modpk
class to do operations mod p^k for int's p and k
Definition fac_util.h:23
modpk::getk
int getk() const
Definition fac_util.h:36
modpk::getpk
CanonicalForm getpk() const
Definition fac_util.h:38
modpk::getp
int getp() const
Definition fac_util.h:35
debug.h
functions to print debug output
DEBINCLEVEL
#define DEBINCLEVEL(stream, msg)
Definition debug.h:44
DEBOUTLN
#define DEBOUTLN(stream, objects)
Definition debug.h:49
DEBDECLEVEL
#define DEBDECLEVEL(stream, msg)
Definition debug.h:45
H
CanonicalForm H
Definition facAbsFact.cc:60
B
b *CanonicalForm B
Definition facBivar.cc:52
j
int j
Definition facHensel.cc:110
fac_berlekamp.h
fac_cantzass.h
FpFactorizeUnivariateCZ
CFFList FpFactorizeUnivariateCZ(const CanonicalForm &f, bool issqrfree, int numext, const Variable alpha, const Variable beta)
fac_sqrfree.h
squarefree part and factorization over Q, Q(a)
sqrFreeFp
CFFList sqrFreeFp(const CanonicalForm &f)
fac_univar.h
isSqrFree
bool isSqrFree(const CanonicalForm &f)
ZFactorizeUnivariate
CFFList ZFactorizeUnivariate(const CanonicalForm &ff, bool issqrfree=false)
getZFacModulus
modpk getZFacModulus()
replaceLc
CanonicalForm replaceLc(const CanonicalForm &f, const CanonicalForm &c)
Definition fac_util.cc:90
fac_util.h
operations mod p^k and some other useful functions for factorization
min
static int min(int a, int b)
Definition fast_mult.cc:268
D
#define D(A)
Definition gentable.cc:128
STATIC_INST_VAR
#define STATIC_INST_VAR
Definition globaldefs.h:10
length
static BOOLEAN length(leftv result, leftv arg)
Definition interval.cc:257
G
STATIC_VAR TreeM * G
Definition janet.cc:31
h
STATIC_VAR Poly * h
Definition janet.cc:971
exp
gmp_float exp(const gmp_float &a)
Definition mpr_complex.cc:349
sign
static int sign(int x)
Definition ring.cc:3504
SI_LOG2
static int SI_LOG2(int v)
Definition si_log2.h:6
A
#define A
Definition sirandom.c:24
timing.h
TIMING_DEFINE_PRINT
#define TIMING_DEFINE_PRINT(t)
Definition timing.h:95
TIMING_START
#define TIMING_START(t)
Definition timing.h:92
TIMING_END_AND_PRINT
#define TIMING_END_AND_PRINT(t, msg)
Definition timing.h:94
gcd
int gcd(int a, int b)
Definition walkSupport.cc:836