My Project
Functions
facFqBivar.h File Reference

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

#include "timing.h"
#include "cf_assert.h"
#include "facFqBivarUtil.h"
#include "DegreePattern.h"
#include "ExtensionInfo.h"
#include "cf_util.h"
#include "facFqSquarefree.h"
#include "cf_map.h"
#include "cfNewtonPolygon.h"
#include "fac_util.h"
#include "cf_algorithm.h"

Go to the source code of this file.

Functions

 TIMING_DEFINE_PRINT (fac_fq_bi_sqrf) TIMING_DEFINE_PRINT(fac_fq_bi_factor_sqrf) static const double log2exp
 
CFList biFactorize (const CanonicalForm &F, const ExtensionInfo &info)
 Factorization of a squarefree bivariate polynomials over an arbitrary finite field, information on the current field we work over is in info. info may also contain information about the initial field if initial and current field do not coincide. In this case the current field is an extension of the initial field and the factors returned are factors of F over the initial field. More...
 
CFList biSqrfFactorizeHelper (const CanonicalForm &G, const ExtensionInfo &info)
 
CFList FpBiSqrfFactorize (const CanonicalForm &G)
 factorize a squarefree bivariate polynomial over $ F_{p} $. More...
 
CFList FqBiSqrfFactorize (const CanonicalForm &G, const Variable &alpha)
 factorize a squarefree bivariate polynomial over $ F_{p}(\alpha ) $. More...
 
CFList GFBiSqrfFactorize (const CanonicalForm &G)
 factorize a squarefree bivariate polynomial over GF More...
 
CFFList FpBiFactorize (const CanonicalForm &G, bool substCheck=true)
 factorize a bivariate polynomial over $ F_{p} $ More...
 
CFFList FqBiFactorize (const CanonicalForm &G, const Variable &alpha, bool substCheck=true)
 factorize a bivariate polynomial over $ F_{p}(\alpha ) $ More...
 
CFFList GFBiFactorize (const CanonicalForm &G, bool substCheck=true)
 factorize a bivariate polynomial over GF More...
 
CanonicalForm prodMod0 (const CFList &L, const CanonicalForm &M, const modpk &b=modpk())
 $ \prod_{f\in L} {f (0, x)} \ mod\ M $ via divide-and-conquer More...
 
CanonicalForm evalPoint (const CanonicalForm &F, CanonicalForm &eval, const Variable &alpha, CFList &list, const bool &GF, bool &fail)
 find an evaluation point p, s.t. F(p,y) is squarefree and $ deg_{y} (F(p,y))= deg_{y} (F(x,y)) $. More...
 
CFList uniFactorizer (const CanonicalForm &A, const Variable &alpha, const bool &GF)
 Univariate factorization of squarefree monic polys over finite fields via NTL. If the characteristic is even special GF2 routines of NTL are used. More...
 
CFList extFactorRecombination (CFList &factors, CanonicalForm &F, const CanonicalForm &M, const ExtensionInfo &info, DegreePattern &degs, const CanonicalForm &eval, int s, int thres)
 naive factor recombination over an extension of the initial field. Uses precomputed data to exclude combinations that are not possible. More...
 
CFList factorRecombination (CFList &factors, CanonicalForm &F, const CanonicalForm &M, DegreePattern &degs, const CanonicalForm &eval, int s, int thres, const modpk &b=modpk(), const CanonicalForm &den=1)
 naive factor recombination. Uses precomputed data to exclude combinations that are not possible. More...
 
Variable chooseExtension (const Variable &alpha, const Variable &beta, int k)
 chooses a field extension. More...
 
int * getLiftPrecisions (const CanonicalForm &F, int &sizeOfOutput, int degreeLC)
 compute lifting precisions from the shape of the Newton polygon of F More...
 
void earlyFactorDetection (CFList &reconstructedFactors, CanonicalForm &F, CFList &factors, int &adaptedLiftBound, int *&factorsFoundIndex, DegreePattern &degs, bool &success, int deg, const CanonicalForm &eval, const modpk &b=modpk())
 detects factors of F at stage deg of Hensel lifting. No combinations of more than one factor are tested. Lift bound and possible degree pattern are updated. More...
 
void extEarlyFactorDetection (CFList &reconstructedFactors, CanonicalForm &F, CFList &factors, int &adaptedLiftBound, int *&factorsFoundIndex, DegreePattern &degs, bool &success, const ExtensionInfo &info, const CanonicalForm &eval, int deg)
 detects factors of F at stage deg of Hensel lifting. No combinations of more than one factor are tested. Lift bound and possible degree pattern are updated. More...
 
CFList henselLiftAndEarly (CanonicalForm &A, bool &earlySuccess, CFList &earlyFactors, DegreePattern &degs, int &liftBound, const CFList &uniFactors, const ExtensionInfo &info, const CanonicalForm &eval, modpk &b, CanonicalForm &den)
 hensel Lifting and early factor detection More...
 
CFList henselLiftAndEarly (CanonicalForm &A, bool &earlySuccess, CFList &earlyFactors, DegreePattern &degs, int &liftBound, const CFList &uniFactors, const ExtensionInfo &info, const CanonicalForm &eval)
 hensel Lifting and early factor detection More...
 
CFList extBiFactorize (const CanonicalForm &F, const ExtensionInfo &info)
 Factorization over an extension of initial field. More...
 

Detailed Description

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

Author
Martin Lee

Definition in file facFqBivar.h.

Function Documentation

◆ biFactorize()

CFList biFactorize ( const CanonicalForm F,
const ExtensionInfo info 
)

Factorization of a squarefree bivariate polynomials over an arbitrary finite field, information on the current field we work over is in info. info may also contain information about the initial field if initial and current field do not coincide. In this case the current field is an extension of the initial field and the factors returned are factors of F over the initial field.

Returns
biFactorize returns a list of factors of F. If F is not monic its leading coefficient is not outputted.
See also
extBifactorize()

Factorization of a squarefree bivariate polynomials over an arbitrary finite field, information on the current field we work over is in info. info may also contain information about the initial field if initial and current field do not coincide. In this case the current field is an extension of the initial field and the factors returned are factors of F over the initial field.

Parameters
[in]Fa sqrfree bivariate poly
[in]infoinformation about extension

Definition at line 8303 of file facFqBivar.cc.

8304 {
8305  if (F.inCoeffDomain())
8306  return CFList(F);
8307 
8308  CanonicalForm A= F;
8309  bool GF= (CFFactory::gettype() == GaloisFieldDomain);
8310 
8313  CanonicalForm gamma= info.getGamma();
8315  int k= info.getGFDegree();
8316  bool extension= info.isInExtension();
8317  if (A.isUnivariate())
8318  {
8319  if (extension == false)
8320  return uniFactorizer (F, alpha, GF);
8321  else
8322  {
8323  CFList source, dest;
8324  A= mapDown (A, info, source, dest);
8325  return uniFactorizer (A, beta, GF);
8326  }
8327  }
8328 
8329  CFMap N;
8330  A= compress (A, N);
8331  Variable y= A.mvar();
8332 
8333  if (y.level() > 2) return CFList (F);
8334  Variable x= Variable (1);
8335 
8336  //remove and factorize content
8337  CanonicalForm contentAx= content (A, x);
8338  CanonicalForm contentAy= content (A);
8339 
8340  A= A/(contentAx*contentAy);
8341  CFList contentAxFactors, contentAyFactors;
8342 
8343  if (!extension)
8344  {
8345  contentAxFactors= uniFactorizer (contentAx, alpha, GF);
8346  contentAyFactors= uniFactorizer (contentAy, alpha, GF);
8347  }
8348 
8349  //trivial case
8350  CFList factors;
8351  if (A.inCoeffDomain())
8352  {
8353  append (factors, contentAxFactors);
8354  append (factors, contentAyFactors);
8355  decompress (factors, N);
8356  return factors;
8357  }
8358  else if (A.isUnivariate())
8359  {
8360  factors= uniFactorizer (A, alpha, GF);
8361  append (factors, contentAxFactors);
8362  append (factors, contentAyFactors);
8363  decompress (factors, N);
8364  return factors;
8365  }
8366 
8367 
8368  //check trivial case
8369  if (degree (A) == 1 || degree (A, 1) == 1 ||
8370  (size (A) == 2 && igcd (degree (A), degree (A,1))==1))
8371  {
8372  factors.append (A);
8373 
8374  appendSwapDecompress (factors, contentAxFactors, contentAyFactors,
8375  false, false, N);
8376 
8377  if (!extension)
8378  normalize (factors);
8379  return factors;
8380  }
8381 
8382  // check derivatives
8383  bool derivXZero= false;
8384  CanonicalForm derivX= deriv (A, x);
8385  CanonicalForm gcdDerivX;
8386  if (derivX.isZero())
8387  derivXZero= true;
8388  else
8389  {
8390  gcdDerivX= gcd (A, derivX);
8391  if (degree (gcdDerivX) > 0)
8392  {
8393  CanonicalForm g= A/gcdDerivX;
8394  CFList factorsG=
8395  Union (biFactorize (g, info), biFactorize (gcdDerivX, info));
8396  append (factorsG, contentAxFactors);
8397  append (factorsG, contentAyFactors);
8398  decompress (factorsG, N);
8399  if (!extension)
8400  normalize (factorsG);
8401  return factorsG;
8402  }
8403  }
8404  bool derivYZero= false;
8405  CanonicalForm derivY= deriv (A, y);
8406  CanonicalForm gcdDerivY;
8407  if (derivY.isZero())
8408  derivYZero= true;
8409  else
8410  {
8411  gcdDerivY= gcd (A, derivY);
8412  if (degree (gcdDerivY) > 0)
8413  {
8414  CanonicalForm g= A/gcdDerivY;
8415  CFList factorsG=
8416  Union (biFactorize (g, info), biFactorize (gcdDerivY, info));
8417  append (factorsG, contentAxFactors);
8418  append (factorsG, contentAyFactors);
8419  decompress (factorsG, N);
8420  if (!extension)
8421  normalize (factorsG);
8422  return factorsG;
8423  }
8424  }
8425  //main variable is chosen s.t. the degree in x is minimal
8426  bool swap= false;
8427  if ((degree (A) > degree (A, x)) || derivXZero)
8428  {
8429  if (!derivYZero)
8430  {
8431  A= swapvar (A, y, x);
8432  swap= derivXZero;
8433  derivXZero= derivYZero;
8434  derivYZero= swap;
8435  swap= true;
8436  }
8437  }
8438 
8439  int boundsLength;
8440  bool isIrreducible= false;
8441  int * bounds= computeBounds (A, boundsLength, isIrreducible);
8442  if (isIrreducible)
8443  {
8444  delete [] bounds;
8445  factors.append (A);
8446 
8447  appendSwapDecompress (factors, contentAxFactors, contentAyFactors,
8448  swap, false, N);
8449 
8450  if (!extension)
8451  normalize (factors);
8452  return factors;
8453  }
8454 
8455  int minBound= bounds[0];
8456  for (int i= 1; i < boundsLength; i++)
8457  {
8458  if (bounds[i] != 0)
8459  minBound= tmin (minBound, bounds[i]);
8460  }
8461 
8462  int boundsLength2;
8463  int * bounds2= computeBoundsWrtDiffMainvar (A, boundsLength2, isIrreducible);
8464  int minBound2= bounds2[0];
8465  for (int i= 1; i < boundsLength2; i++)
8466  {
8467  if (bounds2[i] != 0)
8468  minBound2= tmin (minBound2, bounds2[i]);
8469  }
8470 
8471 
8472  bool fail= false;
8473  CanonicalForm Aeval, evaluation, bufAeval, bufEvaluation, buf, tmp;
8474  CFList uniFactors, list, bufUniFactors;
8475  DegreePattern degs;
8476  DegreePattern bufDegs;
8477 
8478  bool fail2= false;
8479  CanonicalForm Aeval2, evaluation2, bufAeval2, bufEvaluation2;
8480  CFList bufUniFactors2, list2, uniFactors2;
8481  DegreePattern degs2;
8482  DegreePattern bufDegs2;
8483  bool swap2= false;
8484 
8485  // several univariate factorizations to obtain more information about the
8486  // degree pattern therefore usually less combinations have to be tried during
8487  // the recombination process
8488  int factorNums= 3;
8489  int subCheck1= substituteCheck (A, x);
8490  int subCheck2= substituteCheck (A, y);
8491  bool symmetric= false;
8492 
8493  TIMING_START (fac_fq_uni_total);
8494  for (int i= 0; i < factorNums; i++)
8495  {
8496  bufAeval= A;
8497  TIMING_START (fac_fq_bi_evaluation);
8498  bufEvaluation= evalPoint (A, bufAeval, alpha, list, GF, fail);
8499  TIMING_END_AND_PRINT (fac_fq_bi_evaluation, "time to find eval point: ");
8500  if (!derivXZero && !fail2 && !symmetric)
8501  {
8502  if (i == 0)
8503  {
8504  buf= swapvar (A, x, y);
8505  symmetric= (A/Lc (A) == buf/Lc (buf));
8506  }
8507  bufAeval2= buf;
8508  TIMING_START (fac_fq_bi_evaluation);
8509  bufEvaluation2= evalPoint (buf, bufAeval2, alpha, list2, GF, fail2);
8510  TIMING_END_AND_PRINT (fac_fq_bi_evaluation,
8511  "time to find eval point wrt y: ");
8512  }
8513  // first try to change main variable if there is no valid evaluation point
8514  if (fail && (i == 0))
8515  {
8516  if (!derivXZero && !fail2 && !symmetric)
8517  {
8518  bufEvaluation= bufEvaluation2;
8519  int dummy= subCheck2;
8520  subCheck2= subCheck1;
8521  subCheck1= dummy;
8522  tmp= A;
8523  A= buf;
8524  buf= tmp;
8525  bufAeval= bufAeval2;
8526  swap2= true;
8527  fail= false;
8528  }
8529  else
8530  fail= true;
8531  }
8532 
8533  // if there is no valid evaluation point pass to a field extension
8534  if (fail && (i == 0))
8535  {
8536  factors= extBiFactorize (A, info);
8537  appendSwapDecompress (factors, contentAxFactors, contentAyFactors,
8538  swap, swap2, N);
8539  normalize (factors);
8540  delete [] bounds;
8541  delete [] bounds2;
8542  return factors;
8543  }
8544 
8545  // there is at least one valid evaluation point
8546  // but we do not compute more univariate factorization over an extension
8547  if (fail && (i != 0))
8548  break;
8549 
8550  // univariate factorization
8551  TIMING_START (fac_fq_uni_factorizer);
8552  bufUniFactors= uniFactorizer (bufAeval, alpha, GF);
8553  TIMING_END_AND_PRINT (fac_fq_uni_factorizer,
8554  "time for univariate factorization over Fq: ");
8555  DEBOUTLN (cerr, "Lc (bufAeval)*prod (bufUniFactors)== bufAeval " <<
8556  (prod (bufUniFactors)*Lc (bufAeval) == bufAeval));
8557 
8558  if (!derivXZero && !fail2 && !symmetric)
8559  {
8560  TIMING_START (fac_fq_uni_factorizer);
8561  bufUniFactors2= uniFactorizer (bufAeval2, alpha, GF);
8562  TIMING_END_AND_PRINT (fac_fq_uni_factorizer,
8563  "time for univariate factorization in y over Fq: ");
8564  DEBOUTLN (cerr, "Lc (bufAeval2)*prod (bufUniFactors2)== bufAeval2 " <<
8565  (prod (bufUniFactors2)*Lc (bufAeval2) == bufAeval2));
8566  }
8567 
8568  if (bufUniFactors.length() == 1 ||
8569  (!fail2 && !derivXZero && !symmetric && (bufUniFactors2.length() == 1)))
8570  {
8571  if (extension)
8572  {
8573  CFList source, dest;
8574  appendMapDown (factors, A, info, source, dest);
8575  }
8576  else
8577  factors.append (A);
8578 
8579  appendSwapDecompress (factors, contentAxFactors, contentAyFactors,
8580  swap, swap2, N);
8581 
8582  if (!extension)
8583  normalize (factors);
8584  delete [] bounds;
8585  delete [] bounds2;
8586  return factors;
8587  }
8588 
8589  if (i == 0 && !extension)
8590  {
8591  if (subCheck1 > 0)
8592  {
8593  int subCheck= substituteCheck (bufUniFactors);
8594 
8595  if (subCheck > 1 && (subCheck1%subCheck == 0))
8596  {
8597  CanonicalForm bufA= A;
8598  subst (bufA, bufA, subCheck, x);
8599  factors= biFactorize (bufA, info);
8600  reverseSubst (factors, subCheck, x);
8601  appendSwapDecompress (factors, contentAxFactors, contentAyFactors,
8602  swap, swap2, N);
8603  if (!extension)
8604  normalize (factors);
8605  delete [] bounds;
8606  delete [] bounds2;
8607  return factors;
8608  }
8609  }
8610 
8611  if (!derivXZero && !fail2 && !symmetric && subCheck2 > 0)
8612  {
8613  int subCheck= substituteCheck (bufUniFactors2);
8614 
8615  if (subCheck > 1 && (subCheck2%subCheck == 0))
8616  {
8617  CanonicalForm bufA= A;
8618  subst (bufA, bufA, subCheck, y);
8619  factors= biFactorize (bufA, info);
8620  reverseSubst (factors, subCheck, y);
8621  appendSwapDecompress (factors, contentAxFactors, contentAyFactors,
8622  swap, swap2, N);
8623  if (!extension)
8624  normalize (factors);
8625  delete [] bounds;
8626  delete [] bounds2;
8627  return factors;
8628  }
8629  }
8630  }
8631 
8632  // degree analysis
8633  bufDegs = DegreePattern (bufUniFactors);
8634  if (!derivXZero && !fail2 && !symmetric)
8635  bufDegs2= DegreePattern (bufUniFactors2);
8636 
8637  if (i == 0)
8638  {
8639  Aeval= bufAeval;
8640  evaluation= bufEvaluation;
8641  uniFactors= bufUniFactors;
8642  degs= bufDegs;
8643  if (!derivXZero && !fail2 && !symmetric)
8644  {
8645  Aeval2= bufAeval2;
8646  evaluation2= bufEvaluation2;
8647  uniFactors2= bufUniFactors2;
8648  degs2= bufDegs2;
8649  }
8650  }
8651  else
8652  {
8653  degs.intersect (bufDegs);
8654  if (!derivXZero && !fail2 && !symmetric)
8655  {
8656  degs2.intersect (bufDegs2);
8657  if (bufUniFactors2.length() < uniFactors2.length())
8658  {
8659  uniFactors2= bufUniFactors2;
8660  Aeval2= bufAeval2;
8661  evaluation2= bufEvaluation2;
8662  }
8663  }
8664  if (bufUniFactors.length() < uniFactors.length())
8665  {
8666  uniFactors= bufUniFactors;
8667  Aeval= bufAeval;
8668  evaluation= bufEvaluation;
8669  }
8670  }
8671  list.append (bufEvaluation);
8672  if (!derivXZero && !fail2 && !symmetric)
8673  list2.append (bufEvaluation2);
8674  }
8675  TIMING_END_AND_PRINT (fac_fq_uni_total,
8676  "total time for univariate factorizations: ");
8677 
8678  if (!derivXZero && !fail2 && !symmetric)
8679  {
8680  if ((uniFactors.length() > uniFactors2.length() && minBound2 <= minBound)||
8681  (uniFactors.length() == uniFactors2.length()
8682  && degs.getLength() > degs2.getLength() && minBound2 <= minBound))
8683  {
8684  degs= degs2;
8685  uniFactors= uniFactors2;
8686  evaluation= evaluation2;
8687  Aeval= Aeval2;
8688  A= buf;
8689  swap2= true;
8690  }
8691  }
8692 
8693  if (degs.getLength() == 1) // A is irreducible
8694  {
8695  if (extension)
8696  {
8697  CFList source, dest;
8698  appendMapDown (factors, A, info, source, dest);
8699  }
8700  else
8701  factors.append (A);
8702  appendSwapDecompress (factors, contentAxFactors, contentAyFactors,
8703  swap, swap2, N);
8704  if (!extension)
8705  normalize (factors);
8706  delete [] bounds;
8707  delete [] bounds2;
8708  return factors;
8709  }
8710 
8711  int liftBound= degree (A, y) + 1;
8712 
8713  if (swap2)
8714  {
8715  delete [] bounds;
8716  bounds= bounds2;
8717  minBound= minBound2;
8718  }
8719 
8720  TIMING_START (fac_fq_bi_shift_to_zero);
8721  A= A (y + evaluation, y);
8722  TIMING_END_AND_PRINT (fac_fq_bi_shift_to_zero,
8723  "time to shift eval to zero: ");
8724 
8725  int degMipo= 1;
8726  if (extension && alpha.level() != 1 && k==1)
8727  degMipo= degree (getMipo (alpha));
8728 
8729  DEBOUTLN (cerr, "uniFactors= " << uniFactors);
8730 
8731  if ((GF && !extension) || (GF && extension && k != 1))
8732  {
8733  bool earlySuccess= false;
8734  CFList earlyFactors;
8735  TIMING_START (fac_fq_bi_hensel_lift);
8736  uniFactors= henselLiftAndEarly
8737  (A, earlySuccess, earlyFactors, degs, liftBound,
8738  uniFactors, info, evaluation);
8739  TIMING_END_AND_PRINT (fac_fq_bi_hensel_lift,
8740  "time for bivariate hensel lifting over Fq: ");
8741  DEBOUTLN (cerr, "lifted factors= " << uniFactors);
8742 
8743  CanonicalForm MODl= power (y, liftBound);
8744 
8745  TIMING_START (fac_fq_bi_factor_recombination);
8746  if (extension)
8747  factors= extFactorRecombination (uniFactors, A, MODl, info, degs,
8748  evaluation, 1, uniFactors.length()/2);
8749  else
8750  factors= factorRecombination (uniFactors, A, MODl, degs, evaluation, 1,
8751  uniFactors.length()/2);
8752  TIMING_END_AND_PRINT (fac_fq_bi_factor_recombination,
8753  "time for naive bivariate factor recombi over Fq: ");
8754 
8755  if (earlySuccess)
8756  factors= Union (earlyFactors, factors);
8757  else if (!earlySuccess && degs.getLength() == 1)
8758  factors= earlyFactors;
8759  }
8760  else if (degree (A) > 4 && beta.level() == 1 && (2*minBound)/degMipo < 32)
8761  {
8762  TIMING_START (fac_fq_bi_hensel_lift);
8763  if (extension)
8764  {
8765  CFList lll= extHenselLiftAndLatticeRecombi (A, uniFactors, info, degs,
8766  evaluation
8767  );
8768  factors= Union (lll, factors);
8769  }
8770  else if (alpha.level() == 1 && !GF)
8771  {
8772  CFList lll= henselLiftAndLatticeRecombi (A, uniFactors, alpha, degs,
8773  symmetric, evaluation);
8774  factors= Union (lll, factors);
8775  }
8776  else if (!extension && (alpha != x || GF))
8777  {
8778  CFList lll= henselLiftAndLatticeRecombi (A, uniFactors, alpha, degs,
8779  symmetric, evaluation);
8780  factors= Union (lll, factors);
8781  }
8782  TIMING_END_AND_PRINT (fac_fq_bi_hensel_lift,
8783  "time to bivar lift and LLL recombi over Fq: ");
8784  DEBOUTLN (cerr, "lifted factors= " << uniFactors);
8785  }
8786  else
8787  {
8788  bool earlySuccess= false;
8789  CFList earlyFactors;
8790  TIMING_START (fac_fq_bi_hensel_lift);
8791  uniFactors= henselLiftAndEarly
8792  (A, earlySuccess, earlyFactors, degs, liftBound,
8793  uniFactors, info, evaluation);
8794  TIMING_END_AND_PRINT (fac_fq_bi_hensel_lift,
8795  "time for bivar hensel lifting over Fq: ");
8796  DEBOUTLN (cerr, "lifted factors= " << uniFactors);
8797 
8798  CanonicalForm MODl= power (y, liftBound);
8799  if (!extension)
8800  {
8801  TIMING_START (fac_fq_bi_factor_recombination);
8802  factors= factorRecombination (uniFactors, A, MODl, degs, evaluation, 1, 3);
8803  TIMING_END_AND_PRINT (fac_fq_bi_factor_recombination,
8804  "time for small subset naive recombi over Fq: ");
8805 
8806  int oldUniFactorsLength= uniFactors.length();
8807  if (degree (A) > 0)
8808  {
8809  CFList tmp;
8810  TIMING_START (fac_fq_bi_hensel_lift);
8811  if (alpha.level() == 1)
8812  tmp= increasePrecision (A, uniFactors, 0, uniFactors.length(), 1,
8813  liftBound, evaluation
8814  );
8815  else
8816  {
8817  if (degree (A) > getCharacteristic())
8818  tmp= increasePrecisionFq2Fp (A, uniFactors, 0, uniFactors.length(),
8819  1, alpha, liftBound, evaluation
8820  );
8821  else
8822  tmp= increasePrecision (A, uniFactors, 0, uniFactors.length(), 1,
8823  alpha, liftBound, evaluation
8824  );
8825  }
8826  TIMING_END_AND_PRINT (fac_fq_bi_hensel_lift,
8827  "time to increase precision: ");
8828  factors= Union (factors, tmp);
8829  if (tmp.length() == 0 || (tmp.length() > 0 && uniFactors.length() != 0
8830  && uniFactors.length() != oldUniFactorsLength)
8831  )
8832  {
8833  DegreePattern bufDegs= DegreePattern (uniFactors);
8834  degs.intersect (bufDegs);
8835  degs.refine ();
8836  factors= Union (factors, factorRecombination (uniFactors, A, MODl,
8837  degs, evaluation, 4,
8838  uniFactors.length()/2
8839  )
8840  );
8841  }
8842  }
8843  }
8844  else
8845  {
8846  if (beta.level() != 1 || k > 1)
8847  {
8848  if (k > 1)
8849  {
8850  factors= extFactorRecombination (uniFactors, A, MODl, info, degs,
8851  evaluation, 1, uniFactors.length()/2
8852  );
8853  }
8854  else
8855  {
8856  factors= extFactorRecombination (uniFactors, A, MODl, info, degs,
8857  evaluation, 1, 3
8858  );
8859  if (degree (A) > 0)
8860  {
8861  CFList tmp= increasePrecision2 (A, uniFactors, alpha, liftBound);
8862  DegreePattern bufDegs= DegreePattern (tmp);
8863  degs.intersect (bufDegs);
8864  degs.refine ();
8865  factors= Union (factors, extFactorRecombination (tmp, A, MODl, info,
8866  degs, evaluation,
8867  1, tmp.length()/2
8868  )
8869  );
8870  }
8871  }
8872  }
8873  else
8874  {
8875  factors= extFactorRecombination (uniFactors, A, MODl, info, degs,
8876  evaluation, 1, 3
8877  );
8878  int oldUniFactorsLength= uniFactors.length();
8879  if (degree (A) > 0)
8880  {
8881  int degMipo;
8882  ExtensionInfo info2= init4ext (info, evaluation, degMipo);
8883 
8884  CFList source, dest;
8885  CFList tmp= extIncreasePrecision (A, uniFactors, 0,
8886  uniFactors.length(), 1, evaluation,
8887  info2, source, dest, liftBound
8888  );
8889  factors= Union (factors, tmp);
8890  if (tmp.length() == 0 || (tmp.length() > 0 && uniFactors.length() != 0
8891  && uniFactors.length() != oldUniFactorsLength)
8892  )
8893  {
8894  DegreePattern bufDegs= DegreePattern (uniFactors);
8895  degs.intersect (bufDegs);
8896  degs.refine ();
8897  factors= Union (factors,extFactorRecombination (uniFactors, A, MODl,
8898  info, degs, evaluation,
8899  4, uniFactors.length()/2
8900  )
8901  );
8902  }
8903  }
8904  }
8905  }
8906 
8907  if (earlySuccess)
8908  factors= Union (earlyFactors, factors);
8909  else if (!earlySuccess && degs.getLength() == 1)
8910  factors= earlyFactors;
8911  }
8912 
8913  if (!swap2)
8914  delete [] bounds2;
8915  delete [] bounds;
8916 
8917  appendSwapDecompress (factors, contentAxFactors, contentAyFactors,
8918  swap, swap2, N);
8919  if (!extension)
8920  normalize (factors);
8921 
8922  return factors;
8923 }
#define swap(_i, _j)
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
CanonicalForm FACTORY_PUBLIC content(const CanonicalForm &)
CanonicalForm content ( const CanonicalForm & f )
Definition: cf_gcd.cc:603
int size(const CanonicalForm &f, const Variable &v)
int size ( const CanonicalForm & f, const Variable & v )
Definition: cf_ops.cc:600
int degree(const CanonicalForm &f)
CanonicalForm deriv(const CanonicalForm &f, const Variable &x)
CanonicalForm FACTORY_PUBLIC swapvar(const CanonicalForm &, const Variable &, const Variable &)
swapvar() - swap variables x1 and x2 in f.
Definition: cf_ops.cc:168
CanonicalForm Lc(const CanonicalForm &f)
List< CanonicalForm > CFList
int FACTORY_PUBLIC getCharacteristic()
Definition: cf_char.cc:70
const CanonicalForm CFMap CFMap & N
Definition: cfEzgcd.cc:56
int k
Definition: cfEzgcd.cc:99
Variable x
Definition: cfModGcd.cc:4082
g
Definition: cfModGcd.cc:4090
CanonicalForm decompress(const CanonicalForm &F, const mpz_t *inverseM, const mpz_t *A)
decompress a bivariate poly
#define GaloisFieldDomain
Definition: cf_defs.h:18
CanonicalForm compress(const CanonicalForm &f, CFMap &m)
CanonicalForm compress ( const CanonicalForm & f, CFMap & m )
Definition: cf_map.cc:210
static CanonicalForm mapDown(const CanonicalForm &F, const Variable &alpha, const CanonicalForm &G, CFList &source, CFList &dest)
the CanonicalForm G is the output of map_up, returns F considered as an element over ,...
Definition: cf_map_ext.cc:123
int igcd(int a, int b)
Definition: cf_util.cc:56
static int gettype()
Definition: cf_factory.h:28
class CFMap
Definition: cf_map.h:85
factory's main class
Definition: canonicalform.h:86
CF_NO_INLINE bool isZero() const
bool inCoeffDomain() const
int level() const
level() returns the level of CO.
DegreePattern provides a functionality to create, intersect and refine degree patterns.
Definition: DegreePattern.h:32
void intersect(const DegreePattern &degPat)
intersect two degree patterns
int getLength() const
getter
Definition: DegreePattern.h:86
void refine()
Refine a degree pattern. Assumes that (*this)[0]:= d is the degree of the poly to be factored....
ExtensionInfo contains information about extension.
Definition: ExtensionInfo.h:51
int getGFDegree() const
getter
bool isInExtension() const
getter
CanonicalForm getGamma() const
getter
CanonicalForm getDelta() const
getter
Variable getAlpha() const
getter
Variable getBeta() const
getter
int length() const
Definition: ftmpl_list.cc:273
void append(const T &)
Definition: ftmpl_list.cc:256
factory's class for variables
Definition: factory.h:127
int level() const
Definition: factory.h:143
#define DEBOUTLN(stream, objects)
Definition: debug.h:49
Variable alpha
Definition: facAbsBiFact.cc:51
const CanonicalForm int const CFList & evaluation
Definition: facAbsFact.cc:52
const CanonicalForm int const CFList const Variable & y
Definition: facAbsFact.cc:53
Variable beta
Definition: facAbsFact.cc:95
TIMING_END_AND_PRINT(fac_alg_resultant, "time to compute resultant0: ")
TIMING_START(fac_alg_resultant)
CFFList append(const CFFList &Inputlist, const CFFactor &TheFactor)
CanonicalForm subst(const CanonicalForm &f, const CFList &a, const CFList &b, const CanonicalForm &Rstar, bool isFunctionField)
CFList *& Aeval
<[in] poly
Definition: facFactorize.h:31
void appendSwapDecompress(CFList &factors1, const CFList &factors2, const CFList &factors3, const bool swap1, const bool swap2, const CFMap &N)
first swap Variables in factors1 if necessary, then append factors2 and factors3 on factors1 and fina...
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
CanonicalForm reverseSubst(const CanonicalForm &F, const int d, const Variable &x)
reverse a substitution x^d->x
int * computeBoundsWrtDiffMainvar(const CanonicalForm &F, int &n, bool &isIrreducible)
as above just wrt to the other variable
int * computeBounds(const CanonicalForm &F, int &n, bool &isIrreducible)
compute bounds for logarithmic derivative as described in K. Belabas, M. van Hoeij,...
int substituteCheck(const CanonicalForm &F, const Variable &x)
check if a substitution x^n->x is possible
CFList biFactorize(const CanonicalForm &F, const ExtensionInfo &info)
bivariate factorization over finite fields as decribed in "Factoring multivariate polynomials over a ...
Definition: facFqBivar.cc:8303
CFList increasePrecision(CanonicalForm &F, CFList &factors, int factorsFound, int oldNumCols, int oldL, int precision, const CanonicalForm &eval)
Definition: facFqBivar.cc:3475
CFList extHenselLiftAndLatticeRecombi(const CanonicalForm &G, const CFList &uniFactors, const ExtensionInfo &extInfo, const DegreePattern &degPat, const CanonicalForm &eval)
Definition: facFqBivar.cc:7712
CFList extBiFactorize(const CanonicalForm &F, const ExtensionInfo &info)
Factorization over an extension of initial field.
Definition: facFqBivar.cc:8928
CFList increasePrecisionFq2Fp(CanonicalForm &F, CFList &factors, int factorsFound, int oldNumCols, int oldL, const Variable &alpha, int precision, const CanonicalForm &eval)
Definition: facFqBivar.cc:4267
CFList extIncreasePrecision(CanonicalForm &F, CFList &factors, int factorsFound, int oldNumCols, int oldL, const CanonicalForm &evaluation, const ExtensionInfo &info, CFList &source, CFList &dest, int precision)
Definition: facFqBivar.cc:3826
CFList henselLiftAndLatticeRecombi(const CanonicalForm &G, const CFList &uniFactors, const Variable &alpha, const DegreePattern &degPat, bool symmetric, const CanonicalForm &eval)
Definition: facFqBivar.cc:6859
CFListIterator i
Definition: facFqBivar.cc:71
CFList extFactorRecombination(CFList &factors, CanonicalForm &F, const CanonicalForm &N, const ExtensionInfo &info, DegreePattern &degs, const CanonicalForm &eval, int s, int thres)
naive factor recombination as decribed in "Factoring multivariate polynomials over a finite field" by...
Definition: facFqBivar.cc:370
CanonicalForm evalPoint(const CanonicalForm &F, CanonicalForm &eval, const Variable &alpha, CFList &list, const bool &GF, bool &fail)
find an evaluation point p, s.t. F(p,y) is squarefree and .
Definition: facFqBivar.cc:84
CFList henselLiftAndEarly(CanonicalForm &A, bool &earlySuccess, CFList &earlyFactors, DegreePattern &degs, int &liftBound, const CFList &uniFactors, const ExtensionInfo &info, const CanonicalForm &eval, modpk &b, CanonicalForm &den)
hensel Lifting and early factor detection
Definition: facFqBivar.cc:1152
CFList uniFactorizer(const CanonicalForm &A, const Variable &alpha, const bool &GF)
Univariate factorization of squarefree monic polys over finite fields via NTL. If the characteristic ...
Definition: facFqBivar.cc:160
CFList factorRecombination(CFList &factors, CanonicalForm &F, const CanonicalForm &N, DegreePattern &degs, const CanonicalForm &eval, int s, int thres, const modpk &b, const CanonicalForm &den)
naive factor recombination as decribed in "Factoring multivariate polynomials over a finite field" by...
Definition: facFqBivar.cc:586
ExtensionInfo init4ext(const ExtensionInfo &info, const CanonicalForm &evaluation, int &degMipo)
Definition: facFqBivar.cc:7657
CFList increasePrecision2(const CanonicalForm &F, CFList &factors, const Variable &alpha, int precision)
Definition: facFqBivar.cc:4134
const ExtensionInfo & info
< [in] sqrfree poly
fq_nmod_poly_t prod
Definition: facHensel.cc:100
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
Definition: variable.cc:207
template CanonicalForm tmin(const CanonicalForm &, const CanonicalForm &)
template List< Variable > Union(const List< Variable > &, const List< Variable > &)
bool isIrreducible(const CanonicalForm &f)
bool isIrreducible ( const CanonicalForm & f )
bool delta(X x, Y y, D d)
Definition: TestSuite.h:160
int status int void * buf
Definition: si_signals.h:59
#define A
Definition: sirandom.c:24
static poly normalize(poly next_p, ideal add_generators, syStrategy syzstr, int *g_l, int *p_l, int crit_comp)
Definition: syz3.cc:1026
int gcd(int a, int b)
Definition: walkSupport.cc:836

◆ biSqrfFactorizeHelper()

CFList biSqrfFactorizeHelper ( const CanonicalForm G,
const ExtensionInfo info 
)
inline

Definition at line 55 of file facFqBivar.h.

56 {
57  CFMap N;
58  CanonicalForm F= compress (G, N);
59  CanonicalForm contentX= content (F, 1);
60  CanonicalForm contentY= content (F, 2);
61  F /= (contentX*contentY);
62  CFFList contentXFactors, contentYFactors;
63  if (info.getAlpha().level() != 1)
64  {
65  contentXFactors= factorize (contentX, info.getAlpha());
66  contentYFactors= factorize (contentY, info.getAlpha());
67  }
68  else if (info.getAlpha().level() == 1 && info.getGFDegree() == 1)
69  {
70  contentXFactors= factorize (contentX);
71  contentYFactors= factorize (contentY);
72  }
73  else if (info.getAlpha().level() == 1 && info.getGFDegree() != 1)
74  {
75  CFList bufContentX, bufContentY;
76  bufContentX= biFactorize (contentX, info);
77  bufContentY= biFactorize (contentY, info);
78  for (CFListIterator iter= bufContentX; iter.hasItem(); iter++)
79  contentXFactors.append (CFFactor (iter.getItem(), 1));
80  for (CFListIterator iter= bufContentY; iter.hasItem(); iter++)
81  contentYFactors.append (CFFactor (iter.getItem(), 1));
82  }
83 
84  if (contentXFactors.getFirst().factor().inCoeffDomain())
85  contentXFactors.removeFirst();
86  if (contentYFactors.getFirst().factor().inCoeffDomain())
87  contentYFactors.removeFirst();
88  if (F.inCoeffDomain())
89  {
90  CFList result;
91  for (CFFListIterator i= contentXFactors; i.hasItem(); i++)
92  result.append (N (i.getItem().factor()));
93  for (CFFListIterator i= contentYFactors; i.hasItem(); i++)
94  result.append (N (i.getItem().factor()));
95  normalize (result);
96  result.insert (Lc (G));
97  return result;
98  }
99  mpz_t * M=new mpz_t [4];
100  mpz_init (M[0]);
101  mpz_init (M[1]);
102  mpz_init (M[2]);
103  mpz_init (M[3]);
104 
105  mpz_t * S=new mpz_t [2];
106  mpz_init (S[0]);
107  mpz_init (S[1]);
108 
109  F= compress (F, M, S);
111  for (CFListIterator i= result; i.hasItem(); i++)
112  i.getItem()= N (decompress (i.getItem(), M, S));
113  for (CFFListIterator i= contentXFactors; i.hasItem(); i++)
114  result.append (N(i.getItem().factor()));
115  for (CFFListIterator i= contentYFactors; i.hasItem(); i++)
116  result.append (N (i.getItem().factor()));
117  normalize (result);
118  result.insert (Lc(G));
119 
120  mpz_clear (M[0]);
121  mpz_clear (M[1]);
122  mpz_clear (M[2]);
123  mpz_clear (M[3]);
124  delete [] M;
125 
126  mpz_clear (S[0]);
127  mpz_clear (S[1]);
128  delete [] S;
129 
130  return result;
131 }
int i
Definition: cfEzgcd.cc:132
CFFList FACTORY_PUBLIC factorize(const CanonicalForm &f, bool issqrfree=false)
factorization over or
Definition: cf_factor.cc:405
T & getItem() const
Definition: ftmpl_list.cc:431
T getFirst() const
Definition: ftmpl_list.cc:279
void removeFirst()
Definition: ftmpl_list.cc:287
CFFListIterator iter
Definition: facAbsBiFact.cc:53
return result
Definition: facAbsBiFact.cc:75
CFList biFactorize(const CanonicalForm &F, const ExtensionInfo &info)
Factorization of a squarefree bivariate polynomials over an arbitrary finite field,...
Definition: facFqBivar.cc:8303
STATIC_VAR TreeM * G
Definition: janet.cc:31
#define M
Definition: sirandom.c:25

◆ chooseExtension()

Variable chooseExtension ( const Variable alpha,
const Variable beta,
int  k 
)

chooses a field extension.

Returns
chooseExtension returns an extension specified by beta of appropiate size
Parameters
[in]alphasome algebraic variable
[in]betasome algebraic variable
[in]ksome int

Definition at line 806 of file facFqBivar.cc.

807 {
808  int i=1, m= 2;
809  // extension of F_p needed
810  if (alpha.level() == 1 && beta.level() == 1 && k == 1)
811  {
812  i= 1;
813  m= 2;
814  } //extension of F_p(alpha) needed but want to factorize over F_p
815  else if (alpha.level() != 1 && beta.level() == 1 && k == 1)
816  {
817  i= 1;
818  m= degree (getMipo (alpha)) + 1;
819  } //extension of F_p(alpha) needed for first time
820  else if (alpha.level() != 1 && beta.level() == 1 && k != 1)
821  {
822  i= 2;
823  m= degree (getMipo (alpha));
824  }
825  else if (alpha.level() != 1 && beta.level() != 1 && k != 1)
826  {
827  m= degree (getMipo (beta));
828  i= degree (getMipo (alpha))/m + 1;
829  }
830  #if defined(HAVE_FLINT)
831  nmod_poly_t Irredpoly;
832  nmod_poly_init(Irredpoly,getCharacteristic());
833  nmod_poly_randtest_monic_irreducible(Irredpoly,FLINTrandom,i*m+1);
834  CanonicalForm newMipo= convertnmod_poly_t2FacCF(Irredpoly,Variable (1));
835  #elif defined(HAVE_NTL)
837  {
840  }
841  zz_pX NTLIrredpoly;
842  BuildIrred (NTLIrredpoly, i*m);
843  CanonicalForm newMipo= convertNTLzzpX2CF (NTLIrredpoly, Variable (1));
844  #else
845  factoryError("NTL/FLINT missing: chooseExtension");
846  #endif
847  return rootOf (newMipo);
848 }
CanonicalForm convertnmod_poly_t2FacCF(const nmod_poly_t poly, const Variable &x)
conversion of a FLINT poly over Z/p to CanonicalForm
CanonicalForm convertNTLzzpX2CF(const zz_pX &poly, const Variable &x)
Definition: NTLconvert.cc:255
VAR long fac_NTL_char
Definition: NTLconvert.cc:46
int m
Definition: cfEzgcd.cc:128
GLOBAL_VAR flint_rand_t FLINTrandom
Definition: cf_random.cc:25
VAR void(* factoryError)(const char *s)
Definition: cf_util.cc:80
nmod_poly_init(FLINTmipo, getCharacteristic())
Variable FACTORY_PUBLIC rootOf(const CanonicalForm &, char name='@')
returns a symbolic root of polynomial with name name Use it to define algebraic variables
Definition: variable.cc:162
void init()
Definition: lintree.cc:864

◆ earlyFactorDetection()

void earlyFactorDetection ( CFList reconstructedFactors,
CanonicalForm F,
CFList factors,
int &  adaptedLiftBound,
int *&  factorsFoundIndex,
DegreePattern degs,
bool &  success,
int  deg,
const CanonicalForm eval,
const modpk b = modpk() 
)

detects factors of F at stage deg of Hensel lifting. No combinations of more than one factor are tested. Lift bound and possible degree pattern are updated.

See also
factorRecombination(), extEarlyFactorDetection()
Parameters
[in,out]reconstructedFactorslist of reconstructed factors
[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]factorsFoundIndexfactors already considered
[in,out]degsdegree pattern, is updated whenever we find a factor
[in,out]successindicating success
[in]degstage of Hensel lifting
[in]evalevaluation point
[in]bcoeff bound

Definition at line 971 of file facFqBivar.cc.

975 {
976  CanonicalForm den= 1;
977  earlyFactorDetection (reconstructedFactors, F, factors, adaptedLiftBound,
978  factorsFoundIndex, degs, success, deg, eval, b, den);
979 }
CanonicalForm den(const CanonicalForm &f)
CFList & eval
Definition: facFactorize.cc:47
void earlyFactorDetection(CFList &reconstructedFactors, CanonicalForm &F, CFList &factors, int &adaptedLiftBound, int *&factorsFoundIndex, DegreePattern &degs, bool &success, int deg, const CanonicalForm &eval, const modpk &b, CanonicalForm &den)
Definition: facFqBivar.cc:852
const CanonicalForm const modpk & b
Definition: facFqBivar.cc:61

◆ evalPoint()

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

find an evaluation point p, s.t. F(p,y) is squarefree and $ deg_{y} (F(p,y))= deg_{y} (F(x,y)) $.

Returns
evalPoint returns an evaluation point, which is valid if and only if fail == false.
Parameters
[in]Fcompressed, bivariate poly
[in,out]evalF (p, y)
[in]alphaalgebraic variable
[in]listlist of points already considered
[in]GFGaloisFieldDomain?
[in,out]failequals true, if there is no valid evaluation point

Definition at line 84 of file facFqBivar.cc.

87 {
88  fail= false;
89  Variable x= Variable(2);
90  Variable y= Variable(1);
91  FFRandom genFF;
92  GFRandom genGF;
93  CanonicalForm random, mipo;
94  double bound;
95  int p= getCharacteristic ();
96  if (alpha.level() != 1)
97  {
98  mipo= getMipo (alpha);
99  int d= degree (mipo);
100  bound= pow ((double) p, (double) d);
101  }
102  else if (GF)
103  {
104  int d= getGFDegree();
105  bound= ipower (p, d);
106  }
107  else
108  bound= p;
109 
110  random= 0;
111  do
112  {
113  if (list.length() >= bound)
114  {
115  fail= true;
116  break;
117  }
118  if (list.isEmpty())
119  random= 0;
120  else if (GF)
121  {
122  if (list.length() == 1)
123  random= getGFGenerator();
124  else
125  random= genGF.generate();
126  }
127  else if (list.length() < p || alpha.level() == 1)
128  random= genFF.generate();
129  else if (alpha != x && list.length() >= p)
130  {
131  if (list.length() == p)
132  random= alpha;
133  else
134  {
135  AlgExtRandomF genAlgExt (alpha);
136  random= genAlgExt.generate();
137  }
138  }
139  if (find (list, random)) continue;
140  eval= F (random, x);
141  if (degree (eval) != degree (F, y))
142  { //leading coeff vanishes
143  if (!find (list, random))
144  list.append (random);
145  continue;
146  }
147  if (degree (gcd (deriv (eval, eval.mvar()), eval), eval.mvar()) > 0)
148  { //evaluated polynomial is not squarefree
149  if (!find (list, random))
150  list.append (random);
151  continue;
152  }
153  } while (find (list, random));
154 
155  return random;
156 }
Rational pow(const Rational &a, int e)
Definition: GMPrat.cc:411
int getGFDegree()
Definition: cf_char.cc:75
CanonicalForm getGFGenerator()
Definition: cf_char.cc:81
int p
Definition: cfModGcd.cc:4078
static CanonicalForm bound(const CFMatrix &M)
Definition: cf_linsys.cc:460
int ipower(int b, int m)
int ipower ( int b, int m )
Definition: cf_util.cc:27
generate random elements in F_p(alpha)
Definition: cf_random.h:70
generate random elements in F_p
Definition: cf_random.h:44
CanonicalForm generate() const
Definition: cf_random.cc:68
generate random elements in GF
Definition: cf_random.h:32
CanonicalForm generate() const
Definition: cf_random.cc:78
int isEmpty() const
Definition: ftmpl_list.cc:267
CanonicalForm mipo
Definition: facAlgExt.cc:57
template bool find(const List< CanonicalForm > &, const CanonicalForm &)

◆ extBiFactorize()

CFList extBiFactorize ( const CanonicalForm F,
const ExtensionInfo info 
)

Factorization over an extension of initial field.

Returns
extBiFactorize returns factorization of F over initial field
See also
biFactorize()
Parameters
[in]Fpoly to be factored
[in]infoinfo about extension

Definition at line 8928 of file facFqBivar.cc.

8929 {
8930 
8931  CanonicalForm A= F;
8934  int k= info.getGFDegree();
8935  char cGFName= info.getGFName();
8937 
8938  bool GF= (CFFactory::gettype() == GaloisFieldDomain);
8939  Variable x= Variable (1);
8940  CFList factors;
8941  if (!GF && alpha == x) // we are in F_p
8942  {
8943  bool extension= true;
8944  int p= getCharacteristic();
8945  if (p*p < (1<<16)) // pass to GF if possible
8946  {
8948  A= A.mapinto();
8949  ExtensionInfo info2= ExtensionInfo (extension);
8950  factors= biFactorize (A, info2);
8951 
8954  Variable vBuf= rootOf (mipo.mapinto());
8955  for (CFListIterator j= factors; j.hasItem(); j++)
8956  j.getItem()= GF2FalphaRep (j.getItem(), vBuf);
8957  prune (vBuf);
8958  }
8959  else // not able to pass to GF, pass to F_p(\alpha)
8960  {
8962  Variable v= rootOf (mipo);
8963  ExtensionInfo info2= ExtensionInfo (v);
8964  factors= biFactorize (A, info2);
8965  prune (v);
8966  }
8967  return factors;
8968  }
8969  else if (!GF && (alpha != x)) // we are in F_p(\alpha)
8970  {
8971  if (k == 1) // need factorization over F_p
8972  {
8973  int extDeg= degree (getMipo (alpha));
8974  extDeg++;
8975  CanonicalForm mipo= randomIrredpoly (extDeg, x);
8976  Variable v= rootOf (mipo);
8977  ExtensionInfo info2= ExtensionInfo (v);
8978  factors= biFactorize (A, info2);
8979  prune (v);
8980  }
8981  else
8982  {
8983  if (beta == x)
8984  {
8986  CanonicalForm primElem, imPrimElem;
8987  bool primFail= false;
8988  Variable vBuf;
8989  primElem= primitiveElement (alpha, vBuf, primFail);
8990  ASSERT (!primFail, "failure in integer factorizer");
8991  if (primFail)
8992  ; //ERROR
8993  else
8994  imPrimElem= mapPrimElem (primElem, alpha, v);
8995 
8996  CFList source, dest;
8997  CanonicalForm bufA= mapUp (A, alpha, v, primElem, imPrimElem,
8998  source, dest);
8999  ExtensionInfo info2= ExtensionInfo (v, alpha, imPrimElem, primElem);
9000  factors= biFactorize (bufA, info2);
9001  prune (v);
9002  }
9003  else
9004  {
9006  CanonicalForm primElem, imPrimElem;
9007  bool primFail= false;
9008  Variable vBuf;
9009  ASSERT (!primFail, "failure in integer factorizer");
9010  if (primFail)
9011  ; //ERROR
9012  else
9013  imPrimElem= mapPrimElem (delta, beta, v);
9014 
9015  CFList source, dest;
9016  CanonicalForm bufA= mapDown (A, info, source, dest);
9017  source= CFList();
9018  dest= CFList();
9019  bufA= mapUp (bufA, beta, v, delta, imPrimElem, source, dest);
9020  ExtensionInfo info2= ExtensionInfo (v, beta, imPrimElem, delta);
9021  factors= biFactorize (bufA, info2);
9022  prune (v);
9023  }
9024  }
9025  return factors;
9026  }
9027  else // we are in GF (p^k)
9028  {
9029  int p= getCharacteristic();
9030  int extensionDeg= getGFDegree();
9031  bool extension= true;
9032  if (k == 1) // need factorization over F_p
9033  {
9034  extensionDeg++;
9035  if (ipower (p, extensionDeg) < (1<<16))
9036  // pass to GF(p^k+1)
9037  {
9039  setCharacteristic (p);
9040  Variable vBuf= rootOf (mipo.mapinto());
9041  A= GF2FalphaRep (A, vBuf);
9042  setCharacteristic (p, extensionDeg, 'Z');
9043  ExtensionInfo info2= ExtensionInfo (extension);
9044  factors= biFactorize (A.mapinto(), info2);
9045  prune (vBuf);
9046  }
9047  else // not able to pass to another GF, pass to F_p(\alpha)
9048  {
9050  setCharacteristic (p);
9051  Variable vBuf= rootOf (mipo.mapinto());
9052  A= GF2FalphaRep (A, vBuf);
9053  Variable v= chooseExtension (vBuf, beta, k);
9054  ExtensionInfo info2= ExtensionInfo (v, extension);
9055  factors= biFactorize (A, info2);
9056  prune (vBuf);
9057  }
9058  }
9059  else // need factorization over GF (p^k)
9060  {
9061  if (ipower (p, 2*extensionDeg) < (1<<16))
9062  // pass to GF (p^2k)
9063  {
9064  setCharacteristic (p, 2*extensionDeg, 'Z');
9065  ExtensionInfo info2= ExtensionInfo (k, cGFName, extension);
9066  factors= biFactorize (GFMapUp (A, extensionDeg), info2);
9067  setCharacteristic (p, extensionDeg, cGFName);
9068  }
9069  else // not able to pass to GF (p^2k), pass to F_p (\alpha)
9070  {
9072  setCharacteristic (p);
9073  Variable v1= rootOf (mipo.mapinto());
9074  A= GF2FalphaRep (A, v1);
9075  Variable v2= chooseExtension (v1, v1, k);
9076  CanonicalForm primElem, imPrimElem;
9077  bool primFail= false;
9078  Variable vBuf;
9079  primElem= primitiveElement (v1, vBuf, primFail);
9080  ASSERT (!primFail, "failure in integer factorizer");
9081  if (primFail)
9082  ; //ERROR
9083  else
9084  imPrimElem= mapPrimElem (primElem, v1, v2);
9085 
9086  CFList source, dest;
9087  CanonicalForm bufA= mapUp (A, v1, v2, primElem, imPrimElem,
9088  source, dest);
9089  ExtensionInfo info2= ExtensionInfo (v2, v1, imPrimElem, primElem);
9090  factors= biFactorize (bufA, info2);
9091  setCharacteristic (p, k, cGFName);
9092  for (CFListIterator i= factors; i.hasItem(); i++)
9093  i.getItem()= Falpha2GFRep (i.getItem());
9094  prune (v1);
9095  }
9096  }
9097  return factors;
9098  }
9099 }
void FACTORY_PUBLIC setCharacteristic(int c)
Definition: cf_char.cc:28
#define ASSERT(expression, message)
Definition: cf_assert.h:99
CanonicalForm randomIrredpoly(int i, const Variable &x)
computes a random monic irreducible univariate polynomial in x over Fp of degree i via NTL/FLINT
Definition: cf_irred.cc:26
CanonicalForm mapPrimElem(const CanonicalForm &primElem, const Variable &alpha, const Variable &beta)
compute the image of a primitive element of in . We assume .
Definition: cf_map_ext.cc:450
CanonicalForm primitiveElement(const Variable &alpha, Variable &beta, bool &fail)
determine a primitive element of , is a primitive element of a field which is isomorphic to
Definition: cf_map_ext.cc:342
static CanonicalForm mapUp(const Variable &alpha, const Variable &beta)
and is a primitive element, returns the image of
Definition: cf_map_ext.cc:70
CanonicalForm Falpha2GFRep(const CanonicalForm &F)
change representation by residue classes modulo a Conway polynomial to representation by primitive el...
Definition: cf_map_ext.cc:203
CanonicalForm GFMapUp(const CanonicalForm &F, int k)
maps a polynomial over to a polynomial over , d needs to be a multiple of k
Definition: cf_map_ext.cc:240
CanonicalForm GF2FalphaRep(const CanonicalForm &F, const Variable &alpha)
changes representation by primitive element to representation by residue classes modulo a Conway poly...
Definition: cf_map_ext.cc:195
CanonicalForm mapinto() const
char getGFName() const
getter
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:39
Variable chooseExtension(const Variable &alpha, const Variable &beta, int k)
chooses a field extension.
Definition: facFqBivar.cc:806
int j
Definition: facHensel.cc:110
void FACTORY_PUBLIC prune(Variable &alpha)
Definition: variable.cc:261
INST_VAR CanonicalForm gf_mipo
Definition: gfops.cc:56

◆ extEarlyFactorDetection()

void extEarlyFactorDetection ( CFList reconstructedFactors,
CanonicalForm F,
CFList factors,
int &  adaptedLiftBound,
int *&  factorsFoundIndex,
DegreePattern degs,
bool &  success,
const ExtensionInfo info,
const CanonicalForm eval,
int  deg 
)

detects factors of F at stage deg of Hensel lifting. No combinations of more than one factor are tested. Lift bound and possible degree pattern are updated.

See also
factorRecombination(), earlyFactorDetection()
Parameters
[in,out]reconstructedFactorslist of reconstructed factors
[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]factorsFoundIndexfactors already considered
[in,out]degsdegree pattern, is updated whenever we find a factor
[in,out]successindicating success
[in]infoinformation about extension
[in]evalevaluation point
[in]degstage of Hensel lifting

Definition at line 982 of file facFqBivar.cc.

987 {
990  CanonicalForm gamma= info.getGamma();
992  int k= info.getGFDegree();
993  DegreePattern bufDegs1= degs, bufDegs2;
994  CFList result;
995  CFList T= factors;
996  Variable y= F.mvar();
997  Variable x= Variable (1);
998  CanonicalForm buf= F, LCBuf= LC (buf, x), g, buf2;
999  CanonicalForm M= power (y, deg);
1000  adaptedLiftBound= 0;
1001  bool trueFactor= false;
1002  int d= degree (F), l= 0;
1003  CFList source, dest;
1004  int degMipoBeta= 1;
1005  if (!k && beta.level() != 1)
1006  degMipoBeta= degree (getMipo (beta));
1007  CanonicalForm quot;
1008  for (CFListIterator i= factors; i.hasItem(); i++, l++)
1009  {
1010  if (!bufDegs1.find (degree (i.getItem(), 1)) || factorsFoundIndex[l] == 1)
1011  continue;
1012  else
1013  {
1014  g= mulMod2 (i.getItem(), LCBuf, M);
1015  g /= content (g, x);
1016  if (fdivides (g, buf, quot))
1017  {
1018  buf2= g (y - eval, y);
1019  buf2 /= Lc (buf2);
1020 
1021  if (!k && beta == x)
1022  {
1023  if (degree (buf2, alpha) < degMipoBeta)
1024  {
1025  appendTestMapDown (reconstructedFactors, buf2, info, source, dest);
1026  factorsFoundIndex[l]= 1;
1027  buf= quot;
1028  d -= degree (g);
1029  LCBuf= LC (buf, x);
1030  trueFactor= true;
1031  }
1032  }
1033  else
1034  {
1035  if (!isInExtension (buf2, gamma, k, delta, source, dest))
1036  {
1037  appendTestMapDown (reconstructedFactors, buf2, info, source, dest);
1038  factorsFoundIndex[l]= 1;
1039  buf= quot;
1040  d -= degree (g);
1041  LCBuf= LC (buf, x);
1042  trueFactor= true;
1043  }
1044  }
1045  if (trueFactor)
1046  {
1047  T= Difference (T, CFList (i.getItem()));
1048  F= buf;
1049 
1050  // compute new possible degree pattern
1051  bufDegs2= DegreePattern (T);
1052  bufDegs1.intersect (bufDegs2);
1053  bufDegs1.refine ();
1054  trueFactor= false;
1055  if (bufDegs1.getLength() <= 1)
1056  {
1057  if (!buf.inCoeffDomain())
1058  {
1059  buf= buf (y - eval, y);
1060  buf /= Lc (buf);
1061  appendMapDown (reconstructedFactors, buf, info, source, dest);
1062  F= 1;
1063  }
1064  break;
1065  }
1066  }
1067  }
1068  }
1069  }
1070  adaptedLiftBound= d + 1;
1071  if (adaptedLiftBound < deg)
1072  {
1073  degs= bufDegs1;
1074  success= true;
1075  }
1076  if (bufDegs1.getLength() <= 1)
1077  degs= bufDegs1;
1078 }
CanonicalForm LC(const CanonicalForm &f)
int l
Definition: cfEzgcd.cc:100
bool fdivides(const CanonicalForm &f, const CanonicalForm &g)
bool fdivides ( const CanonicalForm & f, const CanonicalForm & g )
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
int find(const int x) const
find an element x
void appendTestMapDown(CFList &factors, const CanonicalForm &f, const ExtensionInfo &info, CFList &source, CFList &dest)
test if g is in a subfield of the current field, if so map it down and append it to factors
bool isInExtension(const CanonicalForm &F, const CanonicalForm &gamma, const int k, const CanonicalForm &delta, CFList &source, CFList &dest)
tests if F is not contained in a subfield defined by gamma (Fq case) or k (GF case)
CanonicalForm buf2
Definition: facFqBivar.cc:73
const CanonicalForm & M
Definition: facFqBivar.cc:60
CanonicalForm mulMod2(const CanonicalForm &A, const CanonicalForm &B, const CanonicalForm &M)
Karatsuba style modular multiplication for bivariate polynomials.
Definition: facMul.cc:2986
template List< Variable > Difference(const List< Variable > &, const List< Variable > &)
STATIC_VAR jList * T
Definition: janet.cc:30

◆ extFactorRecombination()

CFList extFactorRecombination ( CFList factors,
CanonicalForm F,
const CanonicalForm N,
const ExtensionInfo info,
DegreePattern degs,
const CanonicalForm eval,
int  s,
int  thres 
)

naive factor recombination over an extension of the initial field. Uses precomputed data to exclude combinations that are not possible.

Returns
extFactorRecombination returns a list of factors over the initial field, whose shift to zero is reversed.
See also
factorRecombination(), extEarlyFactorDetection()

naive factor recombination over an extension of the initial field. Uses precomputed data to exclude combinations that are not possible.

Parameters
[in,out]factorslist of lifted factors that are monic wrt Variable (1), original factors-factors found
[in,out]Fpoly to be factored, F/factors found
[in]NVariable (2)^liftBound
[in]infocontains information about extension
[in]evalevaluation point
[in]salgorithm starts checking subsets of size s
[in]thresthreshold for the size of subsets which are checked, for a full factor recombination choose thres= factors.length()/2

Definition at line 370 of file facFqBivar.cc.

374 {
375  if (factors.length() == 0)
376  {
377  F= 1;
378  return CFList();
379  }
380  if (F.inCoeffDomain())
381  return CFList();
382 
385  CanonicalForm gamma= info.getGamma();
387  int k= info.getGFDegree();
388 
389  CanonicalForm M= N;
390  int l= degree (N);
391  Variable y= F.mvar();
392  Variable x= Variable (1);
393  CFList source, dest;
394  if (degs.getLength() <= 1 || factors.length() == 1)
395  {
396  CFList result= CFList(mapDown (F(y-eval, y), info, source, dest));
397  F= 1;
398  return result;
399  }
400 
401  DEBOUTLN (cerr, "LC (F, 1)*prodMod (factors, M) == F " <<
402  (mod (LC (F, 1)*prodMod (factors, M), M)/Lc (mod (LC (F, 1)*prodMod (factors, M), M)) == F/Lc (F)));
403  int degMipoBeta= 1;
404  if (!k && beta.level() != 1)
405  degMipoBeta= degree (getMipo (beta));
406 
407  CFList T, S, Diff;
408  T= factors;
409 
410  CFList result;
411  CanonicalForm buf, buf2, quot;
412 
413  buf= F;
414 
415  CanonicalForm g, LCBuf= LC (buf, x);
416  int * v= new int [T.length()];
417  for (int i= 0; i < T.length(); i++)
418  v[i]= 0;
419 
420  CFArray TT;
421  DegreePattern bufDegs1, bufDegs2;
422  bufDegs1= degs;
423  int subsetDeg;
424  TT= copy (factors);
425  bool nosubset= false;
426  bool recombination= false;
427  bool trueFactor= false;
429  CanonicalForm buf0= buf (0, x)*LCBuf;
430  while (T.length() >= 2*s && s <= thres)
431  {
432  while (nosubset == false)
433  {
434  if (T.length() == s)
435  {
436  delete [] v;
437  if (recombination)
438  {
439  T.insert (LCBuf);
440  g= prodMod (T, M);
441  T.removeFirst();
442  g /= content(g);
443  g= g (y - eval, y);
444  g /= Lc (g);
445  appendTestMapDown (result, g, info, source, dest);
446  F= 1;
447  return result;
448  }
449  else
450  {
451  appendMapDown (result, F (y - eval, y), info, source, dest);
452  F= 1;
453  return result;
454  }
455  }
456  S= subset (v, s, TT, nosubset);
457  if (nosubset) break;
458  subsetDeg= subsetDegree (S);
459  // skip those combinations that are not possible
460  if (!degs.find (subsetDeg))
461  continue;
462  else
463  {
464  test= prodMod0 (S, M);
465  test *= LCBuf;
466  test = mod (test, M);
467  if (fdivides (test, buf0))
468  {
469  S.insert (LCBuf);
470  g= prodMod (S, M);
471  S.removeFirst();
472  g /= content (g, x);
473  if (fdivides (g, buf, quot))
474  {
475  buf2= g (y - eval, y);
476  buf2 /= Lc (buf2);
477 
478  if (!k && beta.level() == 1)
479  {
480  if (degree (buf2, alpha) < degMipoBeta)
481  {
482  buf= quot;
483  LCBuf= LC (buf, x);
484  recombination= true;
485  appendTestMapDown (result, buf2, info, source, dest);
486  trueFactor= true;
487  }
488  }
489  else
490  {
491  if (!isInExtension (buf2, gamma, k, delta, source, dest))
492  {
493  buf= quot;
494  LCBuf= LC (buf, x);
495  recombination= true;
496  appendTestMapDown (result, buf2, info, source, dest);
497  trueFactor= true;
498  }
499  }
500  if (trueFactor)
501  {
502  T= Difference (T, S);
503  l -= degree (g);
504  M= power (y, l);
505  buf0= buf (0, x)*LCBuf;
506 
507  // compute new possible degree pattern
508  bufDegs2= DegreePattern (T);
509  bufDegs1.intersect (bufDegs2);
510  bufDegs1.refine ();
511  if (T.length() < 2*s || T.length() == s ||
512  bufDegs1.getLength() == 1)
513  {
514  delete [] v;
515  if (recombination)
516  {
517  buf= buf (y-eval,y);
518  buf /= Lc (buf);
519  appendTestMapDown (result, buf, info, source,
520  dest);
521  F= 1;
522  return result;
523  }
524  else
525  {
526  appendMapDown (result, F (y - eval, y), info, source, dest);
527  F= 1;
528  return result;
529  }
530  }
531  trueFactor= false;
532  TT= copy (T);
533  indexUpdate (v, s, T.length(), nosubset);
534  if (nosubset) break;
535  }
536  }
537  }
538  }
539  }
540  s++;
541  if (T.length() < 2*s || T.length() == s)
542  {
543  delete [] v;
544  if (recombination)
545  {
546  buf= buf (y-eval,y);
547  buf /= Lc (buf);
548  appendTestMapDown (result, buf, info, source, dest);
549  F= 1;
550  return result;
551  }
552  else
553  {
554  appendMapDown (result, F (y - eval, y), info, source, dest);
555  F= 1;
556  return result;
557  }
558  }
559  for (int i= 0; i < T.length(); i++)
560  v[i]= 0;
561  nosubset= false;
562  }
563  if (T.length() < 2*s)
564  {
565  appendMapDown (result, F (y - eval, y), info, source, dest);
566  F= 1;
567  delete [] v;
568  return result;
569  }
570 
571  if (s > thres)
572  {
573  factors= T;
574  F= buf;
575  degs= bufDegs1;
576  }
577 
578  delete [] v;
579  return result;
580 }
CanonicalForm test
Definition: cfModGcd.cc:4096
void insert(const T &)
Definition: ftmpl_list.cc:193
const CanonicalForm int s
Definition: facAbsFact.cc:51
int subsetDegree(const CFList &S)
compute the sum of degrees in Variable(1) of elements in S
void indexUpdate(int index[], const int &subsetSize, const int &setSize, bool &noSubset)
update index
CFArray copy(const CFList &list)
write elements of list into an array
CFList subset(int index[], const int &s, const CFArray &elements, bool &noSubset)
extract a subset given by index of size s from elements, if there is no subset we have not yet consid...
return mod(mulNTL(buf1, buf2, b), M)
CanonicalForm prodMod0(const CFList &L, const CanonicalForm &M, const modpk &b=modpk())
via divide-and-conquer
CFList recombination(const CFList &factors1, const CFList &factors2, int s, int thres, const CanonicalForm &evalPoint, const Variable &x)
recombination of bivariate factors factors1 s. t. the result evaluated at evalPoint coincides with fa...
CanonicalForm prodMod(const CFList &L, const CanonicalForm &M)
product of all elements in L modulo M via divide-and-conquer.
Definition: facMul.cc:3180

◆ factorRecombination()

CFList factorRecombination ( CFList factors,
CanonicalForm F,
const CanonicalForm N,
DegreePattern degs,
const CanonicalForm eval,
int  s,
int  thres,
const modpk b,
const CanonicalForm den 
)

naive factor recombination. Uses precomputed data to exclude combinations that are not possible.

Returns
factorRecombination returns a list of factors of F.
See also
extFactorRecombination(), earlyFactorDetectection()

naive factor recombination. Uses precomputed data to exclude combinations that are not possible.

Parameters
[in,out]factorslist of lifted factors that are monic wrt Variable (1)
[in,out]Fpoly to be factored
[in]NVariable (2)^liftBound
[in]degsdegree pattern
[in]evalevaluation point
[in]salgorithm starts checking subsets of size s
[in]thresthreshold for the size of subsets which are checked, for a full factor recombination choose thres= factors.length()/2
[in]bcoeff bound
[in]denbound on the den if over Q (a)

Definition at line 586 of file facFqBivar.cc.

591 {
592  if (factors.length() == 0)
593  {
594  F= 1;
595  return CFList ();
596  }
597  if (F.inCoeffDomain())
598  return CFList();
599  Variable y= Variable (2);
600  if (degs.getLength() <= 1 || factors.length() == 1)
601  {
602  CFList result= CFList (F(y-eval,y));
603  F= 1;
604  return result;
605  }
606 #ifdef DEBUGOUTPUT
607  if (b.getp() == 0)
608  DEBOUTLN (cerr, "LC (F, 1)*prodMod (factors, N) == F " <<
609  (mod (LC (F, 1)*prodMod (factors, N),N)/Lc (mod (LC (F, 1)*prodMod (factors, N),N)) == F/Lc(F)));
610  else
611  DEBOUTLN (cerr, "LC (F, 1)*prodMod (factors, N) == F " <<
612  (mod (b(LC (F, 1)*prodMod (factors, N)),N)/Lc (mod (b(LC (F, 1)*prodMod (factors, N)),N)) == F/Lc(F)));
613 #endif
614 
615  CFList T, S;
616 
617  CanonicalForm M= N;
618  int l= degree (N);
619  T= factors;
620  CFList result;
621  Variable x= Variable (1);
622  CanonicalForm denom= den, denQuot;
623  CanonicalForm LCBuf= LC (F, x)*denom;
624  CanonicalForm g, quot, buf= F;
625  int * v= new int [T.length()];
626  for (int i= 0; i < T.length(); i++)
627  v[i]= 0;
628  bool nosubset= false;
629  CFArray TT;
630  DegreePattern bufDegs1, bufDegs2;
631  bufDegs1= degs;
632  int subsetDeg;
633  TT= copy (factors);
634  bool recombination= false;
636  bool isRat= (isOn (SW_RATIONAL) && getCharacteristic() == 0) ||
637  getCharacteristic() > 0;
638  if (!isRat)
639  On (SW_RATIONAL);
640  CanonicalForm buf0= mulNTL (buf (0, x), LCBuf);
641  if (!isRat)
642  Off (SW_RATIONAL);
643  while (T.length() >= 2*s && s <= thres)
644  {
645  while (nosubset == false)
646  {
647  if (T.length() == s)
648  {
649  delete [] v;
650  if (recombination)
651  {
652  T.insert (LCBuf);
653  g= prodMod (T, M);
654  if (b.getp() != 0)
655  g= b(g);
656  T.removeFirst();
657  g /= content (g,x);
658  result.append (g(y-eval,y));
659  F= 1;
660  return result;
661  }
662  else
663  {
664  result= CFList (F(y-eval,y));
665  F= 1;
666  return result;
667  }
668  }
669  S= subset (v, s, TT, nosubset);
670  if (nosubset) break;
671  subsetDeg= subsetDegree (S);
672  // skip those combinations that are not possible
673  if (!degs.find (subsetDeg))
674  continue;
675  else
676  {
677  if (!isRat)
678  On (SW_RATIONAL);
679  test= prodMod0 (S, M);
680  if (!isRat)
681  {
682  test *= bCommonDen (test);
683  Off (SW_RATIONAL);
684  }
685  test= mulNTL (test, LCBuf, b);
686  test= mod (test, M);
687  if (uniFdivides (test, buf0))
688  {
689  if (!isRat)
690  On (SW_RATIONAL);
691  S.insert (LCBuf);
692  g= prodMod (S, M);
693  S.removeFirst();
694  if (!isRat)
695  {
696  g *= bCommonDen(g);
697  Off (SW_RATIONAL);
698  }
699  if (b.getp() != 0)
700  g= b(g);
701  if (!isRat)
702  On (SW_RATIONAL);
703  g /= content (g, x);
704  if (!isRat)
705  {
706  On (SW_RATIONAL);
707  if (!Lc (g).inBaseDomain())
708  g /= Lc (g);
709  g *= bCommonDen (g);
710  Off (SW_RATIONAL);
711  g /= icontent (g);
712  On (SW_RATIONAL);
713  }
714  if (fdivides (g, buf, quot))
715  {
716  denom *= abs (lc (g));
717  recombination= true;
718  result.append (g (y-eval,y));
719  if (b.getp() != 0)
720  {
721  denQuot= bCommonDen (quot);
722  buf= quot*denQuot;
723  Off (SW_RATIONAL);
724  denom /= gcd (denom, denQuot);
725  On (SW_RATIONAL);
726  }
727  else
728  buf= quot;
729  LCBuf= LC (buf, x)*denom;
730  T= Difference (T, S);
731  l -= degree (g);
732  M= power (y, l);
733  buf0= mulNTL (buf (0, x), LCBuf);
734  if (!isRat)
735  Off (SW_RATIONAL);
736  // compute new possible degree pattern
737  bufDegs2= DegreePattern (T);
738  bufDegs1.intersect (bufDegs2);
739  bufDegs1.refine ();
740  if (T.length() < 2*s || T.length() == s ||
741  bufDegs1.getLength() == 1)
742  {
743  delete [] v;
744  if (recombination)
745  {
746  result.append (buf (y-eval,y));
747  F= 1;
748  return result;
749  }
750  else
751  {
752  result= CFList (F (y-eval,y));
753  F= 1;
754  return result;
755  }
756  }
757  TT= copy (T);
758  indexUpdate (v, s, T.length(), nosubset);
759  if (nosubset) break;
760  }
761  if (!isRat)
762  Off (SW_RATIONAL);
763  }
764  }
765  }
766  s++;
767  if (T.length() < 2*s || T.length() == s)
768  {
769  delete [] v;
770  if (recombination)
771  {
772  result.append (buf(y-eval,y));
773  F= 1;
774  return result;
775  }
776  else
777  {
778  result= CFList (F(y-eval,y));
779  F= 1;
780  return result;
781  }
782  }
783  for (int i= 0; i < T.length(); i++)
784  v[i]= 0;
785  nosubset= false;
786  }
787  delete [] v;
788  if (T.length() < 2*s)
789  {
790  result.append (F(y-eval,y));
791  F= 1;
792  return result;
793  }
794 
795  if (s > thres)
796  {
797  factors= T;
798  F= buf;
799  degs= bufDegs1;
800  }
801 
802  return result;
803 }
Rational abs(const Rational &a)
Definition: GMPrat.cc:436
bool isOn(int sw)
switches
void On(int sw)
switches
void Off(int sw)
switches
CanonicalForm lc(const CanonicalForm &f)
CanonicalForm FACTORY_PUBLIC icontent(const CanonicalForm &f)
CanonicalForm icontent ( const CanonicalForm & f )
Definition: cf_gcd.cc:74
CanonicalForm bCommonDen(const CanonicalForm &f)
CanonicalForm bCommonDen ( const CanonicalForm & f )
static const int SW_RATIONAL
set to 1 for computations over Q
Definition: cf_defs.h:31
CanonicalForm mulNTL(const CanonicalForm &F, const CanonicalForm &G, const modpk &b)
multiplication of univariate polys using FLINT/NTL over F_p, F_q, Z/p^k, Z/p^k[t]/(f),...
Definition: facMul.cc:411
bool uniFdivides(const CanonicalForm &A, const CanonicalForm &B)
divisibility test for univariate polys
Definition: facMul.cc:3759

◆ FpBiFactorize()

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

factorize a bivariate polynomial over $ F_{p} $

Returns
FpBiFactorize returns a list of monic factors with multiplicity, the first element is the leading coefficient.
See also
FqBiFactorize(), GFBiFactorize()
Parameters
[in]Ga bivariate poly
[in]substCheckenables substitute check

Definition at line 190 of file facFqBivar.h.

193 {
195  CFMap N;
196  CanonicalForm F= compress (G, N);
197 
198  if (substCheck)
199  {
200  bool foundOne= false;
201  int * substDegree= NEW_ARRAY(int,F.level());
202  for (int i= 1; i <= F.level(); i++)
203  {
204  substDegree[i-1]= substituteCheck (F, Variable (i));
205  if (substDegree [i-1] > 1)
206  {
207  foundOne= true;
208  subst (F, F, substDegree[i-1], Variable (i));
209  }
210  }
211  if (foundOne)
212  {
213  CFFList result= FpBiFactorize (F, 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 <= F.level(); j++)
222  {
223  if (substDegree[j-1] > 1)
224  tmp2= reverseSubst (tmp2, substDegree[j-1], Variable (j));
225  }
226  tmp= FpBiFactorize (tmp2, 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  decompress (newResult, N);
233  DELETE_ARRAY(substDegree);
234  return newResult;
235  }
236  DELETE_ARRAY(substDegree);
237  }
238 
239  CanonicalForm LcF= Lc (F);
240  CanonicalForm contentX= content (F, 1);
241  CanonicalForm contentY= content (F, 2);
242  F /= (contentX*contentY);
243  CFFList contentXFactors, contentYFactors;
244  contentXFactors= factorize (contentX);
245  contentYFactors= factorize (contentY);
246  if (contentXFactors.getFirst().factor().inCoeffDomain())
247  contentXFactors.removeFirst();
248  if (contentYFactors.getFirst().factor().inCoeffDomain())
249  contentYFactors.removeFirst();
250  decompress (contentXFactors, N);
251  decompress (contentYFactors, N);
252  CFFList result;
253  if (F.inCoeffDomain())
254  {
255  result= Union (contentXFactors, contentYFactors);
256  normalize (result);
257  result.insert (CFFactor (LcF, 1));
258  return result;
259  }
260  mpz_t * M=new mpz_t [4];
261  mpz_init (M[0]);
262  mpz_init (M[1]);
263  mpz_init (M[2]);
264  mpz_init (M[3]);
265 
266  mpz_t * S=new mpz_t [2];
267  mpz_init (S[0]);
268  mpz_init (S[1]);
269 
270  F= compress (F, M, S);
271 
272  TIMING_START (fac_fq_bi_sqrf);
273  CFFList sqrf= FpSqrf (F, false);
274  TIMING_END_AND_PRINT (fac_fq_bi_sqrf,
275  "time for bivariate sqrf factors over Fp: ");
276  CFList bufResult;
277  sqrf.removeFirst();
279  for (CFFListIterator iter= sqrf; iter.hasItem(); iter++)
280  {
281  TIMING_START (fac_fq_bi_factor_sqrf);
282  bufResult= biFactorize (iter.getItem().factor(), info);
283  TIMING_END_AND_PRINT (fac_fq_bi_factor_sqrf,
284  "time to factor bivariate sqrf factors over Fp: ");
285  for (i= bufResult; i.hasItem(); i++)
286  result.append (CFFactor (N (decompress (i.getItem(), M, S)),
287  iter.getItem().exp()));
288  }
289 
290  result= Union (result, contentXFactors);
291  result= Union (result, contentYFactors);
292  normalize (result);
293  result.insert (CFFactor (LcF, 1));
294 
295  mpz_clear (M[0]);
296  mpz_clear (M[1]);
297  mpz_clear (M[2]);
298  mpz_clear (M[3]);
299  delete [] M;
300 
301  mpz_clear (S[0]);
302  mpz_clear (S[1]);
303  delete [] S;
304 
305  return result;
306 }
#define DELETE_ARRAY(P)
Definition: cf_defs.h:65
#define NEW_ARRAY(T, N)
Definition: cf_defs.h:64
CanonicalForm LcF
Definition: facAbsBiFact.cc:50
CFList tmp2
Definition: facFqBivar.cc:72
CFFList FpBiFactorize(const CanonicalForm &G, bool substCheck=true)
factorize a bivariate polynomial over
Definition: facFqBivar.h:190
CFFList FpSqrf(const CanonicalForm &F, bool sort=true)
squarefree factorization over . If input is not monic, the leading coefficient is dropped

◆ FpBiSqrfFactorize()

CFList FpBiSqrfFactorize ( const CanonicalForm G)
inline

factorize a squarefree bivariate polynomial over $ F_{p} $.

Returns
FpBiSqrfFactorize returns a list of monic factors, the first element is the leading coefficient.
See also
FqBiSqrfFactorize(), GFBiSqrfFactorize()
Parameters
[in]Ga bivariate poly

Definition at line 141 of file facFqBivar.h.

143 {
145  return biSqrfFactorizeHelper (G, info);
146 }
CFList biSqrfFactorizeHelper(const CanonicalForm &G, const ExtensionInfo &info)
Definition: facFqBivar.h:55

◆ FqBiFactorize()

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

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

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

Definition at line 317 of file facFqBivar.h.

321 {
323  CFMap N;
324  CanonicalForm F= compress (G, N);
325 
326  if (substCheck)
327  {
328  bool foundOne= false;
329  int * substDegree= NEW_ARRAY(int,F.level());
330  for (int i= 1; i <= F.level(); i++)
331  {
332  substDegree[i-1]= substituteCheck (F, Variable (i));
333  if (substDegree [i-1] > 1)
334  {
335  foundOne= true;
336  subst (F, F, substDegree[i-1], Variable (i));
337  }
338  }
339  if (foundOne)
340  {
341  CFFList result= FqBiFactorize (F, alpha, false);
342  CFFList newResult, tmp;
344  newResult.insert (result.getFirst());
345  result.removeFirst();
346  for (CFFListIterator i= result; i.hasItem(); i++)
347  {
348  tmp2= i.getItem().factor();
349  for (int j= 1; j <= F.level(); j++)
350  {
351  if (substDegree[j-1] > 1)
352  tmp2= reverseSubst (tmp2, substDegree[j-1], Variable (j));
353  }
354  tmp= FqBiFactorize (tmp2, alpha, false);
355  tmp.removeFirst();
356  for (CFFListIterator j= tmp; j.hasItem(); j++)
357  newResult.append (CFFactor (j.getItem().factor(),
358  j.getItem().exp()*i.getItem().exp()));
359  }
360  decompress (newResult, N);
361  DELETE_ARRAY(substDegree);
362  return newResult;
363  }
364  DELETE_ARRAY(substDegree);
365  }
366 
367  CanonicalForm LcF= Lc (F);
368  CanonicalForm contentX= content (F, 1);
369  CanonicalForm contentY= content (F, 2);
370  F /= (contentX*contentY);
371  CFFList contentXFactors, contentYFactors;
372  contentXFactors= factorize (contentX, alpha);
373  contentYFactors= factorize (contentY, alpha);
374  if (contentXFactors.getFirst().factor().inCoeffDomain())
375  contentXFactors.removeFirst();
376  if (contentYFactors.getFirst().factor().inCoeffDomain())
377  contentYFactors.removeFirst();
378  decompress (contentXFactors, N);
379  decompress (contentYFactors, N);
380  CFFList result;
381  if (F.inCoeffDomain())
382  {
383  result= Union (contentXFactors, contentYFactors);
384  normalize (result);
385  result.insert (CFFactor (LcF, 1));
386  return result;
387  }
388 
389  mpz_t * M=new mpz_t [4];
390  mpz_init (M[0]);
391  mpz_init (M[1]);
392  mpz_init (M[2]);
393  mpz_init (M[3]);
394 
395  mpz_t * S=new mpz_t [2];
396  mpz_init (S[0]);
397  mpz_init (S[1]);
398 
399  F= compress (F, M, S);
400 
401  TIMING_START (fac_fq_bi_sqrf);
402  CFFList sqrf= FqSqrf (F, alpha, false);
403  TIMING_END_AND_PRINT (fac_fq_bi_sqrf,
404  "time for bivariate sqrf factors over Fq: ");
405  CFList bufResult;
406  sqrf.removeFirst();
408  for (CFFListIterator iter= sqrf; iter.hasItem(); iter++)
409  {
410  TIMING_START (fac_fq_bi_factor_sqrf);
411  bufResult= biFactorize (iter.getItem().factor(), info);
412  TIMING_END_AND_PRINT (fac_fq_bi_factor_sqrf,
413  "time to factor bivariate sqrf factors over Fq: ");
414  for (i= bufResult; i.hasItem(); i++)
415  result.append (CFFactor (N (decompress (i.getItem(), M, S)),
416  iter.getItem().exp()));
417  }
418 
419  result= Union (result, contentXFactors);
420  result= Union (result, contentYFactors);
421  normalize (result);
422  result.insert (CFFactor (LcF, 1));
423 
424  mpz_clear (M[0]);
425  mpz_clear (M[1]);
426  mpz_clear (M[2]);
427  mpz_clear (M[3]);
428  delete [] M;
429 
430  mpz_clear (S[0]);
431  mpz_clear (S[1]);
432  delete [] S;
433 
434  return result;
435 }
CFFList FqBiFactorize(const CanonicalForm &G, const Variable &alpha, bool substCheck=true)
factorize a bivariate polynomial over
Definition: facFqBivar.h:317
CFFList FqSqrf(const CanonicalForm &F, const Variable &alpha, bool sort=true)
squarefree factorization over . If input is not monic, the leading coefficient is dropped

◆ FqBiSqrfFactorize()

CFList FqBiSqrfFactorize ( const CanonicalForm G,
const Variable alpha 
)
inline

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

Returns
FqBiSqrfFactorize returns a list of monic factors, the first element is the leading coefficient.
See also
FpBiSqrfFactorize(), GFBiSqrfFactorize()
Parameters
[in]Ga bivariate poly
[in]alphaalgebraic variable

Definition at line 156 of file facFqBivar.h.

159 {
161  return biSqrfFactorizeHelper (G, info);
162 }

◆ getLiftPrecisions()

int* getLiftPrecisions ( const CanonicalForm F,
int &  sizeOfOutput,
int  degreeLC 
)

compute lifting precisions from the shape of the Newton polygon of F

Returns
getLiftPrecisions returns lifting precisions computed from the shape of the Newton polygon of F
Parameters
[in]Fa bivariate poly
[in,out]sizeOfOutputsize of the output
[in]degreeLCdegree of the leading coeff [in] of F wrt. Variable (1)

Definition at line 1120 of file facFqBivar.cc.

1121 {
1122  int sizeOfNewtonPoly;
1123  int ** newtonPolyg= newtonPolygon (F, sizeOfNewtonPoly);
1124  int sizeOfRightSide;
1125  int * rightSide= getRightSide(newtonPolyg, sizeOfNewtonPoly, sizeOfRightSide);
1126  int * result= getCombinations(rightSide, sizeOfRightSide, sizeOfOutput,
1127  degreeLC);
1128  delete [] rightSide;
1129  for (int i= 0; i < sizeOfNewtonPoly; i++)
1130  delete [] newtonPolyg[i];
1131  delete [] newtonPolyg;
1132  return result;
1133 }
int * getRightSide(int **polygon, int sizeOfPolygon, int &sizeOfOutput)
get the y-direction slopes of all edges with positive slope in y-direction of a convex polygon with a...
int ** newtonPolygon(const CanonicalForm &F, int &sizeOfNewtonPoly)
compute the Newton polygon of a bivariate polynomial
int * getCombinations(int *rightSide, int sizeOfRightSide, int &sizeOfOutput, int degreeLC)
Definition: facFqBivar.cc:1081

◆ GFBiFactorize()

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

factorize a bivariate polynomial over GF

Returns
GFBiFactorize returns a list of monic factors with multiplicity, the first element is the leading coefficient.
See also
FpBiFactorize(), FqBiFactorize()
Parameters
[in]Ga bivariate poly
[in]substCheckenables substitute check

Definition at line 446 of file facFqBivar.h.

449 {
451  "GF as base field expected");
453  CFMap N;
454  CanonicalForm F= compress (G, N);
455 
456  if (substCheck)
457  {
458  bool foundOne= false;
459  int * substDegree=NEW_ARRAY(int,F.level());
460  for (int i= 1; i <= F.level(); i++)
461  {
462  substDegree[i-1]= substituteCheck (F, Variable (i));
463  if (substDegree [i-1] > 1)
464  {
465  foundOne= true;
466  subst (F, F, substDegree[i-1], Variable (i));
467  }
468  }
469  if (foundOne)
470  {
471  CFFList result= GFBiFactorize (F, false);
472  CFFList newResult, tmp;
474  newResult.insert (result.getFirst());
475  result.removeFirst();
476  for (CFFListIterator i= result; i.hasItem(); i++)
477  {
478  tmp2= i.getItem().factor();
479  for (int j= 1; j <= F.level(); j++)
480  {
481  if (substDegree[j-1] > 1)
482  tmp2= reverseSubst (tmp2, substDegree[j-1], Variable (j));
483  }
484  tmp= GFBiFactorize (tmp2, false);
485  tmp.removeFirst();
486  for (CFFListIterator j= tmp; j.hasItem(); j++)
487  newResult.append (CFFactor (j.getItem().factor(),
488  j.getItem().exp()*i.getItem().exp()));
489  }
490  decompress (newResult, N);
491  DELETE_ARRAY(substDegree);
492  return newResult;
493  }
494  DELETE_ARRAY(substDegree);
495  }
496 
497  CanonicalForm LcF= Lc (F);
498  CanonicalForm contentX= content (F, 1);
499  CanonicalForm contentY= content (F, 2);
500  F /= (contentX*contentY);
501  CFFList contentXFactors, contentYFactors;
502  contentXFactors= factorize (contentX);
503  contentYFactors= factorize (contentY);
504  if (contentXFactors.getFirst().factor().inCoeffDomain())
505  contentXFactors.removeFirst();
506  if (contentYFactors.getFirst().factor().inCoeffDomain())
507  contentYFactors.removeFirst();
508  decompress (contentXFactors, N);
509  decompress (contentYFactors, N);
510  CFFList result;
511  if (F.inCoeffDomain())
512  {
513  result= Union (contentXFactors, contentYFactors);
514  normalize (result);
515  result.insert (CFFactor (LcF, 1));
516  return result;
517  }
518 
519  mpz_t * M=new mpz_t [4];
520  mpz_init (M[0]);
521  mpz_init (M[1]);
522  mpz_init (M[2]);
523  mpz_init (M[3]);
524 
525  mpz_t * S=new mpz_t [2];
526  mpz_init (S[0]);
527  mpz_init (S[1]);
528 
529  F= compress (F, M, S);
530 
531  TIMING_START (fac_fq_bi_sqrf);
532  CFFList sqrf= GFSqrf (F, false);
533  TIMING_END_AND_PRINT (fac_fq_bi_sqrf,
534  "time for bivariate sqrf factors over GF: ");
535  CFList bufResult;
536  sqrf.removeFirst();
538  for (CFFListIterator iter= sqrf; iter.hasItem(); iter++)
539  {
540  TIMING_START (fac_fq_bi_factor_sqrf);
541  bufResult= biFactorize (iter.getItem().factor(), info);
542  TIMING_END_AND_PRINT (fac_fq_bi_factor_sqrf,
543  "time to factor bivariate sqrf factors over GF: ");
544  for (i= bufResult; i.hasItem(); i++)
545  result.append (CFFactor (N (decompress (i.getItem(), M, S)),
546  iter.getItem().exp()));
547  }
548 
549  result= Union (result, contentXFactors);
550  result= Union (result, contentYFactors);
551  normalize (result);
552  result.insert (CFFactor (LcF, 1));
553 
554  mpz_clear (M[0]);
555  mpz_clear (M[1]);
556  mpz_clear (M[2]);
557  mpz_clear (M[3]);
558  delete [] M;
559 
560  mpz_clear (S[0]);
561  mpz_clear (S[1]);
562  delete [] S;
563 
564  return result;
565 }
CFFList GFBiFactorize(const CanonicalForm &G, bool substCheck=true)
factorize a bivariate polynomial over GF
Definition: facFqBivar.h:446
CFFList GFSqrf(const CanonicalForm &F, bool sort=true)
squarefree factorization over GF. If input is not monic, the leading coefficient is dropped
VAR char gf_name
Definition: gfops.cc:52

◆ GFBiSqrfFactorize()

CFList GFBiSqrfFactorize ( const CanonicalForm G)
inline

factorize a squarefree bivariate polynomial over GF

Returns
GFBiSqrfFactorize returns a list of monic factors, the first element is the leading coefficient.
See also
FpBiSqrfFactorize(), FqBiSqrfFactorize()
Parameters
[in]Ga bivariate poly

Definition at line 172 of file facFqBivar.h.

174 {
176  "GF as base field expected");
178  return biSqrfFactorizeHelper (G, info);
179 }

◆ henselLiftAndEarly() [1/2]

CFList henselLiftAndEarly ( CanonicalForm A,
bool &  earlySuccess,
CFList earlyFactors,
DegreePattern degs,
int &  liftBound,
const CFList uniFactors,
const ExtensionInfo info,
const CanonicalForm eval 
)

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
earlyFactorDetection(), extEarlyFactorDetection()
Parameters
[in,out]Apoly to be factored, returns poly divided by detected factors in case of success
[in,out]earlySuccessindicating success
[in,out]earlyFactorslist of factors detected at early stage of Hensel lifting
[in,out]degsdegree pattern
[in,out]liftBound(adapted) lift bound
[in]uniFactorsunivariate factors
[in]infoinformation about extension
[in]evalevaluation point

Definition at line 1455 of file facFqBivar.cc.

1459 {
1460  modpk dummy= modpk();
1461  CanonicalForm den= 1;
1462  return henselLiftAndEarly (A, earlySuccess, earlyFactors, degs, liftBound,
1463  uniFactors, info, eval, dummy, den);
1464 }
class to do operations mod p^k for int's p and k
Definition: fac_util.h:23
return modpk(p, k)

◆ henselLiftAndEarly() [2/2]

CFList henselLiftAndEarly ( CanonicalForm A,
bool &  earlySuccess,
CFList earlyFactors,
DegreePattern degs,
int &  liftBound,
const CFList uniFactors,
const ExtensionInfo info,
const CanonicalForm eval,
modpk b,
CanonicalForm den 
)

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
earlyFactorDetection(), extEarlyFactorDetection()
Parameters
[in,out]Apoly to be factored, returns poly divided by detected factors in case of success
[in,out]earlySuccessindicating success
[in,out]earlyFactorslist of factors detected at early stage of Hensel lifting
[in,out]degsdegree pattern
[in,out]liftBound(adapted) lift bound
[in]uniFactorsunivariate factors
[in]infoinformation about extension
[in]evalevaluation point
[in]bcoeff bound
[in]denbound on the den if over Q(a)

Definition at line 1152 of file facFqBivar.cc.

1156 {
1159  CanonicalForm gamma= info.getGamma();
1161  bool extension= info.isInExtension();
1162 
1163  int sizeOfLiftPre;
1164  int * liftPre= getLiftPrecisions (A, sizeOfLiftPre, degree (LC (A, 1), 2));
1165 
1166  Variable x= Variable (1);
1167  Variable y= Variable (2);
1168  CFArray Pi;
1169  CFList diophant;
1170  CFList bufUniFactors= uniFactors;
1171  On (SW_RATIONAL);
1172  CanonicalForm bufA= A;
1173  if (!Lc (A).inBaseDomain())
1174  {
1175  bufA /= Lc (A);
1176  CanonicalForm denBufA= bCommonDen (bufA);
1177  bufA *= denBufA;
1178  Off (SW_RATIONAL);
1179  den /= gcd (den, denBufA);
1180  }
1181  else
1182  {
1183  bufA= A;
1184  Off (SW_RATIONAL);
1185  den /= gcd (den, Lc (A));
1186  }
1187  CanonicalForm lcA0= 0;
1188  bool mipoHasDen= false;
1189  if (getCharacteristic() == 0 && b.getp() != 0)
1190  {
1191  if (alpha.level() == 1)
1192  {
1193  lcA0= lc (A (0, 2));
1194  A *= b.inverse (lcA0);
1195  A= b (A);
1196  for (CFListIterator i= bufUniFactors; i.hasItem(); i++)
1197  i.getItem()= b (i.getItem()*b.inverse (lc (i.getItem())));
1198  }
1199  else
1200  {
1201  lcA0= Lc (A (0,2));
1202  On (SW_RATIONAL);
1203  mipoHasDen= !bCommonDen(getMipo(alpha)).isOne();
1204  Off (SW_RATIONAL);
1205  CanonicalForm lcA0inverse= b.inverse (lcA0);
1206  A *= lcA0inverse;
1207  A= b (A);
1208  // Lc of bufUniFactors is in Z
1209  for (CFListIterator i= bufUniFactors; i.hasItem(); i++)
1210  i.getItem()= b (i.getItem()*b.inverse (lc (i.getItem())));
1211  }
1212  }
1213  bufUniFactors.insert (LC (A, x));
1214  CFMatrix M= CFMatrix (liftBound, bufUniFactors.length() - 1);
1215  earlySuccess= false;
1216  int newLiftBound= 0;
1217 
1218  int smallFactorDeg= tmin (11, liftPre [sizeOfLiftPre- 1] + 1);//this is a tunable parameter
1219  int dummy;
1220  int * factorsFoundIndex= new int [uniFactors.length()];
1221  for (int i= 0; i < uniFactors.length(); i++)
1222  factorsFoundIndex [i]= 0;
1223 
1224  CFList bufBufUniFactors;
1225  Variable v= alpha;
1226  if (smallFactorDeg >= liftBound || degree (A,y) <= 4)
1227  henselLift12 (A, bufUniFactors, liftBound, Pi, diophant, M, b, true);
1228  else if (sizeOfLiftPre > 1 && sizeOfLiftPre < 30)
1229  {
1230  henselLift12 (A, bufUniFactors, smallFactorDeg, Pi, diophant, M, b, true);
1231  if (mipoHasDen)
1232  {
1233  for (CFListIterator iter= bufUniFactors; iter.hasItem(); iter++)
1234  if (hasFirstAlgVar (iter.getItem(), v))
1235  break;
1236  if (v != alpha)
1237  {
1238  bufBufUniFactors= bufUniFactors;
1239  for (CFListIterator iter= bufBufUniFactors; iter.hasItem(); iter++)
1241  A= replacevar (A, alpha, v);
1242  }
1243  }
1244 
1245  if (!extension)
1246  {
1247  if (v==alpha)
1248  earlyFactorDetection (earlyFactors, bufA, bufUniFactors, newLiftBound,
1249  factorsFoundIndex, degs, earlySuccess,
1250  smallFactorDeg, eval, b, den);
1251  else
1252  earlyFactorDetection(earlyFactors, bufA, bufBufUniFactors, newLiftBound,
1253  factorsFoundIndex, degs, earlySuccess,
1254  smallFactorDeg, eval, b, den);
1255  }
1256  else
1257  extEarlyFactorDetection (earlyFactors, bufA, bufUniFactors, newLiftBound,
1258  factorsFoundIndex, degs, earlySuccess, info,
1259  eval, smallFactorDeg);
1260  if (degs.getLength() > 1 && !earlySuccess &&
1261  smallFactorDeg != liftPre [sizeOfLiftPre-1] + 1)
1262  {
1263  if (newLiftBound >= liftPre[sizeOfLiftPre-1]+1)
1264  {
1265  bufUniFactors.insert (LC (A, x));
1266  henselLiftResume12 (A, bufUniFactors, smallFactorDeg,
1267  liftPre[sizeOfLiftPre-1] + 1, Pi, diophant, M, b);
1268  if (v!=alpha)
1269  {
1270  bufBufUniFactors= bufUniFactors;
1271  for (CFListIterator iter= bufBufUniFactors; iter.hasItem(); iter++)
1273  }
1274  if (!extension)
1275  {
1276  if (v==alpha)
1277  earlyFactorDetection (earlyFactors, bufA, bufUniFactors, newLiftBound,
1278  factorsFoundIndex, degs, earlySuccess,
1279  liftPre[sizeOfLiftPre-1] + 1, eval, b, den);
1280  else
1281  earlyFactorDetection (earlyFactors,bufA,bufBufUniFactors,newLiftBound,
1282  factorsFoundIndex, degs, earlySuccess,
1283  liftPre[sizeOfLiftPre-1] + 1, eval, b, den);
1284  }
1285  else
1286  extEarlyFactorDetection (earlyFactors,bufA,bufUniFactors,newLiftBound,
1287  factorsFoundIndex, degs, earlySuccess, info,
1288  eval, liftPre[sizeOfLiftPre-1] + 1);
1289  }
1290  }
1291  else if (earlySuccess)
1292  liftBound= newLiftBound;
1293 
1294  int i= sizeOfLiftPre - 1;
1295  while (degs.getLength() > 1 && !earlySuccess && i - 1 >= 0)
1296  {
1297  if (newLiftBound >= liftPre[i] + 1)
1298  {
1299  bufUniFactors.insert (LC (A, x));
1300  henselLiftResume12 (A, bufUniFactors, liftPre[i] + 1,
1301  liftPre[i-1] + 1, Pi, diophant, M, b);
1302  if (v!=alpha)
1303  {
1304  bufBufUniFactors= bufUniFactors;
1305  for (CFListIterator iter= bufBufUniFactors; iter.hasItem(); iter++)
1307  }
1308  if (!extension)
1309  {
1310  if (v==alpha)
1311  earlyFactorDetection (earlyFactors, bufA, bufUniFactors, newLiftBound,
1312  factorsFoundIndex, degs, earlySuccess,
1313  liftPre[i-1] + 1, eval, b, den);
1314  else
1315  earlyFactorDetection (earlyFactors,bufA,bufBufUniFactors,newLiftBound,
1316  factorsFoundIndex, degs, earlySuccess,
1317  liftPre[i-1] + 1, eval, b, den);
1318  }
1319  else
1320  extEarlyFactorDetection (earlyFactors,bufA,bufUniFactors,newLiftBound,
1321  factorsFoundIndex, degs, earlySuccess, info,
1322  eval, liftPre[i-1] + 1);
1323  }
1324  else
1325  {
1326  liftBound= newLiftBound;
1327  break;
1328  }
1329  i--;
1330  }
1331  if (earlySuccess)
1332  liftBound= newLiftBound;
1333  //after here all factors are lifted to liftPre[sizeOfLiftPre-1]
1334  }
1335  else
1336  {
1337  henselLift12 (A, bufUniFactors, smallFactorDeg, Pi, diophant, M, b, true);
1338  if (mipoHasDen)
1339  {
1340  for (CFListIterator iter= bufUniFactors; iter.hasItem(); iter++)
1341  if (hasFirstAlgVar (iter.getItem(), v))
1342  break;
1343  if (v != alpha)
1344  {
1345  bufBufUniFactors= bufUniFactors;
1346  for (CFListIterator iter= bufBufUniFactors; iter.hasItem(); iter++)
1348  A= replacevar (A, alpha, v);
1349  }
1350  }
1351  if (!extension)
1352  {
1353  if (v==alpha)
1354  earlyFactorDetection (earlyFactors, bufA, bufUniFactors, newLiftBound,
1355  factorsFoundIndex, degs, earlySuccess,
1356  smallFactorDeg, eval, b, den);
1357  else
1358  earlyFactorDetection (earlyFactors, bufA, bufBufUniFactors, newLiftBound,
1359  factorsFoundIndex, degs, earlySuccess,
1360  smallFactorDeg, eval, b, den);
1361  }
1362  else
1363  extEarlyFactorDetection (earlyFactors, bufA, bufUniFactors, newLiftBound,
1364  factorsFoundIndex, degs, earlySuccess, info,
1365  eval, smallFactorDeg);
1366  int i= 1;
1367  while ((degree (A,y)/4)*i + 4 <= smallFactorDeg)
1368  i++;
1369  dummy= tmin (degree (A,y)+1, (degree (A,y)/4)*i+4);
1370  if (degs.getLength() > 1 && !earlySuccess && dummy > smallFactorDeg)
1371  {
1372  bufUniFactors.insert (LC (A, x));
1373  henselLiftResume12 (A, bufUniFactors, smallFactorDeg,
1374  dummy, Pi, diophant, M, b);
1375  if (v!=alpha)
1376  {
1377  bufBufUniFactors= bufUniFactors;
1378  for (CFListIterator iter= bufBufUniFactors; iter.hasItem(); iter++)
1380  }
1381  if (!extension)
1382  {
1383  if (v==alpha)
1384  earlyFactorDetection (earlyFactors, bufA, bufUniFactors, newLiftBound,
1385  factorsFoundIndex, degs, earlySuccess, dummy,eval,
1386  b, den);
1387  else
1388  earlyFactorDetection (earlyFactors, bufA,bufBufUniFactors, newLiftBound,
1389  factorsFoundIndex, degs, earlySuccess, dummy,eval,
1390  b, den);
1391  }
1392  else
1393  extEarlyFactorDetection (earlyFactors, bufA,bufUniFactors, newLiftBound,
1394  factorsFoundIndex, degs, earlySuccess, info,
1395  eval, dummy);
1396  }
1397  while (degs.getLength() > 1 && !earlySuccess && i < 4)
1398  {
1399  if (newLiftBound >= dummy)
1400  {
1401  bufUniFactors.insert (LC (A, x));
1402  dummy= tmin (degree (A,y)+1, (degree (A,y)/4)*(i+1)+4);
1403  henselLiftResume12 (A, bufUniFactors, (degree (A,y)/4)*i + 4,
1404  dummy, Pi, diophant, M, b);
1405  if (v!=alpha)
1406  {
1407  bufBufUniFactors= bufUniFactors;
1408  for (CFListIterator iter= bufBufUniFactors; iter.hasItem(); iter++)
1410  }
1411  if (!extension)
1412  {
1413  if (v==alpha)
1414  earlyFactorDetection (earlyFactors, bufA, bufUniFactors, newLiftBound,
1415  factorsFoundIndex, degs, earlySuccess, dummy,
1416  eval, b, den);
1417  else
1418  earlyFactorDetection (earlyFactors,bufA,bufBufUniFactors,newLiftBound,
1419  factorsFoundIndex, degs, earlySuccess, dummy,
1420  eval, b, den);
1421  }
1422  else
1423  extEarlyFactorDetection (earlyFactors,bufA,bufUniFactors,newLiftBound,
1424  factorsFoundIndex, degs, earlySuccess, info,
1425  eval, dummy);
1426  }
1427  else
1428  {
1429  liftBound= newLiftBound;
1430  break;
1431  }
1432  i++;
1433  }
1434  if (earlySuccess)
1435  liftBound= newLiftBound;
1436  }
1437 
1438  A= bufA;
1439  if (earlyFactors.length() > 0 && degs.getLength() > 1)
1440  {
1441  liftBound= degree (A,y) + 1;
1442  earlySuccess= true;
1443  deleteFactors (bufUniFactors, factorsFoundIndex);
1444  }
1445 
1446  delete [] factorsFoundIndex;
1447  delete [] liftPre;
1448 
1449  return bufUniFactors;
1450 }
CanonicalForm FACTORY_PUBLIC replacevar(const CanonicalForm &, const Variable &, const Variable &)
CanonicalForm replacevar ( const CanonicalForm & f, const Variable & x1, const Variable & x2 )
Definition: cf_ops.cc:271
bool hasFirstAlgVar(const CanonicalForm &f, Variable &a)
check if poly f contains an algebraic variable a
Definition: cf_ops.cc:679
Matrix< CanonicalForm > CFMatrix
CF_NO_INLINE bool isOne() const
void extEarlyFactorDetection(CFList &reconstructedFactors, CanonicalForm &F, CFList &factors, int &adaptedLiftBound, int *&factorsFoundIndex, DegreePattern &degs, bool &success, const ExtensionInfo &info, const CanonicalForm &eval, int deg)
detects factors of F at stage deg of Hensel lifting. No combinations of more than one factor are test...
Definition: facFqBivar.cc:982
void deleteFactors(CFList &factors, int *factorsFoundIndex)
Definition: facFqBivar.cc:1136
int * getLiftPrecisions(const CanonicalForm &F, int &sizeOfOutput, int degreeLC)
compute lifting precisions from the shape of the Newton polygon of F
Definition: facFqBivar.cc:1120
void henselLift12(const CanonicalForm &F, CFList &factors, int l, CFArray &Pi, CFList &diophant, CFMatrix &M, modpk &b, bool sort)
Hensel lift from univariate to bivariate.
Definition: facHensel.cc:1274
void henselLiftResume12(const CanonicalForm &F, CFList &factors, int start, int end, CFArray &Pi, const CFList &diophant, CFMatrix &M, const modpk &b)
resume Hensel lift from univariate to bivariate. Assumes factors are lifted to precision Variable (2)...
Definition: facHensel.cc:1343

◆ prodMod0()

CanonicalForm prodMod0 ( const CFList L,
const CanonicalForm M,
const modpk b = modpk() 
)

$ \prod_{f\in L} {f (0, x)} \ mod\ M $ via divide-and-conquer

Returns
prodMod0 computes the above defined product
See also
prodMod()
Parameters
[in]La list of compressed, bivariate polynomials
[in]Ma power of Variable (2)
[in]bcoeff bound

◆ TIMING_DEFINE_PRINT()

TIMING_DEFINE_PRINT ( fac_fq_bi_sqrf  ) const

◆ uniFactorizer()

CFList uniFactorizer ( const CanonicalForm A,
const Variable alpha,
const bool &  GF 
)

Univariate factorization of squarefree monic polys over finite fields via NTL. If the characteristic is even special GF2 routines of NTL are used.

Returns
uniFactorizer returns a list of monic factors
Parameters
[in]Asquarefree univariate poly
[in]alphaalgebraic variable
[in]GFGaloisFieldDomain?

Definition at line 160 of file facFqBivar.cc.

161 {
162  Variable x= A.mvar();
163  if (A.inCoeffDomain())
164  return CFList();
165  ASSERT (A.isUnivariate(),
166  "univariate polynomial expected or constant expected");
167  CFFList factorsA;
168  if (GF)
169  {
170  int k= getGFDegree();
171  char cGFName= gf_name;
176 #ifdef HAVE_NTL
177  if (getCharacteristic() > 2)
178 #else
179  if (getCharacteristic() > 0)
180 #endif
181  {
182 #if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
183  nmod_poly_t FLINTmipo, leadingCoeff;
184  fq_nmod_ctx_t fq_con;
185  fq_nmod_poly_t FLINTA;
186  fq_nmod_poly_factor_t FLINTFactorsA;
187 
188  nmod_poly_init (FLINTmipo, getCharacteristic());
189  convertFacCF2nmod_poly_t (FLINTmipo, mipo.mapinto());
190 
191  fq_nmod_ctx_init_modulus (fq_con, FLINTmipo, "Z");
192 
194  fq_nmod_poly_make_monic (FLINTA, FLINTA, fq_con);
195 
196  fq_nmod_poly_factor_init (FLINTFactorsA, fq_con);
197  nmod_poly_init (leadingCoeff, getCharacteristic());
198 
199  fq_nmod_poly_factor (FLINTFactorsA, leadingCoeff, FLINTA, fq_con);
200 
201  factorsA= convertFLINTFq_nmod_poly_factor2FacCFFList (FLINTFactorsA, x,
202  beta, fq_con);
203 
204  fq_nmod_poly_factor_clear (FLINTFactorsA, fq_con);
205  fq_nmod_poly_clear (FLINTA, fq_con);
206  nmod_poly_clear (FLINTmipo);
207  nmod_poly_clear (leadingCoeff);
209 #else
211  {
214  }
215  zz_pX NTLMipo= convertFacCF2NTLzzpX (mipo.mapinto());
216  zz_pE::init (NTLMipo);
217  zz_pEX NTLA= convertFacCF2NTLzz_pEX (buf, NTLMipo);
218  MakeMonic (NTLA);
219  vec_pair_zz_pEX_long NTLFactorsA= CanZass (NTLA);
220  zz_pE multi= to_zz_pE (1);
221  factorsA= convertNTLvec_pair_zzpEX_long2FacCFFList (NTLFactorsA, multi,
222  x, beta);
223 #endif
224  }
225 #ifdef HAVE_NTL
226  else
227  {
228  GF2X NTLMipo= convertFacCF2NTLGF2X (mipo.mapinto());
229  GF2E::init (NTLMipo);
230  GF2EX NTLA= convertFacCF2NTLGF2EX (buf, NTLMipo);
231  MakeMonic (NTLA);
232  vec_pair_GF2EX_long NTLFactorsA= CanZass (NTLA);
233  GF2E multi= to_GF2E (1);
234  factorsA= convertNTLvec_pair_GF2EX_long2FacCFFList (NTLFactorsA, multi,
235  x, beta);
236  }
237 #endif
238  setCharacteristic (getCharacteristic(), k, cGFName);
239  for (CFFListIterator i= factorsA; i.hasItem(); i++)
240  {
241  buf= i.getItem().factor();
242  buf= Falpha2GFRep (buf);
243  i.getItem()= CFFactor (buf, i.getItem().exp());
244  }
245  prune (beta);
246  }
247  else if (alpha.level() != 1)
248  {
249 #ifdef HAVE_NTL
250  if (getCharacteristic() > 2)
251 #else
252  if (getCharacteristic() > 0)
253 #endif
254  {
255 #if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
256  nmod_poly_t FLINTmipo, leadingCoeff;
257  fq_nmod_ctx_t fq_con;
258  fq_nmod_poly_t FLINTA;
259  fq_nmod_poly_factor_t FLINTFactorsA;
260 
261  nmod_poly_init (FLINTmipo, getCharacteristic());
262  convertFacCF2nmod_poly_t (FLINTmipo, getMipo (alpha));
263 
264  fq_nmod_ctx_init_modulus (fq_con, FLINTmipo, "Z");
265 
267  fq_nmod_poly_make_monic (FLINTA, FLINTA, fq_con);
268 
269  fq_nmod_poly_factor_init (FLINTFactorsA, fq_con);
270  nmod_poly_init (leadingCoeff, getCharacteristic());
271 
272  fq_nmod_poly_factor (FLINTFactorsA, leadingCoeff, FLINTA, fq_con);
273 
274  factorsA= convertFLINTFq_nmod_poly_factor2FacCFFList (FLINTFactorsA, x,
275  alpha, fq_con);
276 
277  fq_nmod_poly_factor_clear (FLINTFactorsA, fq_con);
278  fq_nmod_poly_clear (FLINTA, fq_con);
279  nmod_poly_clear (FLINTmipo);
280  nmod_poly_clear (leadingCoeff);
282 #else
284  {
287  }
288  zz_pX NTLMipo= convertFacCF2NTLzzpX (getMipo (alpha));
289  zz_pE::init (NTLMipo);
290  zz_pEX NTLA= convertFacCF2NTLzz_pEX (A, NTLMipo);
291  MakeMonic (NTLA);
292  vec_pair_zz_pEX_long NTLFactorsA= CanZass (NTLA);
293  zz_pE multi= to_zz_pE (1);
294  factorsA= convertNTLvec_pair_zzpEX_long2FacCFFList (NTLFactorsA, multi,
295  x, alpha);
296 #endif
297  }
298 #ifdef HAVE_NTL
299  else
300  {
301  GF2X NTLMipo= convertFacCF2NTLGF2X (getMipo (alpha));
302  GF2E::init (NTLMipo);
303  GF2EX NTLA= convertFacCF2NTLGF2EX (A, NTLMipo);
304  MakeMonic (NTLA);
305  vec_pair_GF2EX_long NTLFactorsA= CanZass (NTLA);
306  GF2E multi= to_GF2E (1);
307  factorsA= convertNTLvec_pair_GF2EX_long2FacCFFList (NTLFactorsA, multi,
308  x, alpha);
309  }
310 #endif
311  }
312  else
313  {
314 #ifdef HAVE_FLINT
315 #ifdef HAVE_NTL
316  if (degree (A) < 300)
317 #endif
318  {
319  nmod_poly_t FLINTA;
320  convertFacCF2nmod_poly_t (FLINTA, A);
321  nmod_poly_factor_t result;
322  nmod_poly_factor_init (result);
323  mp_limb_t leadingCoeff= nmod_poly_factor (result, FLINTA);
324  factorsA= convertFLINTnmod_poly_factor2FacCFFList (result, leadingCoeff, x);
325  if (factorsA.getFirst().factor().inCoeffDomain())
326  factorsA.removeFirst();
327  nmod_poly_factor_clear (result);
328  nmod_poly_clear (FLINTA);
329  }
330 #ifdef HAVE_NTL
331  else
332 #endif
333 #endif /* HAVE_FLINT */
334 #ifdef HAVE_NTL
335  if (getCharacteristic() > 2)
336  {
338  {
341  }
342  zz_pX NTLA= convertFacCF2NTLzzpX (A);
343  MakeMonic (NTLA);
344  vec_pair_zz_pX_long NTLFactorsA= CanZass (NTLA);
345  zz_p multi= to_zz_p (1);
346  factorsA= convertNTLvec_pair_zzpX_long2FacCFFList (NTLFactorsA, multi,
347  x);
348  }
349  else
350  {
351  GF2X NTLA= convertFacCF2NTLGF2X (A);
352  vec_pair_GF2X_long NTLFactorsA= CanZass (NTLA);
353  GF2 multi= to_GF2 (1);
354  factorsA= convertNTLvec_pair_GF2X_long2FacCFFList (NTLFactorsA, multi,
355  x);
356  }
357 #endif
358  }
359  CFList uniFactors;
360  for (CFFListIterator i= factorsA; i.hasItem(); i++)
361  uniFactors.append (i.getItem().factor());
362  return uniFactors;
363 }
CFFList convertFLINTFq_nmod_poly_factor2FacCFFList(const fq_nmod_poly_factor_t fac, const Variable &x, const Variable &alpha, const fq_nmod_ctx_t fq_con)
conversion of a FLINT factorization over Fq (for word size p) to a CFFList
void convertFacCF2Fq_nmod_poly_t(fq_nmod_poly_t result, const CanonicalForm &f, const fq_nmod_ctx_t ctx)
conversion of a factory univariate poly over F_q to a FLINT fq_nmod_poly_t
CFFList convertFLINTnmod_poly_factor2FacCFFList(const nmod_poly_factor_t fac, const mp_limb_t leadingCoeff, const Variable &x)
conversion of a FLINT factorization over Z/p (for word size p) to a CFFList
CFFList convertNTLvec_pair_GF2X_long2FacCFFList(const vec_pair_GF2X_long &e, GF2, const Variable &x)
NAME: convertNTLvec_pair_GF2X_long2FacCFFList.
Definition: NTLconvert.cc:446
zz_pEX convertFacCF2NTLzz_pEX(const CanonicalForm &f, const zz_pX &mipo)
Definition: NTLconvert.cc:1064
CFFList convertNTLvec_pair_zzpEX_long2FacCFFList(const vec_pair_zz_pEX_long &e, const zz_pE &cont, const Variable &x, const Variable &alpha)
Definition: NTLconvert.cc:870
CFFList convertNTLvec_pair_GF2EX_long2FacCFFList(const vec_pair_GF2EX_long &e, const GF2E &cont, const Variable &x, const Variable &alpha)
NAME: convertNTLvec_pair_GF2EX_long2FacCFFList.
Definition: NTLconvert.cc:959
CFFList convertNTLvec_pair_zzpX_long2FacCFFList(const vec_pair_zz_pX_long &e, const zz_p cont, const Variable &x)
Definition: NTLconvert.cc:399
GF2EX convertFacCF2NTLGF2EX(const CanonicalForm &f, const GF2X &mipo)
CanonicalForm in Z_2(a)[X] to NTL GF2EX.
Definition: NTLconvert.cc:1007
zz_pX convertFacCF2NTLzzpX(const CanonicalForm &f)
Definition: NTLconvert.cc:105
GF2X convertFacCF2NTLGF2X(const CanonicalForm &f)
NAME: convertFacCF2NTLGF2X.
Definition: NTLconvert.cc:184
Factor< CanonicalForm > CFFactor
fq_nmod_ctx_t fq_con
Definition: facHensel.cc:99
fq_nmod_ctx_clear(fq_con)
fq_nmod_ctx_init_modulus(fq_con, FLINTmipo, "Z")
convertFacCF2nmod_poly_t(FLINTmipo, M)
nmod_poly_clear(FLINTmipo)
fq_nmod_poly_clear(prod, fq_con)