Macros | Functions
facFqFactorize.cc File Reference

This file implements functions for factoring a multivariate polynomial over a finite field. More...

#include "config.h"
#include "cf_assert.h"
#include "debug.h"
#include "timing.h"
#include "facFqFactorizeUtil.h"
#include "facFqFactorize.h"
#include "cf_random.h"
#include "facHensel.h"
#include "cf_irred.h"
#include "cf_map_ext.h"
#include "facSparseHensel.h"
#include "facMul.h"
#include "cfUnivarGcd.h"
#include "NTLconvert.h"

Go to the source code of this file.

Macros

#define CHAR_THRESHOLD   8
 

Functions

 TIMING_DEFINE_PRINT (fac_fq_bi_factorizer) TIMING_DEFINE_PRINT(fac_fq_hensel_lift) TIMING_DEFINE_PRINT(fac_fq_factor_recombination) TIMING_DEFINE_PRINT(fac_fq_shift_to_zero) TIMING_DEFINE_PRINT(fac_fq_precompute_leadcoeff) TIMING_DEFINE_PRINT(fac_fq_evaluation) TIMING_DEFINE_PRINT(fac_fq_recover_factors) TIMING_DEFINE_PRINT(fac_fq_preprocess_and_content) TIMING_DEFINE_PRINT(fac_fq_bifactor_total) TIMING_DEFINE_PRINT(fac_fq_luckswang) TIMING_DEFINE_PRINT(fac_fq_lcheuristic) TIMING_DEFINE_PRINT(fac_fq_content) TIMING_DEFINE_PRINT(fac_fq_check_mainvar) TIMING_DEFINE_PRINT(fac_fq_compress) static inline CanonicalForm listGCD(const CFList &L)
 
static CanonicalForm myContent (const CanonicalForm &F)
 
static CanonicalForm listGCD (const CFList &L)
 
static CanonicalForm myContent (const CanonicalForm &F, const Variable &x)
 
CanonicalForm myCompress (const CanonicalForm &F, CFMap &N)
 compress a polynomial s.t. $ deg_{x_{i}} (F) >= deg_{x_{i+1}} (F) $ and no gaps between the variables occur More...
 
CFList extFactorRecombination (const CFList &factors, const CanonicalForm &F, const CFList &M, const ExtensionInfo &info, const CFList &evaluation)
 Naive factor recombination for multivariate factorization over an extension of the initial field. No precomputed is used to exclude combinations. More...
 
CFList factorRecombination (const CanonicalForm &F, const CFList &factors, const CFList &M)
 Naive factor recombination for multivariate factorization. No precomputed is used to exclude combinations. More...
 
int liftBoundAdaption (const CanonicalForm &F, const CFList &factors, bool &success, const int deg, const CFList &MOD, const int bound)
 Lift bound adaption. Essentially an early factor detection but only the lift bound is adapted. More...
 
int extLiftBoundAdaption (const CanonicalForm &F, const CFList &factors, bool &success, const ExtensionInfo &info, const CFList &eval, const int deg, const CFList &MOD, const int bound)
 Lift bound adaption over an extension of the initial field. Essentially an early factor detection but only the lift bound is adapted. More...
 
CFList earlyFactorDetect (CanonicalForm &F, CFList &factors, int &adaptedLiftBound, bool &success, const int deg, const CFList &MOD, const int bound)
 detects factors of F at stage deg of Hensel lifting. No combinations of more than one factor are tested. Lift bound is adapted. More...
 
CFList extEarlyFactorDetect (CanonicalForm &F, CFList &factors, int &adaptedLiftBound, bool &success, const ExtensionInfo &info, const CFList &eval, const int deg, const CFList &MOD, const int bound)
 detects factors of F at stage deg of Hensel lifting. No combinations of more than one factor are tested. Lift bound is adapted. More...
 
CFList evalPoints (const CanonicalForm &F, CFList &eval, const Variable &alpha, CFList &list, const bool &GF, bool &fail)
 evaluation point search for multivariate factorization, looks for a (F.level() - 1)-tuple such that the resulting univariate polynomial has main variable Variable (1), is squarefree and its degree coincides with degree(F) and the bivariate one is primitive wrt. Variable(1), and successively evaluated polynomials have the same degree in their main variable as F has, fails if there are no valid evaluation points, eval contains the intermediate evaluated polynomials. More...
 
static int newMainVariableSearch (CanonicalForm &A, CFList &Aeval, CFList &evaluation, const Variable &alpha, const int lev, CanonicalForm &g)
 
CanonicalForm lcmContent (const CanonicalForm &A, CFList &contentAi)
 compute the LCM of the contents of A wrt to each variable occuring in A. More...
 
CFList henselLiftAndEarly (CanonicalForm &A, CFList &MOD, int *&liftBounds, bool &earlySuccess, CFList &earlyFactors, const CFList &Aeval, const CFList &biFactors, const CFList &evaluation, const ExtensionInfo &info)
 hensel Lifting and early factor detection More...
 
void gcdFreeBasis (CFFList &factors1, CFFList &factors2)
 gcd free basis of two lists of factors More...
 
CFList distributeContent (const CFList &L, const CFList *differentSecondVarFactors, int length)
 distribute content More...
 
int testFactors (const CanonicalForm &G, const CFList &uniFactors, const Variable &alpha, CanonicalForm &sqrfPartF, CFList &factors, CFFList *&bufSqrfFactors, CFList &evalSqrfPartF, const CFArray &evalPoint)
 
CFList precomputeLeadingCoeff (const CanonicalForm &LCF, const CFList &LCFFactors, const Variable &alpha, const CFList &evaluation, CFList *&differentSecondVarLCs, int lSecondVarLCs, Variable &y)
 computes a list l of length length(LCFFactors)+1 of polynomials such that prod (l)=LCF, note that the first entry of l may be non constant. Intended to be used to precompute coefficients of a polynomial f from its bivariate factorizations. More...
 
void evaluationWRTDifferentSecondVars (CFList *&Aeval, const CFList &evaluation, const CanonicalForm &A)
 evaluate a poly A with main variable at level 1 at an evaluation point in K^(n-1) wrt different second variables. If this evaluation is valid (see evalPoints) then Aeval contains A successively evaluated at this point, otherwise this entry is empty More...
 
static CanonicalForm prodEval (const CFList &l, const CanonicalForm &evalPoint, const Variable &v)
 
void checkHelper (const CanonicalForm &f1, CFList &factors1, CFList &factors2, CFList &l1, CFList &l2)
 
CFList checkOneToOne (const CFList &factors1, const CFList &factors2, CFList &factors3, const CanonicalForm &evalPoint, const Variable &x)
 check if univariate factors factors2 of factors3 coincide with univariate factors of factors1 and recombine if necessary. The recombined factors of factors1 are returned and factors3 is recombined accordingly. More...
 
CFList recombination (const CFList &factors1, const CFList &factors2, int s, int thres, const CanonicalForm &evalPoint, const Variable &x)
 recombination of bivariate factors factors1 s. t. the result evaluated at evalPoint coincides with factors2 More...
 
void factorizationWRTDifferentSecondVars (const CanonicalForm &A, CFList *&Aeval, const ExtensionInfo &info, int &minFactorsLength, bool &irred)
 
CFList conv (const CFArray &A)
 
void getLeadingCoeffs (const CanonicalForm &A, CFList *&Aeval)
 extract leading coefficients wrt Variable(1) from bivariate factors obtained from factorizations of A wrt different second variables More...
 
void sortByUniFactors (CFList *&Aeval, int AevalLength, CFList &uniFactors, CFList &biFactors, const CFList &evaluation)
 sort bivariate factors in Aeval such that their corresponding univariate factors coincide with uniFactors, uniFactors and biFactors may get recombined if necessary More...
 
CFList buildUniFactors (const CFList &biFactors, const CanonicalForm &evalPoint, const Variable &y)
 plug in evalPoint for y in a list of polys More...
 
void refineBiFactors (const CanonicalForm &A, CFList &biFactors, CFList *const &Aeval, const CFList &evaluation, int minFactorsLength)
 refine a bivariate factorization of A with l factors to one with minFactorsLength if possible More...
 
void prepareLeadingCoeffs (CFList *&LCs, CanonicalForm &A, CFList &Aeval, int n, const CFList &leadingCoeffs, const CFList &biFactors, const CFList &evaluation)
 normalize precomputed leading coefficients such that leading coefficients evaluated at evaluation in K^(n-2) equal the leading coeffs wrt Variable(1) of bivariate factors and change A and Aeval accordingly More...
 
CFList extNonMonicFactorRecombination (const CFList &factors, const CanonicalForm &F, const ExtensionInfo &info)
 
void changeSecondVariable (CanonicalForm &A, CFList &biFactors, CFList &evaluation, CFList *&oldAeval, int lengthAeval2, const CFList &uniFactors, const Variable &w)
 changes the second variable to be w and updates all relevant data More...
 
void distributeLCmultiplier (CanonicalForm &A, CFList &leadingCoeffs, CFList &biFactors, const CFList &evaluation, const CanonicalForm &LCmultipler)
 distributes a divisor LCmultiplier of LC(A,1) on the bivariate factors and the precomputed leading coefficients More...
 
void LCHeuristic (CanonicalForm &A, const CanonicalForm &LCmultiplier, CFList &biFactors, CFList *&leadingCoeffs, const CFList *oldAeval, int lengthAeval, const CFList &evaluation, const CFList &oldBiFactors)
 heuristic to distribute LCmultiplier onto factors based on the variables that occur in LCmultiplier and in the leading coeffs of bivariate factors More...
 
void LCHeuristicCheck (const CFList &LCs, const CFList &contents, CanonicalForm &A, const CanonicalForm &oldA, CFList &leadingCoeffs, bool &foundTrueMultiplier)
 checks if prod(LCs)==LC (oldA,1) and if so divides elements of leadingCoeffs by elements in contents, sets A to oldA and sets foundTrueMultiplier to true More...
 
void LCHeuristic2 (const CanonicalForm &LCmultiplier, const CFList &factors, CFList &leadingCoeffs, CFList &contents, CFList &LCs, bool &foundTrueMultiplier)
 heuristic to distribute LCmultiplier onto factors based on the contents of factors. factors are assumed to come from LucksWangSparseHeuristic. If not successful contents will contain the content of each element of factors and LCs will contain the LC of each element of factors divided by its content More...
 
void LCHeuristic3 (const CanonicalForm &LCmultiplier, const CFList &factors, const CFList &oldBiFactors, const CFList &contents, const CFList *oldAeval, CanonicalForm &A, CFList *&leadingCoeffs, int lengthAeval, bool &foundMultiplier)
 heuristic to remove LCmultiplier from a factor based on the contents of factors. factors are assumed to come from LucksWangSparseHeuristic. More...
 
void LCHeuristic4 (const CFList &oldBiFactors, const CFList *oldAeval, const CFList &contents, const CFList &factors, const CanonicalForm &testVars, int lengthAeval, CFList *&leadingCoeffs, CanonicalForm &A, CanonicalForm &LCmultiplier, bool &foundMultiplier)
 heuristic to remove factors of LCmultiplier from factors. More precisely checks if elements of contents divide LCmultiplier. Assumes LCHeuristic3 is run before it and was successful. More...
 
CFList extFactorize (const CanonicalForm &F, const ExtensionInfo &info)
 multivariate factorization over an extension of the initial field More...
 
CFList multiFactorize (const CanonicalForm &F, const ExtensionInfo &info)
 

Detailed Description

This file implements functions for factoring a multivariate polynomial over a finite field.

ABSTRACT: "Efficient Multivariate Factorization over Finite Fields" by L. Bernardin & M. Monagon. Precomputation of leading coefficients is described in "Sparse Hensel lifting" by E. Kaltofen

Author
Martin Lee

Definition in file facFqFactorize.cc.

Macro Definition Documentation

§ CHAR_THRESHOLD

#define CHAR_THRESHOLD   8

Definition at line 738 of file facFqFactorize.cc.

Function Documentation

§ buildUniFactors()

CFList buildUniFactors ( const CFList biFactors,
const CanonicalForm evalPoint,
const Variable y 
)

plug in evalPoint for y in a list of polys

Returns
returns a list of the evaluated polys, these evaluated polys are made monic
Parameters
[in]biFactorsa list of polys
[in]evalPointsome evaluation point
[in]ysome variable

Definition at line 2304 of file facFqFactorize.cc.

2306 {
2307  CFList result;
2308  CanonicalForm tmp;
2309  for (CFListIterator i= biFactors; i.hasItem(); i++)
2310  {
2311  tmp= mod (i.getItem(), y - evalPoint);
2312  tmp /= Lc (tmp);
2313  result.append (tmp);
2314  }
2315  return result;
2316 }
CF_NO_INLINE CanonicalForm mod(const CanonicalForm &, const CanonicalForm &)
Definition: cf_inline.cc:564
factory's main class
Definition: canonicalform.h:75
CanonicalForm Lc(const CanonicalForm &f)
int i
Definition: cfEzgcd.cc:123
void append(const T &)
Definition: ftmpl_list.cc:256
static void evalPoint(const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &FEval, CanonicalForm &GEval, CFGenerator &evalPoint)
return result
Definition: facAbsBiFact.cc:76

§ changeSecondVariable()

void changeSecondVariable ( CanonicalForm A,
CFList biFactors,
CFList evaluation,
CFList *&  oldAeval,
int  lengthAeval2,
const CFList uniFactors,
const Variable w 
)

changes the second variable to be w and updates all relevant data

Parameters
[in,out]Aa multivariate poly
[in,out]biFactorsbivariate factors
[in,out]evaluationevaluation point
[in,out]oldAevalold bivariate factors wrt. different second vars
[in]lengthAeval2length of oldAeval
[in]uniFactorsunivariate factors
[in]wsome variable

Definition at line 2527 of file facFqFactorize.cc.

2530 {
2531  Variable y= Variable (2);
2532  A= swapvar (A, y, w);
2533  int i= A.level();
2535  for (CFListIterator iter= evaluation; iter.hasItem(); iter++, i--)
2536  {
2537  if (i == w.level())
2538  {
2539  evalPoint= iter.getItem();
2540  iter.getItem()= evaluation.getLast();
2541  evaluation.removeLast();
2542  evaluation.append (evalPoint);
2543  break;
2544  }
2545  }
2546  for (i= 0; i < lengthAeval2; i++)
2547  {
2548  if (oldAeval[i].isEmpty())
2549  continue;
2550  if (oldAeval[i].getFirst().level() == w.level())
2551  {
2552  CFArray tmp= copy (oldAeval[i]);
2553  oldAeval[i]= biFactors;
2554  for (CFListIterator iter= oldAeval[i]; iter.hasItem(); iter++)
2555  iter.getItem()= swapvar (iter.getItem(), w, y);
2556  for (int ii= 0; ii < tmp.size(); ii++)
2557  tmp[ii]= swapvar (tmp[ii], w, y);
2558  CFArray tmp2= CFArray (tmp.size());
2560  for (int ii= 0; ii < tmp.size(); ii++)
2561  {
2562  buf= tmp[ii] (evaluation.getLast(),y);
2563  buf /= Lc (buf);
2564  tmp2[findItem (uniFactors, buf)-1]=tmp[ii];
2565  }
2566  biFactors= CFList();
2567  for (int j= 0; j < tmp2.size(); j++)
2568  biFactors.append (tmp2[j]);
2569  }
2570  }
2571 }
List< CanonicalForm > CFList
const CanonicalForm int const CFList const Variable & y
Definition: facAbsFact.cc:57
CFArray copy(const CFList &list)
write elements of list into an array
int level(const CanonicalForm &f)
factory&#39;s class for variables
Definition: factory.h:115
CFFListIterator iter
Definition: facAbsBiFact.cc:54
factory&#39;s main class
Definition: canonicalform.h:75
Array< CanonicalForm > CFArray
CanonicalForm Lc(const CanonicalForm &f)
int size() const
Definition: ftmpl_array.cc:92
CanonicalForm swapvar(const CanonicalForm &, const Variable &, const Variable &)
swapvar() - swap variables x1 and x2 in f.
Definition: cf_ops.cc:168
void removeLast()
Definition: ftmpl_list.cc:317
int j
Definition: myNF.cc:70
int status int void * buf
Definition: si_signals.h:59
int level() const
Definition: factory.h:132
T & getItem() const
Definition: ftmpl_list.cc:431
int i
Definition: cfEzgcd.cc:123
T getLast() const
Definition: ftmpl_list.cc:309
CFList tmp2
Definition: facFqBivar.cc:70
const CanonicalForm & w
Definition: facAbsFact.cc:55
int level() const
level() returns the level of CO.
void append(const T &)
Definition: ftmpl_list.cc:256
int findItem(const CFList &list, const CanonicalForm &item)
helper function
Definition: cf_map_ext.cc:37
static void evalPoint(const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &FEval, CanonicalForm &GEval, CFGenerator &evalPoint)

§ checkHelper()

void checkHelper ( const CanonicalForm f1,
CFList factors1,
CFList factors2,
CFList l1,
CFList l2 
)

Definition at line 2008 of file facFqFactorize.cc.

2010 {
2011  CanonicalForm g1= f1, g2;
2012  CFListIterator iter1= factors1, iter2= factors2;
2013  for (; iter1.hasItem(); iter1++, iter2++)
2014  {
2015  g2= gcd (g1, iter1.getItem());
2016  if (!g2.inCoeffDomain())
2017  {
2018  l1.append (iter1.getItem());
2019  l2.append (iter2.getItem());
2020  g1 /= g2;
2021  }
2022  }
2023  factors1= Difference (factors1, l1);
2024  factors2= Difference (factors2, l2);
2025 }
factory&#39;s main class
Definition: canonicalform.h:75
const CFList & factors2
T & getItem() const
Definition: ftmpl_list.cc:431
int gcd(int a, int b)
Definition: walkSupport.cc:839
void append(const T &)
Definition: ftmpl_list.cc:256
template List< Variable > Difference(const List< Variable > &, const List< Variable > &)

§ checkOneToOne()

CFList checkOneToOne ( const CFList factors1,
const CFList factors2,
CFList factors3,
const CanonicalForm evalPoint,
const Variable x 
)

check if univariate factors factors2 of factors3 coincide with univariate factors of factors1 and recombine if necessary. The recombined factors of factors1 are returned and factors3 is recombined accordingly.

Definition at line 2032 of file facFqFactorize.cc.

2034 {
2035  CFList uniFactorsOfFactors1;
2036  CFList result, result2;
2037  CFList bad1= factors2;
2038  CFListIterator iter, iter2, iter3;
2039  CanonicalForm tmp;
2040  int pos;
2041 
2042  for (iter= factors1; iter.hasItem(); iter++)
2043  {
2044  tmp= iter.getItem() (evalPoint, x);
2045  tmp /= Lc (tmp);
2046  if ((pos= findItem (factors2, tmp)))
2047  {
2048  result2.append (getItem (factors3, pos));
2049  result.append (iter.getItem());
2050  bad1= Difference (bad1, CFList (tmp));
2051  }
2052  else
2053  uniFactorsOfFactors1.append (tmp);
2054  }
2055 
2056  CFList bad2, bad3;
2057  bad2= Difference (factors1, result);
2058  bad3= Difference (factors3, result2);
2059  CFList tmp2, tmp3;
2060  CanonicalForm g1, g2, g3, g4;
2061 
2062  while (!uniFactorsOfFactors1.isEmpty())
2063  {
2064  tmp= uniFactorsOfFactors1.getFirst();
2065  checkHelper (tmp, bad1, bad3, tmp2, tmp3);
2066  g1= prod (tmp2);
2067  g2= prod (tmp3);
2068  tmp2= CFList();
2069  tmp3= CFList();
2070  checkHelper (g1, uniFactorsOfFactors1, bad2, tmp2, tmp3);
2071  g3= prod (tmp2);
2072  g4= prod (tmp3);
2073  tmp2= CFList();
2074  tmp3= CFList();
2075  do
2076  {
2077  checkHelper (g3, bad1, bad3, tmp2, tmp3);
2078  g1 *= prod (tmp2);
2079  g2 *= prod (tmp3);
2080  tmp2= CFList();
2081  tmp3= CFList();
2082  checkHelper (g1, uniFactorsOfFactors1, bad2, tmp2, tmp3);
2083  g3 *= prod (tmp2);
2084  g4 *= prod (tmp3);
2085  tmp2= CFList();
2086  tmp3= CFList();
2087  } while (!bad2.isEmpty() && !bad3.isEmpty());
2088  result.append (g4);
2089  result2.append (g2);
2090  }
2091 
2092  if (factors3.length() != result2.length())
2093  factors3= result2;
2094  return result;
2095 }
List< CanonicalForm > CFList
int isEmpty() const
Definition: ftmpl_list.cc:267
CanonicalForm getItem(const CFList &list, const int &pos)
helper function
Definition: cf_map_ext.cc:49
CFFListIterator iter
Definition: facAbsBiFact.cc:54
factory&#39;s main class
Definition: canonicalform.h:75
const CFList & factors2
CanonicalForm Lc(const CanonicalForm &f)
T getFirst() const
Definition: ftmpl_list.cc:279
void checkHelper(const CanonicalForm &f1, CFList &factors1, CFList &factors2, CFList &l1, CFList &l2)
T & getItem() const
Definition: ftmpl_list.cc:431
CFList tmp2
Definition: facFqBivar.cc:70
int length() const
Definition: ftmpl_list.cc:273
fq_nmod_poly_t prod
Definition: facHensel.cc:95
Variable x
Definition: cfModGcd.cc:4023
void append(const T &)
Definition: ftmpl_list.cc:256
int findItem(const CFList &list, const CanonicalForm &item)
helper function
Definition: cf_map_ext.cc:37
static void evalPoint(const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &FEval, CanonicalForm &GEval, CFGenerator &evalPoint)
template List< Variable > Difference(const List< Variable > &, const List< Variable > &)
return result
Definition: facAbsBiFact.cc:76

§ conv()

CFList conv ( const CFArray A)

Definition at line 2207 of file facFqFactorize.cc.

2208 {
2209  CFList result;
2210  for (int i= A.max(); i >= A.min(); i--)
2211  result.insert (A[i]);
2212  return result;
2213 }
void insert(const T &)
Definition: ftmpl_list.cc:193
int min() const
Definition: ftmpl_array.cc:98
int max() const
Definition: ftmpl_array.cc:104
int i
Definition: cfEzgcd.cc:123
return result
Definition: facAbsBiFact.cc:76

§ distributeContent()

CFList distributeContent ( const CFList L,
const CFList differentSecondVarFactors,
int  length 
)

distribute content

Returns
returns a list result of polys such that prod (result)= prod (L) but the first entry of L may be (partially) factorized and these factors are distributed onto other entries in L
Parameters
[in]Llist of polys, first entry the content to be distributed
[in]differentSecondVarFactorsfactorization wrt different second vars
[in]lengthlength ofdifferentSecondVarFactors

Definition at line 1281 of file facFqFactorize.cc.

1284 {
1285  CFList l= L;
1287 
1288  if (content.inCoeffDomain())
1289  return l;
1290 
1291  if (l.length() == 1)
1292  {
1293  CFList result;
1294  for (int i= 0; i < length; i++)
1295  {
1296  if (differentSecondVarFactors[i].isEmpty())
1297  continue;
1298  if (result.isEmpty())
1299  {
1300  result= differentSecondVarFactors[i];
1301  for (CFListIterator iter= result; iter.hasItem(); iter++)
1302  content /= iter.getItem();
1303  }
1304  else
1305  {
1306  CFListIterator iter1= result;
1307  for (CFListIterator iter2= differentSecondVarFactors[i];iter2.hasItem();
1308  iter2++, iter1++)
1309  {
1310  iter1.getItem() *= iter2.getItem();
1311  content /= iter2.getItem();
1312  }
1313  }
1314  }
1315  result.insert (content);
1316  return result;
1317  }
1318 
1319  Variable v;
1320  CFListIterator iter1, iter2;
1321  CanonicalForm tmp, g;
1322  CFList multiplier;
1323  for (int i= 0; i < length; i++)
1324  {
1325  if (differentSecondVarFactors[i].isEmpty())
1326  continue;
1327  iter1= l;
1328  iter1++;
1329 
1330  tmp= 1;
1331  for (iter2= differentSecondVarFactors[i]; iter2.hasItem();
1332  iter2++, iter1++)
1333  {
1334  if (iter2.getItem().inCoeffDomain())
1335  {
1336  multiplier.append (1);
1337  continue;
1338  }
1339  v= iter2.getItem().mvar();
1340  if (degree (iter2.getItem()) == degree (iter1.getItem(),v))
1341  {
1342  multiplier.append (1);
1343  continue;
1344  }
1345  g= gcd (iter2.getItem(), content);
1346  if (!g.inCoeffDomain())
1347  {
1348  tmp *= g;
1349  multiplier.append (g);
1350  }
1351  else
1352  multiplier.append (1);
1353  }
1354  if (!tmp.isOne() && fdivides (tmp, content))
1355  {
1356  iter1= l;
1357  iter1++;
1358  content /= tmp;
1359  for (iter2= multiplier; iter2.hasItem(); iter1++, iter2++)
1360  iter1.getItem() *= iter2.getItem();
1361  }
1362  multiplier= CFList();
1363  }
1364 
1365  l.removeFirst();
1366  l.insert (content);
1367  return l;
1368 }
List< CanonicalForm > CFList
CF_NO_INLINE bool isOne() const
CF_INLINE bool CanonicalForm::isOne, isZero () const.
Definition: cf_inline.cc:354
int isEmpty() const
Definition: ftmpl_list.cc:267
factory&#39;s class for variables
Definition: factory.h:115
CFFListIterator iter
Definition: facAbsBiFact.cc:54
factory&#39;s main class
Definition: canonicalform.h:75
g
Definition: cfModGcd.cc:4031
void insert(const T &)
Definition: ftmpl_list.cc:193
void removeFirst()
Definition: ftmpl_list.cc:287
CanonicalForm content(const CanonicalForm &)
CanonicalForm content ( const CanonicalForm & f )
Definition: cf_gcd.cc:180
T getFirst() const
Definition: ftmpl_list.cc:279
T & getItem() const
Definition: ftmpl_list.cc:431
int i
Definition: cfEzgcd.cc:123
bool fdivides(const CanonicalForm &f, const CanonicalForm &g)
bool fdivides ( const CanonicalForm & f, const CanonicalForm & g )
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:37
int length() const
Definition: ftmpl_list.cc:273
int gcd(int a, int b)
Definition: walkSupport.cc:839
void append(const T &)
Definition: ftmpl_list.cc:256
int degree(const CanonicalForm &f)
return result
Definition: facAbsBiFact.cc:76
int l
Definition: cfEzgcd.cc:94
bool inCoeffDomain() const

§ distributeLCmultiplier()

void distributeLCmultiplier ( CanonicalForm A,
CFList leadingCoeffs,
CFList biFactors,
const CFList evaluation,
const CanonicalForm LCmultipler 
)

distributes a divisor LCmultiplier of LC(A,1) on the bivariate factors and the precomputed leading coefficients

Parameters
[in,out]Asome poly
[in,out]leadingCoeffsleading coefficients
[in,out]biFactorsbivariate factors
[in]evaluationeval. point
[in]LCmultiplermultiplier

Definition at line 2574 of file facFqFactorize.cc.

2577 {
2578  CanonicalForm tmp= power (LCmultipler, biFactors.length() - 1);
2579  A *= tmp;
2580  tmp= LCmultipler;
2581  CFListIterator iter= leadingCoeffs;
2582  for (;iter.hasItem(); iter++)
2583  iter.getItem() *= LCmultipler;
2584  iter= evaluation;
2585  for (int i= A.level(); i > 2; i--, iter++)
2586  tmp= tmp (iter.getItem(), i);
2587  if (!tmp.inCoeffDomain())
2588  {
2589  for (CFListIterator i= biFactors; i.hasItem(); i++)
2590  {
2591  i.getItem() *= tmp/LC (i.getItem(), 1);
2592  i.getItem() /= Lc (i.getItem());
2593  }
2594  }
2595 }
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
CFFListIterator iter
Definition: facAbsBiFact.cc:54
factory&#39;s main class
Definition: canonicalform.h:75
const CanonicalForm int const CFList & evaluation
Definition: facAbsFact.cc:55
CanonicalForm Lc(const CanonicalForm &f)
T & getItem() const
Definition: ftmpl_list.cc:431
int i
Definition: cfEzgcd.cc:123
int length() const
Definition: ftmpl_list.cc:273
CanonicalForm LC(const CanonicalForm &f)
bool inCoeffDomain() const

§ earlyFactorDetect()

CFList earlyFactorDetect ( CanonicalForm F,
CFList factors,
int &  adaptedLiftBound,
bool &  success,
const int  deg,
const CFList MOD,
const int  bound 
)

detects factors of F at stage deg of Hensel lifting. No combinations of more than one factor are tested. Lift bound is adapted.

Returns
earlyFactorDetect returns a list of factors of F (possibly incomplete), in case of success. Otherwise an empty list.
See also
factorRecombination(), extEarlyFactorDetect()
Parameters
[in,out]Fpoly to be factored, returns poly divided by detected factors in case of success
[in,out]factorslist of factors lifted up to deg, returns a list of factors without detected factors
[in,out]adaptedLiftBoundadapted lift bound
[in,out]successindicating success
[in]degstage of Hensel lifting
[in]MODa list of powers of Variables
[in]boundinitial lift bound

Definition at line 605 of file facFqFactorize.cc.

608 {
609  CFList result;
610  CFList T= factors;
611  CanonicalForm buf= F;
612  Variable y= F.mvar();
613  Variable x= Variable (1);
614  CanonicalForm LCBuf= LC (buf, x);
615  CanonicalForm g, quot;
616  CFList M= MOD;
617  M.append (power (y, deg));
618  adaptedLiftBound= 0;
619  int d= bound;
620  int e= 0;
621  int nBuf;
622  for (CFListIterator i= factors; i.hasItem(); i++)
623  {
624  g= mulMod (i.getItem(), LCBuf, M);
625  g /= myContent (g);
626  if (fdivides (g, buf, quot))
627  {
628  result.append (g);
629  nBuf= degree (g, y) + degree (LC (g, x), y);
630  d -= nBuf;
631  e= tmax (e, nBuf);
632  buf= quot;
633  LCBuf= LC (buf, x);
634  T= Difference (T, CFList (i.getItem()));
635  }
636  }
637  adaptedLiftBound= d;
638 
639  if (adaptedLiftBound < deg)
640  {
641  if (adaptedLiftBound < degree (F) + 1)
642  {
643  if (d == 1)
644  adaptedLiftBound= tmin (e + 1, deg);
645  else
646  adaptedLiftBound= deg;
647  }
648  factors= T;
649  F= buf;
650  success= true;
651  }
652  return result;
653 }
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
const CanonicalForm int const CFList const Variable & y
Definition: facAbsFact.cc:57
static CanonicalForm bound(const CFMatrix &M)
Definition: cf_linsys.cc:460
template CanonicalForm tmax(const CanonicalForm &, const CanonicalForm &)
factory&#39;s class for variables
Definition: factory.h:115
factory&#39;s main class
Definition: canonicalform.h:75
g
Definition: cfModGcd.cc:4031
#define M
Definition: sirandom.c:24
int status int void * buf
Definition: si_signals.h:59
static CanonicalForm myContent(const CanonicalForm &F)
int i
Definition: cfEzgcd.cc:123
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
bool fdivides(const CanonicalForm &f, const CanonicalForm &g)
bool fdivides ( const CanonicalForm & f, const CanonicalForm & g )
CanonicalForm mulMod(const CanonicalForm &A, const CanonicalForm &B, const CFList &MOD)
Karatsuba style modular multiplication for multivariate polynomials.
Definition: facMul.cc:2947
Variable x
Definition: cfModGcd.cc:4023
void append(const T &)
Definition: ftmpl_list.cc:256
int degree(const CanonicalForm &f)
static jList * T
Definition: janet.cc:37
CanonicalForm LC(const CanonicalForm &f)
template List< Variable > Difference(const List< Variable > &, const List< Variable > &)
return result
Definition: facAbsBiFact.cc:76
template CanonicalForm tmin(const CanonicalForm &, const CanonicalForm &)

§ evalPoints()

CFList evalPoints ( const CanonicalForm F,
CFList eval,
const Variable alpha,
CFList list,
const bool &  GF,
bool &  fail 
)

evaluation point search for multivariate factorization, looks for a (F.level() - 1)-tuple such that the resulting univariate polynomial has main variable Variable (1), is squarefree and its degree coincides with degree(F) and the bivariate one is primitive wrt. Variable(1), and successively evaluated polynomials have the same degree in their main variable as F has, fails if there are no valid evaluation points, eval contains the intermediate evaluated polynomials.

Returns
evalPoints returns an evaluation point, which is valid if and only if fail == false.
Parameters
[in]Fa compressed poly
[in,out]evalan empty list, returns F successive evaluated
[in]alphaalgebraic variable
[in,out]lista list of points already considered, a point is encoded as a poly of degree F.level()-1 in Variable(1)
[in]GFGF?
[in,out]failindicates failure

Definition at line 740 of file facFqFactorize.cc.

742 {
743  int k= F.level() - 1;
744  Variable x= Variable (1);
745  CanonicalForm LCF=LC (F, x);
746  CFList LCFeval;
747 
748  CFList result;
749  FFRandom genFF;
750  GFRandom genGF;
751  int p= getCharacteristic ();
752  if (p < CHAR_THRESHOLD)
753  {
754  if (!GF && alpha.level() == 1)
755  {
756  fail= true;
757  return CFList();
758  }
759  else if (!GF && alpha.level() != 1)
760  {
761  if ((p == 2 && degree (getMipo (alpha)) < 6) ||
762  (p == 3 && degree (getMipo (alpha)) < 4) ||
763  (p == 5 && degree (getMipo (alpha)) < 3))
764  {
765  fail= true;
766  return CFList();
767  }
768  }
769  }
770  double bound;
771  if (alpha != x)
772  {
773  bound= pow ((double) p, (double) degree (getMipo(alpha)));
774  bound *= (double) k;
775  }
776  else if (GF)
777  {
778  bound= pow ((double) p, (double) getGFDegree());
779  bound *= (double) k;
780  }
781  else
782  bound= pow ((double) p, (double) k);
783 
784  CanonicalForm random;
786  do
787  {
788  random= 0;
789  // possible overflow if list.length() does not fit into a int
790  if (list.length() >= bound)
791  {
792  fail= true;
793  break;
794  }
795  for (int i= 0; i < k; i++)
796  {
797  if (list.isEmpty())
798  result.append (0);
799  else if (GF)
800  {
801  result.append (genGF.generate());
802  random += result.getLast()*power (x, i);
803  }
804  else if (alpha.level() != 1)
805  {
806  AlgExtRandomF genAlgExt (alpha);
807  result.append (genAlgExt.generate());
808  random += result.getLast()*power (x, i);
809  }
810  else
811  {
812  result.append (genFF.generate());
813  random += result.getLast()*power (x, i);
814  }
815  }
816  if (find (list, random))
817  {
818  result= CFList();
819  continue;
820  }
821  int l= F.level();
822  eval.insert (F);
823  LCFeval.insert (LCF);
824  bool bad= false;
825  for (CFListIterator i= result; i.hasItem(); i++, l--)
826  {
827  eval.insert (eval.getFirst()(i.getItem(), l));
828  LCFeval.insert (LCFeval.getFirst()(i.getItem(), l));
829  if (degree (eval.getFirst(), l - 1) != degree (F, l - 1))
830  {
831  if (!find (list, random))
832  list.append (random);
833  result= CFList();
834  eval= CFList();
835  LCFeval= CFList();
836  bad= true;
837  break;
838  }
839  if ((l != 2) && (degree (LCFeval.getFirst(), l-1) != degree (LCF, l-1)))
840  {
841  if (!find (list, random))
842  list.append (random);
843  result= CFList();
844  eval= CFList();
845  LCFeval= CFList();
846  bad= true;
847  break;
848  }
849  }
850 
851  if (bad)
852  continue;
853 
854  if (degree (eval.getFirst()) != degree (F, 1))
855  {
856  if (!find (list, random))
857  list.append (random);
858  result= CFList();
859  LCFeval= CFList();
860  eval= CFList();
861  continue;
862  }
863 
864  deriv_x= deriv (eval.getFirst(), x);
865  gcd_deriv= gcd (eval.getFirst(), deriv_x);
866  if (degree (gcd_deriv) > 0)
867  {
868  if (!find (list, random))
869  list.append (random);
870  result= CFList();
871  LCFeval= CFList();
872  eval= CFList();
873  continue;
874  }
876  i++;
878  if (degree (contentx) > 0)
879  {
880  if (!find (list, random))
881  list.append (random);
882  result= CFList();
883  LCFeval= CFList();
884  eval= CFList();
885  continue;
886  }
887 
888  contentx= content (i.getItem());
889  if (degree (contentx) > 0)
890  {
891  if (!find (list, random))
892  list.append (random);
893  result= CFList();
894  LCFeval= CFList();
895  eval= CFList();
896  continue;
897  }
898 
899  if (list.length() >= bound)
900  {
901  fail= true;
902  break;
903  }
904  } while (find (list, random));
905 
906  if (!eval.isEmpty())
907  eval.removeFirst();
908 
909  return result;
910 }
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
List< CanonicalForm > CFList
CFList LCFeval
Definition: facFactorize.cc:54
generate random elements in GF
Definition: cf_random.h:31
static CanonicalForm bound(const CFMatrix &M)
Definition: cf_linsys.cc:460
int isEmpty() const
Definition: ftmpl_list.cc:267
CanonicalForm LCF
Definition: facFactorize.cc:53
CanonicalForm deriv(const CanonicalForm &f, const Variable &x)
return P p
Definition: myNF.cc:203
factory&#39;s class for variables
Definition: factory.h:115
bool bad
Definition: facFactorize.cc:65
CanonicalForm gcd_deriv
Definition: facFactorize.cc:59
factory&#39;s main class
Definition: canonicalform.h:75
int k
Definition: cfEzgcd.cc:93
void insert(const T &)
Definition: ftmpl_list.cc:193
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
Definition: variable.cc:207
int getCharacteristic()
Definition: cf_char.cc:51
#define CHAR_THRESHOLD
template bool find(const List< CanonicalForm > &, const CanonicalForm &)
void removeFirst()
Definition: ftmpl_list.cc:287
CanonicalForm content(const CanonicalForm &)
CanonicalForm content ( const CanonicalForm & f )
Definition: cf_gcd.cc:180
T getFirst() const
Definition: ftmpl_list.cc:279
CanonicalForm generate() const
Definition: cf_random.cc:66
int level() const
Definition: factory.h:132
T & getItem() const
Definition: ftmpl_list.cc:431
CanonicalForm generate() const
Definition: cf_random.cc:56
CFList & eval
Definition: facFactorize.cc:48
generate random elements in F_p
Definition: cf_random.h:43
int i
Definition: cfEzgcd.cc:123
T getLast() const
Definition: ftmpl_list.cc:309
CanonicalForm contentx
generate random elements in F_p(alpha)
Definition: cf_random.h:70
int length() const
Definition: ftmpl_list.cc:273
int gcd(int a, int b)
Definition: walkSupport.cc:839
int getGFDegree()
Definition: cf_char.cc:56
Variable x
Definition: cfModGcd.cc:4023
CanonicalForm deriv_x
Definition: facFactorize.cc:59
int level() const
level() returns the level of CO.
void append(const T &)
Definition: ftmpl_list.cc:256
int degree(const CanonicalForm &f)
CanonicalForm LC(const CanonicalForm &f)
Rational pow(const Rational &a, int e)
Definition: GMPrat.cc:418
int l
Definition: cfEzgcd.cc:94
return result
Definition: facAbsBiFact.cc:76

§ evaluationWRTDifferentSecondVars()

void evaluationWRTDifferentSecondVars ( CFList *&  Aeval,
const CFList evaluation,
const CanonicalForm A 
)

evaluate a poly A with main variable at level 1 at an evaluation point in K^(n-1) wrt different second variables. If this evaluation is valid (see evalPoints) then Aeval contains A successively evaluated at this point, otherwise this entry is empty

Parameters
[in,out]Aevalan array of length n-2 if variable at level i > 2 admits a valid evaluation this entry contains A successively evaluated at this point otherwise an empty list
[in]evaluationa valid evaluation point for main variable at level 1 and second variable at level 2
[in]Asome poly

Definition at line 1950 of file facFqFactorize.cc.

1952 {
1953  CanonicalForm tmp;
1954  CFList tmp2;
1956  bool preserveDegree= true;
1957  Variable x= Variable (1);
1958  int j, degAi, degA1= degree (A,1);
1959  for (int i= A.level(); i > 2; i--)
1960  {
1961  tmp= A;
1962  tmp2= CFList();
1963  iter= evaluation;
1964  preserveDegree= true;
1965  degAi= degree (A,i);
1966  for (j= A.level(); j > 1; j--, iter++)
1967  {
1968  if (j == i)
1969  continue;
1970  else
1971  {
1972  tmp= tmp (iter.getItem(), j);
1973  tmp2.insert (tmp);
1974  if ((degree (tmp, i) != degAi) ||
1975  (degree (tmp, 1) != degA1))
1976  {
1977  preserveDegree= false;
1978  break;
1979  }
1980  }
1981  }
1982  if (!content(tmp,1).inCoeffDomain())
1983  preserveDegree= false;
1984  if (!content(tmp).inCoeffDomain())
1985  preserveDegree= false;
1986  if (!(gcd (deriv (tmp,x), tmp)).inCoeffDomain())
1987  preserveDegree= false;
1988  if (preserveDegree)
1989  Aeval [i - 3]= tmp2;
1990  else
1991  Aeval [i - 3]= CFList();
1992  }
1993 }
List< CanonicalForm > CFList
CanonicalForm deriv(const CanonicalForm &f, const Variable &x)
factory&#39;s class for variables
Definition: factory.h:115
CFFListIterator iter
Definition: facAbsBiFact.cc:54
factory&#39;s main class
Definition: canonicalform.h:75
const CanonicalForm int const CFList & evaluation
Definition: facAbsFact.cc:55
void insert(const T &)
Definition: ftmpl_list.cc:193
CanonicalForm content(const CanonicalForm &)
CanonicalForm content ( const CanonicalForm & f )
Definition: cf_gcd.cc:180
int j
Definition: myNF.cc:70
T & getItem() const
Definition: ftmpl_list.cc:431
#define A
Definition: sirandom.c:23
int i
Definition: cfEzgcd.cc:123
CFList tmp2
Definition: facFqBivar.cc:70
int gcd(int a, int b)
Definition: walkSupport.cc:839
Variable x
Definition: cfModGcd.cc:4023
int level() const
level() returns the level of CO.
int degree(const CanonicalForm &f)

§ extEarlyFactorDetect()

CFList extEarlyFactorDetect ( CanonicalForm F,
CFList factors,
int &  adaptedLiftBound,
bool &  success,
const ExtensionInfo info,
const CFList eval,
const int  deg,
const CFList MOD,
const int  bound 
)

detects factors of F at stage deg of Hensel lifting. No combinations of more than one factor are tested. Lift bound is adapted.

Returns
extEarlyFactorDetect returns a list of factors of F (possibly incomplete), whose shift to zero is reversed, in case of success. Otherwise an empty list.
See also
factorRecombination(), earlyFactorDetection()
Parameters
[in,out]Fpoly to be factored, returns poly divided by detected factors in case of success
[in,out]factorslist of factors lifted up to deg, returns a list of factors without detected factors
[in,out]adaptedLiftBoundadapted lift bound
[in,out]successindicating succes
[in]infoinfo about extension
[in]evalevaluation point
[in]degstage of Hensel lifting
[in]MODa list of powers of Variables
[in]boundinitial lift bound

Definition at line 656 of file facFqFactorize.cc.

659 {
660  Variable alpha= info.getAlpha();
661  Variable beta= info.getBeta();
662  CanonicalForm gamma= info.getGamma();
663  CanonicalForm delta= info.getDelta();
664  int k= info.getGFDegree();
665  CFList result;
666  CFList T= factors;
667  CanonicalForm buf= F;
668  Variable y= F.mvar();
669  Variable x= Variable (1);
670  CanonicalForm LCBuf= LC (buf, x);
671  CanonicalForm g, gg, quot;
672  CFList M= MOD;
673  M.append (power (y, deg));
674  adaptedLiftBound= 0;
675  int d= bound;
676  int e= 0;
677  int nBuf;
678  CFList source, dest;
679 
680  int degMipoBeta= 1;
681  if (!k && beta.level() != 1)
682  degMipoBeta= degree (getMipo (beta));
683 
684  for (CFListIterator i= factors; i.hasItem(); i++)
685  {
686  g= mulMod (i.getItem(), LCBuf, M);
687  g /= myContent (g);
688  if (fdivides (g, buf, quot))
689  {
690  gg= reverseShift (g, eval);
691  gg /= Lc (gg);
692  if (!k && beta == x)
693  {
694  if (degree (gg, alpha) < degMipoBeta)
695  {
696  appendTestMapDown (result, gg, info, source, dest);
697  buf= quot;
698  nBuf= degree (g, y) + degree (LC (g, x), y);
699  d -= nBuf;
700  e= tmax (e, nBuf);
701  LCBuf= LC (buf, x);
702  T= Difference (T, CFList (i.getItem()));
703  }
704  }
705  else
706  {
707  if (!isInExtension (gg, gamma, k, delta, source, dest))
708  {
709  appendTestMapDown (result, gg, info, source, dest);
710  buf= quot;
711  nBuf= degree (g, y) + degree (LC (g, x), y);
712  d -= nBuf;
713  e= tmax (e, nBuf);
714  LCBuf= LC (buf, x);
715  T= Difference (T, CFList (i.getItem()));
716  }
717  }
718  }
719  }
720  adaptedLiftBound= d;
721 
722  if (adaptedLiftBound < deg)
723  {
724  if (adaptedLiftBound < degree (F) + 1)
725  {
726  if (d == 1)
727  adaptedLiftBound= tmin (e + 1, deg);
728  else
729  adaptedLiftBound= deg;
730  }
731  success= true;
732  factors= T;
733  F= buf;
734  }
735  return result;
736 }
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
Variable getAlpha() const
getter
const CanonicalForm int const CFList const Variable & y
Definition: facAbsFact.cc:57
static CanonicalForm bound(const CFMatrix &M)
Definition: cf_linsys.cc:460
CanonicalForm reverseShift(const CanonicalForm &F, const CFList &evaluation, int l)
reverse shifting the evaluation point to zero
CanonicalForm getDelta() const
getter
template CanonicalForm tmax(const CanonicalForm &, const CanonicalForm &)
int getGFDegree() const
getter
factory&#39;s class for variables
Definition: factory.h:115
bool isInExtension(const CanonicalForm &F, const CanonicalForm &gamma, const int k, const CanonicalForm &delta, CFList &source, CFList &dest)
tests if F is not contained in a subfield defined by gamma (Fq case) or k (GF case) ...
factory&#39;s main class
Definition: canonicalform.h:75
g
Definition: cfModGcd.cc:4031
int k
Definition: cfEzgcd.cc:93
Variable alpha
Definition: facAbsBiFact.cc:52
CanonicalForm Lc(const CanonicalForm &f)
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
Definition: variable.cc:207
bool delta(X x, Y y, D d)
Definition: TestSuite.h:160
#define M
Definition: sirandom.c:24
int status int void * buf
Definition: si_signals.h:59
int level() const
Definition: factory.h:132
static CanonicalForm myContent(const CanonicalForm &F)
Variable getBeta() const
getter
int i
Definition: cfEzgcd.cc:123
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
void appendTestMapDown(CFList &factors, const CanonicalForm &f, const ExtensionInfo &info, CFList &source, CFList &dest)
test if g is in a subfield of the current field, if so map it down and append it to factors ...
Variable beta
Definition: facAbsFact.cc:99
bool fdivides(const CanonicalForm &f, const CanonicalForm &g)
bool fdivides ( const CanonicalForm & f, const CanonicalForm & g )
CanonicalForm mulMod(const CanonicalForm &A, const CanonicalForm &B, const CFList &MOD)
Karatsuba style modular multiplication for multivariate polynomials.
Definition: facMul.cc:2947
Variable x
Definition: cfModGcd.cc:4023
void append(const T &)
Definition: ftmpl_list.cc:256
int degree(const CanonicalForm &f)
static jList * T
Definition: janet.cc:37
CanonicalForm LC(const CanonicalForm &f)
CanonicalForm getGamma() const
getter
template List< Variable > Difference(const List< Variable > &, const List< Variable > &)
return result
Definition: facAbsBiFact.cc:76
template CanonicalForm tmin(const CanonicalForm &, const CanonicalForm &)

§ extFactorize()

CFList extFactorize ( const CanonicalForm F,
const ExtensionInfo info 
)

multivariate factorization over an extension of the initial field

Factorization over an extension of initial field.

Parameters
[in]Fpoly to be factored
[in]infoinfo about extension

Definition at line 3640 of file facFqFactorize.cc.

3641 {
3642  CanonicalForm A= F;
3643 
3644  Variable alpha= info.getAlpha();
3645  Variable beta= info.getBeta();
3646  int k= info.getGFDegree();
3647  char cGFName= info.getGFName();
3648  CanonicalForm delta= info.getDelta();
3649  bool GF= (CFFactory::gettype() == GaloisFieldDomain);
3650  Variable w= Variable (1);
3651 
3652  CFList factors;
3653  if (!GF && alpha == w) // we are in F_p
3654  {
3655  CFList factors;
3656  bool extension= true;
3657  int p= getCharacteristic();
3658  if (p < 7)
3659  {
3660  if (p == 2)
3662  else if (p == 3)
3664  else if (p == 5)
3666  ExtensionInfo info= ExtensionInfo (extension);
3667  A= A.mapinto();
3668  factors= multiFactorize (A, info);
3669 
3670  CanonicalForm mipo= gf_mipo;
3672  Variable vBuf= rootOf (mipo.mapinto());
3673  for (CFListIterator j= factors; j.hasItem(); j++)
3674  j.getItem()= GF2FalphaRep (j.getItem(), vBuf);
3675  prune (vBuf);
3676  }
3677  else if (p >= 7 && p*p < (1<<16)) // pass to GF if possible
3678  {
3680  ExtensionInfo info= ExtensionInfo (extension);
3681  A= A.mapinto();
3682  factors= multiFactorize (A, info);
3683 
3684  CanonicalForm mipo= gf_mipo;
3686  Variable vBuf= rootOf (mipo.mapinto());
3687  for (CFListIterator j= factors; j.hasItem(); j++)
3688  j.getItem()= GF2FalphaRep (j.getItem(), vBuf);
3689  prune (vBuf);
3690  }
3691  else // not able to pass to GF, pass to F_p(\alpha)
3692  {
3693  CanonicalForm mipo= randomIrredpoly (2, w);
3694  Variable v= rootOf (mipo);
3695  ExtensionInfo info= ExtensionInfo (v);
3696  factors= multiFactorize (A, info);
3697  prune (v);
3698  }
3699  return factors;
3700  }
3701  else if (!GF && (alpha != w)) // we are in F_p(\alpha)
3702  {
3703  if (k == 1) // need factorization over F_p
3704  {
3705  int extDeg= degree (getMipo (alpha));
3706  extDeg++;
3707  CanonicalForm mipo= randomIrredpoly (extDeg, w);
3708  Variable v= rootOf (mipo);
3709  ExtensionInfo info= ExtensionInfo (v);
3710  factors= multiFactorize (A, info);
3711  prune (v);
3712  }
3713  else
3714  {
3715  if (beta == w)
3716  {
3717  Variable v= chooseExtension (alpha, beta, k);
3718  CanonicalForm primElem, imPrimElem;
3719  bool primFail= false;
3720  Variable vBuf;
3721  primElem= primitiveElement (alpha, vBuf, primFail);
3722  ASSERT (!primFail, "failure in integer factorizer");
3723  if (primFail)
3724  ; //ERROR
3725  else
3726  imPrimElem= mapPrimElem (primElem, alpha, v);
3727 
3728  CFList source, dest;
3729  CanonicalForm bufA= mapUp (A, alpha, v, primElem, imPrimElem,
3730  source, dest);
3731  ExtensionInfo info= ExtensionInfo (v, alpha, imPrimElem, primElem);
3732  factors= multiFactorize (bufA, info);
3733  prune (v);
3734  }
3735  else
3736  {
3737  Variable v= chooseExtension (alpha, beta, k);
3738  CanonicalForm primElem, imPrimElem;
3739  bool primFail= false;
3740  Variable vBuf;
3741  ASSERT (!primFail, "failure in integer factorizer");
3742  if (primFail)
3743  ; //ERROR
3744  else
3745  imPrimElem= mapPrimElem (delta, beta, v);
3746 
3747  CFList source, dest;
3748  CanonicalForm bufA= mapDown (A, info, source, dest);
3749  source= CFList();
3750  dest= CFList();
3751  bufA= mapUp (bufA, beta, v, delta, imPrimElem, source, dest);
3752  ExtensionInfo info= ExtensionInfo (v, beta, imPrimElem, delta);
3753  factors= multiFactorize (bufA, info);
3754  prune (v);
3755  }
3756  }
3757  return factors;
3758  }
3759  else // we are in GF (p^k)
3760  {
3761  int p= getCharacteristic();
3762  int extensionDeg= getGFDegree();
3763  bool extension= true;
3764  if (k == 1) // need factorization over F_p
3765  {
3766  extensionDeg++;
3767  if (pow ((double) p, (double) extensionDeg) < (1<<16))
3768  // pass to GF(p^k+1)
3769  {
3770  CanonicalForm mipo= gf_mipo;
3771  setCharacteristic (p);
3772  Variable vBuf= rootOf (mipo.mapinto());
3773  A= GF2FalphaRep (A, vBuf);
3774  setCharacteristic (p, extensionDeg, 'Z');
3775  ExtensionInfo info= ExtensionInfo (extension);
3776  factors= multiFactorize (A.mapinto(), info);
3777  prune (vBuf);
3778  }
3779  else // not able to pass to another GF, pass to F_p(\alpha)
3780  {
3781  CanonicalForm mipo= gf_mipo;
3782  setCharacteristic (p);
3783  Variable vBuf= rootOf (mipo.mapinto());
3784  A= GF2FalphaRep (A, vBuf);
3785  Variable v= chooseExtension (vBuf, beta, k);
3786  ExtensionInfo info= ExtensionInfo (v, extension);
3787  factors= multiFactorize (A, info);
3788  prune (vBuf);
3789  }
3790  }
3791  else // need factorization over GF (p^k)
3792  {
3793  if (pow ((double) p, (double) 2*extensionDeg) < (1<<16))
3794  // pass to GF(p^2k)
3795  {
3796  setCharacteristic (p, 2*extensionDeg, 'Z');
3797  ExtensionInfo info= ExtensionInfo (k, cGFName, extension);
3798  factors= multiFactorize (GFMapUp (A, extensionDeg), info);
3799  setCharacteristic (p, extensionDeg, cGFName);
3800  }
3801  else // not able to pass to GF (p^2k), pass to F_p (\alpha)
3802  {
3803  CanonicalForm mipo= gf_mipo;
3804  setCharacteristic (p);
3805  Variable v1= rootOf (mipo.mapinto());
3806  A= GF2FalphaRep (A, v1);
3807  Variable v2= chooseExtension (v1, v1, k);
3808  CanonicalForm primElem, imPrimElem;
3809  bool primFail= false;
3810  Variable vBuf;
3811  primElem= primitiveElement (v1, v1, primFail);
3812  if (primFail)
3813  ; //ERROR
3814  else
3815  imPrimElem= mapPrimElem (primElem, v1, v2);
3816  CFList source, dest;
3817  CanonicalForm bufA= mapUp (A, v1, v2, primElem, imPrimElem,
3818  source, dest);
3819  ExtensionInfo info= ExtensionInfo (v2, v1, imPrimElem, primElem);
3820  factors= multiFactorize (bufA, info);
3821  setCharacteristic (p, k, cGFName);
3822  for (CFListIterator i= factors; i.hasItem(); i++)
3823  i.getItem()= Falpha2GFRep (i.getItem());
3824  prune (v1);
3825  }
3826  }
3827  return factors;
3828  }
3829 }
char getGFName() const
getter
List< CanonicalForm > CFList
Variable getAlpha() const
getter
CanonicalForm Falpha2GFRep(const CanonicalForm &F)
change representation by residue classes modulo a Conway polynomial to representation by primitive el...
Definition: cf_map_ext.cc:170
static CanonicalForm mapDown(const CanonicalForm &F, const Variable &alpha, const CanonicalForm &G, CFList &source, CFList &dest)
the CanonicalForm G is the output of map_up, returns F considered as an element over ...
Definition: cf_map_ext.cc:90
CanonicalForm getDelta() const
getter
int getGFDegree() const
getter
static Variable chooseExtension(const Variable &alpha)
Definition: cfModGcd.cc:422
CanonicalForm primitiveElement(const Variable &alpha, Variable &beta, bool &fail)
determine a primitive element of , is a primitive element of a field which is isomorphic to ...
Definition: cf_map_ext.cc:310
return P p
Definition: myNF.cc:203
factory&#39;s class for variables
Definition: factory.h:115
CFList multiFactorize(const CanonicalForm &F, const ExtensionInfo &info)
CanonicalForm gf_mipo(0)
factory&#39;s main class
Definition: canonicalform.h:75
int k
Definition: cfEzgcd.cc:93
Variable alpha
Definition: facAbsBiFact.cc:52
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
Definition: variable.cc:207
void setCharacteristic(int c)
Definition: cf_char.cc:23
bool delta(X x, Y y, D d)
Definition: TestSuite.h:160
int getCharacteristic()
Definition: cf_char.cc:51
void prune(Variable &alpha)
Definition: variable.cc:261
CanonicalForm mapinto() const
Variable rootOf(const CanonicalForm &, char name='@')
returns a symbolic root of polynomial with name name Use it to define algebraic variables ...
Definition: variable.cc:162
ExtensionInfo contains information about extension.
Definition: ExtensionInfo.h:50
static CanonicalForm mapUp(const Variable &alpha, const Variable &beta)
and is a primitive element, returns the image of
Definition: cf_map_ext.cc:67
int j
Definition: myNF.cc:70
const ExtensionInfo & info
< [in] sqrfree poly
#define A
Definition: sirandom.c:23
Variable getBeta() const
getter
int i
Definition: cfEzgcd.cc:123
Variable beta
Definition: facAbsFact.cc:99
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:37
CanonicalForm GF2FalphaRep(const CanonicalForm &F, const Variable &alpha)
changes representation by primitive element to representation by residue classes modulo a Conway poly...
Definition: cf_map_ext.cc:162
static int gettype()
Definition: cf_factory.h:27
CanonicalForm GFMapUp(const CanonicalForm &F, int k)
maps a polynomial over to a polynomial over , d needs to be a multiple of k
Definition: cf_map_ext.cc:207
const CanonicalForm & w
Definition: facAbsFact.cc:55
int getGFDegree()
Definition: cf_char.cc:56
#define GaloisFieldDomain
Definition: cf_defs.h:22
CanonicalForm randomIrredpoly(int i, const Variable &x)
computes a random monic irreducible univariate polynomial in x over Fp of degree i via NTL ...
Definition: cf_irred.cc:42
#define ASSERT(expression, message)
Definition: cf_assert.h:99
int degree(const CanonicalForm &f)
CanonicalForm mapPrimElem(const CanonicalForm &primElem, const Variable &alpha, const Variable &beta)
compute the image of a primitive element of in . We assume .
Definition: cf_map_ext.cc:377
Rational pow(const Rational &a, int e)
Definition: GMPrat.cc:418

§ extFactorRecombination()

CFList extFactorRecombination ( const CFList factors,
const CanonicalForm F,
const CFList M,
const ExtensionInfo info,
const CFList evaluation 
)

Naive factor recombination for multivariate factorization over an extension of the initial field. No precomputed is used to exclude combinations.

Returns
extFactorRecombination returns a list of factors of F, whose shift to zero is reversed.
See also
factorRecombination()
Parameters
[in]factorslist of lifted factors that are monic wrt Variable (1)
[in]Fpoly to be factored
[in]Ma list of powers of Variables
[in]infoinfo about extension
[in]evaluationevaluation point

Definition at line 217 of file facFqFactorize.cc.

220 {
221  Variable alpha= info.getAlpha();
222  Variable beta= info.getBeta();
223  CanonicalForm gamma= info.getGamma();
224  CanonicalForm delta= info.getDelta();
225  int k= info.getGFDegree();
226  CFList source, dest;
227  if (factors.length() == 1)
228  {
229  CanonicalForm buf= reverseShift (F, evaluation);
230  return CFList (mapDown (buf, info, source, dest));
231  }
232  if (factors.length() < 1)
233  return CFList();
234 
235  int degMipoBeta= 1;
236  if (!k && beta.level() != 1)
237  degMipoBeta= degree (getMipo (beta));
238 
239  CFList T, S;
240  T= factors;
241 
242  int s= 1;
243  CFList result;
245 
246  buf= F;
247 
248  Variable x= Variable (1);
249  CanonicalForm g, LCBuf= LC (buf, x);
250  CanonicalForm buf2, quot;
251  int * v= new int [T.length()];
252  for (int i= 0; i < T.length(); i++)
253  v[i]= 0;
254  bool noSubset= false;
255  CFArray TT;
256  TT= copy (factors);
257  bool recombination= false;
258  bool trueFactor= false;
259  while (T.length() >= 2*s)
260  {
261  while (noSubset == false)
262  {
263  if (T.length() == s)
264  {
265  delete [] v;
266  if (recombination)
267  {
268  T.insert (LCBuf);
269  g= prodMod (T, M);
270  T.removeFirst();
271  result.append (g/myContent (g));
272  g= reverseShift (g, evaluation);
273  g /= Lc (g);
274  appendTestMapDown (result, g, info, source, dest);
275  return result;
276  }
277  else
278  {
279  buf= reverseShift (buf, evaluation);
280  return CFList (buf);
281  }
282  }
283 
284  S= subset (v, s, TT, noSubset);
285  if (noSubset) break;
286 
287  S.insert (LCBuf);
288  g= prodMod (S, M);
289  S.removeFirst();
290  g /= myContent (g);
291  if (fdivides (g, buf, quot))
292  {
293  buf2= reverseShift (g, evaluation);
294  buf2 /= Lc (buf2);
295  if (!k && beta == x)
296  {
297  if (degree (buf2, alpha) < degMipoBeta)
298  {
299  appendTestMapDown (result, buf2, info, source, dest);
300  buf= quot;
301  LCBuf= LC (buf, x);
302  recombination= true;
303  trueFactor= true;
304  }
305  }
306  else
307  {
308  if (!isInExtension (buf2, gamma, k, delta, source, dest))
309  {
310  appendTestMapDown (result, buf2, info, source, dest);
311  buf /= g;
312  LCBuf= LC (buf, x);
313  recombination= true;
314  trueFactor= true;
315  }
316  }
317 
318  if (trueFactor)
319  {
320  T= Difference (T, S);
321 
322  if (T.length() < 2*s || T.length() == s)
323  {
324  buf= reverseShift (buf, evaluation);
325  buf /= Lc (buf);
326  appendTestMapDown (result, buf, info, source, dest);
327  delete [] v;
328  return result;
329  }
330  trueFactor= false;
331  TT= copy (T);
332  indexUpdate (v, s, T.length(), noSubset);
333  if (noSubset) break;
334  }
335  }
336  }
337  s++;
338  if (T.length() < 2*s || T.length() == s)
339  {
340  buf= reverseShift (buf, evaluation);
341  appendTestMapDown (result, buf, info, source, dest);
342  delete [] v;
343  return result;
344  }
345  for (int i= 0; i < T.length(); i++)
346  v[i]= 0;
347  noSubset= false;
348  }
349  if (T.length() < 2*s)
350  {
351  buf= reverseShift (F, evaluation);
352  appendMapDown (result, buf, info, source, dest);
353  }
354 
355  delete [] v;
356  return result;
357 }
void indexUpdate(int index [], const int &subsetSize, const int &setSize, bool &noSubset)
update index
List< CanonicalForm > CFList
Variable getAlpha() const
getter
static CanonicalForm mapDown(const CanonicalForm &F, const Variable &alpha, const CanonicalForm &G, CFList &source, CFList &dest)
the CanonicalForm G is the output of map_up, returns F considered as an element over ...
Definition: cf_map_ext.cc:90
const CanonicalForm int s
Definition: facAbsFact.cc:55
CFArray copy(const CFList &list)
write elements of list into an array
CanonicalForm reverseShift(const CanonicalForm &F, const CFList &evaluation, int l)
reverse shifting the evaluation point to zero
CanonicalForm getDelta() const
getter
int getGFDegree() const
getter
factory&#39;s class for variables
Definition: factory.h:115
bool isInExtension(const CanonicalForm &F, const CanonicalForm &gamma, const int k, const CanonicalForm &delta, CFList &source, CFList &dest)
tests if F is not contained in a subfield defined by gamma (Fq case) or k (GF case) ...
factory&#39;s main class
Definition: canonicalform.h:75
g
Definition: cfModGcd.cc:4031
int k
Definition: cfEzgcd.cc:93
Variable alpha
Definition: facAbsBiFact.cc:52
void insert(const T &)
Definition: ftmpl_list.cc:193
CanonicalForm Lc(const CanonicalForm &f)
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
Definition: variable.cc:207
bool delta(X x, Y y, D d)
Definition: TestSuite.h:160
void removeFirst()
Definition: ftmpl_list.cc:287
CFList subset(int index [], const int &s, const CFArray &elements, bool &noSubset)
extract a subset given by index of size s from elements, if there is no subset we have not yet consid...
int status int void * buf
Definition: si_signals.h:59
int level() const
Definition: factory.h:132
static CanonicalForm myContent(const CanonicalForm &F)
Variable getBeta() const
getter
int i
Definition: cfEzgcd.cc:123
void appendMapDown(CFList &factors, const CanonicalForm &g, const ExtensionInfo &info, CFList &source, CFList &dest)
map g down into a subfield of the current field and append it to factors
CFList recombination(const CFList &factors1, const CFList &factors2, int s, int thres, const CanonicalForm &evalPoint, const Variable &x)
recombination of bivariate factors factors1 s. t. the result evaluated at evalPoint coincides with fa...
void appendTestMapDown(CFList &factors, const CanonicalForm &f, const ExtensionInfo &info, CFList &source, CFList &dest)
test if g is in a subfield of the current field, if so map it down and append it to factors ...
CanonicalForm buf2
Definition: facFqBivar.cc:71
Variable beta
Definition: facAbsFact.cc:99
bool fdivides(const CanonicalForm &f, const CanonicalForm &g)
bool fdivides ( const CanonicalForm & f, const CanonicalForm & g )
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:37
int length() const
Definition: ftmpl_list.cc:273
Variable x
Definition: cfModGcd.cc:4023
void append(const T &)
Definition: ftmpl_list.cc:256
int degree(const CanonicalForm &f)
static jList * T
Definition: janet.cc:37
CanonicalForm LC(const CanonicalForm &f)
CanonicalForm getGamma() const
getter
template List< Variable > Difference(const List< Variable > &, const List< Variable > &)
return result
Definition: facAbsBiFact.cc:76
CanonicalForm prodMod(const CFList &L, const CanonicalForm &M)
product of all elements in L modulo M via divide-and-conquer.
Definition: facMul.cc:3047

§ extLiftBoundAdaption()

int extLiftBoundAdaption ( const CanonicalForm F,
const CFList factors,
bool &  success,
const ExtensionInfo info,
const CFList eval,
const int  deg,
const CFList MOD,
const int  bound 
)

Lift bound adaption over an extension of the initial field. Essentially an early factor detection but only the lift bound is adapted.

Returns
liftBoundAdaption returns an adapted lift bound.
See also
earlyFactorDetect(), earlyFactorDetection()
Parameters
[in]Fa poly
[in]factorslist of list of lifted factors that are monic wrt
[in,out]successindicates that no further lifting is necessary
[in]infoinfo about extension
[in]evalevaluation point
[in]degstage of Hensel lifting
[in]MODa list of powers of Variables
[in]boundinitial lift bound

Definition at line 509 of file facFqFactorize.cc.

512 {
513  Variable alpha= info.getAlpha();
514  Variable beta= info.getBeta();
515  CanonicalForm gamma= info.getGamma();
516  CanonicalForm delta= info.getDelta();
517  int k= info.getGFDegree();
518  int adaptedLiftBound= 0;
519  CanonicalForm buf= F;
520  Variable y= F.mvar();
521  Variable x= Variable (1);
522  CanonicalForm LCBuf= LC (buf, x);
523  CanonicalForm g, gg, quot;
524  CFList M= MOD;
525  M.append (power (y, deg));
526  adaptedLiftBound= 0;
527  int d= bound;
528  int e= 0;
529  int nBuf;
530  int degMipoBeta= 1;
531  if (!k && beta.level() != 1)
532  degMipoBeta= degree (getMipo (beta));
533 
534  CFList source, dest;
535  for (CFListIterator i= factors; i.hasItem(); i++)
536  {
537  g= mulMod (i.getItem(), LCBuf, M);
538  g /= myContent (g);
539  if (fdivides (g, buf, quot))
540  {
541  gg= reverseShift (g, eval);
542  gg /= Lc (gg);
543  if (!k && beta == x)
544  {
545  if (degree (gg, alpha) < degMipoBeta)
546  {
547  buf= quot;
548  nBuf= degree (g, y) + degree (LC (g, x), y);
549  d -= nBuf;
550  e= tmax (e, nBuf);
551  LCBuf= LC (buf, x);
552  }
553  }
554  else
555  {
556  if (!isInExtension (gg, gamma, k, delta, source, dest))
557  {
558  buf= quot;
559  nBuf= degree (g, y) + degree (LC (g, x), y);
560  d -= nBuf;
561  e= tmax (e, nBuf);
562  LCBuf= LC (buf, x);
563  }
564  }
565  }
566  }
567  adaptedLiftBound= d;
568 
569  if (adaptedLiftBound < deg)
570  {
571  if (adaptedLiftBound < degree (F) + 1)
572  {
573  if (d == 1)
574  {
575  if (e + 1 > deg)
576  {
577  adaptedLiftBound= deg;
578  success= false;
579  }
580  else
581  {
582  success= true;
583  if (e + 1 < degree (F) + 1)
584  adaptedLiftBound= deg;
585  else
586  adaptedLiftBound= e + 1;
587  }
588  }
589  else
590  {
591  success= true;
592  adaptedLiftBound= deg;
593  }
594  }
595  else
596  {
597  success= true;
598  }
599  }
600 
601  return adaptedLiftBound;
602 }
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
Variable getAlpha() const
getter
const CanonicalForm int const CFList const Variable & y
Definition: facAbsFact.cc:57
static CanonicalForm bound(const CFMatrix &M)
Definition: cf_linsys.cc:460
CanonicalForm reverseShift(const CanonicalForm &F, const CFList &evaluation, int l)
reverse shifting the evaluation point to zero
CanonicalForm getDelta() const
getter
template CanonicalForm tmax(const CanonicalForm &, const CanonicalForm &)
int getGFDegree() const
getter
factory&#39;s class for variables
Definition: factory.h:115
bool isInExtension(const CanonicalForm &F, const CanonicalForm &gamma, const int k, const CanonicalForm &delta, CFList &source, CFList &dest)
tests if F is not contained in a subfield defined by gamma (Fq case) or k (GF case) ...
factory&#39;s main class
Definition: canonicalform.h:75
g
Definition: cfModGcd.cc:4031
int k
Definition: cfEzgcd.cc:93
Variable alpha
Definition: facAbsBiFact.cc:52
CanonicalForm Lc(const CanonicalForm &f)
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
Definition: variable.cc:207
bool delta(X x, Y y, D d)
Definition: TestSuite.h:160
#define M
Definition: sirandom.c:24
int status int void * buf
Definition: si_signals.h:59
int level() const
Definition: factory.h:132
static CanonicalForm myContent(const CanonicalForm &F)
Variable getBeta() const
getter
int i
Definition: cfEzgcd.cc:123
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
Variable beta
Definition: facAbsFact.cc:99
bool fdivides(const CanonicalForm &f, const CanonicalForm &g)
bool fdivides ( const CanonicalForm & f, const CanonicalForm & g )
CanonicalForm mulMod(const CanonicalForm &A, const CanonicalForm &B, const CFList &MOD)
Karatsuba style modular multiplication for multivariate polynomials.
Definition: facMul.cc:2947
Variable x
Definition: cfModGcd.cc:4023
void append(const T &)
Definition: ftmpl_list.cc:256
int degree(const CanonicalForm &f)
CanonicalForm LC(const CanonicalForm &f)
CanonicalForm getGamma() const
getter

§ extNonMonicFactorRecombination()

CFList extNonMonicFactorRecombination ( const CFList factors,
const CanonicalForm F,
const ExtensionInfo info 
)

Definition at line 2404 of file facFqFactorize.cc.

2406 {
2407  Variable alpha= info.getAlpha();
2408  Variable beta= info.getBeta();
2409  CanonicalForm gamma= info.getGamma();
2410  CanonicalForm delta= info.getDelta();
2411  int k= info.getGFDegree();
2412  CFList source, dest;
2413 
2414  int degMipoBeta= 1;
2415  if (!k && beta != Variable(1))
2416  degMipoBeta= degree (getMipo (beta));
2417 
2418  CFList T, S;
2419  T= factors;
2420  int s= 1;
2421  CFList result;
2422  CanonicalForm quot, buf= F;
2423 
2424  CanonicalForm g;
2426  int * v= new int [T.length()];
2427  for (int i= 0; i < T.length(); i++)
2428  v[i]= 0;
2429  bool noSubset= false;
2430  CFArray TT;
2431  TT= copy (factors);
2432  bool recombination= false;
2433  bool trueFactor= false;
2434  while (T.length() >= 2*s)
2435  {
2436  while (noSubset == false)
2437  {
2438  if (T.length() == s)
2439  {
2440  delete [] v;
2441  if (recombination)
2442  {
2443  g= prod (T);
2444  T.removeFirst();
2445  g /= myContent (g);
2446  g /= Lc (g);
2447  appendTestMapDown (result, g, info, source, dest);
2448  return result;
2449  }
2450  else
2451  return CFList (buf/myContent(buf));
2452  }
2453 
2454  S= subset (v, s, TT, noSubset);
2455  if (noSubset) break;
2456 
2457  g= prod (S);
2458  g /= myContent (g);
2459  if (fdivides (g, buf, quot))
2460  {
2461  buf2= g;
2462  buf2 /= Lc (buf2);
2463  if (!k && beta.level() == 1)
2464  {
2465  if (degree (buf2, alpha) < degMipoBeta)
2466  {
2467  appendTestMapDown (result, buf2, info, source, dest);
2468  buf= quot;
2469  recombination= true;
2470  trueFactor= true;
2471  }
2472  }
2473  else
2474  {
2475  if (!isInExtension (buf2, gamma, k, delta, source, dest))
2476  {
2477  appendTestMapDown (result, buf2, info, source, dest);
2478  buf= quot;
2479  recombination= true;
2480  trueFactor= true;
2481  }
2482  }
2483  if (trueFactor)
2484  {
2485  T= Difference (T, S);
2486 
2487  if (T.length() < 2*s || T.length() == s)
2488  {
2489  delete [] v;
2490  buf /= myContent (buf);
2491  buf /= Lc (buf);
2492  appendTestMapDown (result, buf, info, source, dest);
2493  return result;
2494  }
2495  trueFactor= false;
2496  TT= copy (T);
2497  indexUpdate (v, s, T.length(), noSubset);
2498  if (noSubset) break;
2499  }
2500  }
2501  }
2502  s++;
2503  if (T.length() < 2*s || T.length() == s)
2504  {
2505  delete [] v;
2506  buf /= myContent (buf);
2507  buf /= Lc (buf);
2508  appendTestMapDown (result, buf, info, source, dest);
2509  return result;
2510  }
2511  for (int i= 0; i < T.length(); i++)
2512  v[i]= 0;
2513  noSubset= false;
2514  }
2515  if (T.length() < 2*s)
2516  {
2517  buf= F/myContent (F);
2518  buf /= Lc (buf);
2519  appendMapDown (result, buf, info, source, dest);
2520  }
2521 
2522  delete [] v;
2523  return result;
2524 }
void indexUpdate(int index [], const int &subsetSize, const int &setSize, bool &noSubset)
update index
List< CanonicalForm > CFList
Variable getAlpha() const
getter
const CanonicalForm int s
Definition: facAbsFact.cc:55
CFArray copy(const CFList &list)
write elements of list into an array
CanonicalForm getDelta() const
getter
int getGFDegree() const
getter
factory&#39;s class for variables
Definition: factory.h:115
bool isInExtension(const CanonicalForm &F, const CanonicalForm &gamma, const int k, const CanonicalForm &delta, CFList &source, CFList &dest)
tests if F is not contained in a subfield defined by gamma (Fq case) or k (GF case) ...
factory&#39;s main class
Definition: canonicalform.h:75
g
Definition: cfModGcd.cc:4031
int k
Definition: cfEzgcd.cc:93
Variable alpha
Definition: facAbsBiFact.cc:52
CanonicalForm Lc(const CanonicalForm &f)
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
Definition: variable.cc:207
bool delta(X x, Y y, D d)
Definition: TestSuite.h:160
void removeFirst()
Definition: ftmpl_list.cc:287
CFList subset(int index [], const int &s, const CFArray &elements, bool &noSubset)
extract a subset given by index of size s from elements, if there is no subset we have not yet consid...
int status int void * buf
Definition: si_signals.h:59
int level() const
Definition: factory.h:132
static CanonicalForm myContent(const CanonicalForm &F)
Variable getBeta() const
getter
int i
Definition: cfEzgcd.cc:123
void appendMapDown(CFList &factors, const CanonicalForm &g, const ExtensionInfo &info, CFList &source, CFList &dest)
map g down into a subfield of the current field and append it to factors
CFList recombination(const CFList &factors1, const CFList &factors2, int s, int thres, const CanonicalForm &evalPoint, const Variable &x)
recombination of bivariate factors factors1 s. t. the result evaluated at evalPoint coincides with fa...
void appendTestMapDown(CFList &factors, const CanonicalForm &f, const ExtensionInfo &info, CFList &source, CFList &dest)
test if g is in a subfield of the current field, if so map it down and append it to factors ...
CanonicalForm buf2
Definition: facFqBivar.cc:71
Variable beta
Definition: facAbsFact.cc:99
bool fdivides(const CanonicalForm &f, const CanonicalForm &g)
bool fdivides ( const CanonicalForm & f, const CanonicalForm & g )
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:37
int length() const
Definition: ftmpl_list.cc:273
fq_nmod_poly_t prod
Definition: facHensel.cc:95
int degree(const CanonicalForm &f)
static jList * T
Definition: janet.cc:37
CanonicalForm getGamma() const
getter
template List< Variable > Difference(const List< Variable > &, const List< Variable > &)
return result
Definition: facAbsBiFact.cc:76

§ factorizationWRTDifferentSecondVars()

void factorizationWRTDifferentSecondVars ( const CanonicalForm A,
CFList *&  Aeval,
const ExtensionInfo info,
int &  minFactorsLength,
bool &  irred 
)

Definition at line 2169 of file facFqFactorize.cc.

2172 {
2173  Variable x= Variable (1);
2174  minFactorsLength= 0;
2175  irred= false;
2176  CFList factors;
2177  Variable v;
2178  for (int j= 0; j < A.level() - 2; j++)
2179  {
2180  if (!Aeval[j].isEmpty())
2181  {
2182  v= Variable (Aeval[j].getFirst().level());
2184  factors= GFBiSqrfFactorize (Aeval[j].getFirst());
2185  else if (info.getAlpha().level() == 1)
2186  factors= FpBiSqrfFactorize (Aeval[j].getFirst());
2187  else
2188  factors= FqBiSqrfFactorize (Aeval[j].getFirst(), info.getAlpha());
2189 
2190  factors.removeFirst();
2191  if (minFactorsLength == 0)
2192  minFactorsLength= factors.length();
2193  else
2195 
2196  if (factors.length() == 1)
2197  {
2198  irred= true;
2199  return;
2200  }
2201  sortList (factors, x);
2202  Aeval [j]= factors;
2203  }
2204  }
2205 }
Variable getAlpha() const
getter
int level(const CanonicalForm &f)
factory&#39;s class for variables
Definition: factory.h:115
CFList int & minFactorsLength
[in,out] minimal length of < bivariate factors
Definition: facFactorize.h:31
CFList GFBiSqrfFactorize(const CanonicalForm &G)
factorize a squarefree bivariate polynomial over GF
Definition: facFqBivar.h:164
CFList FqBiSqrfFactorize(const CanonicalForm &G, const Variable &alpha)
factorize a squarefree bivariate polynomial over .
Definition: facFqBivar.h:150
void removeFirst()
Definition: ftmpl_list.cc:287
void sortList(CFList &list, const Variable &x)
sort a list of polynomials by their degree in x.
Definition: facHensel.cc:441
int j
Definition: myNF.cc:70
int level() const
Definition: factory.h:132
CFList FpBiSqrfFactorize(const CanonicalForm &G)
factorize a squarefree bivariate polynomial over .
Definition: facFqBivar.h:137
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:37
int length() const
Definition: ftmpl_list.cc:273
static int gettype()
Definition: cf_factory.h:27
Variable x
Definition: cfModGcd.cc:4023
#define GaloisFieldDomain
Definition: cf_defs.h:22
CFList int bool & irred
[in,out] Is A irreducible?
Definition: facFactorize.h:31
int level() const
level() returns the level of CO.
template CanonicalForm tmin(const CanonicalForm &, const CanonicalForm &)

§ factorRecombination()

CFList factorRecombination ( const CanonicalForm F,
const CFList factors,
const CFList M 
)

Naive factor recombination for multivariate factorization. No precomputed is used to exclude combinations.

Returns
factorRecombination returns a list of factors of F
See also
extFactorRecombination()
Parameters
[in]Fpoly to be factored
[in]factorslist of lifted factors that are monic wrt Variable (1)
[in]Ma list of powers of Variables

Definition at line 360 of file facFqFactorize.cc.

362 {
363  if (factors.length() == 1)
364  return CFList(F);
365  if (factors.length() < 1)
366  return CFList();
367 
368  CFList T, S;
369 
370  T= factors;
371 
372  int s= 1;
373  CFList result;
374  CanonicalForm LCBuf= LC (F, Variable (1));
375  CanonicalForm g, buf= F;
376  int * v= new int [T.length()];
377  for (int i= 0; i < T.length(); i++)
378  v[i]= 0;
379  bool noSubset= false;
380  CFArray TT;
381  TT= copy (factors);
382  Variable y= F.level() - 1;
383  bool recombination= false;
384  CanonicalForm h, quot;
385  while (T.length() >= 2*s)
386  {
387  while (noSubset == false)
388  {
389  if (T.length() == s)
390  {
391  delete [] v;
392  if (recombination)
393  {
394  T.insert (LC (buf));
395  g= prodMod (T, M);
396  result.append (g/myContent (g));
397  return result;
398  }
399  else
400  return CFList (F);
401  }
402  S= subset (v, s, TT, noSubset);
403  if (noSubset) break;
404  S.insert (LCBuf);
405  g= prodMod (S, M);
406  S.removeFirst();
407  g /= myContent (g);
408  if (fdivides (g, buf, quot))
409  {
410  recombination= true;
411  result.append (g);
412  buf= quot;
413  LCBuf= LC (buf, Variable(1));
414  T= Difference (T, S);
415  if (T.length() < 2*s || T.length() == s)
416  {
417  result.append (buf);
418  delete [] v;
419  return result;
420  }
421  TT= copy (T);
422  indexUpdate (v, s, T.length(), noSubset);
423  if (noSubset) break;
424  }
425  }
426  s++;
427  if (T.length() < 2*s || T.length() == s)
428  {
429  result.append (buf);
430  delete [] v;
431  return result;
432  }
433  for (int i= 0; i < T.length(); i++)
434  v[i]= 0;
435  noSubset= false;
436  }
437  if (T.length() < 2*s)
438  result.append (F);
439 
440  delete [] v;
441  return result;
442 }
void indexUpdate(int index [], const int &subsetSize, const int &setSize, bool &noSubset)
update index
List< CanonicalForm > CFList
const CanonicalForm int s
Definition: facAbsFact.cc:55
const CanonicalForm int const CFList const Variable & y
Definition: facAbsFact.cc:57
CFArray copy(const CFList &list)
write elements of list into an array
factory&#39;s class for variables
Definition: factory.h:115
factory&#39;s main class
Definition: canonicalform.h:75
g
Definition: cfModGcd.cc:4031
void insert(const T &)
Definition: ftmpl_list.cc:193
void removeFirst()
Definition: ftmpl_list.cc:287
CFList subset(int index [], const int &s, const CFArray &elements, bool &noSubset)
extract a subset given by index of size s from elements, if there is no subset we have not yet consid...
int status int void * buf
Definition: si_signals.h:59
static CanonicalForm myContent(const CanonicalForm &F)
int i
Definition: cfEzgcd.cc:123
CFList recombination(const CFList &factors1, const CFList &factors2, int s, int thres, const CanonicalForm &evalPoint, const Variable &x)
recombination of bivariate factors factors1 s. t. the result evaluated at evalPoint coincides with fa...
bool fdivides(const CanonicalForm &f, const CanonicalForm &g)
bool fdivides ( const CanonicalForm & f, const CanonicalForm & g )
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:37
int length() const
Definition: ftmpl_list.cc:273
int level() const
level() returns the level of CO.
void append(const T &)
Definition: ftmpl_list.cc:256
static jList * T
Definition: janet.cc:37
CanonicalForm LC(const CanonicalForm &f)
static Poly * h
Definition: janet.cc:978
template List< Variable > Difference(const List< Variable > &, const List< Variable > &)
return result
Definition: facAbsBiFact.cc:76
CanonicalForm prodMod(const CFList &L, const CanonicalForm &M)
product of all elements in L modulo M via divide-and-conquer.
Definition: facMul.cc:3047

§ gcdFreeBasis()

void gcdFreeBasis ( CFFList factors1,
CFFList factors2 
)

gcd free basis of two lists of factors

Parameters
[in,out]factors1list of factors, returns gcd free factors
[in,out]factors2list of factors, returns gcd free factors

Definition at line 1255 of file facFqFactorize.cc.

1256 {
1257  CanonicalForm g;
1258  int k= factors1.length();
1259  int l= factors2.length();
1260  int n= 0;
1261  int m;
1263  for (CFFListIterator i= factors1; (n < k && i.hasItem()); i++, n++)
1264  {
1265  m= 0;
1266  for (j= factors2; (m < l && j.hasItem()); j++, m++)
1267  {
1268  g= gcd (i.getItem().factor(), j.getItem().factor());
1269  if (degree (g,1) > 0)
1270  {
1271  j.getItem()= CFFactor (j.getItem().factor()/g, j.getItem().exp());
1272  i.getItem()= CFFactor (i.getItem().factor()/g, i.getItem().exp());
1273  factors1.append (CFFactor (g, i.getItem().exp()));
1274  factors2.append (CFFactor (g, j.getItem().exp()));
1275  }
1276  }
1277  }
1278 }
factory&#39;s main class
Definition: canonicalform.h:75
g
Definition: cfModGcd.cc:4031
int k
Definition: cfEzgcd.cc:93
int j
Definition: myNF.cc:70
T & getItem() const
Definition: ftmpl_list.cc:431
int m
Definition: cfEzgcd.cc:119
int i
Definition: cfEzgcd.cc:123
int length() const
Definition: ftmpl_list.cc:273
Factor< CanonicalForm > CFFactor
int gcd(int a, int b)
Definition: walkSupport.cc:839
void append(const T &)
Definition: ftmpl_list.cc:256
int degree(const CanonicalForm &f)
int l
Definition: cfEzgcd.cc:94

§ getLeadingCoeffs()

void getLeadingCoeffs ( const CanonicalForm A,
CFList *&  Aeval 
)

extract leading coefficients wrt Variable(1) from bivariate factors obtained from factorizations of A wrt different second variables

Parameters
[in]Asome poly
[in,out]Aevalarray of bivariate factors, returns the leading coefficients of these factors

Definition at line 2216 of file facFqFactorize.cc.

2218 {
2220  CFList LCs;
2221  for (int j= 0; j < A.level() - 2; j++)
2222  {
2223  if (!Aeval[j].isEmpty())
2224  {
2225  LCs= CFList();
2226  for (iter= Aeval[j]; iter.hasItem(); iter++)
2227  LCs.append (LC (iter.getItem(), 1));
2228  //normalize (LCs);
2229  Aeval[j]= LCs;
2230  }
2231  }
2232 }
List< CanonicalForm > CFList
CFFListIterator iter
Definition: facAbsBiFact.cc:54
int j
Definition: myNF.cc:70
T & getItem() const
Definition: ftmpl_list.cc:431
int level() const
level() returns the level of CO.
void append(const T &)
Definition: ftmpl_list.cc:256
CanonicalForm LC(const CanonicalForm &f)

§ henselLiftAndEarly()

CFList henselLiftAndEarly ( CanonicalForm A,
CFList MOD,
int *&  liftBounds,
bool &  earlySuccess,
CFList earlyFactors,
const CFList Aeval,
const CFList biFactors,
const CFList evaluation,
const ExtensionInfo info 
)

hensel Lifting and early factor detection

Returns
henselLiftAndEarly returns monic (wrt Variable (1)) lifted factors without factors which have been detected at an early stage of Hensel lifting
See also
earlyFactorDetectn(), extEarlyFactorDetect()
Parameters
[in,out]Apoly to be factored, returns poly divided by detected factors, in case of success
[in,out]MODa list of powers of Variables
[in,out]liftBoundsinitial lift bounds, returns adapted lift bounds
[in,out]earlySuccessindicating success
[in,out]earlyFactorsearly factors
[in]AevalA successively evaluated at elements of evaluation
[in]biFactorsbivariate factors
[in]evaluationevaluation point
[in]infoinfo about extension

Definition at line 972 of file facFqFactorize.cc.

976 {
977  bool extension= info.isInExtension();
978  CFList bufFactors= biFactors;
979  bufFactors.insert (LC (Aeval.getFirst(), 1));
980 
981  sortList (bufFactors, Variable (1));
982 
983  CFList diophant;
984  CFArray Pi;
985  int smallFactorDeg= 11; //tunable parameter
986  CFList result;
987  int adaptedLiftBound= 0;
988  int liftBound= liftBounds[1];
989 
990  earlySuccess= false;
991  CFList earlyReconstFactors;
993  j++;
995  CFMatrix Mat= CFMatrix (liftBound, bufFactors.length() - 1);
996  MOD= CFList (power (Variable (2), liftBounds[0]));
997  if (smallFactorDeg >= liftBound)
998  {
999  result= henselLift23 (Aeval, bufFactors, liftBounds, diophant, Pi, Mat);
1000  }
1001  else if (smallFactorDeg >= degree (buf) + 1)
1002  {
1003  liftBounds[1]= degree (buf) + 1;
1004  result= henselLift23 (Aeval, bufFactors, liftBounds, diophant, Pi, Mat);
1005  if (Aeval.length() == 2)
1006  {
1007  if (!extension)
1008  earlyFactors= earlyFactorDetect
1009  (buf, result, adaptedLiftBound, earlySuccess,
1010  degree (buf) + 1, MOD, liftBound);
1011  else
1012  earlyFactors= extEarlyFactorDetect
1013  (buf, result, adaptedLiftBound, earlySuccess,
1014  info, evaluation, degree
1015  (buf) + 1, MOD, liftBound);
1016  }
1017  else
1018  {
1019  if (!extension)
1020  adaptedLiftBound= liftBoundAdaption (buf, result, earlySuccess,
1021  degree (buf) + 1, MOD, liftBound);
1022  else
1023  adaptedLiftBound= extLiftBoundAdaption (buf, result, earlySuccess, info,
1024  evaluation, degree (buf) + 1,
1025  MOD, liftBound);
1026  }
1027  if (!earlySuccess)
1028  {
1029  result.insert (LC (buf, 1));
1030  liftBounds[1]= adaptedLiftBound;
1031  liftBound= adaptedLiftBound;
1032  henselLiftResume (buf, result, degree (buf) + 1, liftBound,
1033  Pi, diophant, Mat, MOD);
1034  }
1035  else
1036  liftBounds[1]= adaptedLiftBound;
1037  }
1038  else if (smallFactorDeg < degree (buf) + 1)
1039  {
1040  liftBounds[1]= smallFactorDeg;
1041  result= henselLift23 (Aeval, bufFactors, liftBounds, diophant, Pi, Mat);
1042  if (Aeval.length() == 2)
1043  {
1044  if (!extension)
1045  earlyFactors= earlyFactorDetect (buf, result, adaptedLiftBound,
1046  earlySuccess, smallFactorDeg, MOD,
1047  liftBound);
1048  else
1049  earlyFactors= extEarlyFactorDetect (buf, result, adaptedLiftBound,
1050  earlySuccess, info, evaluation,
1051  smallFactorDeg, MOD, liftBound);
1052  }
1053  else
1054  {
1055  if (!extension)
1056  adaptedLiftBound= liftBoundAdaption (buf, result, earlySuccess,
1057  smallFactorDeg, MOD, liftBound);
1058  else
1059  adaptedLiftBound= extLiftBoundAdaption (buf, result, earlySuccess, info,
1060  evaluation, smallFactorDeg, MOD,
1061  liftBound);
1062  }
1063 
1064  if (!earlySuccess)
1065  {
1066  result.insert (LC (buf, 1));
1067  henselLiftResume (buf, result, smallFactorDeg, degree (buf) + 1,
1068  Pi, diophant, Mat, MOD);
1069  if (Aeval.length() == 2)
1070  {
1071  if (!extension)
1072  earlyFactors= earlyFactorDetect (buf, result, adaptedLiftBound,
1073  earlySuccess, degree (buf) + 1,
1074  MOD, liftBound);
1075  else
1076  earlyFactors= extEarlyFactorDetect (buf, result, adaptedLiftBound,
1077  earlySuccess, info, evaluation,
1078  degree (buf) + 1, MOD,
1079  liftBound);
1080  }
1081  else
1082  {
1083  if (!extension)
1084  adaptedLiftBound= liftBoundAdaption (buf, result, earlySuccess,
1085  degree (buf) + 1, MOD,liftBound);
1086  else
1087  adaptedLiftBound= extLiftBoundAdaption (buf, result, earlySuccess,
1088  info, evaluation,
1089  degree (buf) + 1, MOD,
1090  liftBound);
1091  }
1092  if (!earlySuccess)
1093  {
1094  result.insert (LC (buf, 1));
1095  liftBounds[1]= adaptedLiftBound;
1096  liftBound= adaptedLiftBound;
1097  henselLiftResume (buf, result, degree (buf) + 1, liftBound,
1098  Pi, diophant, Mat, MOD);
1099  }
1100  else
1101  liftBounds[1]= adaptedLiftBound;
1102  }
1103  else
1104  liftBounds[1]= adaptedLiftBound;
1105  }
1106 
1107  MOD.append (power (Variable (3), liftBounds[1]));
1108 
1109  if (Aeval.length() > 2)
1110  {
1111  CFListIterator j= Aeval;
1112  j++;
1113  CFList bufEval;
1114  bufEval.append (j.getItem());
1115  j++;
1116  int liftBoundsLength= Aeval.getLast().level() - 1;
1117  for (int i= 2; i <= liftBoundsLength && j.hasItem(); i++, j++)
1118  {
1119  earlySuccess= false;
1120  result.insert (LC (bufEval.getFirst(), 1));
1121  bufEval.append (j.getItem());
1122  liftBound= liftBounds[i];
1123  Mat= CFMatrix (liftBounds[i], result.length() - 1);
1124 
1125  buf= j.getItem();
1126  if (smallFactorDeg >= liftBound)
1127  result= henselLift (bufEval, result, MOD, diophant, Pi, Mat,
1128  liftBounds[i - 1], liftBounds[i]);
1129  else if (smallFactorDeg >= degree (buf) + 1)
1130  {
1131  result= henselLift (bufEval, result, MOD, diophant, Pi, Mat,
1132  liftBounds[i - 1], degree (buf) + 1);
1133 
1134  if (Aeval.length() == i + 1)
1135  {
1136  if (!extension)
1137  earlyFactors= earlyFactorDetect
1138  (buf, result, adaptedLiftBound, earlySuccess,
1139  degree (buf) + 1, MOD, liftBound);
1140  else
1141  earlyFactors= extEarlyFactorDetect
1142  (buf, result, adaptedLiftBound, earlySuccess,
1143  info, evaluation, degree (buf) + 1, MOD, liftBound);
1144  }
1145  else
1146  {
1147  if (!extension)
1148  adaptedLiftBound= liftBoundAdaption
1149  (buf, result, earlySuccess, degree (buf)
1150  + 1, MOD, liftBound);
1151  else
1152  adaptedLiftBound= extLiftBoundAdaption
1153  (buf, result, earlySuccess, info, evaluation,
1154  degree (buf) + 1, MOD, liftBound);
1155  }
1156 
1157  if (!earlySuccess)
1158  {
1159  result.insert (LC (buf, 1));
1160  liftBounds[i]= adaptedLiftBound;
1161  liftBound= adaptedLiftBound;
1162  henselLiftResume (buf, result, degree (buf) + 1, liftBound,
1163  Pi, diophant, Mat, MOD);
1164  }
1165  else
1166  {
1167  liftBounds[i]= adaptedLiftBound;
1168  }
1169  }
1170  else if (smallFactorDeg < degree (buf) + 1)
1171  {
1172  result= henselLift (bufEval, result, MOD, diophant, Pi, Mat,
1173  liftBounds[i - 1], smallFactorDeg);
1174 
1175  if (Aeval.length() == i + 1)
1176  {
1177  if (!extension)
1178  earlyFactors= earlyFactorDetect
1179  (buf, result, adaptedLiftBound, earlySuccess,
1180  smallFactorDeg, MOD, liftBound);
1181  else
1182  earlyFactors= extEarlyFactorDetect
1183  (buf, result, adaptedLiftBound, earlySuccess,
1184  info, evaluation, smallFactorDeg, MOD, liftBound);
1185  }
1186  else
1187  {
1188  if (!extension)
1189  adaptedLiftBound= liftBoundAdaption
1190  (buf, result, earlySuccess,
1191  smallFactorDeg, MOD, liftBound);
1192  else
1193  adaptedLiftBound= extLiftBoundAdaption
1194  (buf, result, earlySuccess, info, evaluation,
1195  smallFactorDeg, MOD, liftBound);
1196  }
1197 
1198  if (!earlySuccess)
1199  {
1200  result.insert (LC (buf, 1));
1201  henselLiftResume (buf, result, smallFactorDeg,
1202  degree (buf) + 1, Pi, diophant, Mat, MOD);
1203  if (Aeval.length() == i + 1)
1204  {
1205  if (!extension)
1206  earlyFactors= earlyFactorDetect
1207  (buf, result, adaptedLiftBound, earlySuccess,
1208  degree (buf) + 1, MOD, liftBound);
1209  else
1210  earlyFactors= extEarlyFactorDetect
1211  (buf, result, adaptedLiftBound, earlySuccess,
1212  info, evaluation, degree (buf) + 1, MOD,
1213  liftBound);
1214  }
1215  else
1216  {
1217  if (!extension)
1218  adaptedLiftBound= liftBoundAdaption
1219  (buf, result, earlySuccess, degree
1220  (buf) + 1, MOD, liftBound);
1221  else
1222  adaptedLiftBound= extLiftBoundAdaption
1223  (buf, result, earlySuccess, info, evaluation,
1224  degree (buf) + 1, MOD, liftBound);
1225  }
1226 
1227  if (!earlySuccess)
1228  {
1229  result.insert (LC (buf, 1));
1230  liftBounds[i]= adaptedLiftBound;
1231  liftBound= adaptedLiftBound;
1232  henselLiftResume (buf, result, degree (buf) + 1, liftBound,
1233  Pi, diophant, Mat, MOD);
1234  }
1235  else
1236  liftBounds[i]= adaptedLiftBound;
1237  }
1238  else
1239  liftBounds[i]= adaptedLiftBound;
1240  }
1241  MOD.append (power (Variable (i + 2), liftBounds[i]));
1242  bufEval.removeFirst();
1243  }
1244  bufFactors= result;
1245  }
1246  else
1247  bufFactors= result;
1248 
1249  if (earlySuccess)
1250  A= buf;
1251  return result;
1252 }
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
List< CanonicalForm > CFList
Matrix< CanonicalForm > CFMatrix
factory&#39;s class for variables
Definition: factory.h:115
CFList *& Aeval
<[in] poly
Definition: facFactorize.h:31
factory&#39;s main class
Definition: canonicalform.h:75
void insert(const T &)
Definition: ftmpl_list.cc:193
CFList earlyFactorDetect(CanonicalForm &F, CFList &factors, int &adaptedLiftBound, bool &success, const int deg, const CFList &MOD, const int bound)
detects factors of F at stage deg of Hensel lifting. No combinations of more than one factor are test...
void removeFirst()
Definition: ftmpl_list.cc:287
void sortList(CFList &list, const Variable &x)
sort a list of polynomials by their degree in x.
Definition: facHensel.cc:441
T getFirst() const
Definition: ftmpl_list.cc:279
int j
Definition: myNF.cc:70
int status int void * buf
Definition: si_signals.h:59
T & getItem() const
Definition: ftmpl_list.cc:431
CFList henselLift23(const CFList &eval, const CFList &factors, int *l, CFList &diophant, CFArray &Pi, CFMatrix &M)
Hensel lifting from bivariate to trivariate.
Definition: facHensel.cc:1653
int extLiftBoundAdaption(const CanonicalForm &F, const CFList &factors, bool &success, const ExtensionInfo &info, const CFList &eval, const int deg, const CFList &MOD, const int bound)
Lift bound adaption over an extension of the initial field. Essentially an early factor detection but...
CFList extEarlyFactorDetect(CanonicalForm &F, CFList &factors, int &adaptedLiftBound, bool &success, const ExtensionInfo &info, const CFList &eval, const int deg, const CFList &MOD, const int bound)
detects factors of F at stage deg of Hensel lifting. No combinations of more than one factor are test...
int i
Definition: cfEzgcd.cc:123
T getLast() const
Definition: ftmpl_list.cc:309
int length() const
Definition: ftmpl_list.cc:273
bool isInExtension() const
getter
void henselLiftResume(const CanonicalForm &F, CFList &factors, int start, int end, CFArray &Pi, const CFList &diophant, CFMatrix &M, const CFList &MOD)
resume Hensel lifting.
Definition: facHensel.cc:1694
int liftBoundAdaption(const CanonicalForm &F, const CFList &factors, bool &success, const int deg, const CFList &MOD, const int bound)
Lift bound adaption. Essentially an early factor detection but only the lift bound is adapted...
int level() const
level() returns the level of CO.
void append(const T &)
Definition: ftmpl_list.cc:256
int degree(const CanonicalForm &f)
CanonicalForm LC(const CanonicalForm &f)
return result
Definition: facAbsBiFact.cc:76
CFList henselLift(const CFList &F, const CFList &factors, const CFList &MOD, CFList &diophant, CFArray &Pi, CFMatrix &M, int lOld, int lNew)
Hensel lifting.
Definition: facHensel.cc:1719

§ LCHeuristic()

void LCHeuristic ( CanonicalForm A,
const CanonicalForm LCmultiplier,
CFList biFactors,
CFList *&  leadingCoeffs,
const CFList oldAeval,
int  lengthAeval,
const CFList evaluation,
const CFList oldBiFactors 
)

heuristic to distribute LCmultiplier onto factors based on the variables that occur in LCmultiplier and in the leading coeffs of bivariate factors

Parameters
[in,out]Aa poly
[in,out]LCmultiplierdivisor of LC (A,1)
[in,out]biFactorsbivariate factors
[in,out]leadingCoeffsleading coeffs
[in]oldAevalbivariate factors wrt. different second vars
[in]lengthAevallength of oldAeval
[in]evaluationevaluation point
[in]oldBiFactorsbivariate factors without LCmultiplier distributed on them

Definition at line 2598 of file facFqFactorize.cc.

2602 {
2603  CFListIterator iter, iter2;
2604  int index;
2605  Variable xx;
2606  CFList vars1;
2607  CFFList sqrfMultiplier= sqrFree (LCmultiplier);
2608  if (sqrfMultiplier.getFirst().factor().inCoeffDomain())
2609  sqrfMultiplier.removeFirst();
2610  sqrfMultiplier= sortCFFListByNumOfVars (sqrfMultiplier);
2611  xx= Variable (2);
2612  for (iter= oldBiFactors; iter.hasItem(); iter++)
2613  vars1.append (power (xx, degree (LC (iter.getItem(),1), xx)));
2614  for (int i= 0; i < lengthAeval; i++)
2615  {
2616  if (oldAeval[i].isEmpty())
2617  continue;
2618  xx= oldAeval[i].getFirst().mvar();
2619  iter2= vars1;
2620  for (iter= oldAeval[i]; iter.hasItem(); iter++, iter2++)
2621  iter2.getItem() *= power (xx, degree (LC (iter.getItem(),1), xx));
2622  }
2623  CanonicalForm tmp, quot1, quot2, quot3;
2624  iter2= vars1;
2625  for (iter= leadingCoeffs[lengthAeval-1]; iter.hasItem(); iter++, iter2++)
2626  {
2627  tmp= iter.getItem()/LCmultiplier;
2628  for (int i=1; i <= tmp.level(); i++)
2629  {
2630  if (degree (tmp,i) > 0 && (degree (iter2.getItem(),i) > degree (tmp,i)))
2631  iter2.getItem() /= power (Variable (i), degree (tmp,i));
2632  }
2633  }
2634  int multi;
2635  for (CFFListIterator ii= sqrfMultiplier; ii.hasItem(); ii++)
2636  {
2637  multi= 0;
2638  for (iter= vars1; iter.hasItem(); iter++)
2639  {
2640  tmp= iter.getItem();
2641  while (fdivides (myGetVars (ii.getItem().factor()), tmp))
2642  {
2643  multi++;
2644  tmp /= myGetVars (ii.getItem().factor());
2645  }
2646  }
2647  if (multi == ii.getItem().exp())
2648  {
2649  index= 1;
2650  for (iter= vars1; iter.hasItem(); iter++, index++)
2651  {
2652  while (fdivides (myGetVars (ii.getItem().factor()), iter.getItem()))
2653  {
2654  int index2= 1;
2655  for (iter2= leadingCoeffs[lengthAeval-1]; iter2.hasItem();iter2++,
2656  index2++)
2657  {
2658  if (index2 == index)
2659  continue;
2660  else
2661  {
2662  tmp= ii.getItem().factor();
2663  if (fdivides (tmp, iter2.getItem(), quot1))
2664  {
2665  CFListIterator iter3= evaluation;
2666  for (int jj= A.level(); jj > 2; jj--, iter3++)
2667  tmp= tmp (iter3.getItem(), jj);
2668  if (!tmp.inCoeffDomain())
2669  {
2670  int index3= 1;
2671  for (iter3= biFactors; iter3.hasItem(); iter3++, index3++)
2672  {
2673  if (index3 == index2)
2674  {
2675  if (fdivides (tmp, iter3.getItem(), quot2))
2676  {
2677  if (fdivides (ii.getItem().factor(), A, quot3))
2678  {
2679  A = quot3;
2680  iter2.getItem() = quot2;
2681  iter3.getItem() = quot3;
2682  iter3.getItem() /= Lc (iter3.getItem());
2683  break;
2684  }
2685  }
2686  }
2687  }
2688  }
2689  }
2690  }
2691  }
2692  iter.getItem() /= getVars (ii.getItem().factor());
2693  }
2694  }
2695  }
2696  else
2697  {
2698  index= 1;
2699  for (iter= vars1; iter.hasItem(); iter++, index++)
2700  {
2701  if (!fdivides (myGetVars (ii.getItem().factor()), iter.getItem()))
2702  {
2703  int index2= 1;
2704  for (iter2= leadingCoeffs[lengthAeval-1];iter2.hasItem();iter2++,
2705  index2++)
2706  {
2707  if (index2 == index)
2708  {
2709  tmp= power (ii.getItem().factor(), ii.getItem().exp());
2710  if (fdivides (tmp, A, quot1))
2711  {
2712  if (fdivides (tmp, iter2.getItem()))
2713  {
2714  CFListIterator iter3= evaluation;
2715  for (int jj= A.level(); jj > 2; jj--, iter3++)
2716  tmp= tmp (iter3.getItem(), jj);
2717  if (!tmp.inCoeffDomain())
2718  {
2719  int index3= 1;
2720  for (iter3= biFactors; iter3.hasItem(); iter3++, index3++)
2721  {
2722  if (index3 == index2)
2723  {
2724  if (fdivides (tmp, iter3.getItem(), quot3))
2725  {
2726  A = quot1;
2727  iter2.getItem() = quot2;
2728  iter3.getItem() = quot3;
2729  iter3.getItem() /= Lc (iter3.getItem());
2730  break;
2731  }
2732  }
2733  }
2734  }
2735  }
2736  }
2737  }
2738  }
2739  }
2740  }
2741  }
2742  }
2743 }
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
factory&#39;s class for variables
Definition: factory.h:115
CFFListIterator iter
Definition: facAbsBiFact.cc:54
factory&#39;s main class
Definition: canonicalform.h:75
const CanonicalForm int const CFList & evaluation
Definition: facAbsFact.cc:55
CanonicalForm Lc(const CanonicalForm &f)
void removeFirst()
Definition: ftmpl_list.cc:287
CFFList sortCFFListByNumOfVars(CFFList &F)
sort CFFList by the number variables in a factor
T getFirst() const
Definition: ftmpl_list.cc:279
CanonicalForm getVars(const CanonicalForm &f)
CanonicalForm getVars ( const CanonicalForm & f )
Definition: cf_ops.cc:350
T & getItem() const
Definition: ftmpl_list.cc:431
#define A
Definition: sirandom.c:23
int i
Definition: cfEzgcd.cc:123
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
static int index(p_Length length, p_Ord ord)
Definition: p_Procs_Impl.h:592
bool fdivides(const CanonicalForm &f, const CanonicalForm &g)
bool fdivides ( const CanonicalForm & f, const CanonicalForm & g )
CanonicalForm myGetVars(const CanonicalForm &F)
like getVars but including multiplicities
int level() const
level() returns the level of CO.
void append(const T &)
Definition: ftmpl_list.cc:256
int degree(const CanonicalForm &f)
CanonicalForm LC(const CanonicalForm &f)
CFFList sqrFree(const CanonicalForm &f, bool sort=false)
squarefree factorization
Definition: cf_factor.cc:757

§ LCHeuristic2()

void LCHeuristic2 ( const CanonicalForm LCmultiplier,
const CFList factors,
CFList leadingCoeffs,
CFList contents,
CFList LCs,
bool &  foundTrueMultiplier 
)

heuristic to distribute LCmultiplier onto factors based on the contents of factors. factors are assumed to come from LucksWangSparseHeuristic. If not successful contents will contain the content of each element of factors and LCs will contain the LC of each element of factors divided by its content

Parameters
[in]LCmultiplierdivisor of LC (A,1)
[in]factorsresult of LucksWangSparseHeuristic
[in,out]leadingCoeffsleading coeffs
[in,out]contentscontent of factors
[in,out]LCsLC of factors divided by content of factors
[in,out]foundTrueMultipliersuccess?

Definition at line 2762 of file facFqFactorize.cc.

2765 {
2766  CanonicalForm cont;
2767  int index= 1;
2768  CFListIterator iter2;
2769  for (CFListIterator iter= factors; iter.hasItem(); iter++, index++)
2770  {
2771  cont= content (iter.getItem(), 1);
2772  cont= gcd (cont, LCmultiplier);
2773  contents.append (cont);
2774  if (cont.inCoeffDomain()) // trivial content->LCmultiplier needs to go there
2775  {
2776  foundTrueMultiplier= true;
2777  int index2= 1;
2778  for (iter2= leadingCoeffs; iter2.hasItem(); iter2++, index2++)
2779  {
2780  if (index2 == index)
2781  continue;
2782  iter2.getItem() /= LCmultiplier;
2783  }
2784  break;
2785  }
2786  else
2787  LCs.append (LC (iter.getItem()/cont, 1));
2788  }
2789 }
CFFListIterator iter
Definition: facAbsBiFact.cc:54
factory&#39;s main class
Definition: canonicalform.h:75
CanonicalForm content(const CanonicalForm &)
CanonicalForm content ( const CanonicalForm & f )
Definition: cf_gcd.cc:180
T & getItem() const
Definition: ftmpl_list.cc:431
static int index(p_Length length, p_Ord ord)
Definition: p_Procs_Impl.h:592
int gcd(int a, int b)
Definition: walkSupport.cc:839
void append(const T &)
Definition: ftmpl_list.cc:256
CanonicalForm LC(const CanonicalForm &f)

§ LCHeuristic3()

void LCHeuristic3 ( const CanonicalForm LCmultiplier,
const CFList factors,
const CFList oldBiFactors,
const CFList contents,
const CFList oldAeval,
CanonicalForm A,
CFList *&  leadingCoeffs,
int  lengthAeval,
bool &  foundMultiplier 
)

heuristic to remove LCmultiplier from a factor based on the contents of factors. factors are assumed to come from LucksWangSparseHeuristic.

Parameters
[in]LCmultiplierdivisor of LC (A,1)
[in]factorsresult of LucksWangSparseHeuristic
[in]oldBiFactorsbivariate factors without LCmultiplier distributed on them
[in]contentscontent of factors
[in]oldAevalbivariate factors wrt. different second vars
[in,out]Apoly
[in,out]leadingCoeffsleading coeffs
[in]lengthAevallength of oldAeval
[in,out]foundMultipliersuccess?

Definition at line 2792 of file facFqFactorize.cc.

2796 {
2797  int index= 1;
2798  CFListIterator iter, iter2= factors;
2799  for (iter= contents; iter.hasItem(); iter++, iter2++, index++)
2800  {
2801  if (fdivides (iter.getItem(), LCmultiplier))
2802  {
2803  if ((LCmultiplier/iter.getItem()).inCoeffDomain() &&
2804  !isOnlyLeadingCoeff(iter2.getItem())) //content divides LCmultiplier completely and factor consists of more terms than just the leading coeff
2805  {
2806  Variable xx= Variable (2);
2807  CanonicalForm vars;
2808  vars= power (xx, degree (LC (getItem(oldBiFactors, index),1),
2809  xx));
2810  for (int i= 0; i < lengthAeval; i++)
2811  {
2812  if (oldAeval[i].isEmpty())
2813  continue;
2814  xx= oldAeval[i].getFirst().mvar();
2815  vars *= power (xx, degree (LC (getItem(oldAeval[i], index),1),
2816  xx));
2817  }
2818  if (vars.level() <= 2)
2819  {
2820  int index2= 1;
2821  for (CFListIterator iter3= leadingCoeffs[lengthAeval-1];
2822  iter3.hasItem(); iter3++, index2++)
2823  {
2824  if (index2 == index)
2825  {
2826  iter3.getItem() /= LCmultiplier;
2827  break;
2828  }
2829  }
2830  A /= LCmultiplier;
2831  foundMultiplier= true;
2832  iter.getItem()= 1;
2833  }
2834  }
2835  }
2836  }
2837 }
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
CanonicalForm getItem(const CFList &list, const int &pos)
helper function
Definition: cf_map_ext.cc:49
factory&#39;s class for variables
Definition: factory.h:115
CFFListIterator iter
Definition: facAbsBiFact.cc:54
factory&#39;s main class
Definition: canonicalform.h:75
bool isOnlyLeadingCoeff(const CanonicalForm &F)
check if F consists of more than just the leading coeff wrt. Variable (1)
T getFirst() const
Definition: ftmpl_list.cc:279
T & getItem() const
Definition: ftmpl_list.cc:431
int i
Definition: cfEzgcd.cc:123
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
static int index(p_Length length, p_Ord ord)
Definition: p_Procs_Impl.h:592
bool fdivides(const CanonicalForm &f, const CanonicalForm &g)
bool fdivides ( const CanonicalForm & f, const CanonicalForm & g )
int level() const
level() returns the level of CO.
int degree(const CanonicalForm &f)
CanonicalForm LC(const CanonicalForm &f)

§ LCHeuristic4()

void LCHeuristic4 ( const CFList oldBiFactors,
const CFList oldAeval,
const CFList contents,
const CFList factors,
const CanonicalForm testVars,
int  lengthAeval,
CFList *&  leadingCoeffs,
CanonicalForm A,
CanonicalForm LCmultiplier,
bool &  foundMultiplier 
)

heuristic to remove factors of LCmultiplier from factors. More precisely checks if elements of contents divide LCmultiplier. Assumes LCHeuristic3 is run before it and was successful.

Parameters
[in]oldBiFactorsbivariate factors without LCmultiplier distributed on them
[in]oldAevalbivariate factors wrt. different second vars
[in]contentscontent of factors
[in]factorsresult of LucksWangSparseHeuristic
[in]testVarsproduct of second vars that occur among oldAeval
[in]lengthAevallength of oldAeval
[in,out]leadingCoeffsleading coeffs
[in,out]Apoly
[in,out]LCmultiplierdivisor of LC (A,1)
[in]foundMultipliersuccess?

Definition at line 2840 of file facFqFactorize.cc.

2845 {
2846  int index=1;
2847  CFListIterator iter, iter2= factors;
2848  for (iter= contents; iter.hasItem(); iter++, iter2++, index++)
2849  {
2850  if (!iter.getItem().isOne() &&
2851  fdivides (iter.getItem(), LCmultiplier))
2852  {
2853  if (!isOnlyLeadingCoeff (iter2.getItem())) // factor is more than just leading coeff
2854  {
2855  int index2= 1;
2856  for (iter2= leadingCoeffs[lengthAeval-1]; iter2.hasItem();
2857  iter2++, index2++)
2858  {
2859  if (index2 == index)
2860  {
2861  iter2.getItem() /= iter.getItem();
2862  foundMultiplier= true;
2863  break;
2864  }
2865  }
2866  A /= iter.getItem();
2867  LCmultiplier /= iter.getItem();
2868  iter.getItem()= 1;
2869  }
2870  else if (fdivides (getVars (LCmultiplier), testVars))//factor consists of just leading coeff
2871  {
2872  Variable xx= Variable (2);
2873  CanonicalForm vars;
2874  vars= power (xx, degree (LC (getItem(oldBiFactors, index),1),
2875  xx));
2876  for (int i= 0; i < lengthAeval; i++)
2877  {
2878  if (oldAeval[i].isEmpty())
2879  continue;
2880  xx= oldAeval[i].getFirst().mvar();
2881  vars *= power (xx, degree (LC (getItem(oldAeval[i], index),1),
2882  xx));
2883  }
2884  if (myGetVars(content(getItem(leadingCoeffs[lengthAeval-1],index),1))
2885  /myGetVars (LCmultiplier) == vars)
2886  {
2887  int index2= 1;
2888  for (iter2= leadingCoeffs[lengthAeval-1]; iter2.hasItem();
2889  iter2++, index2++)
2890  {
2891  if (index2 == index)
2892  {
2893  iter2.getItem() /= LCmultiplier;
2894  foundMultiplier= true;
2895  break;
2896  }
2897  }
2898  A /= LCmultiplier;
2899  iter.getItem()= 1;
2900  }
2901  }
2902  }
2903  }
2904 }
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
CanonicalForm getItem(const CFList &list, const int &pos)
helper function
Definition: cf_map_ext.cc:49
factory&#39;s class for variables
Definition: factory.h:115
CFFListIterator iter
Definition: facAbsBiFact.cc:54
factory&#39;s main class
Definition: canonicalform.h:75
bool isOnlyLeadingCoeff(const CanonicalForm &F)
check if F consists of more than just the leading coeff wrt. Variable (1)
CanonicalForm content(const CanonicalForm &)
CanonicalForm content ( const CanonicalForm & f )
Definition: cf_gcd.cc:180
T getFirst() const
Definition: ftmpl_list.cc:279
CanonicalForm getVars(const CanonicalForm &f)
CanonicalForm getVars ( const CanonicalForm & f )
Definition: cf_ops.cc:350
T & getItem() const
Definition: ftmpl_list.cc:431
int i
Definition: cfEzgcd.cc:123
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
static int index(p_Length length, p_Ord ord)
Definition: p_Procs_Impl.h:592
bool fdivides(const CanonicalForm &f, const CanonicalForm &g)
bool fdivides ( const CanonicalForm & f, const CanonicalForm & g )
CanonicalForm myGetVars(const CanonicalForm &F)
like getVars but including multiplicities
int degree(const CanonicalForm &f)
CanonicalForm LC(const CanonicalForm &f)

§ LCHeuristicCheck()

void LCHeuristicCheck ( const CFList LCs,
const CFList contents,
CanonicalForm A,
const CanonicalForm oldA,
CFList leadingCoeffs,
bool &  foundTrueMultiplier 
)

checks if prod(LCs)==LC (oldA,1) and if so divides elements of leadingCoeffs by elements in contents, sets A to oldA and sets foundTrueMultiplier to true

Parameters
[in]LCsleading coeffs computed
[in]contentscontent of factors
[in,out]AoldA*LCmultiplier^m
[in]oldAsome poly
[in,out]leadingCoeffsleading coefficients
[in,out]foundTrueMultipliersuccess?

Definition at line 2746 of file facFqFactorize.cc.

2749 {
2750  CanonicalForm pLCs= prod (LCs);
2751  if (fdivides (pLCs, LC (oldA,1)) && (LC(oldA,1)/pLCs).inCoeffDomain()) // check if the product of the lead coeffs of the primitive factors equals the lead coeff of the old A
2752  {
2753  A= oldA;
2754  CFListIterator iter2= leadingCoeffs;
2755  for (CFListIterator iter= contents; iter.hasItem(); iter++, iter2++)
2756  iter2.getItem() /= iter.getItem();
2757  foundTrueMultiplier= true;
2758  }
2759 }
CFFListIterator iter
Definition: facAbsBiFact.cc:54
factory&#39;s main class
Definition: canonicalform.h:75
T & getItem() const
Definition: ftmpl_list.cc:431
bool fdivides(const CanonicalForm &f, const CanonicalForm &g)
bool fdivides ( const CanonicalForm & f, const CanonicalForm & g )
fq_nmod_poly_t prod
Definition: facHensel.cc:95
CanonicalForm LC(const CanonicalForm &f)

§ lcmContent()

CanonicalForm lcmContent ( const CanonicalForm A,
CFList contentAi 
)

compute the LCM of the contents of A wrt to each variable occuring in A.

Returns
lcmContent returns the LCM of the contents of A wrt to each variable occuring in A.
Parameters
[in]Aa compressed multivariate poly
[in,out]contentAian empty list, returns a list of the contents of A wrt to each variable occuring in A starting from A.mvar().

Definition at line 954 of file facFqFactorize.cc.

955 {
956  int i= A.level();
958  contentAi.append (content (buf, i));
959  buf /= contentAi.getLast();
960  contentAi.append (content (buf, i - 1));
961  CanonicalForm result= lcm (contentAi.getFirst(), contentAi.getLast());
962  for (i= i - 2; i > 0; i--)
963  {
964  contentAi.append (content (buf, i));
965  buf /= contentAi.getLast();
966  result= lcm (result, contentAi.getLast());
967  }
968  return result;
969 }
int lcm(unsigned long *l, unsigned long *a, unsigned long *b, unsigned long p, int dega, int degb)
Definition: minpoly.cc:711
factory&#39;s main class
Definition: canonicalform.h:75
CanonicalForm content(const CanonicalForm &)
CanonicalForm content ( const CanonicalForm & f )
Definition: cf_gcd.cc:180
T getFirst() const
Definition: ftmpl_list.cc:279
int status int void * buf
Definition: si_signals.h:59
#define A
Definition: sirandom.c:23
int i
Definition: cfEzgcd.cc:123
T getLast() const
Definition: ftmpl_list.cc:309
int level() const
level() returns the level of CO.
void append(const T &)
Definition: ftmpl_list.cc:256
return result
Definition: facAbsBiFact.cc:76

§ liftBoundAdaption()

int liftBoundAdaption ( const CanonicalForm F,
const CFList factors,
bool &  success,
const int  deg,
const CFList MOD,
const int  bound 
)

Lift bound adaption. Essentially an early factor detection but only the lift bound is adapted.

Returns
liftBoundAdaption returns an adapted lift bound.
See also
earlyFactorDetect(), earlyFactorDetection()
Parameters
[in]Fa poly
[in]factorslist of list of lifted factors that are monic wrt Variable (1)
[in,out]successindicates that no further lifting is necessary
[in]degstage of Hensel lifting
[in]MODa list of powers of Variables
[in]boundinitial lift bound

Definition at line 445 of file facFqFactorize.cc.

447 {
448  int adaptedLiftBound= 0;
449  CanonicalForm buf= F;
450  Variable y= F.mvar();
451  Variable x= Variable (1);
452  CanonicalForm LCBuf= LC (buf, x);
453  CanonicalForm g, quot;
454  CFList M= MOD;
455  M.append (power (y, deg));
456  int d= bound;
457  int e= 0;
458  int nBuf;
459  for (CFListIterator i= factors; i.hasItem(); i++)
460  {
461  g= mulMod (i.getItem(), LCBuf, M);
462  g /= myContent (g);
463  if (fdivides (g, buf, quot))
464  {
465  nBuf= degree (g, y) + degree (LC (g, 1), y);
466  d -= nBuf;
467  e= tmax (e, nBuf);
468  buf= quot;
469  LCBuf= LC (buf, x);
470  }
471  }
472  adaptedLiftBound= d;
473 
474  if (adaptedLiftBound < deg)
475  {
476  if (adaptedLiftBound < degree (F) + 1)
477  {
478  if (d == 1)
479  {
480  if (e + 1 > deg)
481  {
482  adaptedLiftBound= deg;
483  success= false;
484  }
485  else
486  {
487  success= true;
488  if (e + 1 < degree (F) + 1)
489  adaptedLiftBound= deg;
490  else
491  adaptedLiftBound= e + 1;
492  }
493  }
494  else
495  {
496  success= true;
497  adaptedLiftBound= deg;
498  }
499  }
500  else
501  {
502  success= true;
503  }
504  }
505  return adaptedLiftBound;
506 }
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
const CanonicalForm int const CFList const Variable & y
Definition: facAbsFact.cc:57
static CanonicalForm bound(const CFMatrix &M)
Definition: cf_linsys.cc:460
template CanonicalForm tmax(const CanonicalForm &, const CanonicalForm &)
factory&#39;s class for variables
Definition: factory.h:115
factory&#39;s main class
Definition: canonicalform.h:75
g
Definition: cfModGcd.cc:4031
#define M
Definition: sirandom.c:24
int status int void * buf
Definition: si_signals.h:59
static CanonicalForm myContent(const CanonicalForm &F)
int i
Definition: cfEzgcd.cc:123
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
bool fdivides(const CanonicalForm &f, const CanonicalForm &g)
bool fdivides ( const CanonicalForm & f, const CanonicalForm & g )
CanonicalForm mulMod(const CanonicalForm &A, const CanonicalForm &B, const CFList &MOD)
Karatsuba style modular multiplication for multivariate polynomials.
Definition: facMul.cc:2947
Variable x
Definition: cfModGcd.cc:4023
void append(const T &)
Definition: ftmpl_list.cc:256
int degree(const CanonicalForm &f)
CanonicalForm LC(const CanonicalForm &f)

§ listGCD()

static CanonicalForm listGCD ( const CFList L)
inlinestatic

Definition at line 77 of file facFqFactorize.cc.

78 {
79  if (L.length() == 0)
80  return 0;
81  if (L.length() == 1)
82  return L.getFirst();
83  if (L.length() == 2)
84  return gcd (L.getFirst(), L.getLast());
85  else
86  {
87  CFList lHi, lLo;
88  CanonicalForm resultHi, resultLo;
89  int length= L.length()/2;
90  int j= 0;
91  for (CFListIterator i= L; j < length; i++, j++)
92  lHi.append (i.getItem());
93  lLo= Difference (L, lHi);
94  resultHi= listGCD (lHi);
95  resultLo= listGCD (lLo);
96  if (resultHi.isOne() || resultLo.isOne())
97  return 1;
98  return gcd (resultHi, resultLo);
99  }
100 }
CF_NO_INLINE bool isOne() const
CF_INLINE bool CanonicalForm::isOne, isZero () const.
Definition: cf_inline.cc:354
factory&#39;s main class
Definition: canonicalform.h:75
T getFirst() const
Definition: ftmpl_list.cc:279
int j
Definition: myNF.cc:70
int i
Definition: cfEzgcd.cc:123
T getLast() const
Definition: ftmpl_list.cc:309
static CanonicalForm listGCD(const CFList &L)
int length() const
Definition: ftmpl_list.cc:273
int gcd(int a, int b)
Definition: walkSupport.cc:839
void append(const T &)
Definition: ftmpl_list.cc:256
template List< Variable > Difference(const List< Variable > &, const List< Variable > &)

§ multiFactorize()

CFList multiFactorize ( const CanonicalForm F,
const ExtensionInfo info 
)

Definition at line 2910 of file facFqFactorize.cc.

2911 {
2912  if (F.inCoeffDomain())
2913  return CFList (F);
2914 
2915  TIMING_START (fac_fq_preprocess_and_content);
2916  // compress and find main Variable
2917  CFMap N;
2918  TIMING_START (fac_fq_compress)
2919  CanonicalForm A= myCompress (F, N);
2920  TIMING_END_AND_PRINT (fac_fq_compress, "time to compress poly over Fq: ")
2921 
2922  A /= Lc (A); // make monic
2923 
2924  Variable alpha= info.getAlpha();
2925  Variable beta= info.getBeta();
2926  CanonicalForm gamma= info.getGamma();
2927  CanonicalForm delta= info.getDelta();
2928  bool extension= info.isInExtension();
2929  bool GF= (CFFactory::gettype() == GaloisFieldDomain);
2930  //univariate case
2931  if (F.isUnivariate())
2932  {
2933  if (extension == false)
2934  return uniFactorizer (F, alpha, GF);
2935  else
2936  {
2937  CFList source, dest;
2938  A= mapDown (F, info, source, dest);
2939  return uniFactorizer (A, beta, GF);
2940  }
2941  }
2942 
2943  //bivariate case
2944  if (A.level() == 2)
2945  {
2946  CFList buf= biSqrfFactorizeHelper (F, info);
2947  if (buf.getFirst().inCoeffDomain())
2948  buf.removeFirst();
2949  return buf;
2950  }
2951 
2952  Variable x= Variable (1);
2953  Variable y= Variable (2);
2954 
2955  // remove content
2956  TIMING_START (fac_fq_content);
2957  CFList contentAi;
2958  CanonicalForm lcmCont= lcmContent (A, contentAi);
2959  A /= lcmCont;
2960  TIMING_END_AND_PRINT (fac_fq_content, "time to extract content over Fq: ");
2961 
2962  // trivial after content removal
2963  CFList contentAFactors;
2964  if (A.inCoeffDomain())
2965  {
2966  for (CFListIterator i= contentAi; i.hasItem(); i++)
2967  {
2968  if (i.getItem().inCoeffDomain())
2969  continue;
2970  else
2971  {
2972  lcmCont /= i.getItem();
2973  contentAFactors=
2974  Union (multiFactorize (lcmCont, info),
2975  multiFactorize (i.getItem(), info));
2976  break;
2977  }
2978  }
2979  decompress (contentAFactors, N);
2980  if (!extension)
2981  normalize (contentAFactors);
2982  return contentAFactors;
2983  }
2984 
2985  // factorize content
2986  TIMING_START (fac_fq_content);
2987  contentAFactors= multiFactorize (lcmCont, info);
2988  TIMING_END_AND_PRINT (fac_fq_content, "time to factor content over Fq: ");
2989 
2990  // univariate after content removal
2991  CFList factors;
2992  if (A.isUnivariate ())
2993  {
2994  factors= uniFactorizer (A, alpha, GF);
2995  append (factors, contentAFactors);
2996  decompress (factors, N);
2997  return factors;
2998  }
2999 
3000  // check main variable
3001  TIMING_START (fac_fq_check_mainvar);
3002  int swapLevel= 0;
3003  CanonicalForm derivZ;
3004  CanonicalForm gcdDerivZ;
3005  CanonicalForm bufA= A;
3006  Variable z;
3007  for (int i= 1; i <= A.level(); i++)
3008  {
3009  z= Variable (i);
3010  derivZ= deriv (bufA, z);
3011  if (derivZ.isZero())
3012  {
3013  if (i == 1)
3014  swapLevel= 1;
3015  else
3016  continue;
3017  }
3018  else
3019  {
3020  gcdDerivZ= gcd (bufA, derivZ);
3021  if (degree (gcdDerivZ) > 0 && !derivZ.isZero())
3022  {
3023  CanonicalForm g= bufA/gcdDerivZ;
3024  CFList factorsG=
3025  Union (multiFactorize (g, info),
3026  multiFactorize (gcdDerivZ, info));
3027  appendSwapDecompress (factorsG, contentAFactors, N, swapLevel, x);
3028  if (!extension)
3029  normalize (factorsG);
3030  return factorsG;
3031  }
3032  else
3033  {
3034  if (swapLevel == 1)
3035  {
3036  swapLevel= i;
3037  bufA= swapvar (A, x, z);
3038  }
3039  A= bufA;
3040  break;
3041  }
3042  }
3043  }
3044  TIMING_END_AND_PRINT (fac_fq_check_mainvar,
3045  "time to check main var over Fq: ");
3046  TIMING_END_AND_PRINT (fac_fq_preprocess_and_content,
3047  "time to preprocess poly and extract content over Fq: ");
3048 
3049  CFList Aeval, list, evaluation, bufEvaluation, bufAeval;
3050  bool fail= false;
3051  int swapLevel2= 0;
3052  //int level;
3053  int factorNums= 3;
3054  CFList biFactors, bufBiFactors;
3055  CanonicalForm evalPoly;
3056  int lift, bufLift, lengthAeval2= A.level()-2;
3057  double logarithm= (double) ilog2 (totaldegree (A));
3058  logarithm /= log2exp;
3059  logarithm= ceil (logarithm);
3060  if (factorNums < (int) logarithm)
3061  factorNums= (int) logarithm;
3062  CFList* bufAeval2= new CFList [lengthAeval2];
3063  CFList* Aeval2= new CFList [lengthAeval2];
3064  int counter;
3065  int differentSecondVar= 0;
3066  // several bivariate factorizations
3067  TIMING_START (fac_fq_bifactor_total);
3068  for (int i= 0; i < factorNums; i++)
3069  {
3070  counter= 0;
3071  bufA= A;
3072  bufAeval= CFList();
3073  TIMING_START (fac_fq_evaluation);
3074  bufEvaluation= evalPoints (bufA, bufAeval, alpha, list, GF, fail);
3075  TIMING_END_AND_PRINT (fac_fq_evaluation,
3076  "time to find evaluation point over Fq: ");
3077  evalPoly= 0;
3078 
3079  if (fail && (i == 0))
3080  {
3081  /*if (!swapLevel) //uncomment to reenable search for new main variable
3082  level= 2;
3083  else
3084  level= swapLevel + 1;*/
3085 
3086  //CanonicalForm g;
3087  //swapLevel2= newMainVariableSearch (A, Aeval, evaluation, alpha, level, g);
3088 
3089  /*if (!swapLevel2) // need to pass to an extension
3090  {*/
3091  factors= extFactorize (A, info);
3092  appendSwapDecompress (factors, contentAFactors, N, swapLevel, x);
3093  normalize (factors);
3094  delete [] bufAeval2;
3095  delete [] Aeval2;
3096  return factors;
3097  /*}
3098  else
3099  {
3100  if (swapLevel2 == -1)
3101  {
3102  CFList factorsG=
3103  Union (multiFactorize (g, info),
3104  multiFactorize (A/g, info));
3105  appendSwapDecompress (factorsG, contentAFactors, N, swapLevel, x);
3106  if (!extension)
3107  normalize (factorsG);
3108  delete [] bufAeval2;
3109  delete [] Aeval2;
3110  return factorsG;
3111  }
3112  fail= false;
3113  bufAeval= Aeval;
3114  bufA= A;
3115  bufEvaluation= evaluation;
3116  }*/ //end uncomment
3117  }
3118  else if (fail && (i > 0))
3119  break;
3120 
3121  TIMING_START (fac_fq_evaluation);
3122  evaluationWRTDifferentSecondVars (bufAeval2, bufEvaluation, A);
3123  TIMING_END_AND_PRINT (fac_fq_evaluation,
3124  "time for evaluation wrt diff second vars over Fq: ");
3125 
3126  for (int j= 0; j < lengthAeval2; j++)
3127  {
3128  if (!bufAeval2[j].isEmpty())
3129  counter++;
3130  }
3131 
3132  bufLift= degree (A, y) + 1 + degree (LC(A, x), y);
3133 
3134  TIMING_START (fac_fq_bi_factorizer);
3135  if (!GF && alpha.level() == 1)
3136  bufBiFactors= FpBiSqrfFactorize (bufAeval.getFirst());
3137  else if (GF)
3138  bufBiFactors= GFBiSqrfFactorize (bufAeval.getFirst());
3139  else
3140  bufBiFactors= FqBiSqrfFactorize (bufAeval.getFirst(), alpha);
3141  TIMING_END_AND_PRINT (fac_fq_bi_factorizer,
3142  "time for bivariate factorization: ");
3143  bufBiFactors.removeFirst();
3144 
3145  if (bufBiFactors.length() == 1)
3146  {
3147  if (extension)
3148  {
3149  CFList source, dest;
3150  A= mapDown (A, info, source, dest);
3151  }
3152  factors.append (A);
3153  appendSwapDecompress (factors, contentAFactors, N, swapLevel,
3154  swapLevel2, x);
3155  if (!extension)
3156  normalize (factors);
3157  delete [] bufAeval2;
3158  delete [] Aeval2;
3159  return factors;
3160  }
3161 
3162  if (i == 0)
3163  {
3164  Aeval= bufAeval;
3165  evaluation= bufEvaluation;
3166  biFactors= bufBiFactors;
3167  lift= bufLift;
3168  for (int j= 0; j < lengthAeval2; j++)
3169  Aeval2 [j]= bufAeval2 [j];
3170  differentSecondVar= counter;
3171  }
3172  else
3173  {
3174  if (bufBiFactors.length() < biFactors.length() ||
3175  ((bufLift < lift) && (bufBiFactors.length() == biFactors.length())) ||
3176  counter > differentSecondVar)
3177  {
3178  Aeval= bufAeval;
3179  evaluation= bufEvaluation;
3180  biFactors= bufBiFactors;
3181  lift= bufLift;
3182  for (int j= 0; j < lengthAeval2; j++)
3183  Aeval2 [j]= bufAeval2 [j];
3184  differentSecondVar= counter;
3185  }
3186  }
3187  int k= 0;
3188  for (CFListIterator j= bufEvaluation; j.hasItem(); j++, k++)
3189  evalPoly += j.getItem()*power (x, k);
3190  list.append (evalPoly);
3191  }
3192 
3193  delete [] bufAeval2;
3194 
3195  sortList (biFactors, x);
3196 
3197  int minFactorsLength;
3198  bool irred= false;
3199  TIMING_START (fac_fq_bi_factorizer);
3200  factorizationWRTDifferentSecondVars (A, Aeval2, info, minFactorsLength,irred);
3201  TIMING_END_AND_PRINT (fac_fq_bi_factorizer,
3202  "time for bivariate factorization wrt diff second vars over Fq: ");
3203 
3204  TIMING_END_AND_PRINT (fac_fq_bifactor_total,
3205  "total time for eval and bivar factors over Fq: ");
3206  if (irred)
3207  {
3208  if (extension)
3209  {
3210  CFList source, dest;
3211  A= mapDown (A, info, source, dest);
3212  }
3213  factors.append (A);
3214  appendSwapDecompress (factors, contentAFactors, N, swapLevel,
3215  swapLevel2, x);
3216  if (!extension)
3217  normalize (factors);
3218  delete [] Aeval2;
3219  return factors;
3220  }
3221 
3222  if (minFactorsLength == 0)
3223  minFactorsLength= biFactors.length();
3224  else if (biFactors.length() > minFactorsLength)
3225  refineBiFactors (A, biFactors, Aeval2, evaluation, minFactorsLength);
3226  minFactorsLength= tmin (minFactorsLength, biFactors.length());
3227 
3228  CFList uniFactors= buildUniFactors (biFactors, evaluation.getLast(), y);
3229 
3230  sortByUniFactors (Aeval2, lengthAeval2, uniFactors, biFactors, evaluation);
3231 
3232  minFactorsLength= tmin (minFactorsLength, biFactors.length());
3233 
3234  if (minFactorsLength == 1)
3235  {
3236  if (extension)
3237  {
3238  CFList source, dest;
3239  A= mapDown (A, info, source, dest);
3240  }
3241  factors.append (A);
3242  appendSwapDecompress (factors, contentAFactors, N, swapLevel,
3243  swapLevel2, x);
3244  if (!extension)
3245  normalize (factors);
3246  delete [] Aeval2;
3247  return factors;
3248  }
3249 
3250  if (differentSecondVar == lengthAeval2)
3251  {
3252  bool zeroOccured= false;
3253  for (CFListIterator iter= evaluation; iter.hasItem(); iter++)
3254  {
3255  if (iter.getItem().isZero())
3256  {
3257  zeroOccured= true;
3258  break;
3259  }
3260  }
3261  if (!zeroOccured)
3262  {
3263  factors= sparseHeuristic (A, biFactors, Aeval2, evaluation,
3264  minFactorsLength);
3265  if (factors.length() == biFactors.length())
3266  {
3267  if (extension)
3268  factors= extNonMonicFactorRecombination (factors, A, info);
3269 
3270  appendSwapDecompress (factors, contentAFactors, N, swapLevel,
3271  swapLevel2, x);
3272  if (!extension)
3273  normalize (factors);
3274  delete [] Aeval2;
3275  return factors;
3276  }
3277  else
3278  factors= CFList();
3279  //TODO case where factors.length() > 0
3280  }
3281  }
3282 
3283  CFList * oldAeval= new CFList [lengthAeval2]; //TODO use bufAeval2 for this
3284  for (int i= 0; i < lengthAeval2; i++)
3285  oldAeval[i]= Aeval2[i];
3286 
3287  getLeadingCoeffs (A, Aeval2);
3288 
3289  CFList biFactorsLCs;
3290  for (CFListIterator i= biFactors; i.hasItem(); i++)
3291  biFactorsLCs.append (LC (i.getItem(), 1));
3292 
3293  Variable v;
3294  TIMING_START (fac_fq_precompute_leadcoeff);
3295  CFList leadingCoeffs= precomputeLeadingCoeff (LC (A, 1), biFactorsLCs, alpha,
3296  evaluation, Aeval2, lengthAeval2, v);
3297 
3298  if (v.level() != 1)
3299  changeSecondVariable (A, biFactors, evaluation, oldAeval, lengthAeval2,
3300  uniFactors, v);
3301 
3302  CanonicalForm oldA= A;
3303  CFList oldBiFactors= biFactors;
3304 
3305  CanonicalForm LCmultiplier= leadingCoeffs.getFirst();
3306  bool LCmultiplierIsConst= LCmultiplier.inCoeffDomain();
3307  leadingCoeffs.removeFirst();
3308 
3309  if (!LCmultiplierIsConst)
3310  distributeLCmultiplier (A, leadingCoeffs, biFactors, evaluation, LCmultiplier);
3311 
3312  //prepare leading coefficients
3313  CFList* leadingCoeffs2= new CFList [lengthAeval2];
3314  prepareLeadingCoeffs (leadingCoeffs2, A, Aeval, A.level(), leadingCoeffs,
3315  biFactors, evaluation);
3316 
3318  CFList bufLeadingCoeffs2= leadingCoeffs2[lengthAeval2-1];
3319  bufBiFactors= biFactors;
3320  bufA= A;
3321  CanonicalForm testVars, bufLCmultiplier= LCmultiplier;
3322  if (!LCmultiplierIsConst)
3323  {
3324  testVars= Variable (2);
3325  for (int i= 0; i < lengthAeval2; i++)
3326  {
3327  if (!oldAeval[i].isEmpty())
3328  testVars *= oldAeval[i].getFirst().mvar();
3329  }
3330  }
3331  TIMING_END_AND_PRINT(fac_fq_precompute_leadcoeff,
3332  "time to precompute LC over Fq: ");
3333 
3334  TIMING_START (fac_fq_luckswang);
3335  CFList bufFactors= CFList();
3336  bool LCheuristic= false;
3337  if (LucksWangSparseHeuristic (A, biFactors, 2, leadingCoeffs2[lengthAeval2-1],
3338  factors))
3339  {
3340  int check= biFactors.length();
3341  int * index= new int [factors.length()];
3342  CFList oldFactors= factors;
3343  factors= recoverFactors (A, factors, index);
3344 
3345  if (check == factors.length())
3346  {
3347  if (extension)
3348  factors= extNonMonicFactorRecombination (factors, bufA, info);
3349 
3350  if (v.level() != 1)
3351  {
3352  for (iter= factors; iter.hasItem(); iter++)
3353  iter.getItem()= swapvar (iter.getItem(), v, y);
3354  }
3355 
3356  appendSwapDecompress (factors, contentAFactors, N, swapLevel,
3357  swapLevel2, x);
3358  if (!extension)
3359  normalize (factors);
3360  delete [] index;
3361  delete [] Aeval2;
3362  TIMING_END_AND_PRINT (fac_fq_luckswang,
3363  "time for successful LucksWang over Fq: ");
3364  return factors;
3365  }
3366  else if (factors.length() > 0)
3367  {
3368  int oneCount= 0;
3369  CFList l;
3370  for (int i= 0; i < check; i++)
3371  {
3372  if (index[i] == 1)
3373  {
3374  iter=biFactors;
3375  for (int j=1; j <= i-oneCount; j++)
3376  iter++;
3377  iter.remove (1);
3378  for (int j= 0; j < lengthAeval2; j++)
3379  {
3380  l= leadingCoeffs2[j];
3381  iter= l;
3382  for (int k=1; k <= i-oneCount; k++)
3383  iter++;
3384  iter.remove (1);
3385  leadingCoeffs2[j]=l;
3386  }
3387  oneCount++;
3388  }
3389  }
3390  bufFactors= factors;
3391  factors= CFList();
3392  }
3393  else if (!LCmultiplierIsConst && factors.length() == 0)
3394  {
3395  LCheuristic= true;
3396  factors= oldFactors;
3397  CFList contents, LCs;
3398  bool foundTrueMultiplier= false;
3399  LCHeuristic2 (LCmultiplier, factors, leadingCoeffs2[lengthAeval2-1],
3400  contents, LCs, foundTrueMultiplier);
3401  if (foundTrueMultiplier)
3402  {
3403  A= oldA;
3404  leadingCoeffs= leadingCoeffs2[lengthAeval2-1];
3405  for (int i= lengthAeval2-1; i > -1; i--)
3406  leadingCoeffs2[i]= CFList();
3407  prepareLeadingCoeffs (leadingCoeffs2, A, Aeval, A.level(),
3408  leadingCoeffs, biFactors, evaluation);
3409  }
3410  else
3411  {
3412  bool foundMultiplier= false;
3413  LCHeuristic3 (LCmultiplier, factors, oldBiFactors, contents, oldAeval,
3414  A, leadingCoeffs2, lengthAeval2, foundMultiplier);
3415 
3416  // coming from above: divide out more LCmultiplier if possible
3417  if (foundMultiplier)
3418  {
3419  foundMultiplier= false;
3420  LCHeuristic4 (oldBiFactors, oldAeval, contents, factors, testVars,
3421  lengthAeval2, leadingCoeffs2, A, LCmultiplier,
3422  foundMultiplier);
3423  }
3424  else
3425  {
3426  LCHeuristicCheck (LCs, contents, A, oldA,
3427  leadingCoeffs2[lengthAeval2-1], foundMultiplier);
3428  if (!foundMultiplier && fdivides (getVars (LCmultiplier), testVars))
3429  {
3430  LCHeuristic (A, LCmultiplier, biFactors, leadingCoeffs2, oldAeval,
3431  lengthAeval2, evaluation, oldBiFactors);
3432  }
3433  }
3434 
3435  // patch everything together again
3436  leadingCoeffs= leadingCoeffs2[lengthAeval2-1];
3437  for (int i= lengthAeval2-1; i > -1; i--)
3438  leadingCoeffs2[i]= CFList();
3439  prepareLeadingCoeffs (leadingCoeffs2, A, Aeval, A.level(),leadingCoeffs,
3440  biFactors, evaluation);
3441  }
3442  factors= CFList();
3443  if (!fdivides (LC (oldA,1),prod (leadingCoeffs2[lengthAeval2-1])))
3444  {
3445  LCheuristic= false;
3446  A= bufA;
3447  biFactors= bufBiFactors;
3448  leadingCoeffs2[lengthAeval2-1]= bufLeadingCoeffs2;
3449  LCmultiplier= bufLCmultiplier;
3450  }
3451  }
3452  else
3453  factors= CFList();
3454  delete [] index;
3455  }
3456  TIMING_END_AND_PRINT (fac_fq_luckswang, "time for LucksWang over Fq: ");
3457 
3458  TIMING_START (fac_fq_lcheuristic);
3459  if (!LCheuristic && !LCmultiplierIsConst && bufFactors.isEmpty()
3460  && fdivides (getVars (LCmultiplier), testVars))
3461  {
3462  LCheuristic= true;
3463  LCHeuristic (A, LCmultiplier, biFactors, leadingCoeffs2, oldAeval,
3464  lengthAeval2, evaluation, oldBiFactors);
3465 
3466  leadingCoeffs= leadingCoeffs2[lengthAeval2-1];
3467  for (int i= lengthAeval2-1; i > -1; i--)
3468  leadingCoeffs2[i]= CFList();
3469  prepareLeadingCoeffs (leadingCoeffs2, A, Aeval, A.level(),leadingCoeffs,
3470  biFactors, evaluation);
3471 
3472  if (!fdivides (LC (oldA,1),prod (leadingCoeffs2[lengthAeval2-1])))
3473  {
3474  LCheuristic= false;
3475  A= bufA;
3476  biFactors= bufBiFactors;
3477  leadingCoeffs2[lengthAeval2-1]= bufLeadingCoeffs2;
3478  LCmultiplier= bufLCmultiplier;
3479  }
3480  }
3481  TIMING_END_AND_PRINT (fac_fq_lcheuristic, "time for Lc heuristic over Fq: ");
3482 
3483 tryAgainWithoutHeu:
3484  TIMING_START (fac_fq_shift_to_zero);
3485  A= shift2Zero (A, Aeval, evaluation);
3486 
3487  for (iter= biFactors; iter.hasItem(); iter++)
3488  iter.getItem()= iter.getItem () (y + evaluation.getLast(), y);
3489 
3490  for (int i= 0; i < lengthAeval2-1; i++)
3491  leadingCoeffs2[i]= CFList();
3492  for (iter= leadingCoeffs2[lengthAeval2-1]; iter.hasItem(); iter++)
3493  {
3494  iter.getItem()= shift2Zero (iter.getItem(), list, evaluation);
3495  for (int i= A.level() - 4; i > -1; i--)
3496  {
3497  if (i + 1 == lengthAeval2-1)
3498  leadingCoeffs2[i].append (iter.getItem() (0, i + 4));
3499  else
3500  leadingCoeffs2[i].append (leadingCoeffs2[i+1].getLast() (0, i + 4));
3501  }
3502  }
3503  TIMING_END_AND_PRINT (fac_fq_shift_to_zero,
3504  "time to shift evaluation point to zero: ");
3505 
3506  CFArray Pi;
3507  CFList diophant;
3508  int* liftBounds= new int [A.level() - 1];
3509  int liftBoundsLength= A.level() - 1;
3510  for (int i= 0; i < liftBoundsLength; i++)
3511  liftBounds [i]= degree (A, i + 2) + 1;
3512 
3513  Aeval.removeFirst();
3514  bool noOneToOne= false;
3515  TIMING_START (fac_fq_hensel_lift);
3516  factors= nonMonicHenselLift (Aeval, biFactors, leadingCoeffs2, diophant,
3517  Pi, liftBounds, liftBoundsLength, noOneToOne);
3518  TIMING_END_AND_PRINT (fac_fq_hensel_lift,
3519  "time for non monic hensel lifting over Fq: ");
3520 
3521  if (!noOneToOne)
3522  {
3523  int check= factors.length();
3524  A= oldA;
3525  TIMING_START (fac_fq_recover_factors);
3526  factors= recoverFactors (A, factors, evaluation);
3527  TIMING_END_AND_PRINT (fac_fq_recover_factors,
3528  "time to recover factors over Fq: ");
3529  if (check != factors.length())
3530  noOneToOne= true;
3531  else
3532  factors= Union (factors, bufFactors);
3533 
3534  if (extension && !noOneToOne)
3535  factors= extNonMonicFactorRecombination (factors, A, info);
3536  }
3537  if (noOneToOne)
3538  {
3539  if (!LCmultiplierIsConst && LCheuristic)
3540  {
3541  A= bufA;
3542  biFactors= bufBiFactors;
3543  leadingCoeffs2[lengthAeval2-1]= bufLeadingCoeffs2;
3544  delete [] liftBounds;
3545  LCheuristic= false;
3546  goto tryAgainWithoutHeu;
3547  //something probably went wrong in the heuristic
3548  }
3549 
3550  A= shift2Zero (oldA, Aeval, evaluation);
3551  biFactors= oldBiFactors;
3552  for (iter= biFactors; iter.hasItem(); iter++)
3553  iter.getItem()= iter.getItem () (y + evaluation.getLast(), y);
3554  CanonicalForm LCA= LC (Aeval.getFirst(), 1);
3555  CanonicalForm yToLift= power (y, lift);
3556  CFListIterator i= biFactors;
3557  lift= degree (i.getItem(), 2) + degree (LC (i.getItem(), 1)) + 1;
3558  i++;
3559 
3560  for (; i.hasItem(); i++)
3561  lift= tmax (lift,
3562  degree (i.getItem(), 2) + degree (LC (i.getItem(), 1)) + 1);
3563 
3564  lift= tmax (degree (Aeval.getFirst() , 2) + 1, lift);
3565 
3566  i= biFactors;
3567  yToLift= power (y, lift);
3568  CanonicalForm dummy;
3569  for (; i.hasItem(); i++)
3570  {
3571  LCA= LC (i.getItem(), 1);
3572  extgcd (LCA, yToLift, LCA, dummy);
3573  i.getItem()= mod (i.getItem()*LCA, yToLift);
3574  }
3575 
3576  liftBoundsLength= F.level() - 1;
3577  liftBounds= liftingBounds (A, lift);
3578 
3579  CFList MOD;
3580  bool earlySuccess;
3581  CFList earlyFactors, liftedFactors;
3582  TIMING_START (fac_fq_hensel_lift);
3583  liftedFactors= henselLiftAndEarly
3584  (A, MOD, liftBounds, earlySuccess, earlyFactors,
3585  Aeval, biFactors, evaluation, info);
3586  TIMING_END_AND_PRINT (fac_fq_hensel_lift,
3587  "time for hensel lifting over Fq: ");
3588 
3589  if (!extension)
3590  {
3591  TIMING_START (fac_fq_factor_recombination);
3592  factors= factorRecombination (A, liftedFactors, MOD);
3593  TIMING_END_AND_PRINT (fac_fq_factor_recombination,
3594  "time for factor recombination: ");
3595  }
3596  else
3597  {
3598  TIMING_START (fac_fq_factor_recombination);
3599  factors= extFactorRecombination (liftedFactors, A, MOD, info, evaluation);
3600  TIMING_END_AND_PRINT (fac_fq_factor_recombination,
3601  "time for factor recombination: ");
3602  }
3603 
3604  if (earlySuccess)
3605  factors= Union (factors, earlyFactors);
3606  if (!extension)
3607  {
3608  for (CFListIterator i= factors; i.hasItem(); i++)
3609  {
3610  int kk= Aeval.getLast().level();
3611  for (CFListIterator j= evaluation; j.hasItem(); j++, kk--)
3612  {
3613  if (i.getItem().level() < kk)
3614  continue;
3615  i.getItem()= i.getItem() (Variable (kk) - j.getItem(), kk);
3616  }
3617  }
3618  }
3619  }
3620 
3621  if (v.level() != 1)
3622  {
3623  for (CFListIterator iter= factors; iter.hasItem(); iter++)
3624  iter.getItem()= swapvar (iter.getItem(), v, y);
3625  }
3626 
3627  swap (factors, swapLevel, swapLevel2, x);
3628  append (factors, contentAFactors);
3629  decompress (factors, N);
3630  if (!extension)
3631  normalize (factors);
3632 
3633  delete[] liftBounds;
3634 
3635  return factors;
3636 }
CanonicalForm shift2Zero(const CanonicalForm &F, CFList &Feval, const CFList &evaluation, int l)
shift evaluation point to zero
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
CFList extNonMonicFactorRecombination(const CFList &factors, const CanonicalForm &F, const ExtensionInfo &info)
CFFList append(const CFFList &Inputlist, const CFFactor &TheFactor)
List< CanonicalForm > CFList
static CanonicalForm mapDown(const CanonicalForm &F, const Variable &alpha, const CanonicalForm &G, CFList &source, CFList &dest)
the CanonicalForm G is the output of map_up, returns F considered as an element over ...
Definition: cf_map_ext.cc:90
const CanonicalForm int const CFList const Variable & y
Definition: facAbsFact.cc:57
CFList recoverFactors(const CanonicalForm &F, const CFList &factors)
divides factors by their content wrt. Variable(1) and checks if these polys divide F ...
static poly normalize(poly next_p, ideal add_generators, syStrategy syzstr, int *g_l, int *p_l, int crit_comp)
Definition: syz3.cc:1024
void changeSecondVariable(CanonicalForm &A, CFList &biFactors, CFList &evaluation, CFList *&oldAeval, int lengthAeval2, const CFList &uniFactors, const Variable &w)
changes the second variable to be w and updates all relevant data
CF_NO_INLINE CanonicalForm mod(const CanonicalForm &, const CanonicalForm &)
Definition: cf_inline.cc:564
int isEmpty() const
Definition: ftmpl_list.cc:267
CanonicalForm myCompress(const CanonicalForm &F, CFMap &N)
compress a polynomial s.t. and no gaps between the variables occur
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:173
int check
Definition: libparse.cc:1104
template CanonicalForm tmax(const CanonicalForm &, const CanonicalForm &)
if(0 > strat->sl)
Definition: myNF.cc:73
CanonicalForm deriv(const CanonicalForm &f, const Variable &x)
CFList evalPoints(const CanonicalForm &F, CFList &eval, const Variable &alpha, CFList &list, const bool &GF, bool &fail)
evaluation point search for multivariate factorization, looks for a (F.level() - 1)-tuple such that t...
#define TIMING_END_AND_PRINT(t, msg)
Definition: timing.h:89
void sortByUniFactors(CFList *&Aeval, int AevalLength, CFList &uniFactors, CFList &biFactors, const CFList &evaluation)
sort bivariate factors in Aeval such that their corresponding univariate factors coincide with uniFac...
factory&#39;s class for variables
Definition: factory.h:115
CF_NO_INLINE bool isZero() const
Definition: cf_inline.cc:372
CFList *& Aeval
<[in] poly
Definition: facFactorize.h:31
CFList multiFactorize(const CanonicalForm &F, const ExtensionInfo &info)
bool isInExtension(const CanonicalForm &F, const CanonicalForm &gamma, const int k, const CanonicalForm &delta, CFList &source, CFList &dest)
tests if F is not contained in a subfield defined by gamma (Fq case) or k (GF case) ...
CFList uniFactorizer(const CanonicalForm &A, const Variable &alpha, const bool &GF)
Univariate factorization of squarefree monic polys over finite fields via NTL. If the characteristic ...
Definition: facFqBivar.cc:156
CFFListIterator iter
Definition: facAbsBiFact.cc:54
void factorizationWRTDifferentSecondVars(const CanonicalForm &A, CFList *&Aeval, const ExtensionInfo &info, int &minFactorsLength, bool &irred)
CFList int & minFactorsLength
[in,out] minimal length of < bivariate factors
Definition: facFactorize.h:31
CFList GFBiSqrfFactorize(const CanonicalForm &G)
factorize a squarefree bivariate polynomial over GF
Definition: facFqBivar.h:164
void LCHeuristic(CanonicalForm &A, const CanonicalForm &LCmultiplier, CFList &biFactors, CFList *&leadingCoeffs, const CFList *oldAeval, int lengthAeval, const CFList &evaluation, const CFList &oldBiFactors)
heuristic to distribute LCmultiplier onto factors based on the variables that occur in LCmultiplier a...
factory&#39;s main class
Definition: canonicalform.h:75
CFList extFactorRecombination(const CFList &factors, const CanonicalForm &F, const CFList &M, const ExtensionInfo &info, const CFList &evaluation)
Naive factor recombination for multivariate factorization over an extension of the initial field...
void LCHeuristic4(const CFList &oldBiFactors, const CFList *oldAeval, const CFList &contents, const CFList &factors, const CanonicalForm &testVars, int lengthAeval, CFList *&leadingCoeffs, CanonicalForm &A, CanonicalForm &LCmultiplier, bool &foundMultiplier)
heuristic to remove factors of LCmultiplier from factors. More precisely checks if elements of conten...
g
Definition: cfModGcd.cc:4031
int k
Definition: cfEzgcd.cc:93
const CanonicalForm int const CFList & evaluation
Definition: facAbsFact.cc:55
void appendSwapDecompress(CFList &factors1, const CFList &factors2, const CFList &factors3, const bool swap1, const bool swap2, const CFMap &N)
first swap Variables in factors1 if necessary, then append factors2 and factors3 on factors1 and fina...
int LucksWangSparseHeuristic(const CanonicalForm &F, const CFList &factors, int level, const CFList &leadingCoeffs, CFList &result)
sparse heuristic lifting by Wang and Lucks
Variable alpha
Definition: facAbsBiFact.cc:52
CFList FqBiSqrfFactorize(const CanonicalForm &G, const Variable &alpha)
factorize a squarefree bivariate polynomial over .
Definition: facFqBivar.h:150
static const double log2exp
Definition: cfEzgcd.cc:40
CFList nonMonicHenselLift(const CFList &F, const CFList &factors, const CFList &LCs, CFList &diophant, CFArray &Pi, CFMatrix &M, int lOld, int &lNew, const CFList &MOD, bool &noOneToOne)
Definition: facHensel.cc:2709
CanonicalForm Lc(const CanonicalForm &f)
CanonicalForm compress(const CanonicalForm &f, CFMap &m)
CanonicalForm compress ( const CanonicalForm & f, CFMap & m )
Definition: cf_map.cc:210
bool delta(X x, Y y, D d)
Definition: TestSuite.h:160
void removeFirst()
Definition: ftmpl_list.cc:287
void sortList(CFList &list, const Variable &x)
sort a list of polynomials by their degree in x.
Definition: facHensel.cc:441
T getFirst() const
Definition: ftmpl_list.cc:279
template List< Variable > Union(const List< Variable > &, const List< Variable > &)
ideal lift(const ideal J, const ring r, const ideal inI, const ring s)
Definition: lift.cc:24
CanonicalForm swapvar(const CanonicalForm &, const Variable &, const Variable &)
swapvar() - swap variables x1 and x2 in f.
Definition: cf_ops.cc:168
clock_t to
Definition: walk.cc:99
void refineBiFactors(const CanonicalForm &A, CFList &biFactors, CFList *const &Aeval, const CFList &evaluation, int minFactorsLength)
refine a bivariate factorization of A with l factors to one with minFactorsLength if possible ...
const CanonicalForm CFMap CFMap & N
Definition: cfEzgcd.cc:49
CanonicalForm getVars(const CanonicalForm &f)
CanonicalForm getVars ( const CanonicalForm & f )
Definition: cf_ops.cc:350
int j
Definition: myNF.cc:70
CanonicalForm decompress(const CanonicalForm &F, const mpz_t *inverseM, const mpz_t *A)
decompress a bivariate poly
int status int void * buf
Definition: si_signals.h:59
int level() const
Definition: factory.h:132
T & getItem() const
Definition: ftmpl_list.cc:431
const ExtensionInfo & info
< [in] sqrfree poly
#define A
Definition: sirandom.c:23
else L getLast()(0
void distributeLCmultiplier(CanonicalForm &A, CFList &leadingCoeffs, CFList &biFactors, const CFList &evaluation, const CanonicalForm &LCmultipler)
distributes a divisor LCmultiplier of LC(A,1) on the bivariate factors and the precomputed leading co...
CFList precomputeLeadingCoeff(const CanonicalForm &LCF, const CFList &LCFFactors, const Variable &alpha, const CFList &evaluation, CFList *&differentSecondVarLCs, int lSecondVarLCs, Variable &y)
computes a list l of length length(LCFFactors)+1 of polynomials such that prod (l)=LCF, note that the first entry of l may be non constant. Intended to be used to precompute coefficients of a polynomial f from its bivariate factorizations.
CFList FpBiSqrfFactorize(const CanonicalForm &G)
factorize a squarefree bivariate polynomial over .
Definition: facFqBivar.h:137
CFList biSqrfFactorizeHelper(const CanonicalForm &G, const ExtensionInfo &info)
Definition: facFqBivar.h:53
int i
Definition: cfEzgcd.cc:123
T getLast() const
Definition: ftmpl_list.cc:309
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
int ilog2(const CanonicalForm &a)
static int index(p_Length length, p_Ord ord)
Definition: p_Procs_Impl.h:592
Variable beta
Definition: facAbsFact.cc:99
class CFMap
Definition: cf_map.h:84
bool fdivides(const CanonicalForm &f, const CanonicalForm &g)
bool fdivides ( const CanonicalForm & f, const CanonicalForm & g )
void evaluationWRTDifferentSecondVars(CFList *&Aeval, const CFList &evaluation, const CanonicalForm &A)
evaluate a poly A with main variable at level 1 at an evaluation point in K^(n-1) wrt different secon...
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:37
CFList buildUniFactors(const CFList &biFactors, const CanonicalForm &evalPoint, const Variable &y)
plug in evalPoint for y in a list of polys
CFList sparseHeuristic(const CanonicalForm &A, const CFList &biFactors, CFList *&moreBiFactors, const CFList &evaluation, int minFactorsLength)
sparse heuristic which patches together bivariate factors of A wrt. different second variables by the...
void LCHeuristic3(const CanonicalForm &LCmultiplier, const CFList &factors, const CFList &oldBiFactors, const CFList &contents, const CFList *oldAeval, CanonicalForm &A, CFList *&leadingCoeffs, int lengthAeval, bool &foundMultiplier)
heuristic to remove LCmultiplier from a factor based on the contents of factors. factors are assumed ...
int length() const
Definition: ftmpl_list.cc:273
#define swap(_i, _j)
CFList extFactorize(const CanonicalForm &F, const ExtensionInfo &info)
multivariate factorization over an extension of the initial field
int gcd(int a, int b)
Definition: walkSupport.cc:839
fq_nmod_poly_t prod
Definition: facHensel.cc:95
#define TIMING_START(t)
Definition: timing.h:87
Variable x
Definition: cfModGcd.cc:4023
#define GaloisFieldDomain
Definition: cf_defs.h:22
CFList henselLiftAndEarly(CanonicalForm &A, CFList &MOD, int *&liftBounds, bool &earlySuccess, CFList &earlyFactors, const CFList &Aeval, const CFList &biFactors, const CFList &evaluation, const ExtensionInfo &info)
hensel Lifting and early factor detection
CanonicalForm lcmContent(const CanonicalForm &A, CFList &contentAi)
compute the LCM of the contents of A wrt to each variable occuring in A.
int totaldegree(const CanonicalForm &f)
int totaldegree ( const CanonicalForm & f )
Definition: cf_ops.cc:523
CFList int bool & irred
[in,out] Is A irreducible?
Definition: facFactorize.h:31
void LCHeuristicCheck(const CFList &LCs, const CFList &contents, CanonicalForm &A, const CanonicalForm &oldA, CFList &leadingCoeffs, bool &foundTrueMultiplier)
checks if prod(LCs)==LC (oldA,1) and if so divides elements of leadingCoeffs by elements in contents...
int level() const
level() returns the level of CO.
void append(const T &)
Definition: ftmpl_list.cc:256
int degree(const CanonicalForm &f)
void prepareLeadingCoeffs(CFList *&LCs, CanonicalForm &A, CFList &Aeval, int n, const CFList &leadingCoeffs, const CFList &biFactors, const CFList &evaluation)
normalize precomputed leading coefficients such that leading coefficients evaluated at evaluation in ...
polyrec * poly
Definition: hilb.h:10
CanonicalForm LC(const CanonicalForm &f)
CFList factorRecombination(const CanonicalForm &F, const CFList &factors, const CFList &M)
Naive factor recombination for multivariate factorization. No precomputed is used to exclude combinat...
void LCHeuristic2(const CanonicalForm &LCmultiplier, const CFList &factors, CFList &leadingCoeffs, CFList &contents, CFList &LCs, bool &foundTrueMultiplier)
heuristic to distribute LCmultiplier onto factors based on the contents of factors. factors are assumed to come from LucksWangSparseHeuristic. If not successful contents will contain the content of each element of factors and LCs will contain the LC of each element of factors divided by its content
unsigned long over(const unsigned long n, const unsigned long d)
Definition: mpr_base.cc:2658
void getLeadingCoeffs(const CanonicalForm &A, CFList *&Aeval)
extract leading coefficients wrt Variable(1) from bivariate factors obtained from factorizations of A...
int * liftingBounds(const CanonicalForm &A, const int &bivarLiftBound)
compute lifting bounds
int l
Definition: cfEzgcd.cc:94
template CanonicalForm tmin(const CanonicalForm &, const CanonicalForm &)
bool inCoeffDomain() const

§ myCompress()

CanonicalForm myCompress ( const CanonicalForm F,
CFMap N 
)

compress a polynomial s.t. $ deg_{x_{i}} (F) >= deg_{x_{i+1}} (F) $ and no gaps between the variables occur

Returns
a compressed poly with the above properties
Parameters
[in]Fa poly
[in,out]Na map to decompress

Definition at line 136 of file facFqFactorize.cc.

137 {
138  int n= F.level();
139  int * degsf= new int [n + 1];
140  int ** swap= new int* [n + 1];
141  for (int i= 0; i <= n; i++)
142  {
143  degsf[i]= 0;
144  swap [i]= new int [3];
145  swap [i] [0]= 0;
146  swap [i] [1]= 0;
147  swap [i] [2]= 0;
148  }
149  int i= 1;
150  n= 1;
151  degsf= degrees (F, degsf);
152 
154  while ( i <= F.level() )
155  {
156  while( degsf[i] == 0 ) i++;
157  swap[n][0]= i;
158  swap[n][1]= size (LC (F,i));
159  swap[n][2]= degsf [i];
160  if (i != n)
161  result= swapvar (result, Variable (n), Variable(i));
162  n++; i++;
163  }
164 
165  int buf1, buf2, buf3;
166  n--;
167 
168  for (i= 1; i < n; i++)
169  {
170  for (int j= 1; j < n - i + 1; j++)
171  {
172  if (swap[j][1] > swap[j + 1][1])
173  {
174  buf1= swap [j + 1] [0];
175  buf2= swap [j + 1] [1];
176  buf3= swap [j + 1] [2];
177  swap[j + 1] [0]= swap[j] [0];
178  swap[j + 1] [1]= swap[j] [1];
179  swap[j + 1] [2]= swap[j] [2];
180  swap[j][0]= buf1;
181  swap[j][1]= buf2;
182  swap[j][2]= buf3;
183  result= swapvar (result, Variable (j + 1), Variable (j));
184  }
185  else if (swap[j][1] == swap[j + 1][1] && swap[j][2] < swap[j + 1][2])
186  {
187  buf1= swap [j + 1] [0];
188  buf2= swap [j + 1] [1];
189  buf3= swap [j + 1] [2];
190  swap[j + 1] [0]= swap[j] [0];
191  swap[j + 1] [1]= swap[j] [1];
192  swap[j + 1] [2]= swap[j] [2];
193  swap[j][0]= buf1;
194  swap[j][1]= buf2;
195  swap[j][2]= buf3;
196  result= swapvar (result, Variable (j + 1), Variable (j));
197  }
198  }
199  }
200 
201  for (i= n; i > 0; i--)
202  {
203  if (i != swap[i] [0])
204  N.newpair (Variable (i), Variable (swap[i] [0]));
205  }
206 
207  for (i= 0; i <= F.level(); i++)
208  delete [] swap[i];
209  delete [] swap;
210 
211  delete [] degsf;
212 
213  return result;
214 }
CanonicalForm buf1
Definition: facFqBivar.cc:71
factory&#39;s class for variables
Definition: factory.h:115
int * degrees(const CanonicalForm &f, int *degs=0)
int * degrees ( const CanonicalForm & f, int * degs )
Definition: cf_ops.cc:493
factory&#39;s main class
Definition: canonicalform.h:75
CanonicalForm swapvar(const CanonicalForm &, const Variable &, const Variable &)
swapvar() - swap variables x1 and x2 in f.
Definition: cf_ops.cc:168
int j
Definition: myNF.cc:70
int i
Definition: cfEzgcd.cc:123
int size(const CanonicalForm &f, const Variable &v)
int size ( const CanonicalForm & f, const Variable & v )
Definition: cf_ops.cc:600
CanonicalForm buf2
Definition: facFqBivar.cc:71
void newpair(const Variable &v, const CanonicalForm &s)
void CFMap::newpair ( const Variable & v, const CanonicalForm & s )
Definition: cf_map.cc:120
#define swap(_i, _j)
int level() const
level() returns the level of CO.
int * degsf
Definition: cfEzgcd.cc:53
CanonicalForm LC(const CanonicalForm &f)
return result
Definition: facAbsBiFact.cc:76

§ myContent() [1/2]

static CanonicalForm myContent ( const CanonicalForm F)
inlinestatic

Definition at line 61 of file facFqFactorize.cc.

62 {
63  Variable x= Variable (1);
64  CanonicalForm G= swapvar (F, F.mvar(), x);
65  CFList L;
66  for (CFIterator i= G; i.hasTerms(); i++)
67  L.append (i.coeff());
68  if (L.length() == 2)
69  return swapvar (gcd (L.getFirst(), L.getLast()), F.mvar(), x);
70  if (L.length() == 1)
71  return LC (F, x);
72  return swapvar (listGCD (L), F.mvar(), x);
73 }
factory&#39;s class for variables
Definition: factory.h:115
factory&#39;s main class
Definition: canonicalform.h:75
static TreeM * G
Definition: janet.cc:38
CanonicalForm swapvar(const CanonicalForm &, const Variable &, const Variable &)
swapvar() - swap variables x1 and x2 in f.
Definition: cf_ops.cc:168
int i
Definition: cfEzgcd.cc:123
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
class to iterate through CanonicalForm&#39;s
Definition: cf_iter.h:44
static CanonicalForm listGCD(const CFList &L)
int gcd(int a, int b)
Definition: walkSupport.cc:839
Variable x
Definition: cfModGcd.cc:4023
void append(const T &)
Definition: ftmpl_list.cc:256
CanonicalForm LC(const CanonicalForm &f)

§ myContent() [2/2]

static CanonicalForm myContent ( const CanonicalForm F,
const Variable x 
)
inlinestatic

Definition at line 104 of file facFqFactorize.cc.

105 {
106  if (degree (F, x) <= 0)
107  return 1;
108  CanonicalForm G= F;
109  bool swap= false;
110  if (x != F.mvar())
111  {
112  swap= true;
113  G= swapvar (F, x, F.mvar());
114  }
115  CFList L;
116  Variable alpha;
117  for (CFIterator i= G; i.hasTerms(); i++)
118  L.append (i.coeff());
119  if (L.length() == 2)
120  {
121  if (swap)
122  return swapvar (gcd (L.getFirst(), L.getLast()), F.mvar(), x);
123  else
124  return gcd (L.getFirst(), L.getLast());
125  }
126  if (L.length() == 1)
127  {
128  return LC (F, x);
129  }
130  if (swap)
131  return swapvar (listGCD (L), F.mvar(), x);
132  else
133  return listGCD (L);
134 }
factory&#39;s class for variables
Definition: factory.h:115
factory&#39;s main class
Definition: canonicalform.h:75
Variable alpha
Definition: facAbsBiFact.cc:52
static TreeM * G
Definition: janet.cc:38
CanonicalForm swapvar(const CanonicalForm &, const Variable &, const Variable &)
swapvar() - swap variables x1 and x2 in f.
Definition: cf_ops.cc:168
int i
Definition: cfEzgcd.cc:123
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
class to iterate through CanonicalForm&#39;s
Definition: cf_iter.h:44
static CanonicalForm listGCD(const CFList &L)
#define swap(_i, _j)
int gcd(int a, int b)
Definition: walkSupport.cc:839
Variable x
Definition: cfModGcd.cc:4023
int degree(const CanonicalForm &f)
CanonicalForm LC(const CanonicalForm &f)

§ newMainVariableSearch()

static int newMainVariableSearch ( CanonicalForm A,
CFList Aeval,
CFList evaluation,
const Variable alpha,
const int  lev,
CanonicalForm g 
)
inlinestatic

Definition at line 913 of file facFqFactorize.cc.

917 {
918  Variable x= Variable (1);
919  CanonicalForm derivI, buf;
920  bool GF= (CFFactory::gettype() == GaloisFieldDomain);
921  int swapLevel= 0;
922  CFList list;
923  bool fail= false;
924  buf= A;
925  Aeval= CFList();
926  evaluation= CFList();
927  for (int i= lev; i <= A.level(); i++)
928  {
929  derivI= deriv (buf, Variable (i));
930  if (!derivI.isZero())
931  {
932  g= gcd (buf, derivI);
933  if (degree (g) > 0)
934  return -1;
935 
936  buf= swapvar (buf, x, Variable (i));
937  Aeval= CFList();
938  evaluation= CFList();
939  fail= false;
940  evaluation= evalPoints (buf, Aeval, alpha, list, GF, fail);
941  if (!fail)
942  {
943  A= buf;
944  swapLevel= i;
945  break;
946  }
947  else
948  buf= A;
949  }
950  }
951  return swapLevel;
952 }
List< CanonicalForm > CFList
CanonicalForm deriv(const CanonicalForm &f, const Variable &x)
CFList evalPoints(const CanonicalForm &F, CFList &eval, const Variable &alpha, CFList &list, const bool &GF, bool &fail)
evaluation point search for multivariate factorization, looks for a (F.level() - 1)-tuple such that t...
factory&#39;s class for variables
Definition: factory.h:115
CF_NO_INLINE bool isZero() const
Definition: cf_inline.cc:372
factory&#39;s main class
Definition: canonicalform.h:75
CanonicalForm swapvar(const CanonicalForm &, const Variable &, const Variable &)
swapvar() - swap variables x1 and x2 in f.
Definition: cf_ops.cc:168
int status int void * buf
Definition: si_signals.h:59
#define A
Definition: sirandom.c:23
int i
Definition: cfEzgcd.cc:123
static int gettype()
Definition: cf_factory.h:27
int gcd(int a, int b)
Definition: walkSupport.cc:839
Variable x
Definition: cfModGcd.cc:4023
#define GaloisFieldDomain
Definition: cf_defs.h:22
int level() const
level() returns the level of CO.
int degree(const CanonicalForm &f)

§ precomputeLeadingCoeff()

CFList precomputeLeadingCoeff ( const CanonicalForm LCF,
const CFList LCFFactors,
const Variable alpha,
const CFList evaluation,
CFList *&  differentSecondVarLCs,
int  lSecondVarLCs,
Variable y 
)

computes a list l of length length(LCFFactors)+1 of polynomials such that prod (l)=LCF, note that the first entry of l may be non constant. Intended to be used to precompute coefficients of a polynomial f from its bivariate factorizations.

Returns
see above
Parameters
[in]LCFa multivariate poly
[in]LCFFactorsa list of univariate factors of LCF of level 2
[in]alphaalgebraic var.
[in]evaluationan evaluation point having lSecondVarLCs+1 components
[in]differentSecondVarLCsLCs of factors of f wrt different second variables
[in]lSecondVarLCslength of the above
[in,out]yif y.level() is not 1 on output the second variable has been changed to y

Definition at line 1464 of file facFqFactorize.cc.

1469 {
1470  y= Variable (1);
1471  if (LCF.inCoeffDomain())
1472  {
1473  CFList result;
1474  for (int i= 1; i <= LCFFactors.length() + 1; i++)
1475  result.append (1);
1476  return result;
1477  }
1478 
1479  CFMap N, M;
1480  CFArray dummy= CFArray (2);
1481  dummy [0]= LCF;
1482  dummy [1]= Variable (2);
1483  compress (dummy, M, N);
1484  CanonicalForm F= M (LCF);
1485  if (LCF.isUnivariate())
1486  {
1487  CFList result;
1488  int LCFLevel= LCF.level();
1489  bool found= false;
1490  if (LCFLevel == 2)
1491  {
1492  //bivariate leading coefficients are already the true leading coefficients
1493  result= LCFFactors;
1494  found= true;
1495  }
1496  else
1497  {
1498  CFListIterator j;
1499  for (int i= 0; i < lSecondVarLCs; i++)
1500  {
1501  for (j= differentSecondVarLCs[i]; j.hasItem(); j++)
1502  {
1503  if (j.getItem().level() == LCFLevel)
1504  {
1505  found= true;
1506  break;
1507  }
1508  }
1509  if (found)
1510  {
1511  result= differentSecondVarLCs [i];
1512  break;
1513  }
1514  }
1515  if (!found)
1516  result= LCFFactors;
1517  }
1518  if (found)
1519  result.insert (Lc (LCF));
1520  else
1521  result.insert (LCF);
1522 
1523  return result;
1524  }
1525 
1526  CFList factors= LCFFactors;
1527 
1528  for (CFListIterator i= factors; i.hasItem(); i++)
1529  i.getItem()= M (i.getItem());
1530 
1531  CanonicalForm sqrfPartF;
1532  CFFList * bufSqrfFactors= new CFFList [factors.length()];
1533  CFList evalSqrfPartF, bufFactors;
1534  CFArray evalPoint= CFArray (evaluation.length() - 1);
1535  CFArray buf= CFArray (evaluation.length());
1536  CFArray swap= CFArray (evaluation.length());
1538  CanonicalForm vars=getVars (LCF)*Variable (2);
1539  for (int i= evaluation.length() +1; i > 1; i--, iter++)
1540  {
1541  buf[i-2]=iter.getItem();
1542  if (degree (vars, i) > 0)
1543  swap[M(Variable (i)).level()-1]=buf[i-2];
1544  }
1545  buf= swap;
1546  for (int i= 0; i < evaluation.length() - 1; i++)
1547  evalPoint[i]= buf[i+1];
1548 
1549  int pass= testFactors (F, factors, alpha, sqrfPartF,
1550  bufFactors, bufSqrfFactors, evalSqrfPartF, evalPoint);
1551 
1552  bool foundDifferent= false;
1553  Variable z, x= y;
1554  int j= 0;
1555  if (!pass)
1556  {
1557  int lev= 0;
1558  // LCF is non-constant here
1559  CFList bufBufFactors;
1560  CanonicalForm bufF;
1561  for (int i= 0; i < lSecondVarLCs; i++)
1562  {
1563  if (!differentSecondVarLCs [i].isEmpty())
1564  {
1565  bool allConstant= true;
1566  for (iter= differentSecondVarLCs[i]; iter.hasItem(); iter++)
1567  {
1568  if (!iter.getItem().inCoeffDomain())
1569  {
1570  allConstant= false;
1571  y= Variable (iter.getItem().level());
1572  lev= M(y).level();
1573  }
1574  }
1575  if (allConstant)
1576  continue;
1577 
1578  bufFactors= differentSecondVarLCs [i];
1579  for (iter= bufFactors; iter.hasItem(); iter++)
1580  iter.getItem()= swapvar (iter.getItem(), x, y);
1581  bufF= F;
1582  z= Variable (lev);
1583  bufF= swapvar (bufF, x, z);
1584  bufBufFactors= bufFactors;
1585  evalPoint= CFArray (evaluation.length() - 1);
1586  for (int k= 1; k < evaluation.length(); k++)
1587  {
1588  if (N (Variable (k+1)).level() != y.level())
1589  evalPoint[k-1]= buf[k];
1590  else
1591  evalPoint[k-1]= buf[0];
1592  }
1593  pass= testFactors (bufF, bufBufFactors, alpha, sqrfPartF, bufFactors,
1594  bufSqrfFactors, evalSqrfPartF, evalPoint);
1595  if (pass)
1596  {
1597  foundDifferent= true;
1598  F= bufF;
1599  CFList l= factors;
1600  for (iter= l; iter.hasItem(); iter++)
1601  iter.getItem()= swapvar (iter.getItem(), x, y);
1602  differentSecondVarLCs [i]= l;
1603  j= i;
1604  break;
1605  }
1606  if (!pass && i == lSecondVarLCs - 1)
1607  {
1608  CFList result;
1609  result.append (LCF);
1610  for (int j= 1; j <= factors.length(); j++)
1611  result.append (1);
1612  result= distributeContent (result, differentSecondVarLCs, lSecondVarLCs);
1613  y= Variable (1);
1614  delete [] bufSqrfFactors;
1615  return result;
1616  }
1617  }
1618  }
1619  }
1620  if (!pass)
1621  {
1622  CFList result;
1623  result.append (LCF);
1624  for (int j= 1; j <= factors.length(); j++)
1625  result.append (1);
1626  result= distributeContent (result, differentSecondVarLCs, lSecondVarLCs);
1627  y= Variable (1);
1628  delete [] bufSqrfFactors;
1629  return result;
1630  }
1631  else
1632  factors= bufFactors;
1633 
1634  bufFactors= factors;
1635 
1636  CFMap MM, NN;
1637  dummy [0]= sqrfPartF;
1638  dummy [1]= 1;
1639  compress (dummy, MM, NN);
1640  sqrfPartF= MM (sqrfPartF);
1641  CanonicalForm varsSqrfPartF= getVars (sqrfPartF);
1642  for (CFListIterator iter= factors; iter.hasItem(); iter++)
1643  iter.getItem()= MM (iter.getItem());
1644 
1645  CFList evaluation2;
1646  for (int i= 2; i <= varsSqrfPartF.level(); i++)
1647  evaluation2.insert (evalPoint[NN (Variable (i)).level()-2]);
1648 
1649  CFList interMedResult;
1650  CanonicalForm oldSqrfPartF= sqrfPartF;
1651  sqrfPartF= shift2Zero (sqrfPartF, evalSqrfPartF, evaluation2);
1652  if (factors.length() > 1)
1653  {
1654  CanonicalForm LC1= LC (oldSqrfPartF, 1);
1655  CFList leadingCoeffs;
1656  for (int i= 0; i < factors.length(); i++)
1657  leadingCoeffs.append (LC1);
1658 
1659  CFList LC1eval= evaluateAtEval (LC1, evaluation2, 2);
1660  CFList oldFactors= factors;
1661  for (CFListIterator i= oldFactors; i.hasItem(); i++)
1662  i.getItem() *= LC1eval.getFirst()/Lc (i.getItem());
1663 
1664  bool success= false;
1665  CanonicalForm oldSqrfPartFPowLC= oldSqrfPartF*power(LC1,factors.length()-1);
1666  CFList heuResult;
1667  if (size (oldSqrfPartFPowLC)/getNumVars (oldSqrfPartFPowLC) < 500 &&
1668  LucksWangSparseHeuristic (oldSqrfPartFPowLC,
1669  oldFactors, 2, leadingCoeffs, heuResult))
1670  {
1671  interMedResult= recoverFactors (oldSqrfPartF, heuResult);
1672  if (oldFactors.length() == interMedResult.length())
1673  success= true;
1674  }
1675  if (!success)
1676  {
1677  LC1= LC (evalSqrfPartF.getFirst(), 1);
1678 
1679  CFArray leadingCoeffs= CFArray (factors.length());
1680  for (int i= 0; i < factors.length(); i++)
1681  leadingCoeffs[i]= LC1;
1682 
1683  for (CFListIterator i= factors; i.hasItem(); i++)
1684  i.getItem() *= LC1 (0,2)/Lc (i.getItem());
1685  factors.insert (1);
1686 
1688  newSqrfPartF= evalSqrfPartF.getFirst()*power (LC1, factors.length() - 2);
1689 
1690  int liftBound= degree (newSqrfPartF,2) + 1;
1691 
1692  CFMatrix M= CFMatrix (liftBound, factors.length() - 1);
1693  CFArray Pi;
1694  CFList diophant;
1695  nonMonicHenselLift12 (newSqrfPartF, factors, liftBound, Pi, diophant, M,
1696  leadingCoeffs, false);
1697 
1698  if (sqrfPartF.level() > 2)
1699  {
1700  int* liftBounds= new int [sqrfPartF.level() - 1];
1701  bool noOneToOne= false;
1702  CFList *leadingCoeffs2= new CFList [sqrfPartF.level()-2];
1703  LC1= LC (evalSqrfPartF.getLast(), 1);
1704  CFList LCs;
1705  for (int i= 0; i < factors.length(); i++)
1706  LCs.append (LC1);
1707  leadingCoeffs2 [sqrfPartF.level() - 3]= LCs;
1708  for (int i= sqrfPartF.level() - 1; i > 2; i--)
1709  {
1710  for (CFListIterator j= LCs; j.hasItem(); j++)
1711  j.getItem()= j.getItem() (0, i + 1);
1712  leadingCoeffs2 [i - 3]= LCs;
1713  }
1714  sqrfPartF *= power (LC1, factors.length()-1);
1715 
1716  int liftBoundsLength= sqrfPartF.level() - 1;
1717  for (int i= 0; i < liftBoundsLength; i++)
1718  liftBounds [i]= degree (sqrfPartF, i + 2) + 1;
1719  evalSqrfPartF= evaluateAtZero (sqrfPartF);
1720  evalSqrfPartF.removeFirst();
1721  factors= nonMonicHenselLift (evalSqrfPartF, factors, leadingCoeffs2,
1722  diophant, Pi, liftBounds, sqrfPartF.level() - 1, noOneToOne);
1723  delete [] leadingCoeffs2;
1724  delete [] liftBounds;
1725  }
1726  for (CFListIterator iter= factors; iter.hasItem(); iter++)
1727  iter.getItem()= reverseShift (iter.getItem(), evaluation2);
1728 
1729  interMedResult=
1730  recoverFactors (reverseShift(evalSqrfPartF.getLast(),evaluation2),
1731  factors);
1732  }
1733  }
1734  else
1735  {
1736  CanonicalForm contF=content (oldSqrfPartF,1);
1737  factors= CFList (oldSqrfPartF/contF);
1738  interMedResult= recoverFactors (oldSqrfPartF, factors);
1739  }
1740 
1741  for (CFListIterator iter= interMedResult; iter.hasItem(); iter++)
1742  iter.getItem()= NN (iter.getItem());
1743 
1744  CFList result;
1746  for (int i= 0; i < LCFFactors.length(); i++)
1747  {
1748  CanonicalForm tmp= 1;
1749  for (k= bufSqrfFactors[i]; k.hasItem(); k++)
1750  {
1751  int pos= findItem (bufFactors, k.getItem().factor());
1752  if (pos)
1753  tmp *= power (getItem (interMedResult, pos), k.getItem().exp());
1754  }
1755  result.append (tmp);
1756  }
1757 
1758  for (CFListIterator i= result; i.hasItem(); i++)
1759  {
1760  F /= i.getItem();
1761  if (foundDifferent)
1762  i.getItem()= swapvar (i.getItem(), x, z);
1763  i.getItem()= N (i.getItem());
1764  }
1765 
1766  if (foundDifferent)
1767  {
1768  CFList l= differentSecondVarLCs [j];
1769  for (CFListIterator i= l; i.hasItem(); i++)
1770  i.getItem()= swapvar (i.getItem(), y, z);
1771  differentSecondVarLCs [j]= l;
1772  F= swapvar (F, x, z);
1773  }
1774 
1775  result.insert (N (F));
1776 
1777  result= distributeContent (result, differentSecondVarLCs, lSecondVarLCs);
1778 
1779  if (!result.getFirst().inCoeffDomain())
1780  {
1781  // prepare input for recursion
1782  if (foundDifferent)
1783  {
1784  for (CFListIterator i= result; i.hasItem(); i++)
1785  i.getItem()= swapvar (i.getItem(), Variable (2), y);
1786  CFList l= differentSecondVarLCs [j];
1787  for (CFListIterator i= l; i.hasItem(); i++)
1788  i.getItem()= swapvar (i.getItem(), y, z);
1789  differentSecondVarLCs [j]= l;
1790  }
1791 
1792  F= result.getFirst();
1793  int level= 0;
1794  if (foundDifferent)
1795  {
1796  level= y.level() - 2;
1797  for (int i= y.level(); i > 1; i--)
1798  {
1799  if (degree (F,i) > 0)
1800  {
1801  if (y.level() == 3)
1802  level= 0;
1803  else
1804  level= i-3;
1805  }
1806  }
1807  }
1808 lcretry:
1809  if (lSecondVarLCs - level > 0)
1810  {
1811  CFList evaluation2= evaluation;
1812  int j= lSecondVarLCs+2;
1814  CFListIterator i;
1815  for (i= evaluation2; i.hasItem(); i++, j--)
1816  {
1817  if (j==y.level())
1818  {
1819  swap= i.getItem();
1820  i.getItem()= evaluation2.getLast();
1821  evaluation2.removeLast();
1822  evaluation2.append (swap);
1823  }
1824  }
1825 
1826  CFList newLCs= differentSecondVarLCs[level];
1827  if (newLCs.isEmpty())
1828  {
1829  if (degree (F, level+3) > 0)
1830  {
1831  delete [] bufSqrfFactors;
1832  return result; //TODO handle this case
1833  }
1834  level=level+1;
1835  goto lcretry;
1836  }
1837  i= newLCs;
1838  CFListIterator iter= result;
1839  iter++;
1840  CanonicalForm quot;
1841  for (;iter.hasItem(); iter++, i++)
1842  {
1843  swap= iter.getItem();
1844  if (degree (swap, level+3) > 0)
1845  {
1846  int count= evaluation.length()+1;
1847  for (CFListIterator iter2= evaluation2; iter2.hasItem(); iter2++,
1848  count--)
1849  {
1850  if (count != level+3)
1851  swap= swap (iter2.getItem(), count);
1852  }
1853  if (fdivides (swap, i.getItem(), quot))
1854  i.getItem()= quot;
1855  }
1856  }
1857  CFList * differentSecondVarLCs2= new CFList [lSecondVarLCs - level - 1];
1858  for (int j= level+1; j < lSecondVarLCs; j++)
1859  {
1860  if (degree (F, j+3) > 0)
1861  {
1862  if (!differentSecondVarLCs[j].isEmpty())
1863  {
1864  differentSecondVarLCs2[j - level - 1]= differentSecondVarLCs[j];
1865  i= differentSecondVarLCs2[j-level - 1];
1866  iter=result;
1867  iter++;
1868  for (;iter.hasItem(); iter++, i++)
1869  {
1870  swap= iter.getItem();
1871  if (degree (swap, j+3) > 0)
1872  {
1873  int count= evaluation.length()+1;
1874  for (CFListIterator iter2= evaluation2; iter2.hasItem();iter2++,
1875  count--)
1876  {
1877  if (count != j+3)
1878  swap= swap (iter2.getItem(), count);
1879  }
1880  if (fdivides (swap, i.getItem(), quot))
1881  i.getItem()= quot;
1882  }
1883  }
1884  }
1885  }
1886  }
1887 
1888  for (int j= 0; j < level+1; j++)
1889  evaluation2.removeLast();
1890  Variable dummyvar= Variable (1);
1891 
1892  CanonicalForm newLCF= result.getFirst();
1893  newLCF=swapvar (newLCF, Variable (2), Variable (level+3));
1894  for (i=newLCs; i.hasItem(); i++)
1895  i.getItem()= swapvar (i.getItem(), Variable (2), Variable (level+3));
1896  for (int j= 1; j < lSecondVarLCs-level;j++)
1897  {
1898  for (i= differentSecondVarLCs2[j-1]; i.hasItem(); i++)
1899  i.getItem()= swapvar (i.getItem(), Variable (2+j),
1900  Variable (level+3+j));
1901  newLCF= swapvar (newLCF, Variable (2+j), Variable (level+3+j));
1902  }
1903 
1904  CFList recursiveResult=
1905  precomputeLeadingCoeff (newLCF, newLCs, alpha, evaluation2,
1906  differentSecondVarLCs2, lSecondVarLCs - level - 1,
1907  dummyvar);
1908 
1909  if (dummyvar.level() != 1)
1910  {
1911  for (i= recursiveResult; i.hasItem(); i++)
1912  i.getItem()= swapvar (i.getItem(), Variable (2), dummyvar);
1913  }
1914  for (i= recursiveResult; i.hasItem(); i++)
1915  {
1916  for (int j= lSecondVarLCs-level-1; j > 0; j--)
1917  i.getItem()=swapvar (i.getItem(), Variable (2+j),
1918  Variable (level+3+j));
1919  i.getItem()= swapvar (i.getItem(), Variable (2), Variable (level+3));
1920  }
1921 
1922  if (recursiveResult.getFirst() == result.getFirst())
1923  {
1924  delete [] bufSqrfFactors;
1925  delete [] differentSecondVarLCs2;
1926  return result;
1927  }
1928  else
1929  {
1930  iter=recursiveResult;
1931  i= result;
1932  i.getItem()= iter.getItem();
1933  i++;
1934  iter++;
1935  for (; i.hasItem(); i++, iter++)
1936  i.getItem() *= iter.getItem();
1937  delete [] differentSecondVarLCs2;
1938  }
1939  }
1940  }
1941  else
1942  y= Variable (1);
1943 
1944  delete [] bufSqrfFactors;
1945 
1946  return result;
1947 }
int status int void size_t count
Definition: si_signals.h:59
int testFactors(const CanonicalForm &G, const CFList &uniFactors, const Variable &alpha, CanonicalForm &sqrfPartF, CFList &factors, CFFList *&bufSqrfFactors, CFList &evalSqrfPartF, const CFArray &evalPoint)
CanonicalForm shift2Zero(const CanonicalForm &F, CFList &Feval, const CFList &evaluation, int l)
shift evaluation point to zero
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
List< CanonicalForm > CFList
const CanonicalForm int const CFList const Variable & y
Definition: facAbsFact.cc:57
CFList recoverFactors(const CanonicalForm &F, const CFList &factors)
divides factors by their content wrt. Variable(1) and checks if these polys divide F ...
CFList distributeContent(const CFList &L, const CFList *differentSecondVarFactors, int length)
distribute content
CFList evaluateAtEval(const CanonicalForm &F, const CFArray &eval)
evaluate F at evaluation
int level(const CanonicalForm &f)
int isEmpty() const
Definition: ftmpl_list.cc:267
Matrix< CanonicalForm > CFMatrix
CanonicalForm reverseShift(const CanonicalForm &F, const CFList &evaluation, int l)
reverse shifting the evaluation point to zero
CanonicalForm LCF
Definition: facFactorize.cc:53
CanonicalForm getItem(const CFList &list, const int &pos)
helper function
Definition: cf_map_ext.cc:49
factory&#39;s class for variables
Definition: factory.h:115
CFFListIterator iter
Definition: facAbsBiFact.cc:54
factory&#39;s main class
Definition: canonicalform.h:75
Array< CanonicalForm > CFArray
int k
Definition: cfEzgcd.cc:93
const CanonicalForm int const CFList & evaluation
Definition: facAbsFact.cc:55
int LucksWangSparseHeuristic(const CanonicalForm &F, const CFList &factors, int level, const CFList &leadingCoeffs, CFList &result)
sparse heuristic lifting by Wang and Lucks
CFList nonMonicHenselLift(const CFList &F, const CFList &factors, const CFList &LCs, CFList &diophant, CFArray &Pi, CFMatrix &M, int lOld, int &lNew, const CFList &MOD, bool &noOneToOne)
Definition: facHensel.cc:2709
void insert(const T &)
Definition: ftmpl_list.cc:193
CanonicalForm Lc(const CanonicalForm &f)
CanonicalForm compress(const CanonicalForm &f, CFMap &m)
CanonicalForm compress ( const CanonicalForm & f, CFMap & m )
Definition: cf_map.cc:210
void removeFirst()
Definition: ftmpl_list.cc:287
CanonicalForm content(const CanonicalForm &)
CanonicalForm content ( const CanonicalForm & f )
Definition: cf_gcd.cc:180
CFList evaluateAtZero(const CanonicalForm &F)
evaluate F successively n-2 at 0
bool found
Definition: facFactorize.cc:56
T getFirst() const
Definition: ftmpl_list.cc:279
#define M
Definition: sirandom.c:24
CanonicalForm swapvar(const CanonicalForm &, const Variable &, const Variable &)
swapvar() - swap variables x1 and x2 in f.
Definition: cf_ops.cc:168
void removeLast()
Definition: ftmpl_list.cc:317
const CanonicalForm CFMap CFMap & N
Definition: cfEzgcd.cc:49
CanonicalForm getVars(const CanonicalForm &f)
CanonicalForm getVars ( const CanonicalForm & f )
Definition: cf_ops.cc:350
int j
Definition: myNF.cc:70
int status int void * buf
Definition: si_signals.h:59
int level() const
Definition: factory.h:132
bool isUnivariate() const
T & getItem() const
Definition: ftmpl_list.cc:431
CFList precomputeLeadingCoeff(const CanonicalForm &LCF, const CFList &LCFFactors, const Variable &alpha, const CFList &evaluation, CFList *&differentSecondVarLCs, int lSecondVarLCs, Variable &y)
computes a list l of length length(LCFFactors)+1 of polynomials such that prod (l)=LCF, note that the first entry of l may be non constant. Intended to be used to precompute coefficients of a polynomial f from its bivariate factorizations.
int i
Definition: cfEzgcd.cc:123
T getLast() const
Definition: ftmpl_list.cc:309
int size(const CanonicalForm &f, const Variable &v)
int size ( const CanonicalForm & f, const Variable & v )
Definition: cf_ops.cc:600
class CFMap
Definition: cf_map.h:84
bool fdivides(const CanonicalForm &f, const CanonicalForm &g)
bool fdivides ( const CanonicalForm & f, const CanonicalForm & g )
int getNumVars(const CanonicalForm &f)
int getNumVars ( const CanonicalForm & f )
Definition: cf_ops.cc:314
int length() const
Definition: ftmpl_list.cc:273
#define swap(_i, _j)
Variable x
Definition: cfModGcd.cc:4023
int level() const
level() returns the level of CO.
void append(const T &)
Definition: ftmpl_list.cc:256
int degree(const CanonicalForm &f)
CanonicalForm LC(const CanonicalForm &f)
int findItem(const CFList &list, const CanonicalForm &item)
helper function
Definition: cf_map_ext.cc:37
static void evalPoint(const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &FEval, CanonicalForm &GEval, CFGenerator &evalPoint)
void nonMonicHenselLift12(const CanonicalForm &F, CFList &factors, int l, CFArray &Pi, CFList &diophant, CFMatrix &M, const CFArray &LCs, bool sort)
Hensel lifting from univariate to bivariate, factors need not to be monic.
Definition: facHensel.cc:2018
int l
Definition: cfEzgcd.cc:94
return result
Definition: facAbsBiFact.cc:76
bool inCoeffDomain() const

§ prepareLeadingCoeffs()

void prepareLeadingCoeffs ( CFList *&  LCs,
CanonicalForm A,
CFList Aeval,
int  n,
const CFList leadingCoeffs,
const CFList biFactors,
const CFList evaluation 
)

normalize precomputed leading coefficients such that leading coefficients evaluated at evaluation in K^(n-2) equal the leading coeffs wrt Variable(1) of bivariate factors and change A and Aeval accordingly

Parameters
[in,out]LCs
[in,out]A
[in,out]Aeval
[in]nlevel of poly to be factored
[in]leadingCoeffsprecomputed leading coeffs
[in]biFactorsbivariate factors
[in]evaluationevaluation point

Definition at line 2365 of file facFqFactorize.cc.

2368 {
2369  CFList l= leadingCoeffs;
2370  LCs [n-3]= l;
2371  CFListIterator j;
2373  for (int i= n - 1; i > 2; i--, iter++)
2374  {
2375  for (j= l; j.hasItem(); j++)
2376  j.getItem()= j.getItem() (iter.getItem(), i + 1);
2377  LCs [i - 3]= l;
2378  }
2379  l= LCs [0];
2380  for (CFListIterator i= l; i.hasItem(); i++)
2381  i.getItem()= i.getItem() (iter.getItem(), 3);
2382  CFListIterator ii= biFactors;
2383  CFList normalizeFactor;
2384  for (CFListIterator i= l; i.hasItem(); i++, ii++)
2385  normalizeFactor.append (Lc (LC (ii.getItem(), 1))/Lc (i.getItem()));
2386  for (int i= 0; i < n-2; i++)
2387  {
2388  ii= normalizeFactor;
2389  for (j= LCs [i]; j.hasItem(); j++, ii++)
2390  j.getItem() *= ii.getItem();
2391  }
2392 
2393  Aeval= evaluateAtEval (A, evaluation, 2);
2394 
2395  CanonicalForm hh= 1/Lc (Aeval.getFirst());
2396 
2397  for (iter= Aeval; iter.hasItem(); iter++)
2398  iter.getItem() *= hh;
2399 
2400  A *= hh;
2401 }
CFList evaluateAtEval(const CanonicalForm &F, const CFArray &eval)
evaluate F at evaluation
CFFListIterator iter
Definition: facAbsBiFact.cc:54
factory&#39;s main class
Definition: canonicalform.h:75
const CanonicalForm int const CFList & evaluation
Definition: facAbsFact.cc:55
CanonicalForm Lc(const CanonicalForm &f)
T getFirst() const
Definition: ftmpl_list.cc:279
int j
Definition: myNF.cc:70
T & getItem() const
Definition: ftmpl_list.cc:431
int i
Definition: cfEzgcd.cc:123
void append(const T &)
Definition: ftmpl_list.cc:256
CanonicalForm LC(const CanonicalForm &f)
int l
Definition: cfEzgcd.cc:94

§ prodEval()

static CanonicalForm prodEval ( const CFList l,
const CanonicalForm evalPoint,
const Variable v 
)
inlinestatic

Definition at line 1998 of file facFqFactorize.cc.

2000 {
2001  CanonicalForm result= 1;
2002  for (CFListIterator i= l; i.hasItem(); i++)
2003  result *= i.getItem() (evalPoint, v);
2004  return result;
2005 }
factory&#39;s main class
Definition: canonicalform.h:75
int i
Definition: cfEzgcd.cc:123
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:37
static void evalPoint(const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &FEval, CanonicalForm &GEval, CFGenerator &evalPoint)
return result
Definition: facAbsBiFact.cc:76

§ recombination()

CFList recombination ( const CFList factors1,
const CFList factors2,
int  s,
int  thres,
const CanonicalForm evalPoint,
const Variable x 
)

recombination of bivariate factors factors1 s. t. the result evaluated at evalPoint coincides with factors2

Parameters
[in]factors1list of bivariate factors
[in]factors2list univariate factors
[in]salgorithm starts checking subsets of size s
[in]thresthreshold for the size of subsets which are checked
[in]evalPointevaluation point
[in]xsecond variable of bivariate factors

Definition at line 2100 of file facFqFactorize.cc.

2102 {
2103  CFList T, S;
2104 
2105  T= factors1;
2106  CFList result;
2108  int * v= new int [T.length()];
2109  for (int i= 0; i < T.length(); i++)
2110  v[i]= 0;
2111  bool nosubset= false;
2112  CFArray TT;
2113  TT= copy (factors1);
2114  int recombinations= 0;
2115  while (T.length() >= 2*s && s <= thres)
2116  {
2117  while (nosubset == false)
2118  {
2119  if (T.length() == s)
2120  {
2121  delete [] v;
2122  if (recombinations == factors2.length() - 1)
2123  result.append (prod (T));
2124  else
2125  result= Union (result, T);
2126  return result;
2127  }
2128  S= subset (v, s, TT, nosubset);
2129  if (nosubset) break;
2130  buf= prodEval (S, evalPoint, x);
2131  buf /= Lc (buf);
2132  if (find (factors2, buf))
2133  {
2134  recombinations++;
2135  T= Difference (T, S);
2136  result.append (prod (S));
2137  TT= copy (T);
2138  indexUpdate (v, s, T.length(), nosubset);
2139  if (nosubset) break;
2140  }
2141  }
2142  s++;
2143  if (T.length() < 2*s || T.length() == s)
2144  {
2145  if (recombinations == factors2.length() - 1)
2146  result.append (prod (T));
2147  else
2148  result= Union (result, T);
2149  delete [] v;
2150  return result;
2151  }
2152  for (int i= 0; i < T.length(); i++)
2153  v[i]= 0;
2154  nosubset= false;
2155  }
2156 
2157  delete [] v;
2158  if (T.length() < 2*s)
2159  {
2160  result= Union (result, T);
2161  return result;
2162  }
2163 
2164  return result;
2165 }
void indexUpdate(int index [], const int &subsetSize, const int &setSize, bool &noSubset)
update index
const CanonicalForm int s
Definition: facAbsFact.cc:55
CFArray copy(const CFList &list)
write elements of list into an array
static CanonicalForm prodEval(const CFList &l, const CanonicalForm &evalPoint, const Variable &v)
factory&#39;s main class
Definition: canonicalform.h:75
CanonicalForm Lc(const CanonicalForm &f)
template bool find(const List< CanonicalForm > &, const CanonicalForm &)
CFList subset(int index [], const int &s, const CFArray &elements, bool &noSubset)
extract a subset given by index of size s from elements, if there is no subset we have not yet consid...
template List< Variable > Union(const List< Variable > &, const List< Variable > &)
int status int void * buf
Definition: si_signals.h:59
int i
Definition: cfEzgcd.cc:123
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:37
int length() const
Definition: ftmpl_list.cc:273
fq_nmod_poly_t prod
Definition: facHensel.cc:95
void append(const T &)
Definition: ftmpl_list.cc:256
static jList * T
Definition: janet.cc:37
template List< Variable > Difference(const List< Variable > &, const List< Variable > &)
return result
Definition: facAbsBiFact.cc:76

§ refineBiFactors()

void refineBiFactors ( const CanonicalForm A,
CFList biFactors,
CFList *const Aeval,
const CFList evaluation,
int  minFactorsLength 
)

refine a bivariate factorization of A with l factors to one with minFactorsLength if possible

Parameters
[in]Asome poly
[in,out]biFactorslist of bivariate to be refined, returns refined factors
[in]Aevallist of bivariate factorizations of A wrt different second variables
[in]evaluationthe evaluation point
[in]minFactorsLengththe minimal number of factors

Definition at line 2318 of file facFqFactorize.cc.

2321 {
2322  CFListIterator iter, iter2;
2324  int i;
2325  Variable v;
2326  Variable y= Variable (2);
2327  CFList list;
2328  bool leaveLoop= false;
2329  for (int j= 0; j < A.level() - 2; j++)
2330  {
2331  if (Aeval[j].length() == minFactorsLength)
2332  {
2333  i= A.level();
2334 
2335  for (iter= evaluation; iter.hasItem(); iter++, i--)
2336  {
2337  for (iter2= Aeval[j]; iter2.hasItem(); iter2++)
2338  {
2339  if (i == iter2.getItem().level())
2340  {
2341  evalPoint= iter.getItem();
2342  leaveLoop= true;
2343  break;
2344  }
2345  }
2346  if (leaveLoop)
2347  {
2348  leaveLoop= false;
2349  break;
2350  }
2351  }
2352 
2353  v= Variable (i);
2354  list= buildUniFactors (Aeval[j], evalPoint, v);
2355 
2356  biFactors= recombination (biFactors, list, 1,
2357  biFactors.length() - list.length() + 1,
2358  evaluation.getLast(), y);
2359  return;
2360  }
2361  }
2362 }
const CanonicalForm int const CFList const Variable & y
Definition: facAbsFact.cc:57
factory&#39;s class for variables
Definition: factory.h:115
CFFListIterator iter
Definition: facAbsBiFact.cc:54
CFList int & minFactorsLength
[in,out] minimal length of < bivariate factors
Definition: facFactorize.h:31
factory&#39;s main class
Definition: canonicalform.h:75
int j
Definition: myNF.cc:70
T & getItem() const
Definition: ftmpl_list.cc:431
int i
Definition: cfEzgcd.cc:123
T getLast() const
Definition: ftmpl_list.cc:309
CFList recombination(const CFList &factors1, const CFList &factors2, int s, int thres, const CanonicalForm &evalPoint, const Variable &x)
recombination of bivariate factors factors1 s. t. the result evaluated at evalPoint coincides with fa...
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:37
CFList buildUniFactors(const CFList &biFactors, const CanonicalForm &evalPoint, const Variable &y)
plug in evalPoint for y in a list of polys
int length() const
Definition: ftmpl_list.cc:273
int level() const
level() returns the level of CO.
static void evalPoint(const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &FEval, CanonicalForm &GEval, CFGenerator &evalPoint)

§ sortByUniFactors()

void sortByUniFactors ( CFList *&  Aeval,
int  AevalLength,
CFList uniFactors,
CFList biFactors,
const CFList evaluation 
)

sort bivariate factors in Aeval such that their corresponding univariate factors coincide with uniFactors, uniFactors and biFactors may get recombined if necessary

Parameters
[in,out]Aevalarray of bivariate factors
[in]AevalLengthlength of Aeval
[in,out]uniFactorsunivariate factors
[in,out]biFactorsbivariate factors
[in]evaluationevaluation point

Definition at line 2234 of file facFqFactorize.cc.

2238 {
2240  int i;
2241  CFListIterator iter, iter2;
2242  Variable v;
2243  CFList LCs, buf;
2244  CFArray l;
2245  int pos, index, checklength;
2246  bool leaveLoop=false;
2247 recurse:
2248  for (int j= 0; j < AevalLength; j++)
2249  {
2250  if (!Aeval[j].isEmpty())
2251  {
2252  i= evaluation.length() + 1;
2253  for (iter= evaluation; iter.hasItem(); iter++, i--)
2254  {
2255  for (iter2= Aeval[j]; iter2.hasItem(); iter2++)
2256  {
2257  if (i == iter2.getItem().level())
2258  {
2259  evalPoint= iter.getItem();
2260  leaveLoop= true;
2261  break;
2262  }
2263  }
2264  if (leaveLoop)
2265  {
2266  leaveLoop= false;
2267  break;
2268  }
2269  }
2270 
2271  v= Variable (i);
2272  if (Aeval[j].length() > uniFactors.length())
2273  Aeval[j]= recombination (Aeval[j], uniFactors, 1,
2274  Aeval[j].length() - uniFactors.length() + 1,
2275  evalPoint, v);
2276 
2277  checklength= biFactors.length();
2278  Aeval[j]= checkOneToOne (Aeval[j], uniFactors, biFactors, evalPoint, v);
2279  if (checklength > biFactors.length())
2280  {
2281  uniFactors= buildUniFactors (biFactors, evaluation.getLast(),
2282  Variable (2));
2283  goto recurse;
2284  }
2285 
2286  buf= buildUniFactors (Aeval[j], evalPoint, v);
2287  l= CFArray (uniFactors.length());
2288  index= 1;
2289  for (iter= buf; iter.hasItem(); iter++, index++)
2290  {
2291  pos= findItem (uniFactors, iter.getItem());
2292  if (pos)
2293  l[pos-1]= getItem (Aeval[j], index);
2294  }
2295  buf= conv (l);
2296  Aeval [j]= buf;
2297 
2298  buf= buildUniFactors (Aeval[j], evalPoint, v);
2299  }
2300  }
2301 }
CanonicalForm getItem(const CFList &list, const int &pos)
helper function
Definition: cf_map_ext.cc:49
factory&#39;s class for variables
Definition: factory.h:115
CFFListIterator iter
Definition: facAbsBiFact.cc:54
factory&#39;s main class
Definition: canonicalform.h:75
Array< CanonicalForm > CFArray
CFList checkOneToOne(const CFList &factors1, const CFList &factors2, CFList &factors3, const CanonicalForm &evalPoint, const Variable &x)
check if univariate factors factors2 of factors3 coincide with univariate factors of factors1 and rec...
int j
Definition: myNF.cc:70
int status int void * buf
Definition: si_signals.h:59
T & getItem() const
Definition: ftmpl_list.cc:431
int i
Definition: cfEzgcd.cc:123
T getLast() const
Definition: ftmpl_list.cc:309
CFList recombination(const CFList &factors1, const CFList &factors2, int s, int thres, const CanonicalForm &evalPoint, const Variable &x)
recombination of bivariate factors factors1 s. t. the result evaluated at evalPoint coincides with fa...
static int index(p_Length length, p_Ord ord)
Definition: p_Procs_Impl.h:592
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:37
CFList buildUniFactors(const CFList &biFactors, const CanonicalForm &evalPoint, const Variable &y)
plug in evalPoint for y in a list of polys
int length() const
Definition: ftmpl_list.cc:273
CFList conv(const CFArray &A)
int findItem(const CFList &list, const CanonicalForm &item)
helper function
Definition: cf_map_ext.cc:37
static void evalPoint(const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &FEval, CanonicalForm &GEval, CFGenerator &evalPoint)
int l
Definition: cfEzgcd.cc:94

§ testFactors()

int testFactors ( const CanonicalForm G,
const CFList uniFactors,
const Variable alpha,
CanonicalForm sqrfPartF,
CFList factors,
CFFList *&  bufSqrfFactors,
CFList evalSqrfPartF,
const CFArray evalPoint 
)

Definition at line 1371 of file facFqFactorize.cc.

1375 {
1376  CanonicalForm F= G;
1377  CFFList sqrfFactorization;
1378  if (getCharacteristic() > 0)
1379  sqrfFactorization= squarefreeFactorization (F, alpha);
1380  else
1381  sqrfFactorization= sqrFree (F);
1382 
1383  sqrfPartF= 1;
1384  for (CFFListIterator i= sqrfFactorization; i.hasItem(); i++)
1385  sqrfPartF *= i.getItem().factor();
1386 
1387  evalSqrfPartF= evaluateAtEval (sqrfPartF, evalPoint);
1388 
1389  CanonicalForm test= evalSqrfPartF.getFirst() (evalPoint[0], 2);
1390 
1391  if (degree (test) != degree (sqrfPartF, 1) || test.inCoeffDomain())
1392  return 0;
1393 
1394  CFFList sqrfFactors;
1395  CanonicalForm tmp;
1396  CFList tmp2;
1397  int k= 0;
1398  factors= uniFactors;
1400  for (CFListIterator i= factors; i.hasItem(); i++, k++)
1401  {
1402  tmp= 1;
1403  if (getCharacteristic() > 0)
1404  sqrfFactors= squarefreeFactorization (i.getItem(), alpha);
1405  else
1406  sqrfFactors= sqrFree (i.getItem());
1407 
1408  for (iter= sqrfFactors; iter.hasItem(); iter++)
1409  {
1410  tmp2.append (iter.getItem().factor());
1411  tmp *= iter.getItem().factor();
1412  }
1413  i.getItem()= tmp/Lc(tmp);
1414  bufSqrfFactors [k]= sqrfFactors;
1415  }
1416 
1417  for (int i= 0; i < factors.length() - 1; i++)
1418  {
1419  for (k= i + 1; k < factors.length(); k++)
1420  {
1421  gcdFreeBasis (bufSqrfFactors [i], bufSqrfFactors[k]);
1422  }
1423  }
1424 
1425  factors= CFList();
1426  for (int i= 0; i < uniFactors.length(); i++)
1427  {
1428  if (i == 0)
1429  {
1430  for (iter= bufSqrfFactors [i]; iter.hasItem(); iter++)
1431  {
1432  if (iter.getItem().factor().inCoeffDomain())
1433  continue;
1434  iter.getItem()= CFFactor (iter.getItem().factor()/
1435  Lc (iter.getItem().factor()),
1436  iter.getItem().exp());
1437  factors.append (iter.getItem().factor());
1438  }
1439  }
1440  else
1441  {
1442  for (iter= bufSqrfFactors [i]; iter.hasItem(); iter++)
1443  {
1444  if (iter.getItem().factor().inCoeffDomain())
1445  continue;
1446  iter.getItem()= CFFactor (iter.getItem().factor()/
1447  Lc (iter.getItem().factor()),
1448  iter.getItem().exp());
1449  if (!find (factors, iter.getItem().factor()))
1450  factors.append (iter.getItem().factor());
1451  }
1452  }
1453  }
1454 
1455  test= prod (factors);
1456  tmp= evalSqrfPartF.getFirst() (evalPoint[0],2);
1457  if (test/Lc (test) != tmp/Lc (tmp))
1458  return 0;
1459  else
1460  return 1;
1461 }
List< CanonicalForm > CFList
CFList evaluateAtEval(const CanonicalForm &F, const CFArray &eval)
evaluate F at evaluation
CFFListIterator iter
Definition: facAbsBiFact.cc:54
factory&#39;s main class
Definition: canonicalform.h:75
int k
Definition: cfEzgcd.cc:93
Variable alpha
Definition: facAbsBiFact.cc:52
static TreeM * G
Definition: janet.cc:38
CanonicalForm Lc(const CanonicalForm &f)
int getCharacteristic()
Definition: cf_char.cc:51
template bool find(const List< CanonicalForm > &, const CanonicalForm &)
T getFirst() const
Definition: ftmpl_list.cc:279
CFFList squarefreeFactorization(const CanonicalForm &F, const Variable &alpha)
squarefree factorization over a finite field return a list of squarefree factors with multiplicity ...
T & getItem() const
Definition: ftmpl_list.cc:431
int i
Definition: cfEzgcd.cc:123
CFList tmp2
Definition: facFqBivar.cc:70
CanonicalForm test
Definition: cfModGcd.cc:4037
int length() const
Definition: ftmpl_list.cc:273
Factor< CanonicalForm > CFFactor
fq_nmod_poly_t prod
Definition: facHensel.cc:95
void gcdFreeBasis(CFFList &factors1, CFFList &factors2)
gcd free basis of two lists of factors
void append(const T &)
Definition: ftmpl_list.cc:256
int degree(const CanonicalForm &f)
CFFList sqrFree(const CanonicalForm &f, bool sort=false)
squarefree factorization
Definition: cf_factor.cc:757
bool inCoeffDomain() const

§ TIMING_DEFINE_PRINT()

TIMING_DEFINE_PRINT ( fac_fq_bi_factorizer  ) const