My Project
Functions | Variables
facFqFactorize.h File Reference

This file provides functions for factorizing a multivariate polynomial over $ F_{p} $ , $ F_{p}(\alpha ) $ or GF. More...

#include "timing.h"
#include "facFqBivar.h"
#include "DegreePattern.h"
#include "ExtensionInfo.h"
#include "cf_util.h"
#include "facFqSquarefree.h"
#include "facFqBivarUtil.h"

Go to the source code of this file.

Functions

 TIMING_DEFINE_PRINT (fac_fq_squarefree) TIMING_DEFINE_PRINT(fac_fq_factor_squarefree) CFList multiFactorize(const CanonicalForm &F
 Factorization over a finite field. More...
 
CFList FpSqrfFactorize (const CanonicalForm &F)
 factorize a squarefree multivariate polynomial over $ F_{p} $ More...
 
CFList FqSqrfFactorize (const CanonicalForm &F, const Variable &alpha)
 factorize a squarefree multivariate polynomial over $ F_{p} (\alpha ) $ More...
 
CFList GFSqrfFactorize (const CanonicalForm &F)
 factorize a squarefree multivariate polynomial over GF More...
 
CFFList FpFactorize (const CanonicalForm &G, bool substCheck=true)
 factorize a multivariate polynomial over $ F_{p} $ More...
 
CFFList FqFactorize (const CanonicalForm &G, const Variable &alpha, bool substCheck=true)
 factorize a multivariate polynomial over $ F_{p} (\alpha ) $ More...
 
CFFList GFFactorize (const CanonicalForm &G, bool substCheck=true)
 factorize a multivariate polynomial over GF 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...
 
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...
 
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...
 
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...
 
CFList extFactorize (const CanonicalForm &F, const ExtensionInfo &info)
 Factorization over an extension of initial field. More...
 
CanonicalForm lcmContent (const CanonicalForm &A, CFList &contentAi)
 compute the LCM of the contents of A wrt to each variable occuring in A. More...
 
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...
 
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...
 
void refineBiFactors (const CanonicalForm &A, CFList &biFactors, CFList *const &factors, const CFList &evaluation, int minFactorsLength)
 refine a bivariate factorization of A with l factors to one with minFactorsLength if possible More...
 
CFList buildUniFactors (const CFList &biFactors, const CanonicalForm &evalPoint, const Variable &y)
 plug in evalPoint for y in a list of polys 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...
 
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 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 leadingCoeffReconstruction (const CanonicalForm &F, const CFList &factors, const CFList &M)
 obtain factors of F by reconstructing their leading coeffs More...
 
CFList distributeContent (const CFList &L, const CFList *differentSecondVarFactors, int length)
 distribute content More...
 
void gcdFreeBasis (CFFList &factors1, CFFList &factors2)
 gcd free basis of two lists of factors More...
 
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 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...
 

Variables

const ExtensionInfoinfo
 < [in] sqrfree poly More...
 

Detailed Description

This file provides functions for factorizing a multivariate polynomial over $ F_{p} $ , $ F_{p}(\alpha ) $ or GF.

Author
Martin Lee

Definition in file facFqFactorize.h.

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

◆ 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
int gcd(int a, int b)
Definition: walkSupport.cc:836

◆ 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)
int length() const
Definition: ftmpl_list.cc:273

◆ 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 }
Variable x
Definition: cfModGcd.cc:4084
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 List< Variable > Difference(const List< Variable > &, const List< Variable > &)
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
T getFirst() const
Definition: ftmpl_list.cc:279
void removeFirst()
Definition: ftmpl_list.cc:287
void insert(const T &)
Definition: ftmpl_list.cc:193
int isEmpty() const
Definition: ftmpl_list.cc:267
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 
)

Factorization over an extension of initial field.

Returns
extFactorize returns factorization of F over initial field
See also
extBiFactorize(), multiFactorize()

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 }

◆ 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

◆ FpFactorize()

CFFList FpFactorize ( const CanonicalForm G,
bool  substCheck = true 
)
inline

factorize a multivariate polynomial over $ F_{p} $

Returns
FpFactorize returns a list of monic factors with multiplicity, the first element is the leading coefficient.
See also
FqFactorize(), GFFactorize()
Parameters
[in]Ga multivariate poly
[in]substCheckenables substitute check

Definition at line 101 of file facFqFactorize.h.

104 {
105  if (getNumVars (G) == 2)
106  return FpBiFactorize (G, substCheck);
107 
108  CanonicalForm F= G;
109  if (substCheck)
110  {
111  bool foundOne= false;
112  int * substDegree= NEW_ARRAY(int,F.level());
113  for (int i= 1; i <= F.level(); i++)
114  {
115  if (degree (F, i) > 0)
116  {
117  substDegree[i-1]= substituteCheck (F, Variable (i));
118  if (substDegree [i-1] > 1)
119  {
120  foundOne= true;
121  subst (F, F, substDegree[i-1], Variable (i));
122  }
123  }
124  else
125  substDegree[i-1]= -1;
126  }
127  if (foundOne)
128  {
129  CFFList result= FpFactorize (F, false);
130  CFFList newResult, tmp;
132  newResult.insert (result.getFirst());
133  result.removeFirst();
134  for (CFFListIterator i= result; i.hasItem(); i++)
135  {
136  tmp2= i.getItem().factor();
137  for (int j= 1; j <= G.level(); j++)
138  {
139  if (substDegree[j-1] > 1)
140  tmp2= reverseSubst (tmp2, substDegree[j-1], Variable (j));
141  }
142  tmp= FpFactorize (tmp2, false);
143  tmp.removeFirst();
144  for (CFFListIterator j= tmp; j.hasItem(); j++)
145  newResult.append (CFFactor (j.getItem().factor(),
146  j.getItem().exp()*i.getItem().exp()));
147  }
148  DELETE_ARRAY(substDegree);
149  return newResult;
150  }
151  DELETE_ARRAY(substDegree);
152  }
153 
155  Variable a= Variable (1);
156  CanonicalForm LcF= Lc (F);
157  TIMING_START (fac_fq_squarefree);
158  CFFList sqrf= FpSqrf (F, false);
159  TIMING_END_AND_PRINT (fac_fq_squarefree,
160  "time for squarefree factorization over Fq: ");
161  CFFList result;
162  CFList bufResult;
163  sqrf.removeFirst();
165  for (CFFListIterator iter= sqrf; iter.hasItem(); iter++)
166  {
167  TIMING_START (fac_fq_factor_squarefree);
168  bufResult= multiFactorize (iter.getItem().factor(), info);
169  TIMING_END_AND_PRINT (fac_fq_factor_squarefree,
170  "time to factorize sqrfree factor over Fq: ");
171  for (i= bufResult; i.hasItem(); i++)
172  result.append (CFFactor (i.getItem(), iter.getItem().exp()));
173  }
174  result.insert (CFFactor (LcF, 1));
175  return result;
176 }
int getNumVars(const CanonicalForm &f)
int getNumVars ( const CanonicalForm & f )
Definition: cf_ops.cc:314
#define DELETE_ARRAY(P)
Definition: cf_defs.h:64
#define NEW_ARRAY(T, N)
Definition: cf_defs.h:63
CanonicalForm LcF
Definition: facAbsBiFact.cc:50
TIMING_END_AND_PRINT(fac_alg_resultant, "time to compute resultant0: ")
TIMING_START(fac_alg_resultant)
CanonicalForm subst(const CanonicalForm &f, const CFList &a, const CFList &b, const CanonicalForm &Rstar, bool isFunctionField)
CFList multiFactorize(const CanonicalForm &F, const Variable &v)
Factorization over Q (a)
CanonicalForm reverseSubst(const CanonicalForm &F, const int d, const Variable &x)
reverse a substitution x^d->x
int substituteCheck(const CanonicalForm &F, const Variable &x)
check if a substitution x^n->x is possible
CFFList FpBiFactorize(const CanonicalForm &G, bool substCheck=true)
factorize a bivariate polynomial over
Definition: facFqBivar.h:190
CFFList FpFactorize(const CanonicalForm &G, bool substCheck=true)
factorize a multivariate polynomial over
CFFList FpSqrf(const CanonicalForm &F, bool sort=true)
squarefree factorization over . If input is not monic, the leading coefficient is dropped
STATIC_VAR TreeM * G
Definition: janet.cc:31

◆ FpSqrfFactorize()

CFList FpSqrfFactorize ( const CanonicalForm F)
inline

factorize a squarefree multivariate polynomial over $ F_{p} $

Returns
FpSqrfFactorize returns a list of monic factors, the first element is the leading coefficient.
See also
FqSqrfFactorize(), GFSqrfFactorize()
Parameters
[in]Fa multivariate poly

Definition at line 47 of file facFqFactorize.h.

49 {
50  if (getNumVars (F) == 2)
51  return FpBiSqrfFactorize (F);
54  result.insert (Lc(F));
55  return result;
56 }
CFList FpBiSqrfFactorize(const CanonicalForm &G)
factorize a squarefree bivariate polynomial over .
Definition: facFqBivar.h:141

◆ FqFactorize()

CFFList FqFactorize ( const CanonicalForm G,
const Variable alpha,
bool  substCheck = true 
)
inline

factorize a multivariate polynomial over $ F_{p} (\alpha ) $

Returns
FqFactorize returns a list of monic factors with multiplicity, the first element is the leading coefficient.
See also
FpFactorize(), GFFactorize()
Parameters
[in]Ga multivariate poly
[in]alphaalgebraic variable
[in]substCheckenables substitute check

Definition at line 184 of file facFqFactorize.h.

188 {
189  if (getNumVars (G) == 2)
190  return FqBiFactorize (G, alpha, substCheck);
191 
192  CanonicalForm F= G;
193  if (substCheck)
194  {
195  bool foundOne= false;
196  int * substDegree= NEW_ARRAY(int,F.level());
197  for (int i= 1; i <= F.level(); i++)
198  {
199  if (degree (F, i) > 0)
200  {
201  substDegree[i-1]= substituteCheck (F, Variable (i));
202  if (substDegree [i-1] > 1)
203  {
204  foundOne= true;
205  subst (F, F, substDegree[i-1], Variable (i));
206  }
207  }
208  else
209  substDegree[i-1]= -1;
210  }
211  if (foundOne)
212  {
213  CFFList result= FqFactorize (F, alpha, false);
214  CFFList newResult, tmp;
216  newResult.insert (result.getFirst());
217  result.removeFirst();
218  for (CFFListIterator i= result; i.hasItem(); i++)
219  {
220  tmp2= i.getItem().factor();
221  for (int j= 1; j <= G.level(); j++)
222  {
223  if (substDegree[j-1] > 1)
224  tmp2= reverseSubst (tmp2, substDegree[j-1], Variable (j));
225  }
226  tmp= FqFactorize (tmp2, alpha, false);
227  tmp.removeFirst();
228  for (CFFListIterator j= tmp; j.hasItem(); j++)
229  newResult.append (CFFactor (j.getItem().factor(),
230  j.getItem().exp()*i.getItem().exp()));
231  }
232  DELETE_ARRAY(substDegree);
233  return newResult;
234  }
235  DELETE_ARRAY(substDegree);
236  }
237 
239  CanonicalForm LcF= Lc (F);
240  TIMING_START (fac_fq_squarefree);
241  CFFList sqrf= FqSqrf (F, alpha, false);
242  TIMING_END_AND_PRINT (fac_fq_squarefree,
243  "time for squarefree factorization over Fq: ");
244  CFFList result;
245  CFList bufResult;
246  sqrf.removeFirst();
248  for (CFFListIterator iter= sqrf; iter.hasItem(); iter++)
249  {
250  TIMING_START (fac_fq_factor_squarefree);
251  bufResult= multiFactorize (iter.getItem().factor(), info);
252  TIMING_END_AND_PRINT (fac_fq_factor_squarefree,
253  "time to factorize sqrfree factor over Fq: ");
254  for (i= bufResult; i.hasItem(); i++)
255  result.append (CFFactor (i.getItem(), iter.getItem().exp()));
256  }
257  result.insert (CFFactor (LcF, 1));
258  return result;
259 }
CFFList FqBiFactorize(const CanonicalForm &G, const Variable &alpha, bool substCheck=true)
factorize a bivariate polynomial over
Definition: facFqBivar.h:317
CFFList FqFactorize(const CanonicalForm &G, const Variable &alpha, bool substCheck=true)
factorize a multivariate polynomial over
CFFList FqSqrf(const CanonicalForm &F, const Variable &alpha, bool sort=true)
squarefree factorization over . If input is not monic, the leading coefficient is dropped

◆ FqSqrfFactorize()

CFList FqSqrfFactorize ( const CanonicalForm F,
const Variable alpha 
)
inline

factorize a squarefree multivariate polynomial over $ F_{p} (\alpha ) $

Returns
FqSqrfFactorize returns a list of monic factors, the first element is the leading coefficient.
See also
FpSqrfFactorize(), GFSqrfFactorize()
Parameters
[in]Fa multivariate poly
[in]alphaalgebraic variable

Definition at line 64 of file facFqFactorize.h.

67 {
68  if (getNumVars (F) == 2)
69  return FqBiSqrfFactorize (F, alpha);
72  result.insert (Lc(F));
73  return result;
74 }
CFList FqBiSqrfFactorize(const CanonicalForm &G, const Variable &alpha)
factorize a squarefree bivariate polynomial over .
Definition: facFqBivar.h:156

◆ 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
const CFList & factors2

◆ 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 }

◆ GFFactorize()

CFFList GFFactorize ( const CanonicalForm G,
bool  substCheck = true 
)
inline

factorize a multivariate polynomial over GF

Returns
GFFactorize returns a list of monic factors with multiplicity, the first element is the leading coefficient.
See also
FpFactorize(), FqFactorize()
Parameters
[in]Ga multivariate poly
[in]substCheckenables substitute check

Definition at line 267 of file facFqFactorize.h.

270 {
272  "GF as base field expected");
273  if (getNumVars (G) == 2)
274  return GFBiFactorize (G, substCheck);
275 
276  CanonicalForm F= G;
277  if (substCheck)
278  {
279  bool foundOne= false;
280  int * substDegree= NEW_ARRAY(int,F.level());
281  for (int i= 1; i <= F.level(); i++)
282  {
283  if (degree (F, i) > 0)
284  {
285  substDegree[i-1]= substituteCheck (F, Variable (i));
286  if (substDegree [i-1] > 1)
287  {
288  foundOne= true;
289  subst (F, F, substDegree[i-1], Variable (i));
290  }
291  }
292  else
293  substDegree[i-1]= -1;
294  }
295  if (foundOne)
296  {
297  CFFList result= GFFactorize (F, false);
298  CFFList newResult, tmp;
300  newResult.insert (result.getFirst());
301  result.removeFirst();
302  for (CFFListIterator i= result; i.hasItem(); i++)
303  {
304  tmp2= i.getItem().factor();
305  for (int j= 1; j <= G.level(); j++)
306  {
307  if (substDegree[j-1] > 1)
308  tmp2= reverseSubst (tmp2, substDegree[j-1], Variable (j));
309  }
310  tmp= GFFactorize (tmp2, false);
311  tmp.removeFirst();
312  for (CFFListIterator j= tmp; j.hasItem(); j++)
313  newResult.append (CFFactor (j.getItem().factor(),
314  j.getItem().exp()*i.getItem().exp()));
315  }
316  DELETE_ARRAY(substDegree);
317  return newResult;
318  }
319  DELETE_ARRAY(substDegree);
320  }
321 
322  Variable a= Variable (1);
324  CanonicalForm LcF= Lc (F);
325  CFFList sqrf= GFSqrf (F, false);
326  CFFList result;
327  CFList bufResult;
328  sqrf.removeFirst();
330  for (CFFListIterator iter= sqrf; iter.hasItem(); iter++)
331  {
332  bufResult= multiFactorize (iter.getItem().factor(), info);
333  for (i= bufResult; i.hasItem(); i++)
334  result.append (CFFactor (i.getItem(), iter.getItem().exp()));
335  }
336  result.insert (CFFactor (LcF, 1));
337  return result;
338 }
CFFList GFBiFactorize(const CanonicalForm &G, bool substCheck=true)
factorize a bivariate polynomial over GF
Definition: facFqBivar.h:446
CFFList GFFactorize(const CanonicalForm &G, bool substCheck=true)
factorize a multivariate polynomial over GF
CFFList GFSqrf(const CanonicalForm &F, bool sort=true)
squarefree factorization over GF. If input is not monic, the leading coefficient is dropped
VAR char gf_name
Definition: gfops.cc:52

◆ GFSqrfFactorize()

CFList GFSqrfFactorize ( const CanonicalForm F)
inline

factorize a squarefree multivariate polynomial over GF

Returns
GFSqrfFactorize returns a list of monic factors, the first element is the leading coefficient.
See also
FpSqrfFactorize(), FqSqrfFactorize()
Parameters
[in]Fa multivariate poly

Definition at line 82 of file facFqFactorize.h.

84 {
86  "GF as base field expected");
87  if (getNumVars (F) == 2)
88  return GFBiSqrfFactorize (F);
91  result.insert (Lc(F));
92  return result;
93 }
CFList GFBiSqrfFactorize(const CanonicalForm &G)
factorize a squarefree bivariate polynomial over GF
Definition: facFqBivar.h:172

◆ 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
void sortList(CFList &list, const Variable &x)
sort a list of polynomials by their degree in x.
Definition: facHensel.cc:449

◆ 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 }
CanonicalForm getItem(const CFList &list, const int &pos)
helper function
Definition: cf_map_ext.cc:53
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 }
fq_nmod_poly_t prod
Definition: facHensel.cc:100

◆ 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

◆ leadingCoeffReconstruction()

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

obtain factors of F by reconstructing their leading coeffs

Returns
returns the reconstructed factors
See also
factorRecombination()
Parameters
[in]Fpoly to be factored
[in]factorsfactors of f monic wrt Variable (1)
[in]Ma list of powers of Variables

◆ 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 }

◆ 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 }
#define swap(_i, _j)
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
const CanonicalForm CFMap CFMap & N
Definition: cfEzgcd.cc:56
int * degsf
Definition: cfEzgcd.cc:59
CanonicalForm buf1
Definition: facFqBivar.cc:73

◆ 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 }
CanonicalForm compress(const CanonicalForm &f, CFMap &m)
CanonicalForm compress ( const CanonicalForm & f, CFMap & m )
Definition: cf_map.cc:210
class CFMap
Definition: cf_map.h:85
bool isUnivariate() const
void removeLast()
Definition: ftmpl_list.cc:317
bool found
Definition: facFactorize.cc: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
CFList evaluateAtZero(const CanonicalForm &F)
evaluate F successively n-2 at 0
CFList evaluateAtEval(const CanonicalForm &F, const CFArray &eval)
evaluate F at evaluation
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,...
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
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
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 LucksWangSparseHeuristic(const CanonicalForm &F, const CFList &factors, int level, const CFList &leadingCoeffs, CFList &result)
sparse heuristic lifting by Wang and Lucks
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 }

◆ 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)
template List< Variable > Union(const List< Variable > &, const List< Variable > &)

◆ refineBiFactors()

void refineBiFactors ( const CanonicalForm A,
CFList biFactors,
CFList *const factors,
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]factorslist 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 }
CFList int & minFactorsLength
[in,out] minimal length of bivariate factors
Definition: facFactorize.h:33
CFList buildUniFactors(const CFList &biFactors, const CanonicalForm &evalPoint, const Variable &y)
plug in evalPoint for y in a list of polys

◆ 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)

◆ TIMING_DEFINE_PRINT()

TIMING_DEFINE_PRINT ( fac_fq_squarefree  ) const &

Factorization over a finite field.

Returns
multiFactorize returns a factorization of F
See also
biFactorize(), extFactorize()

Variable Documentation

◆ info

< [in] sqrfree poly

< [in] info about extension

Definition at line 37 of file facFqFactorize.h.