My Project  UNKNOWN_GIT_VERSION
Functions | Variables
facFqFactorize.h File Reference
#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 2304 of file facFqFactorize.cc.

2306 {
2307  CFList result;
2308  CanonicalForm tmp;
2309  for (CFListIterator i= biFactors; i.hasItem(); i++)
2310  {
2311  tmp= mod (i.getItem(), y - evalPoint);
2312  tmp /= Lc (tmp);
2313  result.append (tmp);
2314  }
2315  return result;
2316 }

◆ changeSecondVariable()

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

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

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

Definition at line 2527 of file facFqFactorize.cc.

2530 {
2531  Variable y= Variable (2);
2532  A= swapvar (A, y, w);
2533  int i= A.level();
2535  for (CFListIterator iter= evaluation; iter.hasItem(); iter++, i--)
2536  {
2537  if (i == w.level())
2538  {
2539  evalPoint= iter.getItem();
2540  iter.getItem()= evaluation.getLast();
2541  evaluation.removeLast();
2542  evaluation.append (evalPoint);
2543  break;
2544  }
2545  }
2546  for (i= 0; i < lengthAeval2; i++)
2547  {
2548  if (oldAeval[i].isEmpty())
2549  continue;
2550  if (oldAeval[i].getFirst().level() == w.level())
2551  {
2552  CFArray tmp= copy (oldAeval[i]);
2553  oldAeval[i]= biFactors;
2554  for (CFListIterator iter= oldAeval[i]; iter.hasItem(); iter++)
2555  iter.getItem()= swapvar (iter.getItem(), w, y);
2556  for (int ii= 0; ii < tmp.size(); ii++)
2557  tmp[ii]= swapvar (tmp[ii], w, y);
2558  CFArray tmp2= CFArray (tmp.size());
2560  for (int ii= 0; ii < tmp.size(); ii++)
2561  {
2562  buf= tmp[ii] (evaluation.getLast(),y);
2563  buf /= Lc (buf);
2564  tmp2[findItem (uniFactors, buf)-1]=tmp[ii];
2565  }
2566  biFactors= CFList();
2567  for (int j= 0; j < tmp2.size(); j++)
2568  biFactors.append (tmp2[j]);
2569  }
2570  }
2571 }

◆ distributeContent()

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

distribute content

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

Definition at line 1281 of file facFqFactorize.cc.

1284 {
1285  CFList l= L;
1286  CanonicalForm content= l.getFirst();
1287 
1288  if (content.inCoeffDomain())
1289  return l;
1290 
1291  if (l.length() == 1)
1292  {
1293  CFList result;
1294  for (int i= 0; i < length; i++)
1295  {
1296  if (differentSecondVarFactors[i].isEmpty())
1297  continue;
1298  if (result.isEmpty())
1299  {
1300  result= differentSecondVarFactors[i];
1301  for (CFListIterator iter= result; iter.hasItem(); iter++)
1302  content /= iter.getItem();
1303  }
1304  else
1305  {
1306  CFListIterator iter1= result;
1307  for (CFListIterator iter2= differentSecondVarFactors[i];iter2.hasItem();
1308  iter2++, iter1++)
1309  {
1310  iter1.getItem() *= iter2.getItem();
1311  content /= iter2.getItem();
1312  }
1313  }
1314  }
1315  result.insert (content);
1316  return result;
1317  }
1318 
1319  Variable v;
1320  CFListIterator iter1, iter2;
1321  CanonicalForm tmp, g;
1322  CFList multiplier;
1323  for (int i= 0; i < length; i++)
1324  {
1325  if (differentSecondVarFactors[i].isEmpty())
1326  continue;
1327  iter1= l;
1328  iter1++;
1329 
1330  tmp= 1;
1331  for (iter2= differentSecondVarFactors[i]; iter2.hasItem();
1332  iter2++, iter1++)
1333  {
1334  if (iter2.getItem().inCoeffDomain())
1335  {
1336  multiplier.append (1);
1337  continue;
1338  }
1339  v= iter2.getItem().mvar();
1340  if (degree (iter2.getItem()) == degree (iter1.getItem(),v))
1341  {
1342  multiplier.append (1);
1343  continue;
1344  }
1345  g= gcd (iter2.getItem(), content);
1346  if (!g.inCoeffDomain())
1347  {
1348  tmp *= g;
1349  multiplier.append (g);
1350  }
1351  else
1352  multiplier.append (1);
1353  }
1354  if (!tmp.isOne() && fdivides (tmp, content))
1355  {
1356  iter1= l;
1357  iter1++;
1358  content /= tmp;
1359  for (iter2= multiplier; iter2.hasItem(); iter1++, iter2++)
1360  iter1.getItem() *= iter2.getItem();
1361  }
1362  multiplier= CFList();
1363  }
1364 
1365  l.removeFirst();
1366  l.insert (content);
1367  return l;
1368 }

◆ distributeLCmultiplier()

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

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

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

Definition at line 2574 of file facFqFactorize.cc.

2577 {
2578  CanonicalForm tmp= power (LCmultipler, biFactors.length() - 1);
2579  A *= tmp;
2580  tmp= LCmultipler;
2581  CFListIterator iter= leadingCoeffs;
2582  for (;iter.hasItem(); iter++)
2583  iter.getItem() *= LCmultipler;
2584  iter= evaluation;
2585  for (int i= A.level(); i > 2; i--, iter++)
2586  tmp= tmp (iter.getItem(), i);
2587  if (!tmp.inCoeffDomain())
2588  {
2589  for (CFListIterator i= biFactors; i.hasItem(); i++)
2590  {
2591  i.getItem() *= tmp/LC (i.getItem(), 1);
2592  i.getItem() /= Lc (i.getItem());
2593  }
2594  }
2595 }

◆ earlyFactorDetect()

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

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

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

Definition at line 605 of file facFqFactorize.cc.

608 {
609  CFList result;
610  CFList T= factors;
611  CanonicalForm buf= F;
612  Variable y= F.mvar();
613  Variable x= Variable (1);
614  CanonicalForm LCBuf= LC (buf, x);
615  CanonicalForm g, quot;
616  CFList M= MOD;
617  M.append (power (y, deg));
618  adaptedLiftBound= 0;
619  int d= bound;
620  int e= 0;
621  int nBuf;
622  for (CFListIterator i= factors; i.hasItem(); i++)
623  {
624  g= mulMod (i.getItem(), LCBuf, M);
625  g /= myContent (g);
626  if (fdivides (g, buf, quot))
627  {
628  result.append (g);
629  nBuf= degree (g, y) + degree (LC (g, x), y);
630  d -= nBuf;
631  e= tmax (e, nBuf);
632  buf= quot;
633  LCBuf= LC (buf, x);
634  T= Difference (T, CFList (i.getItem()));
635  }
636  }
637  adaptedLiftBound= d;
638 
639  if (adaptedLiftBound < deg)
640  {
641  if (adaptedLiftBound < degree (F) + 1)
642  {
643  if (d == 1)
644  adaptedLiftBound= tmin (e + 1, deg);
645  else
646  adaptedLiftBound= deg;
647  }
648  factors= T;
649  F= buf;
650  success= true;
651  }
652  return result;
653 }

◆ evalPoints()

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

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

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

Definition at line 740 of file facFqFactorize.cc.

742 {
743  int k= F.level() - 1;
744  Variable x= Variable (1);
745  CanonicalForm LCF=LC (F, x);
746  CFList LCFeval;
747 
748  CFList result;
749  FFRandom genFF;
750  GFRandom genGF;
751  int p= getCharacteristic ();
752  if (p < CHAR_THRESHOLD)
753  {
754  if (!GF && alpha.level() == 1)
755  {
756  fail= true;
757  return CFList();
758  }
759  else if (!GF && alpha.level() != 1)
760  {
761  if ((p == 2 && degree (getMipo (alpha)) < 6) ||
762  (p == 3 && degree (getMipo (alpha)) < 4) ||
763  (p == 5 && degree (getMipo (alpha)) < 3))
764  {
765  fail= true;
766  return CFList();
767  }
768  }
769  }
770  double bound;
771  if (alpha != x)
772  {
773  bound= pow ((double) p, (double) degree (getMipo(alpha)));
774  bound *= (double) k;
775  }
776  else if (GF)
777  {
778  bound= pow ((double) p, (double) getGFDegree());
779  bound *= (double) k;
780  }
781  else
782  bound= pow ((double) p, (double) k);
783 
784  CanonicalForm random;
786  do
787  {
788  random= 0;
789  // possible overflow if list.length() does not fit into a int
790  if (list.length() >= bound)
791  {
792  fail= true;
793  break;
794  }
795  for (int i= 0; i < k; i++)
796  {
797  if (list.isEmpty())
798  result.append (0);
799  else if (GF)
800  {
801  result.append (genGF.generate());
802  random += result.getLast()*power (x, i);
803  }
804  else if (alpha.level() != 1)
805  {
806  AlgExtRandomF genAlgExt (alpha);
807  result.append (genAlgExt.generate());
808  random += result.getLast()*power (x, i);
809  }
810  else
811  {
812  result.append (genFF.generate());
813  random += result.getLast()*power (x, i);
814  }
815  }
816  if (find (list, random))
817  {
818  result= CFList();
819  continue;
820  }
821  int l= F.level();
822  eval.insert (F);
823  LCFeval.insert (LCF);
824  bool bad= false;
825  for (CFListIterator i= result; i.hasItem(); i++, l--)
826  {
827  eval.insert (eval.getFirst()(i.getItem(), l));
828  LCFeval.insert (LCFeval.getFirst()(i.getItem(), l));
829  if (degree (eval.getFirst(), l - 1) != degree (F, l - 1))
830  {
831  if (!find (list, random))
832  list.append (random);
833  result= CFList();
834  eval= CFList();
835  LCFeval= CFList();
836  bad= true;
837  break;
838  }
839  if ((l != 2) && (degree (LCFeval.getFirst(), l-1) != degree (LCF, l-1)))
840  {
841  if (!find (list, random))
842  list.append (random);
843  result= CFList();
844  eval= CFList();
845  LCFeval= CFList();
846  bad= true;
847  break;
848  }
849  }
850 
851  if (bad)
852  continue;
853 
854  if (degree (eval.getFirst()) != degree (F, 1))
855  {
856  if (!find (list, random))
857  list.append (random);
858  result= CFList();
859  LCFeval= CFList();
860  eval= CFList();
861  continue;
862  }
863 
864  deriv_x= deriv (eval.getFirst(), x);
866  if (degree (gcd_deriv) > 0)
867  {
868  if (!find (list, random))
869  list.append (random);
870  result= CFList();
871  LCFeval= CFList();
872  eval= CFList();
873  continue;
874  }
876  i++;
877  CanonicalForm contentx= content (i.getItem(), x);
878  if (degree (contentx) > 0)
879  {
880  if (!find (list, random))
881  list.append (random);
882  result= CFList();
883  LCFeval= CFList();
884  eval= CFList();
885  continue;
886  }
887 
888  contentx= content (i.getItem());
889  if (degree (contentx) > 0)
890  {
891  if (!find (list, random))
892  list.append (random);
893  result= CFList();
894  LCFeval= CFList();
895  eval= CFList();
896  continue;
897  }
898 
899  if (list.length() >= bound)
900  {
901  fail= true;
902  break;
903  }
904  } while (find (list, random));
905 
906  if (!eval.isEmpty())
907  eval.removeFirst();
908 
909  return result;
910 }

◆ evaluationWRTDifferentSecondVars()

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

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

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

Definition at line 1950 of file facFqFactorize.cc.

1952 {
1953  CanonicalForm tmp;
1954  CFList tmp2;
1956  bool preserveDegree= true;
1957  Variable x= Variable (1);
1958  int j, degAi, degA1= degree (A,1);
1959  for (int i= A.level(); i > 2; i--)
1960  {
1961  tmp= A;
1962  tmp2= CFList();
1963  iter= evaluation;
1964  preserveDegree= true;
1965  degAi= degree (A,i);
1966  for (j= A.level(); j > 1; j--, iter++)
1967  {
1968  if (j == i)
1969  continue;
1970  else
1971  {
1972  tmp= tmp (iter.getItem(), j);
1973  tmp2.insert (tmp);
1974  if ((degree (tmp, i) != degAi) ||
1975  (degree (tmp, 1) != degA1))
1976  {
1977  preserveDegree= false;
1978  break;
1979  }
1980  }
1981  }
1982  if (!content(tmp,1).inCoeffDomain())
1983  preserveDegree= false;
1984  if (!content(tmp).inCoeffDomain())
1985  preserveDegree= false;
1986  if (!(gcd (deriv (tmp,x), tmp)).inCoeffDomain())
1987  preserveDegree= false;
1988  if (preserveDegree)
1989  Aeval [i - 3]= tmp2;
1990  else
1991  Aeval [i - 3]= CFList();
1992  }
1993 }

◆ extEarlyFactorDetect()

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

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

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

Definition at line 656 of file facFqFactorize.cc.

659 {
662  CanonicalForm gamma= info.getGamma();
664  int k= info.getGFDegree();
665  CFList result;
666  CFList T= factors;
667  CanonicalForm buf= F;
668  Variable y= F.mvar();
669  Variable x= Variable (1);
670  CanonicalForm LCBuf= LC (buf, x);
671  CanonicalForm g, gg, quot;
672  CFList M= MOD;
673  M.append (power (y, deg));
674  adaptedLiftBound= 0;
675  int d= bound;
676  int e= 0;
677  int nBuf;
678  CFList source, dest;
679 
680  int degMipoBeta= 1;
681  if (!k && beta.level() != 1)
682  degMipoBeta= degree (getMipo (beta));
683 
684  for (CFListIterator i= factors; i.hasItem(); i++)
685  {
686  g= mulMod (i.getItem(), LCBuf, M);
687  g /= myContent (g);
688  if (fdivides (g, buf, quot))
689  {
690  gg= reverseShift (g, eval);
691  gg /= Lc (gg);
692  if (!k && beta == x)
693  {
694  if (degree (gg, alpha) < degMipoBeta)
695  {
696  appendTestMapDown (result, gg, info, source, dest);
697  buf= quot;
698  nBuf= degree (g, y) + degree (LC (g, x), y);
699  d -= nBuf;
700  e= tmax (e, nBuf);
701  LCBuf= LC (buf, x);
702  T= Difference (T, CFList (i.getItem()));
703  }
704  }
705  else
706  {
707  if (!isInExtension (gg, gamma, k, delta, source, dest))
708  {
709  appendTestMapDown (result, gg, info, source, dest);
710  buf= quot;
711  nBuf= degree (g, y) + degree (LC (g, x), y);
712  d -= nBuf;
713  e= tmax (e, nBuf);
714  LCBuf= LC (buf, x);
715  T= Difference (T, CFList (i.getItem()));
716  }
717  }
718  }
719  }
720  adaptedLiftBound= d;
721 
722  if (adaptedLiftBound < deg)
723  {
724  if (adaptedLiftBound < degree (F) + 1)
725  {
726  if (d == 1)
727  adaptedLiftBound= tmin (e + 1, deg);
728  else
729  adaptedLiftBound= deg;
730  }
731  success= true;
732  factors= T;
733  F= buf;
734  }
735  return result;
736 }

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

3641 {
3642  CanonicalForm A= F;
3643 
3646  int k= info.getGFDegree();
3647  char cGFName= info.getGFName();
3649  bool GF= (CFFactory::gettype() == GaloisFieldDomain);
3650  Variable w= Variable (1);
3651 
3652  CFList factors;
3653  if (!GF && alpha == w) // we are in F_p
3654  {
3655  CFList factors;
3656  bool extension= true;
3657  int p= getCharacteristic();
3658  if (p < 7)
3659  {
3660  if (p == 2)
3662  else if (p == 3)
3664  else if (p == 5)
3666  ExtensionInfo info= ExtensionInfo (extension);
3667  A= A.mapinto();
3668  factors= multiFactorize (A, info);
3669 
3672  Variable vBuf= rootOf (mipo.mapinto());
3673  for (CFListIterator j= factors; j.hasItem(); j++)
3674  j.getItem()= GF2FalphaRep (j.getItem(), vBuf);
3675  prune (vBuf);
3676  }
3677  else if (p >= 7 && p*p < (1<<16)) // pass to GF if possible
3678  {
3680  ExtensionInfo info= ExtensionInfo (extension);
3681  A= A.mapinto();
3682  factors= multiFactorize (A, info);
3683 
3686  Variable vBuf= rootOf (mipo.mapinto());
3687  for (CFListIterator j= factors; j.hasItem(); j++)
3688  j.getItem()= GF2FalphaRep (j.getItem(), vBuf);
3689  prune (vBuf);
3690  }
3691  else // not able to pass to GF, pass to F_p(\alpha)
3692  {
3694  Variable v= rootOf (mipo);
3696  factors= multiFactorize (A, info);
3697  prune (v);
3698  }
3699  return factors;
3700  }
3701  else if (!GF && (alpha != w)) // we are in F_p(\alpha)
3702  {
3703  if (k == 1) // need factorization over F_p
3704  {
3705  int extDeg= degree (getMipo (alpha));
3706  extDeg++;
3707  CanonicalForm mipo= randomIrredpoly (extDeg, w);
3708  Variable v= rootOf (mipo);
3710  factors= multiFactorize (A, info);
3711  prune (v);
3712  }
3713  else
3714  {
3715  if (beta == w)
3716  {
3718  CanonicalForm primElem, imPrimElem;
3719  bool primFail= false;
3720  Variable vBuf;
3721  primElem= primitiveElement (alpha, vBuf, primFail);
3722  ASSERT (!primFail, "failure in integer factorizer");
3723  if (primFail)
3724  ; //ERROR
3725  else
3726  imPrimElem= mapPrimElem (primElem, alpha, v);
3727 
3728  CFList source, dest;
3729  CanonicalForm bufA= mapUp (A, alpha, v, primElem, imPrimElem,
3730  source, dest);
3731  ExtensionInfo info= ExtensionInfo (v, alpha, imPrimElem, primElem);
3732  factors= multiFactorize (bufA, info);
3733  prune (v);
3734  }
3735  else
3736  {
3738  CanonicalForm primElem, imPrimElem;
3739  bool primFail= false;
3740  Variable vBuf;
3741  ASSERT (!primFail, "failure in integer factorizer");
3742  if (primFail)
3743  ; //ERROR
3744  else
3745  imPrimElem= mapPrimElem (delta, beta, v);
3746 
3747  CFList source, dest;
3748  CanonicalForm bufA= mapDown (A, info, source, dest);
3749  source= CFList();
3750  dest= CFList();
3751  bufA= mapUp (bufA, beta, v, delta, imPrimElem, source, dest);
3752  ExtensionInfo info= ExtensionInfo (v, beta, imPrimElem, delta);
3753  factors= multiFactorize (bufA, info);
3754  prune (v);
3755  }
3756  }
3757  return factors;
3758  }
3759  else // we are in GF (p^k)
3760  {
3761  int p= getCharacteristic();
3762  int extensionDeg= getGFDegree();
3763  bool extension= true;
3764  if (k == 1) // need factorization over F_p
3765  {
3766  extensionDeg++;
3767  if (pow ((double) p, (double) extensionDeg) < (1<<16))
3768  // pass to GF(p^k+1)
3769  {
3771  setCharacteristic (p);
3772  Variable vBuf= rootOf (mipo.mapinto());
3773  A= GF2FalphaRep (A, vBuf);
3774  setCharacteristic (p, extensionDeg, 'Z');
3775  ExtensionInfo info= ExtensionInfo (extension);
3776  factors= multiFactorize (A.mapinto(), info);
3777  prune (vBuf);
3778  }
3779  else // not able to pass to another GF, pass to F_p(\alpha)
3780  {
3782  setCharacteristic (p);
3783  Variable vBuf= rootOf (mipo.mapinto());
3784  A= GF2FalphaRep (A, vBuf);
3785  Variable v= chooseExtension (vBuf, beta, k);
3786  ExtensionInfo info= ExtensionInfo (v, extension);
3787  factors= multiFactorize (A, info);
3788  prune (vBuf);
3789  }
3790  }
3791  else // need factorization over GF (p^k)
3792  {
3793  if (pow ((double) p, (double) 2*extensionDeg) < (1<<16))
3794  // pass to GF(p^2k)
3795  {
3796  setCharacteristic (p, 2*extensionDeg, 'Z');
3797  ExtensionInfo info= ExtensionInfo (k, cGFName, extension);
3798  factors= multiFactorize (GFMapUp (A, extensionDeg), info);
3799  setCharacteristic (p, extensionDeg, cGFName);
3800  }
3801  else // not able to pass to GF (p^2k), pass to F_p (\alpha)
3802  {
3804  setCharacteristic (p);
3805  Variable v1= rootOf (mipo.mapinto());
3806  A= GF2FalphaRep (A, v1);
3807  Variable v2= chooseExtension (v1, v1, k);
3808  CanonicalForm primElem, imPrimElem;
3809  bool primFail= false;
3810  Variable vBuf;
3811  primElem= primitiveElement (v1, v1, primFail);
3812  if (primFail)
3813  ; //ERROR
3814  else
3815  imPrimElem= mapPrimElem (primElem, v1, v2);
3816  CFList source, dest;
3817  CanonicalForm bufA= mapUp (A, v1, v2, primElem, imPrimElem,
3818  source, dest);
3819  ExtensionInfo info= ExtensionInfo (v2, v1, imPrimElem, primElem);
3820  factors= multiFactorize (bufA, info);
3821  setCharacteristic (p, k, cGFName);
3822  for (CFListIterator i= factors; i.hasItem(); i++)
3823  i.getItem()= Falpha2GFRep (i.getItem());
3824  prune (v1);
3825  }
3826  }
3827  return factors;
3828  }
3829 }

◆ extFactorRecombination()

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

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

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

Definition at line 217 of file facFqFactorize.cc.

220 {
223  CanonicalForm gamma= info.getGamma();
225  int k= info.getGFDegree();
226  CFList source, dest;
227  if (factors.length() == 1)
228  {
230  return CFList (mapDown (buf, info, source, dest));
231  }
232  if (factors.length() < 1)
233  return CFList();
234 
235  int degMipoBeta= 1;
236  if (!k && beta.level() != 1)
237  degMipoBeta= degree (getMipo (beta));
238 
239  CFList T, S;
240  T= factors;
241 
242  int s= 1;
243  CFList result;
245 
246  buf= F;
247 
248  Variable x= Variable (1);
249  CanonicalForm g, LCBuf= LC (buf, x);
250  CanonicalForm buf2, quot;
251  int * v= new int [T.length()];
252  for (int i= 0; i < T.length(); i++)
253  v[i]= 0;
254  bool noSubset= false;
255  CFArray TT;
256  TT= copy (factors);
257  bool recombination= false;
258  bool trueFactor= false;
259  while (T.length() >= 2*s)
260  {
261  while (noSubset == false)
262  {
263  if (T.length() == s)
264  {
265  delete [] v;
266  if (recombination)
267  {
268  T.insert (LCBuf);
269  g= prodMod (T, M);
270  T.removeFirst();
271  result.append (g/myContent (g));
273  g /= Lc (g);
274  appendTestMapDown (result, g, info, source, dest);
275  return result;
276  }
277  else
278  {
280  return CFList (buf);
281  }
282  }
283 
284  S= subset (v, s, TT, noSubset);
285  if (noSubset) break;
286 
287  S.insert (LCBuf);
288  g= prodMod (S, M);
289  S.removeFirst();
290  g /= myContent (g);
291  if (fdivides (g, buf, quot))
292  {
294  buf2 /= Lc (buf2);
295  if (!k && beta == x)
296  {
297  if (degree (buf2, alpha) < degMipoBeta)
298  {
299  appendTestMapDown (result, buf2, info, source, dest);
300  buf= quot;
301  LCBuf= LC (buf, x);
302  recombination= true;
303  trueFactor= true;
304  }
305  }
306  else
307  {
308  if (!isInExtension (buf2, gamma, k, delta, source, dest))
309  {
310  appendTestMapDown (result, buf2, info, source, dest);
311  buf /= g;
312  LCBuf= LC (buf, x);
313  recombination= true;
314  trueFactor= true;
315  }
316  }
317 
318  if (trueFactor)
319  {
320  T= Difference (T, S);
321 
322  if (T.length() < 2*s || T.length() == s)
323  {
325  buf /= Lc (buf);
326  appendTestMapDown (result, buf, info, source, dest);
327  delete [] v;
328  return result;
329  }
330  trueFactor= false;
331  TT= copy (T);
332  indexUpdate (v, s, T.length(), noSubset);
333  if (noSubset) break;
334  }
335  }
336  }
337  s++;
338  if (T.length() < 2*s || T.length() == s)
339  {
341  appendTestMapDown (result, buf, info, source, dest);
342  delete [] v;
343  return result;
344  }
345  for (int i= 0; i < T.length(); i++)
346  v[i]= 0;
347  noSubset= false;
348  }
349  if (T.length() < 2*s)
350  {
352  appendMapDown (result, buf, info, source, dest);
353  }
354 
355  delete [] v;
356  return result;
357 }

◆ extLiftBoundAdaption()

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

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

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

Definition at line 509 of file facFqFactorize.cc.

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

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

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

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

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

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

◆ gcdFreeBasis()

void gcdFreeBasis ( CFFList factors1,
CFFList factors2 
)

gcd free basis of two lists of factors

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

Definition at line 1255 of file facFqFactorize.cc.

1256 {
1257  CanonicalForm g;
1258  int k= factors1.length();
1259  int l= factors2.length();
1260  int n= 0;
1261  int m;
1263  for (CFFListIterator i= factors1; (n < k && i.hasItem()); i++, n++)
1264  {
1265  m= 0;
1266  for (j= factors2; (m < l && j.hasItem()); j++, m++)
1267  {
1268  g= gcd (i.getItem().factor(), j.getItem().factor());
1269  if (degree (g,1) > 0)
1270  {
1271  j.getItem()= CFFactor (j.getItem().factor()/g, j.getItem().exp());
1272  i.getItem()= CFFactor (i.getItem().factor()/g, i.getItem().exp());
1273  factors1.append (CFFactor (g, i.getItem().exp()));
1274  factors2.append (CFFactor (g, j.getItem().exp()));
1275  }
1276  }
1277  }
1278 }

◆ getLeadingCoeffs()

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

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

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

Definition at line 2216 of file facFqFactorize.cc.

2218 {
2220  CFList LCs;
2221  for (int j= 0; j < A.level() - 2; j++)
2222  {
2223  if (!Aeval[j].isEmpty())
2224  {
2225  LCs= CFList();
2226  for (iter= Aeval[j]; iter.hasItem(); iter++)
2227  LCs.append (LC (iter.getItem(), 1));
2228  //normalize (LCs);
2229  Aeval[j]= LCs;
2230  }
2231  }
2232 }

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

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

◆ henselLiftAndEarly()

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

hensel Lifting and early factor detection

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

Definition at line 972 of file facFqFactorize.cc.

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

◆ LCHeuristic()

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

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

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

Definition at line 2598 of file facFqFactorize.cc.

2602 {
2603  CFListIterator iter, iter2;
2604  int index;
2605  Variable xx;
2606  CFList vars1;
2607  CFFList sqrfMultiplier= sqrFree (LCmultiplier);
2608  if (sqrfMultiplier.getFirst().factor().inCoeffDomain())
2609  sqrfMultiplier.removeFirst();
2610  sqrfMultiplier= sortCFFListByNumOfVars (sqrfMultiplier);
2611  xx= Variable (2);
2612  for (iter= oldBiFactors; iter.hasItem(); iter++)
2613  vars1.append (power (xx, degree (LC (iter.getItem(),1), xx)));
2614  for (int i= 0; i < lengthAeval; i++)
2615  {
2616  if (oldAeval[i].isEmpty())
2617  continue;
2618  xx= oldAeval[i].getFirst().mvar();
2619  iter2= vars1;
2620  for (iter= oldAeval[i]; iter.hasItem(); iter++, iter2++)
2621  iter2.getItem() *= power (xx, degree (LC (iter.getItem(),1), xx));
2622  }
2623  CanonicalForm tmp, quot1, quot2, quot3;
2624  iter2= vars1;
2625  for (iter= leadingCoeffs[lengthAeval-1]; iter.hasItem(); iter++, iter2++)
2626  {
2627  tmp= iter.getItem()/LCmultiplier;
2628  for (int i=1; i <= tmp.level(); i++)
2629  {
2630  if (degree (tmp,i) > 0 && (degree (iter2.getItem(),i) > degree (tmp,i)))
2631  iter2.getItem() /= power (Variable (i), degree (tmp,i));
2632  }
2633  }
2634  int multi;
2635  for (CFFListIterator ii= sqrfMultiplier; ii.hasItem(); ii++)
2636  {
2637  multi= 0;
2638  for (iter= vars1; iter.hasItem(); iter++)
2639  {
2640  tmp= iter.getItem();
2641  while (fdivides (myGetVars (ii.getItem().factor()), tmp))
2642  {
2643  multi++;
2644  tmp /= myGetVars (ii.getItem().factor());
2645  }
2646  }
2647  if (multi == ii.getItem().exp())
2648  {
2649  index= 1;
2650  for (iter= vars1; iter.hasItem(); iter++, index++)
2651  {
2652  while (fdivides (myGetVars (ii.getItem().factor()), iter.getItem()))
2653  {
2654  int index2= 1;
2655  for (iter2= leadingCoeffs[lengthAeval-1]; iter2.hasItem();iter2++,
2656  index2++)
2657  {
2658  if (index2 == index)
2659  continue;
2660  else
2661  {
2662  tmp= ii.getItem().factor();
2663  if (fdivides (tmp, iter2.getItem(), quot1))
2664  {
2665  CFListIterator iter3= evaluation;
2666  for (int jj= A.level(); jj > 2; jj--, iter3++)
2667  tmp= tmp (iter3.getItem(), jj);
2668  if (!tmp.inCoeffDomain())
2669  {
2670  int index3= 1;
2671  for (iter3= biFactors; iter3.hasItem(); iter3++, index3++)
2672  {
2673  if (index3 == index2)
2674  {
2675  if (fdivides (tmp, iter3.getItem(), quot2))
2676  {
2677  if (fdivides (ii.getItem().factor(), A, quot3))
2678  {
2679  A = quot3;
2680  iter2.getItem() = quot2;
2681  iter3.getItem() = quot3;
2682  iter3.getItem() /= Lc (iter3.getItem());
2683  break;
2684  }
2685  }
2686  }
2687  }
2688  }
2689  }
2690  }
2691  }
2692  iter.getItem() /= getVars (ii.getItem().factor());
2693  }
2694  }
2695  }
2696  else
2697  {
2698  index= 1;
2699  for (iter= vars1; iter.hasItem(); iter++, index++)
2700  {
2701  if (!fdivides (myGetVars (ii.getItem().factor()), iter.getItem()))
2702  {
2703  int index2= 1;
2704  for (iter2= leadingCoeffs[lengthAeval-1];iter2.hasItem();iter2++,
2705  index2++)
2706  {
2707  if (index2 == index)
2708  {
2709  tmp= power (ii.getItem().factor(), ii.getItem().exp());
2710  if (fdivides (tmp, A, quot1))
2711  {
2712  if (fdivides (tmp, iter2.getItem()))
2713  {
2714  CFListIterator iter3= evaluation;
2715  for (int jj= A.level(); jj > 2; jj--, iter3++)
2716  tmp= tmp (iter3.getItem(), jj);
2717  if (!tmp.inCoeffDomain())
2718  {
2719  int index3= 1;
2720  for (iter3= biFactors; iter3.hasItem(); iter3++, index3++)
2721  {
2722  if (index3 == index2)
2723  {
2724  if (fdivides (tmp, iter3.getItem(), quot3))
2725  {
2726  A = quot1;
2727  iter2.getItem() = quot2;
2728  iter3.getItem() = quot3;
2729  iter3.getItem() /= Lc (iter3.getItem());
2730  break;
2731  }
2732  }
2733  }
2734  }
2735  }
2736  }
2737  }
2738  }
2739  }
2740  }
2741  }
2742  }
2743 }

◆ LCHeuristic2()

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

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

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

Definition at line 2762 of file facFqFactorize.cc.

2765 {
2766  CanonicalForm cont;
2767  int index= 1;
2768  CFListIterator iter2;
2769  for (CFListIterator iter= factors; iter.hasItem(); iter++, index++)
2770  {
2771  cont= content (iter.getItem(), 1);
2772  cont= gcd (cont, LCmultiplier);
2773  contents.append (cont);
2774  if (cont.inCoeffDomain()) // trivial content->LCmultiplier needs to go there
2775  {
2776  foundTrueMultiplier= true;
2777  int index2= 1;
2778  for (iter2= leadingCoeffs; iter2.hasItem(); iter2++, index2++)
2779  {
2780  if (index2 == index)
2781  continue;
2782  iter2.getItem() /= LCmultiplier;
2783  }
2784  break;
2785  }
2786  else
2787  LCs.append (LC (iter.getItem()/cont, 1));
2788  }
2789 }

◆ LCHeuristic3()

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

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

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

Definition at line 2792 of file facFqFactorize.cc.

2796 {
2797  int index= 1;
2798  CFListIterator iter, iter2= factors;
2799  for (iter= contents; iter.hasItem(); iter++, iter2++, index++)
2800  {
2801  if (fdivides (iter.getItem(), LCmultiplier))
2802  {
2803  if ((LCmultiplier/iter.getItem()).inCoeffDomain() &&
2804  !isOnlyLeadingCoeff(iter2.getItem())) //content divides LCmultiplier completely and factor consists of more terms than just the leading coeff
2805  {
2806  Variable xx= Variable (2);
2807  CanonicalForm vars;
2808  vars= power (xx, degree (LC (getItem(oldBiFactors, index),1),
2809  xx));
2810  for (int i= 0; i < lengthAeval; i++)
2811  {
2812  if (oldAeval[i].isEmpty())
2813  continue;
2814  xx= oldAeval[i].getFirst().mvar();
2815  vars *= power (xx, degree (LC (getItem(oldAeval[i], index),1),
2816  xx));
2817  }
2818  if (vars.level() <= 2)
2819  {
2820  int index2= 1;
2821  for (CFListIterator iter3= leadingCoeffs[lengthAeval-1];
2822  iter3.hasItem(); iter3++, index2++)
2823  {
2824  if (index2 == index)
2825  {
2826  iter3.getItem() /= LCmultiplier;
2827  break;
2828  }
2829  }
2830  A /= LCmultiplier;
2831  foundMultiplier= true;
2832  iter.getItem()= 1;
2833  }
2834  }
2835  }
2836  }
2837 }

◆ LCHeuristic4()

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

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

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

Definition at line 2840 of file facFqFactorize.cc.

2845 {
2846  int index=1;
2847  CFListIterator iter, iter2= factors;
2848  for (iter= contents; iter.hasItem(); iter++, iter2++, index++)
2849  {
2850  if (!iter.getItem().isOne() &&
2851  fdivides (iter.getItem(), LCmultiplier))
2852  {
2853  if (!isOnlyLeadingCoeff (iter2.getItem())) // factor is more than just leading coeff
2854  {
2855  int index2= 1;
2856  for (iter2= leadingCoeffs[lengthAeval-1]; iter2.hasItem();
2857  iter2++, index2++)
2858  {
2859  if (index2 == index)
2860  {
2861  iter2.getItem() /= iter.getItem();
2862  foundMultiplier= true;
2863  break;
2864  }
2865  }
2866  A /= iter.getItem();
2867  LCmultiplier /= iter.getItem();
2868  iter.getItem()= 1;
2869  }
2870  else if (fdivides (getVars (LCmultiplier), testVars))//factor consists of just leading coeff
2871  {
2872  Variable xx= Variable (2);
2873  CanonicalForm vars;
2874  vars= power (xx, degree (LC (getItem(oldBiFactors, index),1),
2875  xx));
2876  for (int i= 0; i < lengthAeval; i++)
2877  {
2878  if (oldAeval[i].isEmpty())
2879  continue;
2880  xx= oldAeval[i].getFirst().mvar();
2881  vars *= power (xx, degree (LC (getItem(oldAeval[i], index),1),
2882  xx));
2883  }
2884  if (myGetVars(content(getItem(leadingCoeffs[lengthAeval-1],index),1))
2885  /myGetVars (LCmultiplier) == vars)
2886  {
2887  int index2= 1;
2888  for (iter2= leadingCoeffs[lengthAeval-1]; iter2.hasItem();
2889  iter2++, index2++)
2890  {
2891  if (index2 == index)
2892  {
2893  iter2.getItem() /= LCmultiplier;
2894  foundMultiplier= true;
2895  break;
2896  }
2897  }
2898  A /= LCmultiplier;
2899  iter.getItem()= 1;
2900  }
2901  }
2902  }
2903  }
2904 }

◆ LCHeuristicCheck()

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

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

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

Definition at line 2746 of file facFqFactorize.cc.

2749 {
2750  CanonicalForm pLCs= prod (LCs);
2751  if (fdivides (pLCs, LC (oldA,1)) && (LC(oldA,1)/pLCs).inCoeffDomain()) // check if the product of the lead coeffs of the primitive factors equals the lead coeff of the old A
2752  {
2753  A= oldA;
2754  CFListIterator iter2= leadingCoeffs;
2755  for (CFListIterator iter= contents; iter.hasItem(); iter++, iter2++)
2756  iter2.getItem() /= iter.getItem();
2757  foundTrueMultiplier= true;
2758  }
2759 }

◆ lcmContent()

CanonicalForm lcmContent ( const CanonicalForm A,
CFList contentAi 
)

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

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

Definition at line 954 of file facFqFactorize.cc.

955 {
956  int i= A.level();
958  contentAi.append (content (buf, i));
959  buf /= contentAi.getLast();
960  contentAi.append (content (buf, i - 1));
961  CanonicalForm result= lcm (contentAi.getFirst(), contentAi.getLast());
962  for (i= i - 2; i > 0; i--)
963  {
964  contentAi.append (content (buf, i));
965  buf /= contentAi.getLast();
966  result= lcm (result, contentAi.getLast());
967  }
968  return result;
969 }

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

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

◆ myCompress()

CanonicalForm myCompress ( const CanonicalForm F,
CFMap N 
)

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

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

Definition at line 136 of file facFqFactorize.cc.

137 {
138  int n= F.level();
139  int * degsf= NEW_ARRAY(int,n + 1);
140  int ** swap= new int* [n + 1];
141  for (int i= 0; i <= n; i++)
142  {
143  degsf[i]= 0;
144  swap [i]= new int [3];
145  swap [i] [0]= 0;
146  swap [i] [1]= 0;
147  swap [i] [2]= 0;
148  }
149  int i= 1;
150  n= 1;
151  degsf= degrees (F, degsf);
152 
154  while ( i <= F.level() )
155  {
156  while( degsf[i] == 0 ) i++;
157  swap[n][0]= i;
158  swap[n][1]= size (LC (F,i));
159  swap[n][2]= degsf [i];
160  if (i != n)
162  n++; i++;
163  }
164 
165  int buf1, buf2, buf3;
166  n--;
167 
168  for (i= 1; i < n; i++)
169  {
170  for (int j= 1; j < n - i + 1; j++)
171  {
172  if (swap[j][1] > swap[j + 1][1])
173  {
174  buf1= swap [j + 1] [0];
175  buf2= swap [j + 1] [1];
176  buf3= swap [j + 1] [2];
177  swap[j + 1] [0]= swap[j] [0];
178  swap[j + 1] [1]= swap[j] [1];
179  swap[j + 1] [2]= swap[j] [2];
180  swap[j][0]= buf1;
181  swap[j][1]= buf2;
182  swap[j][2]= buf3;
183  result= swapvar (result, Variable (j + 1), Variable (j));
184  }
185  else if (swap[j][1] == swap[j + 1][1] && swap[j][2] < swap[j + 1][2])
186  {
187  buf1= swap [j + 1] [0];
188  buf2= swap [j + 1] [1];
189  buf3= swap [j + 1] [2];
190  swap[j + 1] [0]= swap[j] [0];
191  swap[j + 1] [1]= swap[j] [1];
192  swap[j + 1] [2]= swap[j] [2];
193  swap[j][0]= buf1;
194  swap[j][1]= buf2;
195  swap[j][2]= buf3;
196  result= swapvar (result, Variable (j + 1), Variable (j));
197  }
198  }
199  }
200 
201  for (i= n; i > 0; i--)
202  {
203  if (i != swap[i] [0])
204  N.newpair (Variable (i), Variable (swap[i] [0]));
205  }
206 
207  for (i= F.level(); i >=0 ; i--)
208  delete [] swap[i];
209  delete [] swap;
210 
212 
213  return result;
214 }

◆ precomputeLeadingCoeff()

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

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

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

Definition at line 1464 of file facFqFactorize.cc.

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

◆ prepareLeadingCoeffs()

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

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

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

Definition at line 2365 of file facFqFactorize.cc.

2368 {
2369  CFList l= leadingCoeffs;
2370  LCs [n-3]= l;
2371  CFListIterator j;
2373  for (int i= n - 1; i > 2; i--, iter++)
2374  {
2375  for (j= l; j.hasItem(); j++)
2376  j.getItem()= j.getItem() (iter.getItem(), i + 1);
2377  LCs [i - 3]= l;
2378  }
2379  l= LCs [0];
2380  for (CFListIterator i= l; i.hasItem(); i++)
2381  i.getItem()= i.getItem() (iter.getItem(), 3);
2382  CFListIterator ii= biFactors;
2383  CFList normalizeFactor;
2384  for (CFListIterator i= l; i.hasItem(); i++, ii++)
2385  normalizeFactor.append (Lc (LC (ii.getItem(), 1))/Lc (i.getItem()));
2386  for (int i= 0; i < n-2; i++)
2387  {
2388  ii= normalizeFactor;
2389  for (j= LCs [i]; j.hasItem(); j++, ii++)
2390  j.getItem() *= ii.getItem();
2391  }
2392 
2394 
2395  CanonicalForm hh= 1/Lc (Aeval.getFirst());
2396 
2397  for (iter= Aeval; iter.hasItem(); iter++)
2398  iter.getItem() *= hh;
2399 
2400  A *= hh;
2401 }

◆ recombination()

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

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

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

Definition at line 2100 of file facFqFactorize.cc.

2102 {
2103  CFList T, S;
2104 
2105  T= factors1;
2106  CFList result;
2108  int * v= new int [T.length()];
2109  for (int i= 0; i < T.length(); i++)
2110  v[i]= 0;
2111  bool nosubset= false;
2112  CFArray TT;
2113  TT= copy (factors1);
2114  int recombinations= 0;
2115  while (T.length() >= 2*s && s <= thres)
2116  {
2117  while (nosubset == false)
2118  {
2119  if (T.length() == s)
2120  {
2121  delete [] v;
2122  if (recombinations == factors2.length() - 1)
2123  result.append (prod (T));
2124  else
2125  result= Union (result, T);
2126  return result;
2127  }
2128  S= subset (v, s, TT, nosubset);
2129  if (nosubset) break;
2130  buf= prodEval (S, evalPoint, x);
2131  buf /= Lc (buf);
2132  if (find (factors2, buf))
2133  {
2134  recombinations++;
2135  T= Difference (T, S);
2136  result.append (prod (S));
2137  TT= copy (T);
2138  indexUpdate (v, s, T.length(), nosubset);
2139  if (nosubset) break;
2140  }
2141  }
2142  s++;
2143  if (T.length() < 2*s || T.length() == s)
2144  {
2145  if (recombinations == factors2.length() - 1)
2146  result.append (prod (T));
2147  else
2148  result= Union (result, T);
2149  delete [] v;
2150  return result;
2151  }
2152  for (int i= 0; i < T.length(); i++)
2153  v[i]= 0;
2154  nosubset= false;
2155  }
2156 
2157  delete [] v;
2158  if (T.length() < 2*s)
2159  {
2160  result= Union (result, T);
2161  return result;
2162  }
2163 
2164  return result;
2165 }

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

2321 {
2322  CFListIterator iter, iter2;
2324  int i;
2325  Variable v;
2326  Variable y= Variable (2);
2327  CFList list;
2328  bool leaveLoop= false;
2329  for (int j= 0; j < A.level() - 2; j++)
2330  {
2331  if (Aeval[j].length() == minFactorsLength)
2332  {
2333  i= A.level();
2334 
2335  for (iter= evaluation; iter.hasItem(); iter++, i--)
2336  {
2337  for (iter2= Aeval[j]; iter2.hasItem(); iter2++)
2338  {
2339  if (i == iter2.getItem().level())
2340  {
2341  evalPoint= iter.getItem();
2342  leaveLoop= true;
2343  break;
2344  }
2345  }
2346  if (leaveLoop)
2347  {
2348  leaveLoop= false;
2349  break;
2350  }
2351  }
2352 
2353  v= Variable (i);
2354  list= buildUniFactors (Aeval[j], evalPoint, v);
2355 
2356  biFactors= recombination (biFactors, list, 1,
2357  biFactors.length() - list.length() + 1,
2358  evaluation.getLast(), y);
2359  return;
2360  }
2361  }
2362 }

◆ sortByUniFactors()

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

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

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

Definition at line 2234 of file facFqFactorize.cc.

2238 {
2240  int i;
2241  CFListIterator iter, iter2;
2242  Variable v;
2243  CFList LCs, buf;
2244  CFArray l;
2245  int pos, index, checklength;
2246  bool leaveLoop=false;
2247 recurse:
2248  for (int j= 0; j < AevalLength; j++)
2249  {
2250  if (!Aeval[j].isEmpty())
2251  {
2252  i= evaluation.length() + 1;
2253  for (iter= evaluation; iter.hasItem(); iter++, i--)
2254  {
2255  for (iter2= Aeval[j]; iter2.hasItem(); iter2++)
2256  {
2257  if (i == iter2.getItem().level())
2258  {
2259  evalPoint= iter.getItem();
2260  leaveLoop= true;
2261  break;
2262  }
2263  }
2264  if (leaveLoop)
2265  {
2266  leaveLoop= false;
2267  break;
2268  }
2269  }
2270 
2271  v= Variable (i);
2272  if (Aeval[j].length() > uniFactors.length())
2273  Aeval[j]= recombination (Aeval[j], uniFactors, 1,
2274  Aeval[j].length() - uniFactors.length() + 1,
2275  evalPoint, v);
2276 
2277  checklength= biFactors.length();
2278  Aeval[j]= checkOneToOne (Aeval[j], uniFactors, biFactors, evalPoint, v);
2279  if (checklength > biFactors.length())
2280  {
2281  uniFactors= buildUniFactors (biFactors, evaluation.getLast(),
2282  Variable (2));
2283  goto recurse;
2284  }
2285 
2287  l= CFArray (uniFactors.length());
2288  index= 1;
2289  for (iter= buf; iter.hasItem(); iter++, index++)
2290  {
2291  pos= findItem (uniFactors, iter.getItem());
2292  if (pos)
2293  l[pos-1]= getItem (Aeval[j], index);
2294  }
2295  buf= conv (l);
2296  Aeval [j]= buf;
2297 
2299  }
2300  }
2301 }

◆ 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 38 of file facFqFactorize.h.

prodMod
CanonicalForm prodMod(const CFList &L, const CanonicalForm &M)
product of all elements in L modulo M via divide-and-conquer.
Definition: facMul.cc:3047
Matrix
Definition: ftmpl_matrix.h:20
ExtensionInfo::getGFDegree
int getGFDegree() const
getter
Definition: ExtensionInfo.h:139
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 test...
Definition: facFqFactorize.cc:605
myContent
static CanonicalForm myContent(const CanonicalForm &F)
Definition: facFqFactorize.cc:61
nonMonicHenselLift
CFList nonMonicHenselLift(const CFList &F, const CFList &factors, const CFList &LCs, CFList &diophant, CFArray &Pi, CFMatrix &M, int lOld, int &lNew, const CFList &MOD, bool &noOneToOne)
Definition: facHensel.cc:2709
FpSqrf
CFFList FpSqrf(const CanonicalForm &F, bool sort=true)
squarefree factorization over . If input is not monic, the leading coefficient is dropped
Definition: facFqSquarefree.h:38
FFRandom
generate random elements in F_p
Definition: cf_random.h:43
ExtensionInfo::getBeta
Variable getBeta() const
getter
Definition: ExtensionInfo.h:118
reverseShift
CanonicalForm reverseShift(const CanonicalForm &F, const CFList &evaluation, int l)
reverse shifting the evaluation point to zero
Definition: facFqFactorizeUtil.cc:148
gcd_deriv
CanonicalForm gcd_deriv
Definition: facFactorize.cc:59
j
int j
Definition: facHensel.cc:105
ExtensionInfo::isInExtension
bool isInExtension() const
getter
Definition: ExtensionInfo.h:153
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 test...
Definition: facFqFactorize.cc:656
k
int k
Definition: cfEzgcd.cc:92
x
Variable x
Definition: cfModGcd.cc:4023
y
const CanonicalForm int const CFList const Variable & y
Definition: facAbsFact.cc:57
recoverFactors
CFList recoverFactors(const CanonicalForm &F, const CFList &factors)
divides factors by their content wrt. Variable(1) and checks if these polys divide F
Definition: facFqFactorizeUtil.cc:238
result
return result
Definition: facAbsBiFact.cc:76
recombination
CFList recombination(const CFList &factors1, const CFList &factors2, int s, int thres, const CanonicalForm &evalPoint, const Variable &x)
recombination of bivariate factors factors1 s. t. the result evaluated at evalPoint coincides with fa...
Definition: facFqFactorize.cc:2100
GFBiSqrfFactorize
CFList GFBiSqrfFactorize(const CanonicalForm &G)
factorize a squarefree bivariate polynomial over GF
Definition: facFqBivar.h:164
evaluateAtEval
CFList evaluateAtEval(const CanonicalForm &F, const CFArray &eval)
evaluate F at evaluation
Definition: facFqFactorizeUtil.cc:206
CFArray
Array< CanonicalForm > CFArray
Definition: canonicalform.h:390
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.
Definition: facFqFactorize.cc:445
FqFactorize
CFFList FqFactorize(const CanonicalForm &G, const Variable &alpha, bool substCheck=true)
factorize a multivariate polynomial over
Definition: facFqFactorize.h:184
degrees
int * degrees(const CanonicalForm &f, int *degs=0)
int * degrees ( const CanonicalForm & f, int * degs )
Definition: cf_ops.cc:493
FqSqrf
CFFList FqSqrf(const CanonicalForm &F, const Variable &alpha, bool sort=true)
squarefree factorization over . If input is not monic, the leading coefficient is dropped
Definition: facFqSquarefree.h:77
DELETE_ARRAY
#define DELETE_ARRAY(P)
Definition: cf_defs.h:49
prod
fq_nmod_poly_t prod
Definition: facHensel.cc:95
LCFeval
CFList LCFeval
Definition: facFactorize.cc:54
CFFactory::gettype
static int gettype()
Definition: cf_factory.h:28
CFMap
class CFMap
Definition: cf_map.h:84
sortList
void sortList(CFList &list, const Variable &x)
sort a list of polynomials by their degree in x.
Definition: facHensel.cc:441
isOnlyLeadingCoeff
bool isOnlyLeadingCoeff(const CanonicalForm &F)
check if F consists of more than just the leading coeff wrt. Variable (1)
Definition: facFqFactorizeUtil.cc:162
power
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
Definition: canonicalform.cc:1837
length
static BOOLEAN length(leftv result, leftv arg)
Definition: interval.cc:263
appendTestMapDown
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
Definition: facFqBivarUtil.cc:223
AlgExtRandomF
generate random elements in F_p(alpha)
Definition: cf_random.h:70
GFRandom::generate
CanonicalForm generate() const
Definition: cf_random.cc:66
g
g
Definition: cfModGcd.cc:4031
bad
bool bad
Definition: facFactorize.cc:65
level
int level(const CanonicalForm &f)
Definition: canonicalform.h:324
mod
CF_NO_INLINE CanonicalForm mod(const CanonicalForm &, const CanonicalForm &)
Definition: cf_inline.cc:564
rootOf
Variable rootOf(const CanonicalForm &, char name='@')
returns a symbolic root of polynomial with name name Use it to define algebraic variables
Definition: variable.cc:162
gf_mipo
CanonicalForm gf_mipo
Definition: gfops.cc:56
CFMatrix
Matrix< CanonicalForm > CFMatrix
Definition: canonicalform.h:391
N
const CanonicalForm CFMap CFMap & N
Definition: cfEzgcd.cc:48
randomIrredpoly
CanonicalForm randomIrredpoly(int i, const Variable &x)
computes a random monic irreducible univariate polynomial in x over Fp of degree i via NTL
Definition: cf_irred.cc:42
getItem
CanonicalForm getItem(const CFList &list, const int &pos)
helper function
Definition: cf_map_ext.cc:49
iter
CFFListIterator iter
Definition: facAbsBiFact.cc:54
FqBiSqrfFactorize
CFList FqBiSqrfFactorize(const CanonicalForm &G, const Variable &alpha)
factorize a squarefree bivariate polynomial over .
Definition: facFqBivar.h:150
GFBiFactorize
CFFList GFBiFactorize(const CanonicalForm &G, bool substCheck=true)
factorize a bivariate polynomial over GF
Definition: facFqBivar.h:432
gf_name
char gf_name
Definition: gfops.cc:52
primitiveElement
CanonicalForm primitiveElement(const Variable &alpha, Variable &beta, bool &fail)
determine a primitive element of , is a primitive element of a field which is isomorphic to
Definition: cf_map_ext.cc:310
deriv
CanonicalForm deriv(const CanonicalForm &f, const Variable &x)
Definition: canonicalform.h:339
w
const CanonicalForm & w
Definition: facAbsFact.cc:55
getCharacteristic
int getCharacteristic()
Definition: cf_char.cc:51
CxxTest::delta
bool delta(X x, Y y, D d)
Definition: TestSuite.h:160
CanonicalForm
factory's main class
Definition: canonicalform.h:77
found
bool found
Definition: facFactorize.cc:56
evaluateAtZero
CFList evaluateAtZero(const CanonicalForm &F)
evaluate F successively n-2 at 0
Definition: facFqFactorizeUtil.cc:193
reverseSubst
CanonicalForm reverseSubst(const CanonicalForm &F, const int d, const Variable &x)
reverse a substitution x^d->x
Definition: facFqBivarUtil.cc:1295
minFactorsLength
CFList int & minFactorsLength
[in,out] minimal length of bivariate factors
Definition: facFactorize.h:31
evaluation
const CanonicalForm int const CFList & evaluation
Definition: facAbsFact.cc:55
distributeContent
CFList distributeContent(const CFList &L, const CFList *differentSecondVarFactors, int length)
distribute content
Definition: facFqFactorize.cc:1281
CanonicalForm::isOne
CF_NO_INLINE bool isOne() const
CF_INLINE bool CanonicalForm::isOne, isZero () const.
Definition: cf_inline.cc:354
GaloisFieldDomain
#define GaloisFieldDomain
Definition: cf_defs.h:22
factors2
const CFList & factors2
Definition: facFqBivarUtil.cc:42
buildUniFactors
CFList buildUniFactors(const CFList &biFactors, const CanonicalForm &evalPoint, const Variable &y)
plug in evalPoint for y in a list of polys
Definition: facFqFactorize.cc:2304
mapUp
static CanonicalForm mapUp(const Variable &alpha, const Variable &beta)
and is a primitive element, returns the image of
Definition: cf_map_ext.cc:67
i
int i
Definition: cfEzgcd.cc:125
Lc
CanonicalForm Lc(const CanonicalForm &f)
Definition: canonicalform.h:300
swapvar
CanonicalForm swapvar(const CanonicalForm &, const Variable &, const Variable &)
swapvar() - swap variables x1 and x2 in f.
Definition: cf_ops.cc:168
Array< CanonicalForm >
getMipo
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
Definition: variable.cc:207
nonMonicHenselLift12
void nonMonicHenselLift12(const CanonicalForm &F, CFList &factors, int l, CFArray &Pi, CFList &diophant, CFMatrix &M, const CFArray &LCs, bool sort)
Hensel lifting from univariate to bivariate, factors need not to be monic.
Definition: facHensel.cc:2018
ASSERT
#define ASSERT(expression, message)
Definition: cf_assert.h:99
Difference
template List< Variable > Difference(const List< Variable > &, const List< Variable > &)
M
#define M
Definition: sirandom.c:24
buf
int status int void * buf
Definition: si_signals.h:58
content
CanonicalForm content(const CanonicalForm &)
CanonicalForm content ( const CanonicalForm & f )
Definition: cf_gcd.cc:175
Array::size
int size() const
Definition: ftmpl_array.cc:92
TIMING_START
TIMING_START(fac_alg_resultant)
sortCFFListByNumOfVars
CFFList sortCFFListByNumOfVars(CFFList &F)
sort CFFList by the number variables in a factor
Definition: facFqFactorizeUtil.cc:186
ExtensionInfo::getGamma
CanonicalForm getGamma() const
getter
Definition: ExtensionInfo.h:125
getVars
CanonicalForm getVars(const CanonicalForm &f)
CanonicalForm getVars ( const CanonicalForm & f )
Definition: cf_ops.cc:350
Aeval
CFList *& Aeval
<[in] poly
Definition: facFactorize.h:31
evalPoint
static void evalPoint(const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &FEval, CanonicalForm &GEval, CFGenerator &evalPoint)
Definition: cfModResultant.cc:311
alpha
Variable alpha
Definition: facAbsBiFact.cc:52
conv
CFList conv(const CFArray &A)
Definition: facFqFactorize.cc:2207
List::isEmpty
int isEmpty() const
Definition: ftmpl_list.cc:267
T
static jList * T
Definition: janet.cc:31
h
static Poly * h
Definition: janet.cc:972
henselLiftResume
void henselLiftResume(const CanonicalForm &F, CFList &factors, int start, int end, CFArray &Pi, const CFList &diophant, CFMatrix &M, const CFList &MOD)
resume Hensel lifting.
Definition: facHensel.cc:1694
setCharacteristic
void setCharacteristic(int c)
Definition: cf_char.cc:23
compress
CanonicalForm compress(const CanonicalForm &f, CFMap &m)
CanonicalForm compress ( const CanonicalForm & f, CFMap & m )
Definition: cf_map.cc:210
LcF
CanonicalForm LcF
Definition: facAbsBiFact.cc:51
size
int size(const CanonicalForm &f, const Variable &v)
int size ( const CanonicalForm & f, const Variable & v )
Definition: cf_ops.cc:600
LucksWangSparseHeuristic
int LucksWangSparseHeuristic(const CanonicalForm &F, const CFList &factors, int level, const CFList &leadingCoeffs, CFList &result)
sparse heuristic lifting by Wang and Lucks
Definition: facSparseHensel.cc:26
ExtensionInfo::getGFName
char getGFName() const
getter
Definition: ExtensionInfo.h:146
prune
void prune(Variable &alpha)
Definition: variable.cc:261
FpBiFactorize
CFFList FpBiFactorize(const CanonicalForm &G, bool substCheck=true)
factorize a bivariate polynomial over
Definition: facFqBivar.h:180
isInExtension
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)
Definition: facFqBivarUtil.cc:184
tmin
template CanonicalForm tmin(const CanonicalForm &, const CanonicalForm &)
buf1
CanonicalForm buf1
Definition: facFqBivar.cc:71
Variable::level
int level() const
Definition: factory.h:134
henselLift
CFList henselLift(const CFList &F, const CFList &factors, const CFList &MOD, CFList &diophant, CFArray &Pi, CFMatrix &M, int lOld, int lNew)
Hensel lifting.
Definition: facHensel.cc:1719
eval
CFList & eval
Definition: facFactorize.cc:48
GFRandom
generate random elements in GF
Definition: cf_random.h:31
ListIterator::hasItem
int hasItem()
Definition: ftmpl_list.cc:439
fdivides
bool fdivides(const CanonicalForm &f, const CanonicalForm &g)
bool fdivides ( const CanonicalForm & f, const CanonicalForm & g )
Definition: cf_algorithm.cc:338
beta
Variable beta
Definition: facAbsFact.cc:99
ExtensionInfo::getDelta
CanonicalForm getDelta() const
getter
Definition: ExtensionInfo.h:132
List::removeFirst
void removeFirst()
Definition: ftmpl_list.cc:287
FqBiFactorize
CFFList FqBiFactorize(const CanonicalForm &G, const Variable &alpha, bool substCheck=true)
factorize a bivariate polynomial over
Definition: facFqBivar.h:305
substituteCheck
int substituteCheck(const CanonicalForm &F, const Variable &x)
check if a substitution x^n->x is possible
Definition: facFqBivarUtil.cc:1089
List::getFirst
T getFirst() const
Definition: ftmpl_list.cc:279
getGFDegree
int getGFDegree()
Definition: cf_char.cc:56
Factor
Definition: ftmpl_factor.h:18
tmax
template CanonicalForm tmax(const CanonicalForm &, const CanonicalForm &)
deriv_x
CanonicalForm deriv_x
Definition: facFactorize.cc:59
multiFactorize
CFList multiFactorize(const CanonicalForm &F, const Variable &v)
Factorization over Q (a)
Definition: facFactorize.cc:194
mulMod
CanonicalForm mulMod(const CanonicalForm &A, const CanonicalForm &B, const CFList &MOD)
Karatsuba style modular multiplication for multivariate polynomials.
Definition: facMul.cc:2947
CanonicalForm::inCoeffDomain
bool inCoeffDomain() const
Definition: canonicalform.cc:119
indexUpdate
void indexUpdate(int index[], const int &subsetSize, const int &setSize, bool &noSubset)
update index
Definition: facFqBivarUtil.cc:373
List::length
int length() const
Definition: ftmpl_list.cc:273
testFactors
int testFactors(const CanonicalForm &G, const CFList &uniFactors, const Variable &alpha, CanonicalForm &sqrfPartF, CFList &factors, CFFList *&bufSqrfFactors, CFList &evalSqrfPartF, const CFArray &evalPoint)
Definition: facFqFactorize.cc:1371
multiFactorize
CFList multiFactorize(const CanonicalForm &F, const ExtensionInfo &info)
Definition: facFqFactorize.cc:2910
FpBiSqrfFactorize
CFList FpBiSqrfFactorize(const CanonicalForm &G)
factorize a squarefree bivariate polynomial over .
Definition: facFqBivar.h:137
List::removeLast
void removeLast()
Definition: ftmpl_list.cc:317
TIMING_END_AND_PRINT
TIMING_END_AND_PRINT(fac_alg_resultant, "time to compute resultant0: ")
degsf
int * degsf
Definition: cfEzgcd.cc:52
FpFactorize
CFFList FpFactorize(const CanonicalForm &G, bool substCheck=true)
factorize a multivariate polynomial over
Definition: facFqFactorize.h:101
Variable
factory's class for variables
Definition: factory.h:117
ListIterator::getItem
T & getItem() const
Definition: ftmpl_list.cc:431
bound
static CanonicalForm bound(const CFMatrix &M)
Definition: cf_linsys.cc:460
getNumVars
int getNumVars(const CanonicalForm &f)
int getNumVars ( const CanonicalForm & f )
Definition: cf_ops.cc:314
prodEval
static CanonicalForm prodEval(const CFList &l, const CanonicalForm &evalPoint, const Variable &v)
Definition: facFqFactorize.cc:1998
CanonicalForm::mvar
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
Definition: canonicalform.cc:560
ExtensionInfo
Definition: ExtensionInfo.h:50
mapPrimElem
CanonicalForm mapPrimElem(const CanonicalForm &primElem, const Variable &alpha, const Variable &beta)
compute the image of a primitive element of in . We assume .
Definition: cf_map_ext.cc:377
LC
CanonicalForm LC(const CanonicalForm &f)
Definition: canonicalform.h:303
findItem
int findItem(const CFList &list, const CanonicalForm &item)
helper function
Definition: cf_map_ext.cc:37
appendMapDown
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
Definition: facFqBivarUtil.cc:267
GFSqrf
CFFList GFSqrf(const CanonicalForm &F, bool sort=true)
squarefree factorization over GF. If input is not monic, the leading coefficient is dropped
Definition: facFqSquarefree.h:116
pow
Rational pow(const Rational &a, int e)
Definition: GMPrat.cc:414
FFRandom::generate
CanonicalForm generate() const
Definition: cf_random.cc:56
m
int m
Definition: cfEzgcd.cc:121
sqrFree
CFFList sqrFree(const CanonicalForm &f, bool sort=false)
squarefree factorization
Definition: cf_factor.cc:757
find
template bool find(const List< CanonicalForm > &, const CanonicalForm &)
l
int l
Definition: cfEzgcd.cc:93
myGetVars
CanonicalForm myGetVars(const CanonicalForm &F)
like getVars but including multiplicities
Definition: facFqFactorizeUtil.cc:168
lcm
int lcm(unsigned long *l, unsigned long *a, unsigned long *b, unsigned long p, int dega, int degb)
Definition: minpoly.cc:709
contentx
CanonicalForm contentx
Definition: facFactorize.cc:129
GFFactorize
CFFList GFFactorize(const CanonicalForm &G, bool substCheck=true)
factorize a multivariate polynomial over GF
Definition: facFqFactorize.h:267
CanonicalForm::isUnivariate
bool isUnivariate() const
Definition: canonicalform.cc:152
Union
template List< Variable > Union(const List< Variable > &, const List< Variable > &)
gcd
int gcd(int a, int b)
Definition: walkSupport.cc:836
v
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:37
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...
Definition: facFqFactorize.cc:509
p
int p
Definition: cfModGcd.cc:4019
mipo
CanonicalForm mipo
Definition: facAlgExt.cc:57
List
Definition: ftmpl_list.h:20
swap
#define swap(_i, _j)
CHAR_THRESHOLD
#define CHAR_THRESHOLD
Definition: facFqFactorize.cc:738
Falpha2GFRep
CanonicalForm Falpha2GFRep(const CanonicalForm &F)
change representation by residue classes modulo a Conway polynomial to representation by primitive el...
Definition: cf_map_ext.cc:170
CanonicalForm::mapinto
CanonicalForm mapinto() const
Definition: canonicalform.cc:206
s
const CanonicalForm int s
Definition: facAbsFact.cc:55
CFList
List< CanonicalForm > CFList
Definition: canonicalform.h:388
count
int status int void size_t count
Definition: si_signals.h:58
subset
void subset(std::vector< int > &arr, int size, int left, int index, std::vector< int > &l, std::vector< std::vector< int > > &L)
Definition: gitfan.cc:544
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,...
Definition: facFqFactorize.cc:1464
GF2FalphaRep
CanonicalForm GF2FalphaRep(const CanonicalForm &F, const Variable &alpha)
changes representation by primitive element to representation by residue classes modulo a Conway poly...
Definition: cf_map_ext.cc:162
tmp2
CFList tmp2
Definition: facFqBivar.cc:70
copy
CFArray copy(const CFList &list)
write elements of list into an array
Definition: facFqBivarUtil.cc:364
ExtensionInfo::getAlpha
Variable getAlpha() const
getter
Definition: ExtensionInfo.h:111
GFMapUp
CanonicalForm GFMapUp(const CanonicalForm &F, int k)
maps a polynomial over to a polynomial over , d needs to be a multiple of k
Definition: cf_map_ext.cc:207
G
static TreeM * G
Definition: janet.cc:32
CanonicalForm::level
int level() const
level() returns the level of CO.
Definition: canonicalform.cc:543
CFFactor
Factor< CanonicalForm > CFFactor
Definition: canonicalform.h:385
List::append
void append(const T &)
Definition: ftmpl_list.cc:256
checkOneToOne
CFList checkOneToOne(const CFList &factors1, const CFList &factors2, CFList &factors3, const CanonicalForm &evalPoint, const Variable &x)
check if univariate factors factors2 of factors3 coincide with univariate factors of factors1 and rec...
Definition: facFqFactorize.cc:2032
subst
CanonicalForm subst(const CanonicalForm &f, const CFList &a, const CFList &b, const CanonicalForm &Rstar, bool isFunctionField)
Definition: facAlgFuncUtil.cc:120
index
static int index(p_Length length, p_Ord ord)
Definition: p_Procs_Impl.h:585
A
#define A
Definition: sirandom.c:23
info
const ExtensionInfo & info
< [in] sqrfree poly
Definition: facFqFactorize.h:38
buf2
CanonicalForm buf2
Definition: facFqBivar.cc:71
degree
int degree(const CanonicalForm &f)
Definition: canonicalform.h:309
List::insert
void insert(const T &)
Definition: ftmpl_list.cc:193
LCF
CanonicalForm LCF
Definition: facFactorize.cc:53
shift2Zero
CanonicalForm shift2Zero(const CanonicalForm &F, CFList &Feval, const CFList &evaluation, int l)
shift evaluation point to zero
Definition: facFqFactorizeUtil.cc:131
List::getLast
T getLast() const
Definition: ftmpl_list.cc:309
henselLift23
CFList henselLift23(const CFList &eval, const CFList &factors, int *l, CFList &diophant, CFArray &Pi, CFMatrix &M)
Hensel lifting from bivariate to trivariate.
Definition: facHensel.cc:1653
chooseExtension
static Variable chooseExtension(const Variable &alpha)
Definition: cfModGcd.cc:422
NEW_ARRAY
#define NEW_ARRAY(T, N)
Definition: cf_defs.h:48
mapDown
static CanonicalForm mapDown(const CanonicalForm &F, const Variable &alpha, const CanonicalForm &G, CFList &source, CFList &dest)
the CanonicalForm G is the output of map_up, returns F considered as an element over ,...
Definition: cf_map_ext.cc:90
ListIterator
Definition: ftmpl_list.h:17