My Project
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"

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 748 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 2320 of file facFqFactorize.cc.

2322 {
2323  CFList result;
2324  CanonicalForm tmp;
2325  for (CFListIterator i= biFactors; i.hasItem(); i++)
2326  {
2327  tmp= mod (i.getItem(), y - evalPoint);
2328  tmp /= Lc (tmp);
2329  result.append (tmp);
2330  }
2331  return result;
2332 }
CF_NO_INLINE FACTORY_PUBLIC CanonicalForm mod(const CanonicalForm &, const CanonicalForm &)
CanonicalForm Lc(const CanonicalForm &f)
int i
Definition: cfEzgcd.cc:132
static void evalPoint(const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &FEval, CanonicalForm &GEval, CFGenerator &evalPoint)
factory's main class
Definition: canonicalform.h:86
return result
Definition: facAbsBiFact.cc:75
const CanonicalForm int const CFList const Variable & y
Definition: facAbsFact.cc:53

◆ 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 2543 of file facFqFactorize.cc.

2546 {
2547  Variable y= Variable (2);
2548  A= swapvar (A, y, w);
2549  int i= A.level();
2551  for (CFListIterator iter= evaluation; iter.hasItem(); iter++, i--)
2552  {
2553  if (i == w.level())
2554  {
2555  evalPoint= iter.getItem();
2556  iter.getItem()= evaluation.getLast();
2557  evaluation.removeLast();
2558  evaluation.append (evalPoint);
2559  break;
2560  }
2561  }
2562  for (i= 0; i < lengthAeval2; i++)
2563  {
2564  if (oldAeval[i].isEmpty())
2565  continue;
2566  if (oldAeval[i].getFirst().level() == w.level())
2567  {
2568  CFArray tmp= copy (oldAeval[i]);
2569  oldAeval[i]= biFactors;
2570  for (CFListIterator iter= oldAeval[i]; iter.hasItem(); iter++)
2571  iter.getItem()= swapvar (iter.getItem(), w, y);
2572  for (int ii= 0; ii < tmp.size(); ii++)
2573  tmp[ii]= swapvar (tmp[ii], w, y);
2574  CFArray tmp2= CFArray (tmp.size());
2576  for (int ii= 0; ii < tmp.size(); ii++)
2577  {
2578  buf= tmp[ii] (evaluation.getLast(),y);
2579  buf /= Lc (buf);
2580  tmp2[findItem (uniFactors, buf)-1]=tmp[ii];
2581  }
2582  biFactors= CFList();
2583  for (int j= 0; j < tmp2.size(); j++)
2584  biFactors.append (tmp2[j]);
2585  }
2586  }
2587 }
Array< CanonicalForm > CFArray
CanonicalForm swapvar(const CanonicalForm &, const Variable &, const Variable &)
swapvar() - swap variables x1 and x2 in f.
Definition: cf_ops.cc:168
int level(const CanonicalForm &f)
List< CanonicalForm > CFList
int findItem(const CFList &list, const CanonicalForm &item)
helper function
Definition: cf_map_ext.cc:41
int size() const
Definition: ftmpl_array.cc:92
int level() const
level() returns the level of CO.
T & getItem() const
Definition: ftmpl_list.cc:431
void append(const T &)
Definition: ftmpl_list.cc:256
factory's class for variables
Definition: factory.h:134
CFFListIterator iter
Definition: facAbsBiFact.cc:53
const CanonicalForm int const CFList & evaluation
Definition: facAbsFact.cc:52
const CanonicalForm & w
Definition: facAbsFact.cc:51
CFArray copy(const CFList &list)
write elements of list into an array
CFList tmp2
Definition: facFqBivar.cc:72
int j
Definition: facHensel.cc:110
int status int void * buf
Definition: si_signals.h:59
#define A
Definition: sirandom.c:24

◆ checkHelper()

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

Definition at line 2021 of file facFqFactorize.cc.

2023 {
2024  CanonicalForm g1= f1, g2;
2025  CFListIterator iter1= factors1, iter2= factors2;
2026  for (; iter1.hasItem(); iter1++, iter2++)
2027  {
2028  g2= gcd (g1, iter1.getItem());
2029  if (!g2.inCoeffDomain())
2030  {
2031  l1.append (iter1.getItem());
2032  l2.append (iter2.getItem());
2033  g1 /= g2;
2034  }
2035  }
2036  factors1= Difference (factors1, l1);
2037  factors2= Difference (factors2, l2);
2038 }
const CFList & factors2
template List< Variable > Difference(const List< Variable > &, const List< Variable > &)
int gcd(int a, int b)
Definition: walkSupport.cc:836

◆ 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 2045 of file facFqFactorize.cc.

2047 {
2048  CFList uniFactorsOfFactors1;
2049  CFList result, result2;
2050  CFList bad1= factors2;
2051  CFListIterator iter, iter2, iter3;
2052  CanonicalForm tmp;
2053  int pos;
2054 
2055  for (iter= factors1; iter.hasItem(); iter++)
2056  {
2057  tmp= iter.getItem() (evalPoint, x);
2058  tmp /= Lc (tmp);
2059  if ((pos= findItem (factors2, tmp)))
2060  {
2061  result2.append (getItem (factors3, pos));
2062  result.append (iter.getItem());
2063  bad1= Difference (bad1, CFList (tmp));
2064  }
2065  else
2066  uniFactorsOfFactors1.append (tmp);
2067  }
2068 
2069  CFList bad2, bad3;
2070  bad2= Difference (factors1, result);
2071  bad3= Difference (factors3, result2);
2072  CFList tmp2, tmp3;
2073  CanonicalForm g1, g2, g3, g4;
2074 
2075  while (!uniFactorsOfFactors1.isEmpty())
2076  {
2077  tmp= uniFactorsOfFactors1.getFirst();
2078  checkHelper (tmp, bad1, bad3, tmp2, tmp3);
2079  g1= prod (tmp2);
2080  g2= prod (tmp3);
2081  tmp2= CFList();
2082  tmp3= CFList();
2083  checkHelper (g1, uniFactorsOfFactors1, bad2, tmp2, tmp3);
2084  g3= prod (tmp2);
2085  g4= prod (tmp3);
2086  tmp2= CFList();
2087  tmp3= CFList();
2088  do
2089  {
2090  checkHelper (g3, bad1, bad3, tmp2, tmp3);
2091  g1 *= prod (tmp2);
2092  g2 *= prod (tmp3);
2093  tmp2= CFList();
2094  tmp3= CFList();
2095  checkHelper (g1, uniFactorsOfFactors1, bad2, tmp2, tmp3);
2096  g3 *= prod (tmp2);
2097  g4 *= prod (tmp3);
2098  tmp2= CFList();
2099  tmp3= CFList();
2100  } while (!bad2.isEmpty() && !bad3.isEmpty());
2101  result.append (g4);
2102  result2.append (g2);
2103  }
2104 
2105  if (factors3.length() != result2.length())
2106  factors3= result2;
2107  return result;
2108 }
Variable x
Definition: cfModGcd.cc:4084
CanonicalForm getItem(const CFList &list, const int &pos)
helper function
Definition: cf_map_ext.cc:53
T getFirst() const
Definition: ftmpl_list.cc:279
int length() const
Definition: ftmpl_list.cc:273
int isEmpty() const
Definition: ftmpl_list.cc:267
void checkHelper(const CanonicalForm &f1, CFList &factors1, CFList &factors2, CFList &l1, CFList &l2)
fq_nmod_poly_t prod
Definition: facHensel.cc:100

◆ conv()

CFList conv ( const CFArray A)

Definition at line 2223 of file facFqFactorize.cc.

2224 {
2225  CFList result;
2226  for (int i= A.max(); i >= A.min(); i--)
2227  result.insert (A[i]);
2228  return result;
2229 }

◆ 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 1294 of file facFqFactorize.cc.

1297 {
1298  CFList l= L;
1299  CanonicalForm content= l.getFirst();
1300 
1301  if (content.inCoeffDomain())
1302  return l;
1303 
1304  if (l.length() == 1)
1305  {
1306  CFList result;
1307  for (int i= 0; i < length; i++)
1308  {
1309  if (differentSecondVarFactors[i].isEmpty())
1310  continue;
1311  if (result.isEmpty())
1312  {
1313  result= differentSecondVarFactors[i];
1314  for (CFListIterator iter= result; iter.hasItem(); iter++)
1315  content /= iter.getItem();
1316  }
1317  else
1318  {
1319  CFListIterator iter1= result;
1320  for (CFListIterator iter2= differentSecondVarFactors[i];iter2.hasItem();
1321  iter2++, iter1++)
1322  {
1323  iter1.getItem() *= iter2.getItem();
1324  content /= iter2.getItem();
1325  }
1326  }
1327  }
1328  result.insert (content);
1329  return result;
1330  }
1331 
1332  Variable v;
1333  CFListIterator iter1, iter2;
1334  CanonicalForm tmp, g;
1335  CFList multiplier;
1336  for (int i= 0; i < length; i++)
1337  {
1338  if (differentSecondVarFactors[i].isEmpty())
1339  continue;
1340  iter1= l;
1341  iter1++;
1342 
1343  tmp= 1;
1344  for (iter2= differentSecondVarFactors[i]; iter2.hasItem();
1345  iter2++, iter1++)
1346  {
1347  if (iter2.getItem().inCoeffDomain())
1348  {
1349  multiplier.append (1);
1350  continue;
1351  }
1352  v= iter2.getItem().mvar();
1353  if (degree (iter2.getItem()) == degree (iter1.getItem(),v))
1354  {
1355  multiplier.append (1);
1356  continue;
1357  }
1358  g= gcd (iter2.getItem(), content);
1359  if (!g.inCoeffDomain())
1360  {
1361  tmp *= g;
1362  multiplier.append (g);
1363  }
1364  else
1365  multiplier.append (1);
1366  }
1367  if (!tmp.isOne() && fdivides (tmp, content))
1368  {
1369  iter1= l;
1370  iter1++;
1371  content /= tmp;
1372  for (iter2= multiplier; iter2.hasItem(); iter1++, iter2++)
1373  iter1.getItem() *= iter2.getItem();
1374  }
1375  multiplier= CFList();
1376  }
1377 
1378  l.removeFirst();
1379  l.insert (content);
1380  return l;
1381 }
int degree(const CanonicalForm &f)
CanonicalForm content(const CanonicalForm &)
CanonicalForm content ( const CanonicalForm & f )
Definition: cf_gcd.cc:603
int l
Definition: cfEzgcd.cc:100
g
Definition: cfModGcd.cc:4092
bool fdivides(const CanonicalForm &f, const CanonicalForm &g)
bool fdivides ( const CanonicalForm & f, const CanonicalForm & g )
CF_NO_INLINE bool isOne() const
bool inCoeffDomain() const
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:39
static BOOLEAN length(leftv result, leftv arg)
Definition: interval.cc:257

◆ 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 2590 of file facFqFactorize.cc.

2593 {
2594  CanonicalForm tmp= power (LCmultipler, biFactors.length() - 1);
2595  A *= tmp;
2596  tmp= LCmultipler;
2597  CFListIterator iter= leadingCoeffs;
2598  for (;iter.hasItem(); iter++)
2599  iter.getItem() *= LCmultipler;
2600  iter= evaluation;
2601  for (int i= A.level(); i > 2; i--, iter++)
2602  tmp= tmp (iter.getItem(), i);
2603  if (!tmp.inCoeffDomain())
2604  {
2605  for (CFListIterator i= biFactors; i.hasItem(); i++)
2606  {
2607  i.getItem() *= tmp/LC (i.getItem(), 1);
2608  i.getItem() /= Lc (i.getItem());
2609  }
2610  }
2611 }
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
CanonicalForm LC(const CanonicalForm &f)

◆ 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 611 of file facFqFactorize.cc.

614 {
615  CFList result;
616  CFList T= factors;
617  CanonicalForm buf= F;
618  Variable y= F.mvar();
619  Variable x= Variable (1);
620  CanonicalForm LCBuf= LC (buf, x);
621  CanonicalForm g, quot;
622  CFList M= MOD;
623  M.append (power (y, deg));
624  adaptedLiftBound= 0;
625  int d= bound;
626  int e= 0;
627  int nBuf;
628  for (CFListIterator i= factors; i.hasItem(); i++)
629  {
630  g= mulMod (i.getItem(), LCBuf, M);
631  g /= myContent (g);
632  if (fdivides (g, buf, quot))
633  {
634  result.append (g);
635  nBuf= degree (g, y) + degree (LC (g, x), y);
636  d -= nBuf;
637  e= tmax (e, nBuf);
638  buf= quot;
639  LCBuf= LC (buf, x);
640  T= Difference (T, CFList (i.getItem()));
641  }
642  }
643  adaptedLiftBound= d;
644 
645  if (adaptedLiftBound < deg)
646  {
647  if (adaptedLiftBound < degree (F) + 1)
648  {
649  if (d == 1)
650  adaptedLiftBound= tmin (e + 1, deg);
651  else
652  adaptedLiftBound= deg;
653  }
654  factors= T;
655  F= buf;
656  success= true;
657  }
658  return result;
659 }
static CanonicalForm bound(const CFMatrix &M)
Definition: cf_linsys.cc:460
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
static CanonicalForm myContent(const CanonicalForm &F)
CanonicalForm mulMod(const CanonicalForm &A, const CanonicalForm &B, const CFList &MOD)
Karatsuba style modular multiplication for multivariate polynomials.
Definition: facMul.cc:3080
template CanonicalForm tmax(const CanonicalForm &, const CanonicalForm &)
template CanonicalForm tmin(const CanonicalForm &, const CanonicalForm &)
STATIC_VAR jList * T
Definition: janet.cc:30
#define M
Definition: sirandom.c:25

◆ 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 750 of file facFqFactorize.cc.

752 {
753  int k= F.level() - 1;
754  Variable x= Variable (1);
755  CanonicalForm LCF=LC (F, x);
756  CFList LCFeval;
757 
758  CFList result;
759  FFRandom genFF;
760  GFRandom genGF;
761  int p= getCharacteristic ();
762  if (p < CHAR_THRESHOLD)
763  {
764  if (!GF && alpha.level() == 1)
765  {
766  fail= true;
767  return CFList();
768  }
769  else if (!GF && alpha.level() != 1)
770  {
771  if ((p == 2 && degree (getMipo (alpha)) < 6) ||
772  (p == 3 && degree (getMipo (alpha)) < 4) ||
773  (p == 5 && degree (getMipo (alpha)) < 3))
774  {
775  fail= true;
776  return CFList();
777  }
778  }
779  }
780  double bound;
781  if (alpha != x)
782  {
783  bound= pow ((double) p, (double) degree (getMipo(alpha)));
784  bound *= (double) k;
785  }
786  else if (GF)
787  {
788  bound= pow ((double) p, (double) getGFDegree());
789  bound *= (double) k;
790  }
791  else
792  bound= pow ((double) p, (double) k);
793 
794  CanonicalForm random;
796  do
797  {
798  random= 0;
799  // possible overflow if list.length() does not fit into a int
800  if (list.length() >= bound)
801  {
802  fail= true;
803  break;
804  }
805  for (int i= 0; i < k; i++)
806  {
807  if (list.isEmpty())
808  result.append (0);
809  else if (GF)
810  {
811  result.append (genGF.generate());
812  random += result.getLast()*power (x, i);
813  }
814  else if (alpha.level() != 1)
815  {
816  AlgExtRandomF genAlgExt (alpha);
817  result.append (genAlgExt.generate());
818  random += result.getLast()*power (x, i);
819  }
820  else
821  {
822  result.append (genFF.generate());
823  random += result.getLast()*power (x, i);
824  }
825  }
826  if (find (list, random))
827  {
828  result= CFList();
829  continue;
830  }
831  int l= F.level();
832  eval.insert (F);
833  LCFeval.insert (LCF);
834  bool bad= false;
835  for (CFListIterator i= result; i.hasItem(); i++, l--)
836  {
837  eval.insert (eval.getFirst()(i.getItem(), l));
838  LCFeval.insert (LCFeval.getFirst()(i.getItem(), l));
839  if (degree (eval.getFirst(), l - 1) != degree (F, 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  if ((l != 2) && (degree (LCFeval.getFirst(), l-1) != degree (LCF, l-1)))
850  {
851  if (!find (list, random))
852  list.append (random);
853  result= CFList();
854  eval= CFList();
855  LCFeval= CFList();
856  bad= true;
857  break;
858  }
859  }
860 
861  if (bad)
862  continue;
863 
864  if (degree (eval.getFirst()) != degree (F, 1))
865  {
866  if (!find (list, random))
867  list.append (random);
868  result= CFList();
869  LCFeval= CFList();
870  eval= CFList();
871  continue;
872  }
873 
874  deriv_x= deriv (eval.getFirst(), x);
876  if (degree (gcd_deriv) > 0)
877  {
878  if (!find (list, random))
879  list.append (random);
880  result= CFList();
881  LCFeval= CFList();
882  eval= CFList();
883  continue;
884  }
886  i++;
887  CanonicalForm contentx= content (i.getItem(), x);
888  if (degree (contentx) > 0)
889  {
890  if (!find (list, random))
891  list.append (random);
892  result= CFList();
893  LCFeval= CFList();
894  eval= CFList();
895  continue;
896  }
897 
898  contentx= content (i.getItem());
899  if (degree (contentx) > 0)
900  {
901  if (!find (list, random))
902  list.append (random);
903  result= CFList();
904  LCFeval= CFList();
905  eval= CFList();
906  continue;
907  }
908 
909  if (list.length() >= bound)
910  {
911  fail= true;
912  break;
913  }
914  } while (find (list, random));
915 
916  if (!eval.isEmpty())
917  eval.removeFirst();
918 
919  return result;
920 }
Rational pow(const Rational &a, int e)
Definition: GMPrat.cc:411
CanonicalForm deriv(const CanonicalForm &f, const Variable &x)
int getGFDegree()
Definition: cf_char.cc:75
int FACTORY_PUBLIC getCharacteristic()
Definition: cf_char.cc:70
int k
Definition: cfEzgcd.cc:99
int p
Definition: cfModGcd.cc:4080
generate random elements in F_p(alpha)
Definition: cf_random.h:70
generate random elements in F_p
Definition: cf_random.h:44
CanonicalForm generate() const
Definition: cf_random.cc:68
generate random elements in GF
Definition: cf_random.h:32
CanonicalForm generate() const
Definition: cf_random.cc:78
void removeFirst()
Definition: ftmpl_list.cc:287
void insert(const T &)
Definition: ftmpl_list.cc:193
int level() const
Definition: factory.h:150
Variable alpha
Definition: facAbsBiFact.cc:51
CanonicalForm contentx
CanonicalForm gcd_deriv
Definition: facFactorize.cc:58
CFList LCFeval
Definition: facFactorize.cc:53
CanonicalForm LCF
Definition: facFactorize.cc:52
CanonicalForm deriv_x
Definition: facFactorize.cc:58
bool bad
Definition: facFactorize.cc:64
CFList & eval
Definition: facFactorize.cc:47
#define CHAR_THRESHOLD
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
Definition: variable.cc:207
template bool find(const List< CanonicalForm > &, const CanonicalForm &)

◆ 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 1965 of file facFqFactorize.cc.

1967 {
1968  CanonicalForm tmp;
1969  CFList tmp2;
1971  bool preserveDegree= true;
1972  Variable x= Variable (1);
1973  int j, degAi, degA1= degree (A,1);
1974  for (int i= A.level(); i > 2; i--)
1975  {
1976  tmp= A;
1977  tmp2= CFList();
1978  iter= evaluation;
1979  preserveDegree= true;
1980  degAi= degree (A,i);
1981  for (j= A.level(); j > 1; j--, iter++)
1982  {
1983  if (j == i)
1984  continue;
1985  else
1986  {
1987  tmp= tmp (iter.getItem(), j);
1988  tmp2.insert (tmp);
1989  if ((degree (tmp, i) != degAi) ||
1990  (degree (tmp, 1) != degA1))
1991  {
1992  preserveDegree= false;
1993  break;
1994  }
1995  }
1996  }
1997  if (!content(tmp,1).inCoeffDomain())
1998  preserveDegree= false;
1999  if (!content(tmp).inCoeffDomain())
2000  preserveDegree= false;
2001  if (!(gcd (deriv (tmp,x), tmp)).inCoeffDomain())
2002  preserveDegree= false;
2003  if (preserveDegree)
2004  Aeval [i - 3]= tmp2;
2005  else
2006  Aeval [i - 3]= CFList();
2007  }
2008 }
CFList *& Aeval
<[in] poly
Definition: facFactorize.h:31

◆ 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 664 of file facFqFactorize.cc.

667 {
670  CanonicalForm gamma= info.getGamma();
672  int k= info.getGFDegree();
673  CFList result;
674  CFList T= factors;
675  CanonicalForm buf= F;
676  Variable y= F.mvar();
677  Variable x= Variable (1);
678  CanonicalForm LCBuf= LC (buf, x);
679  CanonicalForm g, gg, quot;
680  CFList M= MOD;
681  M.append (power (y, deg));
682  adaptedLiftBound= 0;
683  int d= bound;
684  int e= 0;
685  int nBuf;
686  CFList source, dest;
687 
688  int degMipoBeta= 1;
689  if (!k && beta.level() != 1)
690  degMipoBeta= degree (getMipo (beta));
691 
692  for (CFListIterator i= factors; i.hasItem(); i++)
693  {
694  g= mulMod (i.getItem(), LCBuf, M);
695  g /= myContent (g);
696  if (fdivides (g, buf, quot))
697  {
698  gg= reverseShift (g, eval);
699  gg /= Lc (gg);
700  if (!k && beta == x)
701  {
702  if (degree (gg, alpha) < degMipoBeta)
703  {
704  appendTestMapDown (result, gg, info, source, dest);
705  buf= quot;
706  nBuf= degree (g, y) + degree (LC (g, x), y);
707  d -= nBuf;
708  e= tmax (e, nBuf);
709  LCBuf= LC (buf, x);
710  T= Difference (T, CFList (i.getItem()));
711  }
712  }
713  else
714  {
715  if (!isInExtension (gg, gamma, k, delta, source, dest))
716  {
717  appendTestMapDown (result, gg, info, source, dest);
718  buf= quot;
719  nBuf= degree (g, y) + degree (LC (g, x), y);
720  d -= nBuf;
721  e= tmax (e, nBuf);
722  LCBuf= LC (buf, x);
723  T= Difference (T, CFList (i.getItem()));
724  }
725  }
726  }
727  }
728  adaptedLiftBound= d;
729 
730  if (adaptedLiftBound < deg)
731  {
732  if (adaptedLiftBound < degree (F) + 1)
733  {
734  if (d == 1)
735  adaptedLiftBound= tmin (e + 1, deg);
736  else
737  adaptedLiftBound= deg;
738  }
739  success= true;
740  factors= T;
741  F= buf;
742  }
743  return result;
744 }
int getGFDegree() const
getter
CanonicalForm getGamma() const
getter
CanonicalForm getDelta() const
getter
Variable getAlpha() const
getter
Variable getBeta() const
getter
Variable beta
Definition: facAbsFact.cc:95
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
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)
CanonicalForm reverseShift(const CanonicalForm &F, const CFList &evaluation, int l)
reverse shifting the evaluation point to zero
const ExtensionInfo & info
< [in] sqrfree poly
bool delta(X x, Y y, D d)
Definition: TestSuite.h:160

◆ 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 3660 of file facFqFactorize.cc.

3661 {
3662  CanonicalForm A= F;
3663 
3666  int k= info.getGFDegree();
3667  char cGFName= info.getGFName();
3669  bool GF= (CFFactory::gettype() == GaloisFieldDomain);
3670  Variable w= Variable (1);
3671 
3672  CFList factors;
3673  if (!GF && alpha == w) // we are in F_p
3674  {
3675  CFList factors;
3676  bool extension= true;
3677  int p= getCharacteristic();
3678  if (p < 7)
3679  {
3680  if (p == 2)
3682  else if (p == 3)
3684  else if (p == 5)
3686  ExtensionInfo info= ExtensionInfo (extension);
3687  A= A.mapinto();
3688  factors= multiFactorize (A, info);
3689 
3692  Variable vBuf= rootOf (mipo.mapinto());
3693  for (CFListIterator j= factors; j.hasItem(); j++)
3694  j.getItem()= GF2FalphaRep (j.getItem(), vBuf);
3695  prune (vBuf);
3696  }
3697  else if (p >= 7 && p*p < (1<<16)) // pass to GF if possible
3698  {
3700  ExtensionInfo info= ExtensionInfo (extension);
3701  A= A.mapinto();
3702  factors= multiFactorize (A, info);
3703 
3706  Variable vBuf= rootOf (mipo.mapinto());
3707  for (CFListIterator j= factors; j.hasItem(); j++)
3708  j.getItem()= GF2FalphaRep (j.getItem(), vBuf);
3709  prune (vBuf);
3710  }
3711  else // not able to pass to GF, pass to F_p(\alpha)
3712  {
3714  Variable v= rootOf (mipo);
3716  factors= multiFactorize (A, info);
3717  prune (v);
3718  }
3719  return factors;
3720  }
3721  else if (!GF && (alpha != w)) // we are in F_p(\alpha)
3722  {
3723  if (k == 1) // need factorization over F_p
3724  {
3725  int extDeg= degree (getMipo (alpha));
3726  extDeg++;
3727  CanonicalForm mipo= randomIrredpoly (extDeg, w);
3728  Variable v= rootOf (mipo);
3730  factors= multiFactorize (A, info);
3731  prune (v);
3732  }
3733  else
3734  {
3735  if (beta == w)
3736  {
3738  CanonicalForm primElem, imPrimElem;
3739  bool primFail= false;
3740  Variable vBuf;
3741  primElem= primitiveElement (alpha, vBuf, primFail);
3742  ASSERT (!primFail, "failure in integer factorizer");
3743  if (primFail)
3744  ; //ERROR
3745  else
3746  imPrimElem= mapPrimElem (primElem, alpha, v);
3747 
3748  CFList source, dest;
3749  CanonicalForm bufA= mapUp (A, alpha, v, primElem, imPrimElem,
3750  source, dest);
3751  ExtensionInfo info= ExtensionInfo (v, alpha, imPrimElem, primElem);
3752  factors= multiFactorize (bufA, info);
3753  prune (v);
3754  }
3755  else
3756  {
3758  CanonicalForm primElem, imPrimElem;
3759  bool primFail= false;
3760  Variable vBuf;
3761  ASSERT (!primFail, "failure in integer factorizer");
3762  if (primFail)
3763  ; //ERROR
3764  else
3765  imPrimElem= mapPrimElem (delta, beta, v);
3766 
3767  CFList source, dest;
3768  CanonicalForm bufA= mapDown (A, info, source, dest);
3769  source= CFList();
3770  dest= CFList();
3771  bufA= mapUp (bufA, beta, v, delta, imPrimElem, source, dest);
3772  ExtensionInfo info= ExtensionInfo (v, beta, imPrimElem, delta);
3773  factors= multiFactorize (bufA, info);
3774  prune (v);
3775  }
3776  }
3777  return factors;
3778  }
3779  else // we are in GF (p^k)
3780  {
3781  int p= getCharacteristic();
3782  int extensionDeg= getGFDegree();
3783  bool extension= true;
3784  if (k == 1) // need factorization over F_p
3785  {
3786  extensionDeg++;
3787  if (pow ((double) p, (double) extensionDeg) < (1<<16))
3788  // pass to GF(p^k+1)
3789  {
3791  setCharacteristic (p);
3792  Variable vBuf= rootOf (mipo.mapinto());
3793  A= GF2FalphaRep (A, vBuf);
3794  setCharacteristic (p, extensionDeg, 'Z');
3795  ExtensionInfo info= ExtensionInfo (extension);
3796  factors= multiFactorize (A.mapinto(), info);
3797  prune (vBuf);
3798  }
3799  else // not able to pass to another GF, pass to F_p(\alpha)
3800  {
3802  setCharacteristic (p);
3803  Variable vBuf= rootOf (mipo.mapinto());
3804  A= GF2FalphaRep (A, vBuf);
3805  Variable v= chooseExtension (vBuf, beta, k);
3806  ExtensionInfo info= ExtensionInfo (v, extension);
3807  factors= multiFactorize (A, info);
3808  prune (vBuf);
3809  }
3810  }
3811  else // need factorization over GF (p^k)
3812  {
3813  if (pow ((double) p, (double) 2*extensionDeg) < (1<<16))
3814  // pass to GF(p^2k)
3815  {
3816  setCharacteristic (p, 2*extensionDeg, 'Z');
3817  ExtensionInfo info= ExtensionInfo (k, cGFName, extension);
3818  factors= multiFactorize (GFMapUp (A, extensionDeg), info);
3819  setCharacteristic (p, extensionDeg, cGFName);
3820  }
3821  else // not able to pass to GF (p^2k), pass to F_p (\alpha)
3822  {
3824  setCharacteristic (p);
3825  Variable v1= rootOf (mipo.mapinto());
3826  A= GF2FalphaRep (A, v1);
3827  Variable v2= chooseExtension (v1, v1, k);
3828  CanonicalForm primElem, imPrimElem;
3829  bool primFail= false;
3830  Variable vBuf;
3831  primElem= primitiveElement (v1, v1, primFail);
3832  if (primFail)
3833  ; //ERROR
3834  else
3835  imPrimElem= mapPrimElem (primElem, v1, v2);
3836  CFList source, dest;
3837  CanonicalForm bufA= mapUp (A, v1, v2, primElem, imPrimElem,
3838  source, dest);
3839  ExtensionInfo info= ExtensionInfo (v2, v1, imPrimElem, primElem);
3840  factors= multiFactorize (bufA, info);
3841  setCharacteristic (p, k, cGFName);
3842  for (CFListIterator i= factors; i.hasItem(); i++)
3843  i.getItem()= Falpha2GFRep (i.getItem());
3844  prune (v1);
3845  }
3846  }
3847  return factors;
3848  }
3849 }
void FACTORY_PUBLIC setCharacteristic(int c)
Definition: cf_char.cc:28
static Variable chooseExtension(const Variable &alpha)
Definition: cfModGcd.cc:422
#define ASSERT(expression, message)
Definition: cf_assert.h:99
#define GaloisFieldDomain
Definition: cf_defs.h:24
CanonicalForm randomIrredpoly(int i, const Variable &x)
computes a random monic irreducible univariate polynomial in x over Fp of degree i via NTL/FLINT
Definition: cf_irred.cc:26
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:450
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:342
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:123
static CanonicalForm mapUp(const Variable &alpha, const Variable &beta)
and is a primitive element, returns the image of
Definition: cf_map_ext.cc:70
CanonicalForm Falpha2GFRep(const CanonicalForm &F)
change representation by residue classes modulo a Conway polynomial to representation by primitive el...
Definition: cf_map_ext.cc:203
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:240
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:195
static int gettype()
Definition: cf_factory.h:28
CanonicalForm mapinto() const
ExtensionInfo contains information about extension.
Definition: ExtensionInfo.h:51
char getGFName() const
getter
CanonicalForm mipo
Definition: facAlgExt.cc:57
CFList multiFactorize(const CanonicalForm &F, const ExtensionInfo &info)
Variable FACTORY_PUBLIC rootOf(const CanonicalForm &, char name='@')
returns a symbolic root of polynomial with name name Use it to define algebraic variables
Definition: variable.cc:162
void FACTORY_PUBLIC prune(Variable &alpha)
Definition: variable.cc:261
INST_VAR CanonicalForm gf_mipo
Definition: gfops.cc:56

◆ 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 215 of file facFqFactorize.cc.

218 {
221  CanonicalForm gamma= info.getGamma();
223  int k= info.getGFDegree();
224  CFList source, dest;
225  if (factors.length() == 1)
226  {
228  return CFList (mapDown (buf, info, source, dest));
229  }
230  if (factors.length() < 1)
231  return CFList();
232 
233  int degMipoBeta= 1;
234  if (!k && beta.level() != 1)
235  degMipoBeta= degree (getMipo (beta));
236 
237  CFList T, S;
238  T= factors;
239 
240  int s= 1;
241  CFList result;
243 
244  buf= F;
245 
246  Variable x= Variable (1);
247  CanonicalForm g, LCBuf= LC (buf, x);
248  CanonicalForm buf2, quot;
249  int * v= new int [T.length()];
250  for (int i= 0; i < T.length(); i++)
251  v[i]= 0;
252  bool noSubset= false;
253  CFArray TT;
254  TT= copy (factors);
255  bool recombination= false;
256  bool trueFactor= false;
257  while (T.length() >= 2*s)
258  {
259  while (noSubset == false)
260  {
261  if (T.length() == s)
262  {
263  delete [] v;
264  if (recombination)
265  {
266  T.insert (LCBuf);
267  g= prodMod (T, M);
268  T.removeFirst();
269  result.append (g/myContent (g));
271  g /= Lc (g);
272  appendTestMapDown (result, g, info, source, dest);
273  return result;
274  }
275  else
276  {
278  return CFList (buf);
279  }
280  }
281 
282  S= subset (v, s, TT, noSubset);
283  if (noSubset) break;
284 
285  S.insert (LCBuf);
286  g= prodMod (S, M);
287  S.removeFirst();
288  g /= myContent (g);
289  if (fdivides (g, buf, quot))
290  {
292  buf2 /= Lc (buf2);
293  if (!k && beta == x)
294  {
295  if (degree (buf2, alpha) < degMipoBeta)
296  {
297  appendTestMapDown (result, buf2, info, source, dest);
298  buf= quot;
299  LCBuf= LC (buf, x);
300  recombination= true;
301  trueFactor= true;
302  }
303  }
304  else
305  {
306  if (!isInExtension (buf2, gamma, k, delta, source, dest))
307  {
308  appendTestMapDown (result, buf2, info, source, dest);
309  buf /= g;
310  LCBuf= LC (buf, x);
311  recombination= true;
312  trueFactor= true;
313  }
314  }
315 
316  if (trueFactor)
317  {
318  T= Difference (T, S);
319 
320  if (T.length() < 2*s || T.length() == s)
321  {
323  buf /= Lc (buf);
324  appendTestMapDown (result, buf, info, source, dest);
325  delete [] v;
326  return result;
327  }
328  trueFactor= false;
329  TT= copy (T);
330  indexUpdate (v, s, T.length(), noSubset);
331  if (noSubset) break;
332  }
333  }
334  }
335  s++;
336  if (T.length() < 2*s || T.length() == s)
337  {
339  appendTestMapDown (result, buf, info, source, dest);
340  delete [] v;
341  return result;
342  }
343  for (int i= 0; i < T.length(); i++)
344  v[i]= 0;
345  noSubset= false;
346  }
347  if (T.length() < 2*s)
348  {
350  appendMapDown (result, buf, info, source, dest);
351  }
352 
353  delete [] v;
354  return result;
355 }
const CanonicalForm int s
Definition: facAbsFact.cc:51
void indexUpdate(int index[], const int &subsetSize, const int &setSize, bool &noSubset)
update index
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 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...
CanonicalForm buf2
Definition: facFqBivar.cc:73
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...
CanonicalForm prodMod(const CFList &L, const CanonicalForm &M)
product of all elements in L modulo M via divide-and-conquer.
Definition: facMul.cc:3180

◆ 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 513 of file facFqFactorize.cc.

516 {
519  CanonicalForm gamma= info.getGamma();
521  int k= info.getGFDegree();
522  int adaptedLiftBound= 0;
523  CanonicalForm buf= F;
524  Variable y= F.mvar();
525  Variable x= Variable (1);
526  CanonicalForm LCBuf= LC (buf, x);
527  CanonicalForm g, gg, quot;
528  CFList M= MOD;
529  M.append (power (y, deg));
530  adaptedLiftBound= 0;
531  int d= bound;
532  int e= 0;
533  int nBuf;
534  int degMipoBeta= 1;
535  if (!k && beta.level() != 1)
536  degMipoBeta= degree (getMipo (beta));
537 
538  CFList source, dest;
539  for (CFListIterator i= factors; i.hasItem(); i++)
540  {
541  g= mulMod (i.getItem(), LCBuf, M);
542  g /= myContent (g);
543  if (fdivides (g, buf, quot))
544  {
545  gg= reverseShift (g, eval);
546  gg /= Lc (gg);
547  if (!k && beta == x)
548  {
549  if (degree (gg, alpha) < degMipoBeta)
550  {
551  buf= quot;
552  nBuf= degree (g, y) + degree (LC (g, x), y);
553  d -= nBuf;
554  e= tmax (e, nBuf);
555  LCBuf= LC (buf, x);
556  }
557  }
558  else
559  {
560  if (!isInExtension (gg, gamma, k, delta, source, dest))
561  {
562  buf= quot;
563  nBuf= degree (g, y) + degree (LC (g, x), y);
564  d -= nBuf;
565  e= tmax (e, nBuf);
566  LCBuf= LC (buf, x);
567  }
568  }
569  }
570  }
571  adaptedLiftBound= d;
572 
573  if (adaptedLiftBound < deg)
574  {
575  if (adaptedLiftBound < degree (F) + 1)
576  {
577  if (d == 1)
578  {
579  if (e + 1 > deg)
580  {
581  adaptedLiftBound= deg;
582  success= false;
583  }
584  else
585  {
586  success= true;
587  if (e + 1 < degree (F) + 1)
588  adaptedLiftBound= deg;
589  else
590  adaptedLiftBound= e + 1;
591  }
592  }
593  else
594  {
595  success= true;
596  adaptedLiftBound= deg;
597  }
598  }
599  else
600  {
601  success= true;
602  }
603  }
604 
605  return adaptedLiftBound;
606 }

◆ extNonMonicFactorRecombination()

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

Definition at line 2420 of file facFqFactorize.cc.

2422 {
2425  CanonicalForm gamma= info.getGamma();
2427  int k= info.getGFDegree();
2428  CFList source, dest;
2429 
2430  int degMipoBeta= 1;
2431  if (!k && beta != Variable(1))
2432  degMipoBeta= degree (getMipo (beta));
2433 
2434  CFList T, S;
2435  T= factors;
2436  int s= 1;
2437  CFList result;
2438  CanonicalForm quot, buf= F;
2439 
2440  CanonicalForm g;
2442  int * v= new int [T.length()];
2443  for (int i= 0; i < T.length(); i++)
2444  v[i]= 0;
2445  bool noSubset= false;
2446  CFArray TT;
2447  TT= copy (factors);
2448  bool recombination= false;
2449  bool trueFactor= false;
2450  while (T.length() >= 2*s)
2451  {
2452  while (noSubset == false)
2453  {
2454  if (T.length() == s)
2455  {
2456  delete [] v;
2457  if (recombination)
2458  {
2459  g= prod (T);
2460  T.removeFirst();
2461  g /= myContent (g);
2462  g /= Lc (g);
2463  appendTestMapDown (result, g, info, source, dest);
2464  return result;
2465  }
2466  else
2467  return CFList (buf/myContent(buf));
2468  }
2469 
2470  S= subset (v, s, TT, noSubset);
2471  if (noSubset) break;
2472 
2473  g= prod (S);
2474  g /= myContent (g);
2475  if (fdivides (g, buf, quot))
2476  {
2477  buf2= g;
2478  buf2 /= Lc (buf2);
2479  if (!k && beta.level() == 1)
2480  {
2481  if (degree (buf2, alpha) < degMipoBeta)
2482  {
2483  appendTestMapDown (result, buf2, info, source, dest);
2484  buf= quot;
2485  recombination= true;
2486  trueFactor= true;
2487  }
2488  }
2489  else
2490  {
2491  if (!isInExtension (buf2, gamma, k, delta, source, dest))
2492  {
2493  appendTestMapDown (result, buf2, info, source, dest);
2494  buf= quot;
2495  recombination= true;
2496  trueFactor= true;
2497  }
2498  }
2499  if (trueFactor)
2500  {
2501  T= Difference (T, S);
2502 
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  trueFactor= false;
2512  TT= copy (T);
2513  indexUpdate (v, s, T.length(), noSubset);
2514  if (noSubset) break;
2515  }
2516  }
2517  }
2518  s++;
2519  if (T.length() < 2*s || T.length() == s)
2520  {
2521  delete [] v;
2522  buf /= myContent (buf);
2523  buf /= Lc (buf);
2524  appendTestMapDown (result, buf, info, source, dest);
2525  return result;
2526  }
2527  for (int i= 0; i < T.length(); i++)
2528  v[i]= 0;
2529  noSubset= false;
2530  }
2531  if (T.length() < 2*s)
2532  {
2533  buf= F/myContent (F);
2534  buf /= Lc (buf);
2535  appendMapDown (result, buf, info, source, dest);
2536  }
2537 
2538  delete [] v;
2539  return result;
2540 }

◆ factorizationWRTDifferentSecondVars()

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

Definition at line 2183 of file facFqFactorize.cc.

2186 {
2187  Variable x= Variable (1);
2188  minFactorsLength= 0;
2189  irred= false;
2190  CFList factors;
2191  Variable v;
2192  for (int j= 0; j < A.level() - 2; j++)
2193  {
2194  if (!Aeval[j].isEmpty())
2195  {
2196  v= Variable (Aeval[j].getFirst().level());
2198  factors= GFBiSqrfFactorize (Aeval[j].getFirst());
2199  else if (info.getAlpha().level() == 1)
2200  factors= FpBiSqrfFactorize (Aeval[j].getFirst());
2201  else
2202  factors= FqBiSqrfFactorize (Aeval[j].getFirst(), info.getAlpha());
2203 
2204  factors.removeFirst();
2205  if (minFactorsLength == 0)
2206  minFactorsLength= factors.length();
2207  else
2209 
2210  if (factors.length() == 1)
2211  {
2212  irred= true;
2213  return;
2214  }
2215  sortList (factors, x);
2216  Aeval [j]= factors;
2217  }
2218  }
2219 }
CFList int & minFactorsLength
[in,out] minimal length of bivariate factors
Definition: facFactorize.h:33
CFList int bool & irred
[in,out] Is A irreducible?
Definition: facFactorize.h:34
CFList FqBiSqrfFactorize(const CanonicalForm &G, const Variable &alpha)
factorize a squarefree bivariate polynomial over .
Definition: facFqBivar.h:156
CFList FpBiSqrfFactorize(const CanonicalForm &G)
factorize a squarefree bivariate polynomial over .
Definition: facFqBivar.h:141
CFList GFBiSqrfFactorize(const CanonicalForm &G)
factorize a squarefree bivariate polynomial over GF
Definition: facFqBivar.h:172
void sortList(CFList &list, const Variable &x)
sort a list of polynomials by their degree in x.
Definition: facHensel.cc:449

◆ 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 }
STATIC_VAR Poly * h
Definition: janet.cc:971

◆ 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 1268 of file facFqFactorize.cc.

1269 {
1270  CanonicalForm g;
1271  int k= factors1.length();
1272  int l= factors2.length();
1273  int n= 0;
1274  int m;
1276  for (CFFListIterator i= factors1; (n < k && i.hasItem()); i++, n++)
1277  {
1278  m= 0;
1279  for (j= factors2; (m < l && j.hasItem()); j++, m++)
1280  {
1281  g= gcd (i.getItem().factor(), j.getItem().factor());
1282  if (degree (g,1) > 0)
1283  {
1284  j.getItem()= CFFactor (j.getItem().factor()/g, j.getItem().exp());
1285  i.getItem()= CFFactor (i.getItem().factor()/g, i.getItem().exp());
1286  factors1.append (CFFactor (g, i.getItem().exp()));
1287  factors2.append (CFFactor (g, j.getItem().exp()));
1288  }
1289  }
1290  }
1291 }
Factor< CanonicalForm > CFFactor
int m
Definition: cfEzgcd.cc:128

◆ 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 2232 of file facFqFactorize.cc.

2234 {
2236  CFList LCs;
2237  for (int j= 0; j < A.level() - 2; j++)
2238  {
2239  if (!Aeval[j].isEmpty())
2240  {
2241  LCs= CFList();
2242  for (iter= Aeval[j]; iter.hasItem(); iter++)
2243  LCs.append (LC (iter.getItem(), 1));
2244  //normalize (LCs);
2245  Aeval[j]= LCs;
2246  }
2247  }
2248 }

◆ 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 984 of file facFqFactorize.cc.

988 {
989  bool extension= info.isInExtension();
990  CFList bufFactors= biFactors;
991  bufFactors.insert (LC (Aeval.getFirst(), 1));
992 
993  sortList (bufFactors, Variable (1));
994 
995  CFList diophant;
996  CFArray Pi;
997  int smallFactorDeg= 11; //tunable parameter
998  CFList result;
999  int adaptedLiftBound= 0;
1000  int liftBound= liftBounds[1];
1001 
1002  earlySuccess= false;
1003  CFList earlyReconstFactors;
1005  j++;
1006  CanonicalForm buf= j.getItem();
1007  CFMatrix Mat= CFMatrix (liftBound, bufFactors.length() - 1);
1008  MOD= CFList (power (Variable (2), liftBounds[0]));
1009  if (smallFactorDeg >= liftBound)
1010  {
1011  result= henselLift23 (Aeval, bufFactors, liftBounds, diophant, Pi, Mat);
1012  }
1013  else if (smallFactorDeg >= degree (buf) + 1)
1014  {
1015  liftBounds[1]= degree (buf) + 1;
1016  result= henselLift23 (Aeval, bufFactors, liftBounds, diophant, Pi, Mat);
1017  if (Aeval.length() == 2)
1018  {
1019  if (!extension)
1020  earlyFactors= earlyFactorDetect
1021  (buf, result, adaptedLiftBound, earlySuccess,
1022  degree (buf) + 1, MOD, liftBound);
1023  else
1024  earlyFactors= extEarlyFactorDetect
1025  (buf, result, adaptedLiftBound, earlySuccess,
1027  (buf) + 1, MOD, liftBound);
1028  }
1029  else
1030  {
1031  if (!extension)
1032  adaptedLiftBound= liftBoundAdaption (buf, result, earlySuccess,
1033  degree (buf) + 1, MOD, liftBound);
1034  else
1035  adaptedLiftBound= extLiftBoundAdaption (buf, result, earlySuccess, info,
1036  evaluation, degree (buf) + 1,
1037  MOD, liftBound);
1038  }
1039  if (!earlySuccess)
1040  {
1041  result.insert (LC (buf, 1));
1042  liftBounds[1]= adaptedLiftBound;
1043  liftBound= adaptedLiftBound;
1044  henselLiftResume (buf, result, degree (buf) + 1, liftBound,
1045  Pi, diophant, Mat, MOD);
1046  }
1047  else
1048  liftBounds[1]= adaptedLiftBound;
1049  }
1050  else if (smallFactorDeg < degree (buf) + 1)
1051  {
1052  liftBounds[1]= smallFactorDeg;
1053  result= henselLift23 (Aeval, bufFactors, liftBounds, diophant, Pi, Mat);
1054  if (Aeval.length() == 2)
1055  {
1056  if (!extension)
1057  earlyFactors= earlyFactorDetect (buf, result, adaptedLiftBound,
1058  earlySuccess, smallFactorDeg, MOD,
1059  liftBound);
1060  else
1061  earlyFactors= extEarlyFactorDetect (buf, result, adaptedLiftBound,
1062  earlySuccess, info, evaluation,
1063  smallFactorDeg, MOD, liftBound);
1064  }
1065  else
1066  {
1067  if (!extension)
1068  adaptedLiftBound= liftBoundAdaption (buf, result, earlySuccess,
1069  smallFactorDeg, MOD, liftBound);
1070  else
1071  adaptedLiftBound= extLiftBoundAdaption (buf, result, earlySuccess, info,
1072  evaluation, smallFactorDeg, MOD,
1073  liftBound);
1074  }
1075 
1076  if (!earlySuccess)
1077  {
1078  result.insert (LC (buf, 1));
1079  henselLiftResume (buf, result, smallFactorDeg, degree (buf) + 1,
1080  Pi, diophant, Mat, MOD);
1081  if (Aeval.length() == 2)
1082  {
1083  if (!extension)
1084  earlyFactors= earlyFactorDetect (buf, result, adaptedLiftBound,
1085  earlySuccess, degree (buf) + 1,
1086  MOD, liftBound);
1087  else
1088  earlyFactors= extEarlyFactorDetect (buf, result, adaptedLiftBound,
1089  earlySuccess, info, evaluation,
1090  degree (buf) + 1, MOD,
1091  liftBound);
1092  }
1093  else
1094  {
1095  if (!extension)
1096  adaptedLiftBound= liftBoundAdaption (buf, result, earlySuccess,
1097  degree (buf) + 1, MOD,liftBound);
1098  else
1099  adaptedLiftBound= extLiftBoundAdaption (buf, result, earlySuccess,
1100  info, evaluation,
1101  degree (buf) + 1, MOD,
1102  liftBound);
1103  }
1104  if (!earlySuccess)
1105  {
1106  result.insert (LC (buf, 1));
1107  liftBounds[1]= adaptedLiftBound;
1108  liftBound= adaptedLiftBound;
1109  henselLiftResume (buf, result, degree (buf) + 1, liftBound,
1110  Pi, diophant, Mat, MOD);
1111  }
1112  else
1113  liftBounds[1]= adaptedLiftBound;
1114  }
1115  else
1116  liftBounds[1]= adaptedLiftBound;
1117  }
1118 
1119  MOD.append (power (Variable (3), liftBounds[1]));
1120 
1121  if (Aeval.length() > 2)
1122  {
1124  j++;
1125  CFList bufEval;
1126  bufEval.append (j.getItem());
1127  j++;
1128  int liftBoundsLength= Aeval.getLast().level() - 1;
1129  for (int i= 2; i <= liftBoundsLength && j.hasItem(); i++, j++)
1130  {
1131  earlySuccess= false;
1132  result.insert (LC (bufEval.getFirst(), 1));
1133  bufEval.append (j.getItem());
1134  liftBound= liftBounds[i];
1135  Mat= CFMatrix (liftBounds[i], result.length() - 1);
1136 
1137  buf= j.getItem();
1138  if (smallFactorDeg >= liftBound)
1139  result= henselLift (bufEval, result, MOD, diophant, Pi, Mat,
1140  liftBounds[i - 1], liftBounds[i]);
1141  else if (smallFactorDeg >= degree (buf) + 1)
1142  {
1143  result= henselLift (bufEval, result, MOD, diophant, Pi, Mat,
1144  liftBounds[i - 1], degree (buf) + 1);
1145 
1146  if (Aeval.length() == i + 1)
1147  {
1148  if (!extension)
1149  earlyFactors= earlyFactorDetect
1150  (buf, result, adaptedLiftBound, earlySuccess,
1151  degree (buf) + 1, MOD, liftBound);
1152  else
1153  earlyFactors= extEarlyFactorDetect
1154  (buf, result, adaptedLiftBound, earlySuccess,
1155  info, evaluation, degree (buf) + 1, MOD, liftBound);
1156  }
1157  else
1158  {
1159  if (!extension)
1160  adaptedLiftBound= liftBoundAdaption
1161  (buf, result, earlySuccess, degree (buf)
1162  + 1, MOD, liftBound);
1163  else
1164  adaptedLiftBound= extLiftBoundAdaption
1165  (buf, result, earlySuccess, info, evaluation,
1166  degree (buf) + 1, MOD, liftBound);
1167  }
1168 
1169  if (!earlySuccess)
1170  {
1171  result.insert (LC (buf, 1));
1172  liftBounds[i]= adaptedLiftBound;
1173  liftBound= adaptedLiftBound;
1174  henselLiftResume (buf, result, degree (buf) + 1, liftBound,
1175  Pi, diophant, Mat, MOD);
1176  }
1177  else
1178  {
1179  liftBounds[i]= adaptedLiftBound;
1180  }
1181  }
1182  else if (smallFactorDeg < degree (buf) + 1)
1183  {
1184  result= henselLift (bufEval, result, MOD, diophant, Pi, Mat,
1185  liftBounds[i - 1], smallFactorDeg);
1186 
1187  if (Aeval.length() == i + 1)
1188  {
1189  if (!extension)
1190  earlyFactors= earlyFactorDetect
1191  (buf, result, adaptedLiftBound, earlySuccess,
1192  smallFactorDeg, MOD, liftBound);
1193  else
1194  earlyFactors= extEarlyFactorDetect
1195  (buf, result, adaptedLiftBound, earlySuccess,
1196  info, evaluation, smallFactorDeg, MOD, liftBound);
1197  }
1198  else
1199  {
1200  if (!extension)
1201  adaptedLiftBound= liftBoundAdaption
1202  (buf, result, earlySuccess,
1203  smallFactorDeg, MOD, liftBound);
1204  else
1205  adaptedLiftBound= extLiftBoundAdaption
1206  (buf, result, earlySuccess, info, evaluation,
1207  smallFactorDeg, MOD, liftBound);
1208  }
1209 
1210  if (!earlySuccess)
1211  {
1212  result.insert (LC (buf, 1));
1213  henselLiftResume (buf, result, smallFactorDeg,
1214  degree (buf) + 1, Pi, diophant, Mat, MOD);
1215  if (Aeval.length() == i + 1)
1216  {
1217  if (!extension)
1218  earlyFactors= earlyFactorDetect
1219  (buf, result, adaptedLiftBound, earlySuccess,
1220  degree (buf) + 1, MOD, liftBound);
1221  else
1222  earlyFactors= extEarlyFactorDetect
1223  (buf, result, adaptedLiftBound, earlySuccess,
1224  info, evaluation, degree (buf) + 1, MOD,
1225  liftBound);
1226  }
1227  else
1228  {
1229  if (!extension)
1230  adaptedLiftBound= liftBoundAdaption
1231  (buf, result, earlySuccess, degree
1232  (buf) + 1, MOD, liftBound);
1233  else
1234  adaptedLiftBound= extLiftBoundAdaption
1235  (buf, result, earlySuccess, info, evaluation,
1236  degree (buf) + 1, MOD, liftBound);
1237  }
1238 
1239  if (!earlySuccess)
1240  {
1241  result.insert (LC (buf, 1));
1242  liftBounds[i]= adaptedLiftBound;
1243  liftBound= adaptedLiftBound;
1244  henselLiftResume (buf, result, degree (buf) + 1, liftBound,
1245  Pi, diophant, Mat, MOD);
1246  }
1247  else
1248  liftBounds[i]= adaptedLiftBound;
1249  }
1250  else
1251  liftBounds[i]= adaptedLiftBound;
1252  }
1253  MOD.append (power (Variable (i + 2), liftBounds[i]));
1254  bufEval.removeFirst();
1255  }
1256  bufFactors= result;
1257  }
1258  else
1259  bufFactors= result;
1260 
1261  if (earlySuccess)
1262  A= buf;
1263  return result;
1264 }
Matrix< CanonicalForm > CFMatrix
bool isInExtension() const
getter
T getLast() const
Definition: ftmpl_list.cc:309
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.
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 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 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...
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:1783
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:1850
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:1825

◆ 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 2614 of file facFqFactorize.cc.

2618 {
2619  CFListIterator iter, iter2;
2620  int index;
2621  Variable xx;
2622  CFList vars1;
2623  CFFList sqrfMultiplier= sqrFree (LCmultiplier);
2624  if (sqrfMultiplier.getFirst().factor().inCoeffDomain())
2625  sqrfMultiplier.removeFirst();
2626  sqrfMultiplier= sortCFFListByNumOfVars (sqrfMultiplier);
2627  xx= Variable (2);
2628  for (iter= oldBiFactors; iter.hasItem(); iter++)
2629  vars1.append (power (xx, degree (LC (iter.getItem(),1), xx)));
2630  for (int i= 0; i < lengthAeval; i++)
2631  {
2632  if (oldAeval[i].isEmpty())
2633  continue;
2634  xx= oldAeval[i].getFirst().mvar();
2635  iter2= vars1;
2636  for (iter= oldAeval[i]; iter.hasItem(); iter++, iter2++)
2637  iter2.getItem() *= power (xx, degree (LC (iter.getItem(),1), xx));
2638  }
2639  CanonicalForm tmp, quot1, quot2, quot3;
2640  iter2= vars1;
2641  for (iter= leadingCoeffs[lengthAeval-1]; iter.hasItem(); iter++, iter2++)
2642  {
2643  tmp= iter.getItem()/LCmultiplier;
2644  for (int i=1; i <= tmp.level(); i++)
2645  {
2646  if (degree (tmp,i) > 0 && (degree (iter2.getItem(),i) > degree (tmp,i)))
2647  iter2.getItem() /= power (Variable (i), degree (tmp,i));
2648  }
2649  }
2650  int multi;
2651  for (CFFListIterator ii= sqrfMultiplier; ii.hasItem(); ii++)
2652  {
2653  multi= 0;
2654  for (iter= vars1; iter.hasItem(); iter++)
2655  {
2656  tmp= iter.getItem();
2657  while (fdivides (myGetVars (ii.getItem().factor()), tmp))
2658  {
2659  multi++;
2660  tmp /= myGetVars (ii.getItem().factor());
2661  }
2662  }
2663  if (multi == ii.getItem().exp())
2664  {
2665  index= 1;
2666  for (iter= vars1; iter.hasItem(); iter++, index++)
2667  {
2668  while (fdivides (myGetVars (ii.getItem().factor()), iter.getItem()))
2669  {
2670  int index2= 1;
2671  for (iter2= leadingCoeffs[lengthAeval-1]; iter2.hasItem();iter2++,
2672  index2++)
2673  {
2674  if (index2 == index)
2675  continue;
2676  else
2677  {
2678  tmp= ii.getItem().factor();
2679  if (fdivides (tmp, iter2.getItem(), quot1))
2680  {
2681  CFListIterator iter3= evaluation;
2682  for (int jj= A.level(); jj > 2; jj--, iter3++)
2683  tmp= tmp (iter3.getItem(), jj);
2684  if (!tmp.inCoeffDomain())
2685  {
2686  int index3= 1;
2687  for (iter3= biFactors; iter3.hasItem(); iter3++, index3++)
2688  {
2689  if (index3 == index2)
2690  {
2691  if (fdivides (tmp, iter3.getItem(), quot2))
2692  {
2693  if (fdivides (ii.getItem().factor(), A, quot3))
2694  {
2695  A = quot3;
2696  iter2.getItem() = quot2;
2697  iter3.getItem() = quot3;
2698  iter3.getItem() /= Lc (iter3.getItem());
2699  break;
2700  }
2701  }
2702  }
2703  }
2704  }
2705  }
2706  }
2707  }
2708  iter.getItem() /= getVars (ii.getItem().factor());
2709  }
2710  }
2711  }
2712  else
2713  {
2714  index= 1;
2715  for (iter= vars1; iter.hasItem(); iter++, index++)
2716  {
2717  if (!fdivides (myGetVars (ii.getItem().factor()), iter.getItem()))
2718  {
2719  int index2= 1;
2720  for (iter2= leadingCoeffs[lengthAeval-1];iter2.hasItem();iter2++,
2721  index2++)
2722  {
2723  if (index2 == index)
2724  {
2725  tmp= power (ii.getItem().factor(), ii.getItem().exp());
2726  if (fdivides (tmp, A, quot1))
2727  {
2728  if (fdivides (tmp, iter2.getItem()))
2729  {
2730  CFListIterator iter3= evaluation;
2731  for (int jj= A.level(); jj > 2; jj--, iter3++)
2732  tmp= tmp (iter3.getItem(), jj);
2733  if (!tmp.inCoeffDomain())
2734  {
2735  int index3= 1;
2736  for (iter3= biFactors; iter3.hasItem(); iter3++, index3++)
2737  {
2738  if (index3 == index2)
2739  {
2740  if (fdivides (tmp, iter3.getItem(), quot3))
2741  {
2742  A = quot1;
2743  iter2.getItem() = quot2;
2744  iter3.getItem() = quot3;
2745  iter3.getItem() /= Lc (iter3.getItem());
2746  break;
2747  }
2748  }
2749  }
2750  }
2751  }
2752  }
2753  }
2754  }
2755  }
2756  }
2757  }
2758  }
2759 }
CanonicalForm getVars(const CanonicalForm &f)
CanonicalForm getVars ( const CanonicalForm & f )
Definition: cf_ops.cc:350
CFFList FACTORY_PUBLIC sqrFree(const CanonicalForm &f, bool sort=false)
squarefree factorization
Definition: cf_factor.cc:946
CFFList sortCFFListByNumOfVars(CFFList &F)
sort CFFList by the number variables in a factor
CanonicalForm myGetVars(const CanonicalForm &F)
like getVars but including multiplicities
static int index(p_Length length, p_Ord ord)
Definition: p_Procs_Impl.h:592

◆ 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 2778 of file facFqFactorize.cc.

2781 {
2782  CanonicalForm cont;
2783  int index= 1;
2784  CFListIterator iter2;
2785  for (CFListIterator iter= factors; iter.hasItem(); iter++, index++)
2786  {
2787  cont= content (iter.getItem(), 1);
2788  cont= gcd (cont, LCmultiplier);
2789  contents.append (cont);
2790  if (cont.inCoeffDomain()) // trivial content->LCmultiplier needs to go there
2791  {
2792  foundTrueMultiplier= true;
2793  int index2= 1;
2794  for (iter2= leadingCoeffs; iter2.hasItem(); iter2++, index2++)
2795  {
2796  if (index2 == index)
2797  continue;
2798  iter2.getItem() /= LCmultiplier;
2799  }
2800  break;
2801  }
2802  else
2803  LCs.append (LC (iter.getItem()/cont, 1));
2804  }
2805 }

◆ 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 2808 of file facFqFactorize.cc.

2812 {
2813  int index= 1;
2814  CFListIterator iter, iter2= factors;
2815  for (iter= contents; iter.hasItem(); iter++, iter2++, index++)
2816  {
2817  if (fdivides (iter.getItem(), LCmultiplier))
2818  {
2819  if ((LCmultiplier/iter.getItem()).inCoeffDomain() &&
2820  !isOnlyLeadingCoeff(iter2.getItem())) //content divides LCmultiplier completely and factor consists of more terms than just the leading coeff
2821  {
2822  Variable xx= Variable (2);
2823  CanonicalForm vars;
2824  vars= power (xx, degree (LC (getItem(oldBiFactors, index),1),
2825  xx));
2826  for (int i= 0; i < lengthAeval; i++)
2827  {
2828  if (oldAeval[i].isEmpty())
2829  continue;
2830  xx= oldAeval[i].getFirst().mvar();
2831  vars *= power (xx, degree (LC (getItem(oldAeval[i], index),1),
2832  xx));
2833  }
2834  if (vars.level() <= 2)
2835  {
2836  int index2= 1;
2837  for (CFListIterator iter3= leadingCoeffs[lengthAeval-1];
2838  iter3.hasItem(); iter3++, index2++)
2839  {
2840  if (index2 == index)
2841  {
2842  iter3.getItem() /= LCmultiplier;
2843  break;
2844  }
2845  }
2846  A /= LCmultiplier;
2847  foundMultiplier= true;
2848  iter.getItem()= 1;
2849  }
2850  }
2851  }
2852  }
2853 }
bool isOnlyLeadingCoeff(const CanonicalForm &F)
check if F consists of more than just the leading coeff wrt. Variable (1)

◆ 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 2856 of file facFqFactorize.cc.

2861 {
2862  int index=1;
2863  CFListIterator iter, iter2= factors;
2864  for (iter= contents; iter.hasItem(); iter++, iter2++, index++)
2865  {
2866  if (!iter.getItem().isOne() &&
2867  fdivides (iter.getItem(), LCmultiplier))
2868  {
2869  if (!isOnlyLeadingCoeff (iter2.getItem())) // factor is more than just leading coeff
2870  {
2871  int index2= 1;
2872  for (iter2= leadingCoeffs[lengthAeval-1]; iter2.hasItem();
2873  iter2++, index2++)
2874  {
2875  if (index2 == index)
2876  {
2877  iter2.getItem() /= iter.getItem();
2878  foundMultiplier= true;
2879  break;
2880  }
2881  }
2882  A /= iter.getItem();
2883  LCmultiplier /= iter.getItem();
2884  iter.getItem()= 1;
2885  }
2886  else if (fdivides (getVars (LCmultiplier), testVars))//factor consists of just leading coeff
2887  {
2888  Variable xx= Variable (2);
2889  CanonicalForm vars;
2890  vars= power (xx, degree (LC (getItem(oldBiFactors, index),1),
2891  xx));
2892  for (int i= 0; i < lengthAeval; i++)
2893  {
2894  if (oldAeval[i].isEmpty())
2895  continue;
2896  xx= oldAeval[i].getFirst().mvar();
2897  vars *= power (xx, degree (LC (getItem(oldAeval[i], index),1),
2898  xx));
2899  }
2900  if (myGetVars(content(getItem(leadingCoeffs[lengthAeval-1],index),1))
2901  /myGetVars (LCmultiplier) == vars)
2902  {
2903  int index2= 1;
2904  for (iter2= leadingCoeffs[lengthAeval-1]; iter2.hasItem();
2905  iter2++, index2++)
2906  {
2907  if (index2 == index)
2908  {
2909  iter2.getItem() /= LCmultiplier;
2910  foundMultiplier= true;
2911  break;
2912  }
2913  }
2914  A /= LCmultiplier;
2915  iter.getItem()= 1;
2916  }
2917  }
2918  }
2919  }
2920 }

◆ 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 2762 of file facFqFactorize.cc.

2765 {
2766  CanonicalForm pLCs= prod (LCs);
2767  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
2768  {
2769  A= oldA;
2770  CFListIterator iter2= leadingCoeffs;
2771  for (CFListIterator iter= contents; iter.hasItem(); iter++, iter2++)
2772  iter2.getItem() /= iter.getItem();
2773  foundTrueMultiplier= true;
2774  }
2775 }

◆ 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 965 of file facFqFactorize.cc.

966 {
967  int i= A.level();
969  contentAi.append (content (buf, i));
970  buf /= contentAi.getLast();
971  contentAi.append (content (buf, i - 1));
972  CanonicalForm result= lcm (contentAi.getFirst(), contentAi.getLast());
973  for (i= i - 2; i > 0; i--)
974  {
975  contentAi.append (content (buf, i));
976  buf /= contentAi.getLast();
977  result= lcm (result, contentAi.getLast());
978  }
979  return result;
980 }
int lcm(unsigned long *l, unsigned long *a, unsigned long *b, unsigned long p, int dega, int degb)
Definition: minpoly.cc:709

◆ 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 447 of file facFqFactorize.cc.

449 {
450  int adaptedLiftBound= 0;
451  CanonicalForm buf= F;
452  Variable y= F.mvar();
453  Variable x= Variable (1);
454  CanonicalForm LCBuf= LC (buf, x);
455  CanonicalForm g, quot;
456  CFList M= MOD;
457  M.append (power (y, deg));
458  int d= bound;
459  int e= 0;
460  int nBuf;
461  for (CFListIterator i= factors; i.hasItem(); i++)
462  {
463  g= mulMod (i.getItem(), LCBuf, M);
464  g /= myContent (g);
465  if (fdivides (g, buf, quot))
466  {
467  nBuf= degree (g, y) + degree (LC (g, 1), y);
468  d -= nBuf;
469  e= tmax (e, nBuf);
470  buf= quot;
471  LCBuf= LC (buf, x);
472  }
473  }
474  adaptedLiftBound= d;
475 
476  if (adaptedLiftBound < deg)
477  {
478  if (adaptedLiftBound < degree (F) + 1)
479  {
480  if (d == 1)
481  {
482  if (e + 1 > deg)
483  {
484  adaptedLiftBound= deg;
485  success= false;
486  }
487  else
488  {
489  success= true;
490  if (e + 1 < degree (F) + 1)
491  adaptedLiftBound= deg;
492  else
493  adaptedLiftBound= e + 1;
494  }
495  }
496  else
497  {
498  success= true;
499  adaptedLiftBound= deg;
500  }
501  }
502  else
503  {
504  success= true;
505  }
506  }
507  return adaptedLiftBound;
508 }

◆ listGCD()

static CanonicalForm listGCD ( const CFList L)
inlinestatic

Definition at line 74 of file facFqFactorize.cc.

75 {
76  if (L.length() == 0)
77  return 0;
78  if (L.length() == 1)
79  return L.getFirst();
80  if (L.length() == 2)
81  return gcd (L.getFirst(), L.getLast());
82  else
83  {
84  CFList lHi, lLo;
85  CanonicalForm resultHi, resultLo;
86  int length= L.length()/2;
87  int j= 0;
88  for (CFListIterator i= L; j < length; i++, j++)
89  lHi.append (i.getItem());
90  lLo= Difference (L, lHi);
91  resultHi= listGCD (lHi);
92  resultLo= listGCD (lLo);
93  if (resultHi.isOne() || resultLo.isOne())
94  return 1;
95  return gcd (resultHi, resultLo);
96  }
97 }
static CanonicalForm listGCD(const CFList &L)

◆ multiFactorize()

CFList multiFactorize ( const CanonicalForm F,
const ExtensionInfo info 
)

Definition at line 2928 of file facFqFactorize.cc.

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

◆ 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 133 of file facFqFactorize.cc.

134 {
135  int n= F.level();
136  int * degsf= NEW_ARRAY(int,n + 1);
137  int ** swap= new int* [n + 1];
138  for (int i= 0; i <= n; i++)
139  {
140  degsf[i]= 0;
141  swap [i]= new int [3];
142  swap [i] [0]= 0;
143  swap [i] [1]= 0;
144  swap [i] [2]= 0;
145  }
146  int i= 1;
147  n= 1;
148  degsf= degrees (F, degsf);
149 
151  while ( i <= F.level() )
152  {
153  while( degsf[i] == 0 ) i++;
154  swap[n][0]= i;
155  swap[n][1]= size (LC (F,i));
156  swap[n][2]= degsf [i];
157  if (i != n)
159  n++; i++;
160  }
161 
162  int buf1, buf2, buf3;
163  n--;
164 
165  for (i= 1; i < n; i++)
166  {
167  for (int j= 1; j < n - i + 1; j++)
168  {
169  if (swap[j][1] > swap[j + 1][1])
170  {
171  buf1= swap [j + 1] [0];
172  buf2= swap [j + 1] [1];
173  buf3= swap [j + 1] [2];
174  swap[j + 1] [0]= swap[j] [0];
175  swap[j + 1] [1]= swap[j] [1];
176  swap[j + 1] [2]= swap[j] [2];
177  swap[j][0]= buf1;
178  swap[j][1]= buf2;
179  swap[j][2]= buf3;
180  result= swapvar (result, Variable (j + 1), Variable (j));
181  }
182  else if (swap[j][1] == swap[j + 1][1] && swap[j][2] < swap[j + 1][2])
183  {
184  buf1= swap [j + 1] [0];
185  buf2= swap [j + 1] [1];
186  buf3= swap [j + 1] [2];
187  swap[j + 1] [0]= swap[j] [0];
188  swap[j + 1] [1]= swap[j] [1];
189  swap[j + 1] [2]= swap[j] [2];
190  swap[j][0]= buf1;
191  swap[j][1]= buf2;
192  swap[j][2]= buf3;
193  result= swapvar (result, Variable (j + 1), Variable (j));
194  }
195  }
196  }
197 
198  for (i= n; i > 0; i--)
199  {
200  if (i != swap[i] [0])
201  N.newpair (Variable (i), Variable (swap[i] [0]));
202  }
203 
204  for (i= F.level(); i >=0 ; i--)
205  delete [] swap[i];
206  delete [] swap;
207 
209 
210  return result;
211 }
int size(const CanonicalForm &f, const Variable &v)
int size ( const CanonicalForm & f, const Variable & v )
Definition: cf_ops.cc:600
int * degrees(const CanonicalForm &f, int *degs=0)
int * degrees ( const CanonicalForm & f, int * degs )
Definition: cf_ops.cc:493
int * degsf
Definition: cfEzgcd.cc:59
#define DELETE_ARRAY(P)
Definition: cf_defs.h:64
#define NEW_ARRAY(T, N)
Definition: cf_defs.h:63
CanonicalForm buf1
Definition: facFqBivar.cc:73

◆ myContent() [1/2]

static CanonicalForm myContent ( const CanonicalForm F)
inlinestatic

Definition at line 58 of file facFqFactorize.cc.

59 {
60  Variable x= Variable (1);
61  CanonicalForm G= swapvar (F, F.mvar(), x);
62  CFList L;
63  for (CFIterator i= G; i.hasTerms(); i++)
64  L.append (i.coeff());
65  if (L.length() == 2)
66  return swapvar (gcd (L.getFirst(), L.getLast()), F.mvar(), x);
67  if (L.length() == 1)
68  return LC (F, x);
69  return swapvar (listGCD (L), F.mvar(), x);
70 }
class to iterate through CanonicalForm's
Definition: cf_iter.h:44
STATIC_VAR TreeM * G
Definition: janet.cc:31

◆ myContent() [2/2]

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

Definition at line 101 of file facFqFactorize.cc.

102 {
103  if (degree (F, x) <= 0)
104  return 1;
105  CanonicalForm G= F;
106  bool swap= false;
107  if (x != F.mvar())
108  {
109  swap= true;
110  G= swapvar (F, x, F.mvar());
111  }
112  CFList L;
113  Variable alpha;
114  for (CFIterator i= G; i.hasTerms(); i++)
115  L.append (i.coeff());
116  if (L.length() == 2)
117  {
118  if (swap)
119  return swapvar (gcd (L.getFirst(), L.getLast()), F.mvar(), x);
120  else
121  return gcd (L.getFirst(), L.getLast());
122  }
123  if (L.length() == 1)
124  {
125  return LC (F, x);
126  }
127  if (swap)
128  return swapvar (listGCD (L), F.mvar(), x);
129  else
130  return listGCD (L);
131 }

◆ newMainVariableSearch()

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

Definition at line 924 of file facFqFactorize.cc.

928 {
929  Variable x= Variable (1);
930  CanonicalForm derivI, buf;
931  bool GF= (CFFactory::gettype() == GaloisFieldDomain);
932  int swapLevel= 0;
933  CFList list;
934  bool fail= false;
935  buf= A;
936  Aeval= CFList();
937  evaluation= CFList();
938  for (int i= lev; i <= A.level(); i++)
939  {
940  derivI= deriv (buf, Variable (i));
941  if (!derivI.isZero())
942  {
943  g= gcd (buf, derivI);
944  if (degree (g) > 0)
945  return -1;
946 
947  buf= swapvar (buf, x, Variable (i));
948  Aeval= CFList();
949  evaluation= CFList();
950  fail= false;
951  evaluation= evalPoints (buf, Aeval, alpha, list, GF, fail);
952  if (!fail)
953  {
954  A= buf;
955  swapLevel= i;
956  break;
957  }
958  else
959  buf= A;
960  }
961  }
962  return swapLevel;
963 }

◆ 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 1478 of file facFqFactorize.cc.

1483 {
1484  y= Variable (1);
1485  if (LCF.inCoeffDomain())
1486  {
1487  CFList result;
1488  for (int i= 1; i <= LCFFactors.length() + 1; i++)
1489  result.append (1);
1490  return result;
1491  }
1492 
1493  CFMap N, M;
1494  CFArray dummy= CFArray (2);
1495  dummy [0]= LCF;
1496  dummy [1]= Variable (2);
1497  compress (dummy, M, N);
1498  CanonicalForm F= M (LCF);
1499  if (LCF.isUnivariate())
1500  {
1501  CFList result;
1502  int LCFLevel= LCF.level();
1503  bool found= false;
1504  if (LCFLevel == 2)
1505  {
1506  //bivariate leading coefficients are already the true leading coefficients
1507  result= LCFFactors;
1508  found= true;
1509  }
1510  else
1511  {
1512  CFListIterator j;
1513  for (int i= 0; i < lSecondVarLCs; i++)
1514  {
1515  for (j= differentSecondVarLCs[i]; j.hasItem(); j++)
1516  {
1517  if (j.getItem().level() == LCFLevel)
1518  {
1519  found= true;
1520  break;
1521  }
1522  }
1523  if (found)
1524  {
1525  result= differentSecondVarLCs [i];
1526  break;
1527  }
1528  }
1529  if (!found)
1530  result= LCFFactors;
1531  }
1532  if (found)
1533  result.insert (Lc (LCF));
1534  else
1535  result.insert (LCF);
1536 
1537  return result;
1538  }
1539 
1540  CFList factors= LCFFactors;
1541 
1542  for (CFListIterator i= factors; i.hasItem(); i++)
1543  i.getItem()= M (i.getItem());
1544 
1545  CanonicalForm sqrfPartF;
1546  CFFList * bufSqrfFactors= new CFFList [factors.length()];
1547  CFList evalSqrfPartF, bufFactors;
1548  CFArray evalPoint= CFArray (evaluation.length() - 1);
1549  CFArray buf= CFArray (evaluation.length());
1550  CFArray swap= CFArray (evaluation.length());
1552  CanonicalForm vars=getVars (LCF)*Variable (2);
1553  for (int i= evaluation.length() +1; i > 1; i--, iter++)
1554  {
1555  buf[i-2]=iter.getItem();
1556  if (degree (vars, i) > 0)
1557  swap[M(Variable (i)).level()-1]=buf[i-2];
1558  }
1559  buf= swap;
1560  for (int i= 0; i < evaluation.length() - 1; i++)
1561  evalPoint[i]= buf[i+1];
1562 
1563  int pass= testFactors (F, factors, alpha, sqrfPartF,
1564  bufFactors, bufSqrfFactors, evalSqrfPartF, evalPoint);
1565 
1566  bool foundDifferent= false;
1567  Variable z, x= y;
1568  int j= 0;
1569  if (!pass)
1570  {
1571  int lev= 0;
1572  // LCF is non-constant here
1573  CFList bufBufFactors;
1574  CanonicalForm bufF;
1575  for (int i= 0; i < lSecondVarLCs; i++)
1576  {
1577  if (!differentSecondVarLCs [i].isEmpty())
1578  {
1579  bool allConstant= true;
1580  for (iter= differentSecondVarLCs[i]; iter.hasItem(); iter++)
1581  {
1582  if (!iter.getItem().inCoeffDomain())
1583  {
1584  allConstant= false;
1585  y= Variable (iter.getItem().level());
1586  lev= M(y).level();
1587  }
1588  }
1589  if (allConstant)
1590  continue;
1591 
1592  bufFactors= differentSecondVarLCs [i];
1593  for (iter= bufFactors; iter.hasItem(); iter++)
1594  iter.getItem()= swapvar (iter.getItem(), x, y);
1595  bufF= F;
1596  z= Variable (lev);
1597  bufF= swapvar (bufF, x, z);
1598  bufBufFactors= bufFactors;
1599  evalPoint= CFArray (evaluation.length() - 1);
1600  for (int k= 1; k < evaluation.length(); k++)
1601  {
1602  if (N (Variable (k+1)).level() != y.level())
1603  evalPoint[k-1]= buf[k];
1604  else
1605  evalPoint[k-1]= buf[0];
1606  }
1607  pass= testFactors (bufF, bufBufFactors, alpha, sqrfPartF, bufFactors,
1608  bufSqrfFactors, evalSqrfPartF, evalPoint);
1609  if (pass)
1610  {
1611  foundDifferent= true;
1612  F= bufF;
1613  CFList l= factors;
1614  for (iter= l; iter.hasItem(); iter++)
1615  iter.getItem()= swapvar (iter.getItem(), x, y);
1616  differentSecondVarLCs [i]= l;
1617  j= i;
1618  break;
1619  }
1620  if (!pass && i == lSecondVarLCs - 1)
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  }
1632  }
1633  }
1634  if (!pass)
1635  {
1636  CFList result;
1637  result.append (LCF);
1638  for (int j= 1; j <= factors.length(); j++)
1639  result.append (1);
1640  result= distributeContent (result, differentSecondVarLCs, lSecondVarLCs);
1641  y= Variable (1);
1642  delete [] bufSqrfFactors;
1643  return result;
1644  }
1645  else
1646  factors= bufFactors;
1647 
1648  bufFactors= factors;
1649 
1650  CFMap MM, NN;
1651  dummy [0]= sqrfPartF;
1652  dummy [1]= 1;
1653  compress (dummy, MM, NN);
1654  sqrfPartF= MM (sqrfPartF);
1655  CanonicalForm varsSqrfPartF= getVars (sqrfPartF);
1656  for (CFListIterator iter= factors; iter.hasItem(); iter++)
1657  iter.getItem()= MM (iter.getItem());
1658 
1659  CFList evaluation2;
1660  for (int i= 2; i <= varsSqrfPartF.level(); i++)
1661  evaluation2.insert (evalPoint[NN (Variable (i)).level()-2]);
1662 
1663  CFList interMedResult;
1664  CanonicalForm oldSqrfPartF= sqrfPartF;
1665  sqrfPartF= shift2Zero (sqrfPartF, evalSqrfPartF, evaluation2);
1666  if (factors.length() > 1)
1667  {
1668  CanonicalForm LC1= LC (oldSqrfPartF, 1);
1669  CFList leadingCoeffs;
1670  for (int i= 0; i < factors.length(); i++)
1671  leadingCoeffs.append (LC1);
1672 
1673  CFList LC1eval= evaluateAtEval (LC1, evaluation2, 2);
1674  CFList oldFactors= factors;
1675  for (CFListIterator i= oldFactors; i.hasItem(); i++)
1676  i.getItem() *= LC1eval.getFirst()/Lc (i.getItem());
1677 
1678  bool success= false;
1679  CanonicalForm oldSqrfPartFPowLC= oldSqrfPartF*power(LC1,factors.length()-1);
1680  CFList heuResult;
1681  if (size (oldSqrfPartFPowLC)/getNumVars (oldSqrfPartFPowLC) < 500 &&
1682  LucksWangSparseHeuristic (oldSqrfPartFPowLC,
1683  oldFactors, 2, leadingCoeffs, heuResult))
1684  {
1685  interMedResult= recoverFactors (oldSqrfPartF, heuResult);
1686  if (oldFactors.length() == interMedResult.length())
1687  success= true;
1688  }
1689  if (!success)
1690  {
1691  LC1= LC (evalSqrfPartF.getFirst(), 1);
1692 
1693  CFArray leadingCoeffs= CFArray (factors.length());
1694  for (int i= 0; i < factors.length(); i++)
1695  leadingCoeffs[i]= LC1;
1696 
1697  for (CFListIterator i= factors; i.hasItem(); i++)
1698  i.getItem() *= LC1 (0,2)/Lc (i.getItem());
1699  factors.insert (1);
1700 
1702  newSqrfPartF= evalSqrfPartF.getFirst()*power (LC1, factors.length() - 2);
1703 
1704  int liftBound= degree (newSqrfPartF,2) + 1;
1705 
1706  CFMatrix M= CFMatrix (liftBound, factors.length() - 1);
1707  CFArray Pi;
1708  CFList diophant;
1709  nonMonicHenselLift12 (newSqrfPartF, factors, liftBound, Pi, diophant, M,
1710  leadingCoeffs, false);
1711 
1712  if (sqrfPartF.level() > 2)
1713  {
1714  int* liftBounds= new int [sqrfPartF.level() - 1];
1715  bool noOneToOne= false;
1716  CFList *leadingCoeffs2= new CFList [sqrfPartF.level()-2];
1717  LC1= LC (evalSqrfPartF.getLast(), 1);
1718  CFList LCs;
1719  for (int i= 0; i < factors.length(); i++)
1720  LCs.append (LC1);
1721  leadingCoeffs2 [sqrfPartF.level() - 3]= LCs;
1722  for (int i= sqrfPartF.level() - 1; i > 2; i--)
1723  {
1724  for (CFListIterator j= LCs; j.hasItem(); j++)
1725  j.getItem()= j.getItem() (0, i + 1);
1726  leadingCoeffs2 [i - 3]= LCs;
1727  }
1728  sqrfPartF *= power (LC1, factors.length()-1);
1729 
1730  int liftBoundsLength= sqrfPartF.level() - 1;
1731  for (int i= 0; i < liftBoundsLength; i++)
1732  liftBounds [i]= degree (sqrfPartF, i + 2) + 1;
1733  evalSqrfPartF= evaluateAtZero (sqrfPartF);
1734  evalSqrfPartF.removeFirst();
1735  factors= nonMonicHenselLift (evalSqrfPartF, factors, leadingCoeffs2,
1736  diophant, Pi, liftBounds, sqrfPartF.level() - 1, noOneToOne);
1737  delete [] leadingCoeffs2;
1738  delete [] liftBounds;
1739  }
1740  for (CFListIterator iter= factors; iter.hasItem(); iter++)
1741  iter.getItem()= reverseShift (iter.getItem(), evaluation2);
1742 
1743  interMedResult=
1744  recoverFactors (reverseShift(evalSqrfPartF.getLast(),evaluation2),
1745  factors);
1746  }
1747  }
1748  else
1749  {
1750  CanonicalForm contF=content (oldSqrfPartF,1);
1751  factors= CFList (oldSqrfPartF/contF);
1752  interMedResult= recoverFactors (oldSqrfPartF, factors);
1753  }
1754 
1755  for (CFListIterator iter= interMedResult; iter.hasItem(); iter++)
1756  iter.getItem()= NN (iter.getItem());
1757 
1758  CFList result;
1760  for (int i= 0; i < LCFFactors.length(); i++)
1761  {
1762  CanonicalForm tmp= 1;
1763  for (k= bufSqrfFactors[i]; k.hasItem(); k++)
1764  {
1765  int pos= findItem (bufFactors, k.getItem().factor());
1766  if (pos)
1767  tmp *= power (getItem (interMedResult, pos), k.getItem().exp());
1768  }
1769  result.append (tmp);
1770  }
1771 
1772  for (CFListIterator i= result; i.hasItem(); i++)
1773  {
1774  F /= i.getItem();
1775  if (foundDifferent)
1776  i.getItem()= swapvar (i.getItem(), x, z);
1777  i.getItem()= N (i.getItem());
1778  }
1779 
1780  if (foundDifferent)
1781  {
1782  CFList l= differentSecondVarLCs [j];
1783  for (CFListIterator i= l; i.hasItem(); i++)
1784  i.getItem()= swapvar (i.getItem(), y, z);
1785  differentSecondVarLCs [j]= l;
1786  F= swapvar (F, x, z);
1787  }
1788 
1789  result.insert (N (F));
1790 
1791  result= distributeContent (result, differentSecondVarLCs, lSecondVarLCs);
1792 
1793  if (!result.getFirst().inCoeffDomain())
1794  {
1795  // prepare input for recursion
1796  if (foundDifferent)
1797  {
1798  for (CFListIterator i= result; i.hasItem(); i++)
1799  i.getItem()= swapvar (i.getItem(), Variable (2), y);
1800  CFList l= differentSecondVarLCs [j];
1801  for (CFListIterator i= l; i.hasItem(); i++)
1802  i.getItem()= swapvar (i.getItem(), y, z);
1803  differentSecondVarLCs [j]= l;
1804  }
1805 
1806  F= result.getFirst();
1807  int level= 0;
1808  if (foundDifferent)
1809  {
1810  level= y.level() - 2;
1811  for (int i= y.level(); i > 1; i--)
1812  {
1813  if (degree (F,i) > 0)
1814  {
1815  if (y.level() == 3)
1816  level= 0;
1817  else
1818  level= i-3;
1819  }
1820  }
1821  }
1822 lcretry:
1823  if (lSecondVarLCs - level > 0)
1824  {
1825  CFList evaluation2= evaluation;
1826  int j= lSecondVarLCs+2;
1828  CFListIterator i;
1829  for (i= evaluation2; i.hasItem(); i++, j--)
1830  {
1831  if (j==y.level())
1832  {
1833  swap= i.getItem();
1834  i.getItem()= evaluation2.getLast();
1835  evaluation2.removeLast();
1836  evaluation2.append (swap);
1837  }
1838  }
1839 
1840  CFList newLCs= differentSecondVarLCs[level];
1841  if (newLCs.isEmpty())
1842  {
1843  if (degree (F, level+3) > 0)
1844  {
1845  delete [] bufSqrfFactors;
1846  return result; //TODO handle this case
1847  }
1848  level=level+1;
1849  goto lcretry;
1850  }
1851  i= newLCs;
1853  iter++;
1854  CanonicalForm quot;
1855  for (;iter.hasItem(); iter++, i++)
1856  {
1857  swap= iter.getItem();
1858  if (degree (swap, level+3) > 0)
1859  {
1860  int count= evaluation.length()+1;
1861  for (CFListIterator iter2= evaluation2; iter2.hasItem(); iter2++,
1862  count--)
1863  {
1864  if (count != level+3)
1865  swap= swap (iter2.getItem(), count);
1866  }
1867  if (fdivides (swap, i.getItem(), quot))
1868  i.getItem()= quot;
1869  }
1870  }
1871  CFList * differentSecondVarLCs2= new CFList [lSecondVarLCs - level - 1];
1872  for (int j= level+1; j < lSecondVarLCs; j++)
1873  {
1874  if (degree (F, j+3) > 0)
1875  {
1876  if (!differentSecondVarLCs[j].isEmpty())
1877  {
1878  differentSecondVarLCs2[j - level - 1]= differentSecondVarLCs[j];
1879  i= differentSecondVarLCs2[j-level - 1];
1880  iter=result;
1881  iter++;
1882  for (;iter.hasItem(); iter++, i++)
1883  {
1884  swap= iter.getItem();
1885  if (degree (swap, j+3) > 0)
1886  {
1887  int count= evaluation.length()+1;
1888  for (CFListIterator iter2= evaluation2; iter2.hasItem();iter2++,
1889  count--)
1890  {
1891  if (count != j+3)
1892  swap= swap (iter2.getItem(), count);
1893  }
1894  if (fdivides (swap, i.getItem(), quot))
1895  i.getItem()= quot;
1896  }
1897  }
1898  }
1899  }
1900  }
1901 
1902  for (int j= 0; j < level+1; j++)
1903  evaluation2.removeLast();
1904  Variable dummyvar= Variable (1);
1905 
1906  CanonicalForm newLCF= result.getFirst();
1907  newLCF=swapvar (newLCF, Variable (2), Variable (level+3));
1908  for (i=newLCs; i.hasItem(); i++)
1909  i.getItem()= swapvar (i.getItem(), Variable (2), Variable (level+3));
1910  for (int j= 1; j < lSecondVarLCs-level;j++)
1911  {
1912  for (i= differentSecondVarLCs2[j-1]; i.hasItem(); i++)
1913  i.getItem()= swapvar (i.getItem(), Variable (2+j),
1914  Variable (level+3+j));
1915  newLCF= swapvar (newLCF, Variable (2+j), Variable (level+3+j));
1916  }
1917 
1918  CFList recursiveResult=
1919  precomputeLeadingCoeff (newLCF, newLCs, alpha, evaluation2,
1920  differentSecondVarLCs2, lSecondVarLCs - level - 1,
1921  dummyvar);
1922 
1923  if (dummyvar.level() != 1)
1924  {
1925  for (i= recursiveResult; i.hasItem(); i++)
1926  i.getItem()= swapvar (i.getItem(), Variable (2), dummyvar);
1927  }
1928  for (i= recursiveResult; i.hasItem(); i++)
1929  {
1930  for (int j= lSecondVarLCs-level-1; j > 0; j--)
1931  i.getItem()=swapvar (i.getItem(), Variable (2+j),
1932  Variable (level+3+j));
1933  i.getItem()= swapvar (i.getItem(), Variable (2), Variable (level+3));
1934  }
1935 
1936  if (recursiveResult.getFirst() == result.getFirst())
1937  {
1938  delete [] bufSqrfFactors;
1939  delete [] differentSecondVarLCs2;
1940  return result;
1941  }
1942  else
1943  {
1944  iter=recursiveResult;
1945  i= result;
1946  i.getItem()= iter.getItem();
1947  i++;
1948  iter++;
1949  for (; i.hasItem(); i++, iter++)
1950  i.getItem() *= iter.getItem();
1951  delete [] differentSecondVarLCs2;
1952  }
1953  }
1954  }
1955  else
1956  y= Variable (1);
1957 
1958  delete [] bufSqrfFactors;
1959 
1960  return result;
1961 }
int getNumVars(const CanonicalForm &f)
int getNumVars ( const CanonicalForm & f )
Definition: cf_ops.cc:314
CanonicalForm compress(const CanonicalForm &f, CFMap &m)
CanonicalForm compress ( const CanonicalForm & f, CFMap & m )
Definition: cf_map.cc:210
bool isUnivariate() const
void removeLast()
Definition: ftmpl_list.cc:317
bool found
Definition: facFactorize.cc:55
CFList evaluateAtZero(const CanonicalForm &F)
evaluate F successively n-2 at 0
CFList evaluateAtEval(const CanonicalForm &F, const CFArray &eval)
evaluate F at evaluation
int testFactors(const CanonicalForm &G, const CFList &uniFactors, const Variable &alpha, CanonicalForm &sqrfPartF, CFList &factors, CFFList *&bufSqrfFactors, CFList &evalSqrfPartF, const CFArray &evalPoint)
CFList distributeContent(const CFList &L, const CFList *differentSecondVarFactors, int length)
distribute content
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:2152
int status int void size_t count
Definition: si_signals.h:59

◆ 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 2381 of file facFqFactorize.cc.

2384 {
2385  CFList l= leadingCoeffs;
2386  LCs [n-3]= l;
2387  CFListIterator j;
2389  for (int i= n - 1; i > 2; i--, iter++)
2390  {
2391  for (j= l; j.hasItem(); j++)
2392  j.getItem()= j.getItem() (iter.getItem(), i + 1);
2393  LCs [i - 3]= l;
2394  }
2395  l= LCs [0];
2396  for (CFListIterator i= l; i.hasItem(); i++)
2397  i.getItem()= i.getItem() (iter.getItem(), 3);
2398  CFListIterator ii= biFactors;
2399  CFList normalizeFactor;
2400  for (CFListIterator i= l; i.hasItem(); i++, ii++)
2401  normalizeFactor.append (Lc (LC (ii.getItem(), 1))/Lc (i.getItem()));
2402  for (int i= 0; i < n-2; i++)
2403  {
2404  ii= normalizeFactor;
2405  for (j= LCs [i]; j.hasItem(); j++, ii++)
2406  j.getItem() *= ii.getItem();
2407  }
2408 
2410 
2411  CanonicalForm hh= 1/Lc (Aeval.getFirst());
2412 
2413  for (iter= Aeval; iter.hasItem(); iter++)
2414  iter.getItem() *= hh;
2415 
2416  A *= hh;
2417 }

◆ prodEval()

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

Definition at line 2011 of file facFqFactorize.cc.

2013 {
2014  CanonicalForm result= 1;
2015  for (CFListIterator i= l; i.hasItem(); i++)
2016  result *= i.getItem() (evalPoint, v);
2017  return result;
2018 }

◆ 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 2113 of file facFqFactorize.cc.

2115 {
2116  CFList T, S;
2117 
2118  T= factors1;
2119  CFList result;
2121  int * v= new int [T.length()];
2122  for (int i= 0; i < T.length(); i++)
2123  v[i]= 0;
2124  bool nosubset= false;
2125  CFArray TT;
2126  TT= copy (factors1);
2127  int recombinations= 0;
2128  while (T.length() >= 2*s && s <= thres)
2129  {
2130  while (nosubset == false)
2131  {
2132  if (T.length() == s)
2133  {
2134  delete [] v;
2135  if (recombinations == factors2.length() - 1)
2136  result.append (prod (T));
2137  else
2138  result= Union (result, T);
2139  return result;
2140  }
2141  S= subset (v, s, TT, nosubset);
2142  if (nosubset) break;
2143  buf= prodEval (S, evalPoint, x);
2144  buf /= Lc (buf);
2145  if (find (factors2, buf))
2146  {
2147  recombinations++;
2148  T= Difference (T, S);
2149  result.append (prod (S));
2150  TT= copy (T);
2151  indexUpdate (v, s, T.length(), nosubset);
2152  if (nosubset) break;
2153  }
2154  }
2155  s++;
2156  if (T.length() < 2*s || T.length() == s)
2157  {
2158  if (recombinations == factors2.length() - 1)
2159  result.append (prod (T));
2160  else
2161  result= Union (result, T);
2162  delete [] v;
2163  return result;
2164  }
2165  for (int i= 0; i < T.length(); i++)
2166  v[i]= 0;
2167  nosubset= false;
2168  }
2169 
2170  delete [] v;
2171  if (T.length() < 2*s)
2172  {
2173  result= Union (result, T);
2174  return result;
2175  }
2176 
2177  return result;
2178 }
static CanonicalForm prodEval(const CFList &l, const CanonicalForm &evalPoint, const Variable &v)

◆ 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 2334 of file facFqFactorize.cc.

2337 {
2338  CFListIterator iter, iter2;
2340  int i;
2341  Variable v;
2342  Variable y= Variable (2);
2343  CFList list;
2344  bool leaveLoop= false;
2345  for (int j= 0; j < A.level() - 2; j++)
2346  {
2347  if (Aeval[j].length() == minFactorsLength)
2348  {
2349  i= A.level();
2350 
2351  for (iter= evaluation; iter.hasItem(); iter++, i--)
2352  {
2353  for (iter2= Aeval[j]; iter2.hasItem(); iter2++)
2354  {
2355  if (i == iter2.getItem().level())
2356  {
2357  evalPoint= iter.getItem();
2358  leaveLoop= true;
2359  break;
2360  }
2361  }
2362  if (leaveLoop)
2363  {
2364  leaveLoop= false;
2365  break;
2366  }
2367  }
2368 
2369  v= Variable (i);
2370  list= buildUniFactors (Aeval[j], evalPoint, v);
2371 
2372  biFactors= recombination (biFactors, list, 1,
2373  biFactors.length() - list.length() + 1,
2374  evaluation.getLast(), y);
2375  return;
2376  }
2377  }
2378 }

◆ 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 2250 of file facFqFactorize.cc.

2254 {
2256  int i;
2257  CFListIterator iter, iter2;
2258  Variable v;
2259  CFList LCs, buf;
2260  CFArray l;
2261  int pos, index, checklength;
2262  bool leaveLoop=false;
2263 recurse:
2264  for (int j= 0; j < AevalLength; j++)
2265  {
2266  if (!Aeval[j].isEmpty())
2267  {
2268  i= evaluation.length() + 1;
2269  for (iter= evaluation; iter.hasItem(); iter++, i--)
2270  {
2271  for (iter2= Aeval[j]; iter2.hasItem(); iter2++)
2272  {
2273  if (i == iter2.getItem().level())
2274  {
2275  evalPoint= iter.getItem();
2276  leaveLoop= true;
2277  break;
2278  }
2279  }
2280  if (leaveLoop)
2281  {
2282  leaveLoop= false;
2283  break;
2284  }
2285  }
2286 
2287  v= Variable (i);
2288  if (Aeval[j].length() > uniFactors.length())
2289  Aeval[j]= recombination (Aeval[j], uniFactors, 1,
2290  Aeval[j].length() - uniFactors.length() + 1,
2291  evalPoint, v);
2292 
2293  checklength= biFactors.length();
2294  Aeval[j]= checkOneToOne (Aeval[j], uniFactors, biFactors, evalPoint, v);
2295  if (checklength > biFactors.length())
2296  {
2297  uniFactors= buildUniFactors (biFactors, evaluation.getLast(),
2298  Variable (2));
2299  goto recurse;
2300  }
2301 
2303  l= CFArray (uniFactors.length());
2304  index= 1;
2305  for (iter= buf; iter.hasItem(); iter++, index++)
2306  {
2307  pos= findItem (uniFactors, iter.getItem());
2308  if (pos)
2309  l[pos-1]= getItem (Aeval[j], index);
2310  }
2311  buf= conv (l);
2312  Aeval [j]= buf;
2313 
2315  }
2316  }
2317 }
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...
CFList conv(const CFArray &A)

◆ 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 1384 of file facFqFactorize.cc.

1388 {
1389  CanonicalForm F= G;
1390  CFFList sqrfFactorization;
1391  if (getCharacteristic() > 0)
1392  sqrfFactorization= squarefreeFactorization (F, alpha);
1393  else
1394  sqrfFactorization= sqrFree (F);
1395 
1396  sqrfPartF= 1;
1397  for (CFFListIterator i= sqrfFactorization; i.hasItem(); i++)
1398  sqrfPartF *= i.getItem().factor();
1399 
1400  evalSqrfPartF= evaluateAtEval (sqrfPartF, evalPoint);
1401 
1402  CanonicalForm test= evalSqrfPartF.getFirst() (evalPoint[0], 2);
1403 
1404  if (degree (test) != degree (sqrfPartF, 1) || test.inCoeffDomain())
1405  return 0;
1406 
1407  CFFList sqrfFactors;
1408  CanonicalForm tmp;
1409  CFList tmp2;
1410  int k= 0;
1411  factors= uniFactors;
1413  for (CFListIterator i= factors; i.hasItem(); i++, k++)
1414  {
1415  tmp= 1;
1416  if (getCharacteristic() > 0)
1417  sqrfFactors= squarefreeFactorization (i.getItem(), alpha);
1418  else
1419  sqrfFactors= sqrFree (i.getItem());
1420 
1421  for (iter= sqrfFactors; iter.hasItem(); iter++)
1422  {
1423  tmp2.append (iter.getItem().factor());
1424  tmp *= iter.getItem().factor();
1425  }
1426  i.getItem()= tmp/Lc(tmp);
1427  bufSqrfFactors [k]= sqrfFactors;
1428  }
1429 
1430  for (int i= 0; i < factors.length() - 1; i++)
1431  {
1432  for (k= i + 1; k < factors.length(); k++)
1433  {
1434  gcdFreeBasis (bufSqrfFactors [i], bufSqrfFactors[k]);
1435  }
1436  }
1437 
1438  factors= CFList();
1439  for (int i= 0; i < uniFactors.length(); i++)
1440  {
1441  if (i == 0)
1442  {
1443  for (iter= bufSqrfFactors [i]; iter.hasItem(); iter++)
1444  {
1445  if (iter.getItem().factor().inCoeffDomain())
1446  continue;
1447  iter.getItem()= CFFactor (iter.getItem().factor()/
1448  Lc (iter.getItem().factor()),
1449  iter.getItem().exp());
1450  factors.append (iter.getItem().factor());
1451  }
1452  }
1453  else
1454  {
1455  for (iter= bufSqrfFactors [i]; iter.hasItem(); iter++)
1456  {
1457  if (iter.getItem().factor().inCoeffDomain())
1458  continue;
1459  iter.getItem()= CFFactor (iter.getItem().factor()/
1460  Lc (iter.getItem().factor()),
1461  iter.getItem().exp());
1462  if (!find (factors, iter.getItem().factor()))
1463  factors.append (iter.getItem().factor());
1464  }
1465  }
1466  }
1467 
1468  test= prod (factors);
1469  tmp= evalSqrfPartF.getFirst() (evalPoint[0],2);
1470  if (test/Lc (test) != tmp/Lc (tmp))
1471  return 0;
1472  else
1473  return 1;
1474 }
CanonicalForm test
Definition: cfModGcd.cc:4098
void gcdFreeBasis(CFFList &factors1, CFFList &factors2)
gcd free basis of two lists of factors
CFFList squarefreeFactorization(const CanonicalForm &F, const Variable &alpha)
squarefree factorization over a finite field return a list of squarefree factors with multiplicity

◆ TIMING_DEFINE_PRINT()

TIMING_DEFINE_PRINT ( fac_fq_bi_factorizer  ) const &