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"

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 8201 of file facFqBivar.cc.

8202 {
8203  if (F.inCoeffDomain())
8204  return CFList(F);
8205 
8206  CanonicalForm A= F;
8207  bool GF= (CFFactory::gettype() == GaloisFieldDomain);
8208 
8209  Variable alpha= info.getAlpha();
8210  Variable beta= info.getBeta();
8211  CanonicalForm gamma= info.getGamma();
8212  CanonicalForm delta= info.getDelta();
8213  int k= info.getGFDegree();
8214  bool extension= info.isInExtension();
8215  if (A.isUnivariate())
8216  {
8217  if (extension == false)
8218  return uniFactorizer (F, alpha, GF);
8219  else
8220  {
8221  CFList source, dest;
8222  A= mapDown (A, info, source, dest);
8223  return uniFactorizer (A, beta, GF);
8224  }
8225  }
8226 
8227  CFMap N;
8228  A= compress (A, N);
8229  Variable y= A.mvar();
8230 
8231  if (y.level() > 2) return CFList (F);
8232  Variable x= Variable (1);
8233 
8234  //remove and factorize content
8235  CanonicalForm contentAx= content (A, x);
8236  CanonicalForm contentAy= content (A);
8237 
8238  A= A/(contentAx*contentAy);
8239  CFList contentAxFactors, contentAyFactors;
8240 
8241  if (!extension)
8242  {
8243  contentAxFactors= uniFactorizer (contentAx, alpha, GF);
8244  contentAyFactors= uniFactorizer (contentAy, alpha, GF);
8245  }
8246 
8247  //trivial case
8248  CFList factors;
8249  if (A.inCoeffDomain())
8250  {
8251  append (factors, contentAxFactors);
8252  append (factors, contentAyFactors);
8253  decompress (factors, N);
8254  return factors;
8255  }
8256  else if (A.isUnivariate())
8257  {
8258  factors= uniFactorizer (A, alpha, GF);
8259  append (factors, contentAxFactors);
8260  append (factors, contentAyFactors);
8261  decompress (factors, N);
8262  return factors;
8263  }
8264 
8265 
8266  //check trivial case
8267  if (degree (A) == 1 || degree (A, 1) == 1 ||
8268  (size (A) == 2 && igcd (degree (A), degree (A,1))==1))
8269  {
8270  factors.append (A);
8271 
8272  appendSwapDecompress (factors, contentAxFactors, contentAyFactors,
8273  false, false, N);
8274 
8275  if (!extension)
8276  normalize (factors);
8277  return factors;
8278  }
8279 
8280  // check derivatives
8281  bool derivXZero= false;
8282  CanonicalForm derivX= deriv (A, x);
8283  CanonicalForm gcdDerivX;
8284  if (derivX.isZero())
8285  derivXZero= true;
8286  else
8287  {
8288  gcdDerivX= gcd (A, derivX);
8289  if (degree (gcdDerivX) > 0)
8290  {
8291  CanonicalForm g= A/gcdDerivX;
8292  CFList factorsG=
8293  Union (biFactorize (g, info), biFactorize (gcdDerivX, info));
8294  append (factorsG, contentAxFactors);
8295  append (factorsG, contentAyFactors);
8296  decompress (factorsG, N);
8297  if (!extension)
8298  normalize (factorsG);
8299  return factorsG;
8300  }
8301  }
8302  bool derivYZero= false;
8303  CanonicalForm derivY= deriv (A, y);
8304  CanonicalForm gcdDerivY;
8305  if (derivY.isZero())
8306  derivYZero= true;
8307  else
8308  {
8309  gcdDerivY= gcd (A, derivY);
8310  if (degree (gcdDerivY) > 0)
8311  {
8312  CanonicalForm g= A/gcdDerivY;
8313  CFList factorsG=
8314  Union (biFactorize (g, info), biFactorize (gcdDerivY, info));
8315  append (factorsG, contentAxFactors);
8316  append (factorsG, contentAyFactors);
8317  decompress (factorsG, N);
8318  if (!extension)
8319  normalize (factorsG);
8320  return factorsG;
8321  }
8322  }
8323  //main variable is chosen s.t. the degree in x is minimal
8324  bool swap= false;
8325  if ((degree (A) > degree (A, x)) || derivXZero)
8326  {
8327  if (!derivYZero)
8328  {
8329  A= swapvar (A, y, x);
8330  swap= derivXZero;
8331  derivXZero= derivYZero;
8332  derivYZero= swap;
8333  swap= true;
8334  }
8335  }
8336 
8337  int boundsLength;
8338  bool isIrreducible= false;
8339  int * bounds= computeBounds (A, boundsLength, isIrreducible);
8340  if (isIrreducible)
8341  {
8342  delete [] bounds;
8343  factors.append (A);
8344 
8345  appendSwapDecompress (factors, contentAxFactors, contentAyFactors,
8346  swap, false, N);
8347 
8348  if (!extension)
8349  normalize (factors);
8350  return factors;
8351  }
8352 
8353  int minBound= bounds[0];
8354  for (int i= 1; i < boundsLength; i++)
8355  {
8356  if (bounds[i] != 0)
8357  minBound= tmin (minBound, bounds[i]);
8358  }
8359 
8360  int boundsLength2;
8361  int * bounds2= computeBoundsWrtDiffMainvar (A, boundsLength2, isIrreducible);
8362  int minBound2= bounds2[0];
8363  for (int i= 1; i < boundsLength2; i++)
8364  {
8365  if (bounds2[i] != 0)
8366  minBound2= tmin (minBound2, bounds2[i]);
8367  }
8368 
8369 
8370  bool fail= false;
8371  CanonicalForm Aeval, evaluation, bufAeval, bufEvaluation, buf, tmp;
8372  CFList uniFactors, list, bufUniFactors;
8373  DegreePattern degs;
8374  DegreePattern bufDegs;
8375 
8376  bool fail2= false;
8377  CanonicalForm Aeval2, evaluation2, bufAeval2, bufEvaluation2;
8378  CFList bufUniFactors2, list2, uniFactors2;
8379  DegreePattern degs2;
8380  DegreePattern bufDegs2;
8381  bool swap2= false;
8382 
8383  // several univariate factorizations to obtain more information about the
8384  // degree pattern therefore usually less combinations have to be tried during
8385  // the recombination process
8386  int factorNums= 3;
8387  int subCheck1= substituteCheck (A, x);
8388  int subCheck2= substituteCheck (A, y);
8389  bool symmetric= false;
8390 
8391  TIMING_START (fac_fq_uni_total);
8392  for (int i= 0; i < factorNums; i++)
8393  {
8394  bufAeval= A;
8395  TIMING_START (fac_fq_bi_evaluation);
8396  bufEvaluation= evalPoint (A, bufAeval, alpha, list, GF, fail);
8397  TIMING_END_AND_PRINT (fac_fq_bi_evaluation, "time to find eval point: ");
8398  if (!derivXZero && !fail2 && !symmetric)
8399  {
8400  if (i == 0)
8401  {
8402  buf= swapvar (A, x, y);
8403  symmetric= (A/Lc (A) == buf/Lc (buf));
8404  }
8405  bufAeval2= buf;
8406  TIMING_START (fac_fq_bi_evaluation);
8407  bufEvaluation2= evalPoint (buf, bufAeval2, alpha, list2, GF, fail2);
8408  TIMING_END_AND_PRINT (fac_fq_bi_evaluation,
8409  "time to find eval point wrt y: ");
8410  }
8411  // first try to change main variable if there is no valid evaluation point
8412  if (fail && (i == 0))
8413  {
8414  if (!derivXZero && !fail2 && !symmetric)
8415  {
8416  bufEvaluation= bufEvaluation2;
8417  int dummy= subCheck2;
8418  subCheck2= subCheck1;
8419  subCheck1= dummy;
8420  tmp= A;
8421  A= buf;
8422  buf= tmp;
8423  bufAeval= bufAeval2;
8424  swap2= true;
8425  fail= false;
8426  }
8427  else
8428  fail= true;
8429  }
8430 
8431  // if there is no valid evaluation point pass to a field extension
8432  if (fail && (i == 0))
8433  {
8434  factors= extBiFactorize (A, info);
8435  appendSwapDecompress (factors, contentAxFactors, contentAyFactors,
8436  swap, swap2, N);
8437  normalize (factors);
8438  delete [] bounds;
8439  delete [] bounds2;
8440  return factors;
8441  }
8442 
8443  // there is at least one valid evaluation point
8444  // but we do not compute more univariate factorization over an extension
8445  if (fail && (i != 0))
8446  break;
8447 
8448  // univariate factorization
8449  TIMING_START (fac_fq_uni_factorizer);
8450  bufUniFactors= uniFactorizer (bufAeval, alpha, GF);
8451  TIMING_END_AND_PRINT (fac_fq_uni_factorizer,
8452  "time for univariate factorization over Fq: ");
8453  DEBOUTLN (cerr, "Lc (bufAeval)*prod (bufUniFactors)== bufAeval " <<
8454  (prod (bufUniFactors)*Lc (bufAeval) == bufAeval));
8455 
8456  if (!derivXZero && !fail2 && !symmetric)
8457  {
8458  TIMING_START (fac_fq_uni_factorizer);
8459  bufUniFactors2= uniFactorizer (bufAeval2, alpha, GF);
8460  TIMING_END_AND_PRINT (fac_fq_uni_factorizer,
8461  "time for univariate factorization in y over Fq: ");
8462  DEBOUTLN (cerr, "Lc (bufAeval2)*prod (bufUniFactors2)== bufAeval2 " <<
8463  (prod (bufUniFactors2)*Lc (bufAeval2) == bufAeval2));
8464  }
8465 
8466  if (bufUniFactors.length() == 1 ||
8467  (!fail2 && !derivXZero && !symmetric && (bufUniFactors2.length() == 1)))
8468  {
8469  if (extension)
8470  {
8471  CFList source, dest;
8472  appendMapDown (factors, A, info, source, dest);
8473  }
8474  else
8475  factors.append (A);
8476 
8477  appendSwapDecompress (factors, contentAxFactors, contentAyFactors,
8478  swap, swap2, N);
8479 
8480  if (!extension)
8481  normalize (factors);
8482  delete [] bounds;
8483  delete [] bounds2;
8484  return factors;
8485  }
8486 
8487  if (i == 0 && !extension)
8488  {
8489  if (subCheck1 > 0)
8490  {
8491  int subCheck= substituteCheck (bufUniFactors);
8492 
8493  if (subCheck > 1 && (subCheck1%subCheck == 0))
8494  {
8495  CanonicalForm bufA= A;
8496  subst (bufA, bufA, subCheck, x);
8497  factors= biFactorize (bufA, info);
8498  reverseSubst (factors, subCheck, x);
8499  appendSwapDecompress (factors, contentAxFactors, contentAyFactors,
8500  swap, swap2, N);
8501  if (!extension)
8502  normalize (factors);
8503  delete [] bounds;
8504  delete [] bounds2;
8505  return factors;
8506  }
8507  }
8508 
8509  if (!derivXZero && !fail2 && !symmetric && subCheck2 > 0)
8510  {
8511  int subCheck= substituteCheck (bufUniFactors2);
8512 
8513  if (subCheck > 1 && (subCheck2%subCheck == 0))
8514  {
8515  CanonicalForm bufA= A;
8516  subst (bufA, bufA, subCheck, y);
8517  factors= biFactorize (bufA, info);
8518  reverseSubst (factors, subCheck, y);
8519  appendSwapDecompress (factors, contentAxFactors, contentAyFactors,
8520  swap, swap2, N);
8521  if (!extension)
8522  normalize (factors);
8523  delete [] bounds;
8524  delete [] bounds2;
8525  return factors;
8526  }
8527  }
8528  }
8529 
8530  // degree analysis
8531  bufDegs = DegreePattern (bufUniFactors);
8532  if (!derivXZero && !fail2 && !symmetric)
8533  bufDegs2= DegreePattern (bufUniFactors2);
8534 
8535  if (i == 0)
8536  {
8537  Aeval= bufAeval;
8538  evaluation= bufEvaluation;
8539  uniFactors= bufUniFactors;
8540  degs= bufDegs;
8541  if (!derivXZero && !fail2 && !symmetric)
8542  {
8543  Aeval2= bufAeval2;
8544  evaluation2= bufEvaluation2;
8545  uniFactors2= bufUniFactors2;
8546  degs2= bufDegs2;
8547  }
8548  }
8549  else
8550  {
8551  degs.intersect (bufDegs);
8552  if (!derivXZero && !fail2 && !symmetric)
8553  {
8554  degs2.intersect (bufDegs2);
8555  if (bufUniFactors2.length() < uniFactors2.length())
8556  {
8557  uniFactors2= bufUniFactors2;
8558  Aeval2= bufAeval2;
8559  evaluation2= bufEvaluation2;
8560  }
8561  }
8562  if (bufUniFactors.length() < uniFactors.length())
8563  {
8564  uniFactors= bufUniFactors;
8565  Aeval= bufAeval;
8566  evaluation= bufEvaluation;
8567  }
8568  }
8569  list.append (bufEvaluation);
8570  if (!derivXZero && !fail2 && !symmetric)
8571  list2.append (bufEvaluation2);
8572  }
8573  TIMING_END_AND_PRINT (fac_fq_uni_total,
8574  "total time for univariate factorizations: ");
8575 
8576  if (!derivXZero && !fail2 && !symmetric)
8577  {
8578  if ((uniFactors.length() > uniFactors2.length() && minBound2 <= minBound)||
8579  (uniFactors.length() == uniFactors2.length()
8580  && degs.getLength() > degs2.getLength() && minBound2 <= minBound))
8581  {
8582  degs= degs2;
8583  uniFactors= uniFactors2;
8584  evaluation= evaluation2;
8585  Aeval= Aeval2;
8586  A= buf;
8587  swap2= true;
8588  }
8589  }
8590 
8591  if (degs.getLength() == 1) // A is irreducible
8592  {
8593  if (extension)
8594  {
8595  CFList source, dest;
8596  appendMapDown (factors, A, info, source, dest);
8597  }
8598  else
8599  factors.append (A);
8600  appendSwapDecompress (factors, contentAxFactors, contentAyFactors,
8601  swap, swap2, N);
8602  if (!extension)
8603  normalize (factors);
8604  delete [] bounds;
8605  delete [] bounds2;
8606  return factors;
8607  }
8608 
8609  int liftBound= degree (A, y) + 1;
8610 
8611  if (swap2)
8612  {
8613  delete [] bounds;
8614  bounds= bounds2;
8615  minBound= minBound2;
8616  }
8617 
8618  TIMING_START (fac_fq_bi_shift_to_zero);
8619  A= A (y + evaluation, y);
8620  TIMING_END_AND_PRINT (fac_fq_bi_shift_to_zero,
8621  "time to shift eval to zero: ");
8622 
8623  int degMipo= 1;
8624  if (extension && alpha.level() != 1 && k==1)
8625  degMipo= degree (getMipo (alpha));
8626 
8627  DEBOUTLN (cerr, "uniFactors= " << uniFactors);
8628 
8629  if ((GF && !extension) || (GF && extension && k != 1))
8630  {
8631  bool earlySuccess= false;
8632  CFList earlyFactors;
8633  TIMING_START (fac_fq_bi_hensel_lift);
8634  uniFactors= henselLiftAndEarly
8635  (A, earlySuccess, earlyFactors, degs, liftBound,
8636  uniFactors, info, evaluation);
8637  TIMING_END_AND_PRINT (fac_fq_bi_hensel_lift,
8638  "time for bivariate hensel lifting over Fq: ");
8639  DEBOUTLN (cerr, "lifted factors= " << uniFactors);
8640 
8641  CanonicalForm MODl= power (y, liftBound);
8642 
8643  TIMING_START (fac_fq_bi_factor_recombination);
8644  if (extension)
8645  factors= extFactorRecombination (uniFactors, A, MODl, info, degs,
8646  evaluation, 1, uniFactors.length()/2);
8647  else
8648  factors= factorRecombination (uniFactors, A, MODl, degs, evaluation, 1,
8649  uniFactors.length()/2);
8650  TIMING_END_AND_PRINT (fac_fq_bi_factor_recombination,
8651  "time for naive bivariate factor recombi over Fq: ");
8652 
8653  if (earlySuccess)
8654  factors= Union (earlyFactors, factors);
8655  else if (!earlySuccess && degs.getLength() == 1)
8656  factors= earlyFactors;
8657  }
8658  else if (degree (A) > 4 && beta.level() == 1 && (2*minBound)/degMipo < 32)
8659  {
8660  TIMING_START (fac_fq_bi_hensel_lift);
8661  if (extension)
8662  {
8663  CFList lll= extHenselLiftAndLatticeRecombi (A, uniFactors, info, degs,
8664  evaluation
8665  );
8666  factors= Union (lll, factors);
8667  }
8668  else if (alpha.level() == 1 && !GF)
8669  {
8670  CFList lll= henselLiftAndLatticeRecombi (A, uniFactors, alpha, degs,
8671  symmetric, evaluation);
8672  factors= Union (lll, factors);
8673  }
8674  else if (!extension && (alpha != x || GF))
8675  {
8676  CFList lll= henselLiftAndLatticeRecombi (A, uniFactors, alpha, degs,
8677  symmetric, evaluation);
8678  factors= Union (lll, factors);
8679  }
8680  TIMING_END_AND_PRINT (fac_fq_bi_hensel_lift,
8681  "time to bivar lift and LLL recombi over Fq: ");
8682  DEBOUTLN (cerr, "lifted factors= " << uniFactors);
8683  }
8684  else
8685  {
8686  bool earlySuccess= false;
8687  CFList earlyFactors;
8688  TIMING_START (fac_fq_bi_hensel_lift);
8689  uniFactors= henselLiftAndEarly
8690  (A, earlySuccess, earlyFactors, degs, liftBound,
8691  uniFactors, info, evaluation);
8692  TIMING_END_AND_PRINT (fac_fq_bi_hensel_lift,
8693  "time for bivar hensel lifting over Fq: ");
8694  DEBOUTLN (cerr, "lifted factors= " << uniFactors);
8695 
8696  CanonicalForm MODl= power (y, liftBound);
8697  if (!extension)
8698  {
8699  TIMING_START (fac_fq_bi_factor_recombination);
8700  factors= factorRecombination (uniFactors, A, MODl, degs, evaluation, 1, 3);
8701  TIMING_END_AND_PRINT (fac_fq_bi_factor_recombination,
8702  "time for small subset naive recombi over Fq: ");
8703 
8704  int oldUniFactorsLength= uniFactors.length();
8705  if (degree (A) > 0)
8706  {
8707  CFList tmp;
8708  TIMING_START (fac_fq_bi_hensel_lift);
8709  if (alpha.level() == 1)
8710  tmp= increasePrecision (A, uniFactors, 0, uniFactors.length(), 1,
8711  liftBound, evaluation
8712  );
8713  else
8714  {
8715  if (degree (A) > getCharacteristic())
8716  tmp= increasePrecisionFq2Fp (A, uniFactors, 0, uniFactors.length(),
8717  1, alpha, liftBound, evaluation
8718  );
8719  else
8720  tmp= increasePrecision (A, uniFactors, 0, uniFactors.length(), 1,
8721  alpha, liftBound, evaluation
8722  );
8723  }
8724  TIMING_END_AND_PRINT (fac_fq_bi_hensel_lift,
8725  "time to increase precision: ");
8726  factors= Union (factors, tmp);
8727  if (tmp.length() == 0 || (tmp.length() > 0 && uniFactors.length() != 0
8728  && uniFactors.length() != oldUniFactorsLength)
8729  )
8730  {
8731  DegreePattern bufDegs= DegreePattern (uniFactors);
8732  degs.intersect (bufDegs);
8733  degs.refine ();
8734  factors= Union (factors, factorRecombination (uniFactors, A, MODl,
8735  degs, evaluation, 4,
8736  uniFactors.length()/2
8737  )
8738  );
8739  }
8740  }
8741  }
8742  else
8743  {
8744  if (beta.level() != 1 || k > 1)
8745  {
8746  if (k > 1)
8747  {
8748  factors= extFactorRecombination (uniFactors, A, MODl, info, degs,
8749  evaluation, 1, uniFactors.length()/2
8750  );
8751  }
8752  else
8753  {
8754  factors= extFactorRecombination (uniFactors, A, MODl, info, degs,
8755  evaluation, 1, 3
8756  );
8757  if (degree (A) > 0)
8758  {
8759  CFList tmp= increasePrecision2 (A, uniFactors, alpha, liftBound);
8760  DegreePattern bufDegs= DegreePattern (tmp);
8761  degs.intersect (bufDegs);
8762  degs.refine ();
8763  factors= Union (factors, extFactorRecombination (tmp, A, MODl, info,
8764  degs, evaluation,
8765  1, tmp.length()/2
8766  )
8767  );
8768  }
8769  }
8770  }
8771  else
8772  {
8773  factors= extFactorRecombination (uniFactors, A, MODl, info, degs,
8774  evaluation, 1, 3
8775  );
8776  int oldUniFactorsLength= uniFactors.length();
8777  if (degree (A) > 0)
8778  {
8779  int degMipo;
8780  ExtensionInfo info2= init4ext (info, evaluation, degMipo);
8781 
8782  CFList source, dest;
8783  CFList tmp= extIncreasePrecision (A, uniFactors, 0,
8784  uniFactors.length(), 1, evaluation,
8785  info2, source, dest, liftBound
8786  );
8787  factors= Union (factors, tmp);
8788  if (tmp.length() == 0 || (tmp.length() > 0 && uniFactors.length() != 0
8789  && uniFactors.length() != oldUniFactorsLength)
8790  )
8791  {
8792  DegreePattern bufDegs= DegreePattern (uniFactors);
8793  degs.intersect (bufDegs);
8794  degs.refine ();
8795  factors= Union (factors,extFactorRecombination (uniFactors, A, MODl,
8796  info, degs, evaluation,
8797  4, uniFactors.length()/2
8798  )
8799  );
8800  }
8801  }
8802  }
8803  }
8804 
8805  if (earlySuccess)
8806  factors= Union (earlyFactors, factors);
8807  else if (!earlySuccess && degs.getLength() == 1)
8808  factors= earlyFactors;
8809  }
8810 
8811  if (!swap2)
8812  delete [] bounds2;
8813  delete [] bounds;
8814 
8815  appendSwapDecompress (factors, contentAxFactors, contentAyFactors,
8816  swap, swap2, N);
8817  if (!extension)
8818  normalize (factors);
8819 
8820  return factors;
8821 }
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
CFFList append(const CFFList &Inputlist, const CFFactor &TheFactor)
List< CanonicalForm > CFList
Variable getAlpha() const
getter
static CanonicalForm mapDown(const CanonicalForm &F, const Variable &alpha, const CanonicalForm &G, CFList &source, CFList &dest)
the CanonicalForm G is the output of map_up, returns F considered as an element over ...
Definition: cf_map_ext.cc:90
DegreePattern provides a functionality to create, intersect and refine degree patterns.
Definition: DegreePattern.h:31
const CanonicalForm int const CFList const Variable & y
Definition: facAbsFact.cc:57
CFList increasePrecisionFq2Fp(CanonicalForm &F, CFList &factors, int factorsFound, int oldNumCols, int oldL, const Variable &alpha, int precision, const CanonicalForm &eval)
Definition: facFqBivar.cc:4200
static poly normalize(poly next_p, ideal add_generators, syStrategy syzstr, int *g_l, int *p_l, int crit_comp)
Definition: syz3.cc:1024
CFList henselLiftAndLatticeRecombi(const CanonicalForm &G, const CFList &uniFactors, const Variable &alpha, const DegreePattern &degPat, bool symmetric, const CanonicalForm &eval)
Definition: facFqBivar.cc:6764
CanonicalForm getDelta() const
getter
int getGFDegree() const
getter
CanonicalForm deriv(const CanonicalForm &f, const Variable &x)
#define TIMING_END_AND_PRINT(t, msg)
Definition: timing.h:89
factory&#39;s class for variables
Definition: factory.h:115
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:1115
int igcd(int a, int b)
Definition: cf_util.cc:51
CF_NO_INLINE bool isZero() const
Definition: cf_inline.cc:372
CFList *& Aeval
<[in] poly
Definition: facFactorize.h:31
CFList uniFactorizer(const CanonicalForm &A, const Variable &alpha, const bool &GF)
Univariate factorization of squarefree monic polys over finite fields via NTL. If the characteristic ...
Definition: facFqBivar.cc:156
ExtensionInfo init4ext(const ExtensionInfo &info, const CanonicalForm &evaluation, int &degMipo)
Definition: facFqBivar.cc:7559
factory&#39;s main class
Definition: canonicalform.h:75
g
Definition: cfModGcd.cc:4031
int k
Definition: cfEzgcd.cc:93
const CanonicalForm int const CFList & evaluation
Definition: facAbsFact.cc:55
void appendSwapDecompress(CFList &factors1, const CFList &factors2, const CFList &factors3, const bool swap1, const bool swap2, const CFMap &N)
first swap Variables in factors1 if necessary, then append factors2 and factors3 on factors1 and fina...
Variable alpha
Definition: facAbsBiFact.cc:52
bool isIrreducible(const CanonicalForm &f)
bool isIrreducible ( const CanonicalForm & f )
CanonicalForm Lc(const CanonicalForm &f)
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:3763
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
Definition: variable.cc:207
CanonicalForm compress(const CanonicalForm &f, CFMap &m)
CanonicalForm compress ( const CanonicalForm & f, CFMap & m )
Definition: cf_map.cc:210
bool delta(X x, Y y, D d)
Definition: TestSuite.h:160
int getCharacteristic()
Definition: cf_char.cc:51
CanonicalForm subst(const CanonicalForm &f, const CFList &a, const CFList &b, const CanonicalForm &Rstar, bool isFunctionField)
CanonicalForm content(const CanonicalForm &)
CanonicalForm content ( const CanonicalForm & f )
Definition: cf_gcd.cc:180
void intersect(const DegreePattern &degPat)
intersect two degree patterns
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:561
template List< Variable > Union(const List< Variable > &, const List< Variable > &)
CFList extHenselLiftAndLatticeRecombi(const CanonicalForm &G, const CFList &uniFactors, const ExtensionInfo &extInfo, const DegreePattern &degPat, const CanonicalForm &eval)
Definition: facFqBivar.cc:7612
ExtensionInfo contains information about extension.
Definition: ExtensionInfo.h:50
CanonicalForm swapvar(const CanonicalForm &, const Variable &, const Variable &)
swapvar() - swap variables x1 and x2 in f.
Definition: cf_ops.cc:168
const CanonicalForm CFMap CFMap & N
Definition: cfEzgcd.cc:49
CFList extBiFactorize(const CanonicalForm &F, const ExtensionInfo &info)
Factorization over an extension of initial field.
Definition: facFqBivar.cc:8824
CanonicalForm decompress(const CanonicalForm &F, const mpz_t *inverseM, const mpz_t *A)
decompress a bivariate poly
int status int void * buf
Definition: si_signals.h:59
int level() const
Definition: factory.h:132
bool isUnivariate() const
#define A
Definition: sirandom.c:23
int * computeBoundsWrtDiffMainvar(const CanonicalForm &F, int &n, bool &isIrreducible)
as above just wrt to the other variable
Variable getBeta() const
getter
int substituteCheck(const CanonicalForm &F, const Variable &x)
check if a substitution x^n->x is possible
CFList increasePrecision(CanonicalForm &F, CFList &factors, int factorsFound, int oldNumCols, int oldL, int precision, const CanonicalForm &eval)
Definition: facFqBivar.cc:3416
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
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
CFList increasePrecision2(const CanonicalForm &F, CFList &factors, const Variable &alpha, int precision)
Definition: facFqBivar.cc:4069
void refine()
Refine a degree pattern. Assumes that (*this)[0]:= d is the degree of the poly to be factored...
CFListIterator i
Definition: facFqBivar.cc:69
int size(const CanonicalForm &f, const Variable &v)
int size ( const CanonicalForm & f, const Variable & v )
Definition: cf_ops.cc:600
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:81
Variable beta
Definition: facAbsFact.cc:99
class CFMap
Definition: cf_map.h:84
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:346
int length() const
Definition: ftmpl_list.cc:273
static int gettype()
Definition: cf_factory.h:27
#define swap(_i, _j)
int getLength() const
getter
Definition: DegreePattern.h:86
int gcd(int a, int b)
Definition: walkSupport.cc:839
fq_nmod_poly_t prod
Definition: facHensel.cc:95
#define TIMING_START(t)
Definition: timing.h:87
bool isInExtension() const
getter
Variable x
Definition: cfModGcd.cc:4023
#define GaloisFieldDomain
Definition: cf_defs.h:22
CFList biFactorize(const CanonicalForm &F, const ExtensionInfo &info)
bivariate factorization over finite fields as decribed in "Factoring multivariate polynomials over a ...
Definition: facFqBivar.cc:8201
CanonicalForm reverseSubst(const CanonicalForm &F, const int d, const Variable &x)
reverse a substitution x^d->x
#define DEBOUTLN(stream, objects)
Definition: debug.h:49
void append(const T &)
Definition: ftmpl_list.cc:256
int degree(const CanonicalForm &f)
CanonicalForm getGamma() const
getter
int * computeBounds(const CanonicalForm &F, int &n, bool &isIrreducible)
compute bounds for logarithmic derivative as described in K. Belabas, M. van Hoeij, J. Klüners, and A. Steel, Factoring polynomials over global fields
template CanonicalForm tmin(const CanonicalForm &, const CanonicalForm &)
bool inCoeffDomain() const

§ biSqrfFactorizeHelper()

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

Definition at line 53 of file facFqBivar.h.

54 {
55  CFMap N;
56  CanonicalForm F= compress (G, N);
57  CanonicalForm contentX= content (F, 1);
58  CanonicalForm contentY= content (F, 2);
59  F /= (contentX*contentY);
60  CFFList contentXFactors, contentYFactors;
61  if (info.getAlpha().level() != 1)
62  {
63  contentXFactors= factorize (contentX, info.getAlpha());
64  contentYFactors= factorize (contentY, info.getAlpha());
65  }
66  else if (info.getAlpha().level() == 1 && info.getGFDegree() == 1)
67  {
68  contentXFactors= factorize (contentX);
69  contentYFactors= factorize (contentY);
70  }
71  else if (info.getAlpha().level() == 1 && info.getGFDegree() != 1)
72  {
73  CFList bufContentX, bufContentY;
74  bufContentX= biFactorize (contentX, info);
75  bufContentY= biFactorize (contentY, info);
76  for (CFListIterator iter= bufContentX; iter.hasItem(); iter++)
77  contentXFactors.append (CFFactor (iter.getItem(), 1));
78  for (CFListIterator iter= bufContentY; iter.hasItem(); iter++)
79  contentYFactors.append (CFFactor (iter.getItem(), 1));
80  }
81 
82  if (contentXFactors.getFirst().factor().inCoeffDomain())
83  contentXFactors.removeFirst();
84  if (contentYFactors.getFirst().factor().inCoeffDomain())
85  contentYFactors.removeFirst();
86  if (F.inCoeffDomain())
87  {
88  CFList result;
89  for (CFFListIterator i= contentXFactors; i.hasItem(); i++)
90  result.append (N (i.getItem().factor()));
91  for (CFFListIterator i= contentYFactors; i.hasItem(); i++)
92  result.append (N (i.getItem().factor()));
93  normalize (result);
94  result.insert (Lc (G));
95  return result;
96  }
97  mpz_t * M=new mpz_t [4];
98  mpz_init (M[0]);
99  mpz_init (M[1]);
100  mpz_init (M[2]);
101  mpz_init (M[3]);
102 
103  mpz_t * S=new mpz_t [2];
104  mpz_init (S[0]);
105  mpz_init (S[1]);
106 
107  F= compress (F, M, S);
108  CFList result= biFactorize (F, info);
109  for (CFListIterator i= result; i.hasItem(); i++)
110  i.getItem()= N (decompress (i.getItem(), M, S));
111  for (CFFListIterator i= contentXFactors; i.hasItem(); i++)
112  result.append (N(i.getItem().factor()));
113  for (CFFListIterator i= contentYFactors; i.hasItem(); i++)
114  result.append (N (i.getItem().factor()));
115  normalize (result);
116  result.insert (Lc(G));
117 
118  mpz_clear (M[0]);
119  mpz_clear (M[1]);
120  mpz_clear (M[2]);
121  mpz_clear (M[3]);
122  delete [] M;
123 
124  mpz_clear (S[0]);
125  mpz_clear (S[1]);
126  delete [] S;
127 
128  return result;
129 }
Variable getAlpha() const
getter
static poly normalize(poly next_p, ideal add_generators, syStrategy syzstr, int *g_l, int *p_l, int crit_comp)
Definition: syz3.cc:1024
int getGFDegree() const
getter
CFFListIterator iter
Definition: facAbsBiFact.cc:54
factory&#39;s main class
Definition: canonicalform.h:75
void insert(const T &)
Definition: ftmpl_list.cc:193
CanonicalForm Lc(const CanonicalForm &f)
CanonicalForm compress(const CanonicalForm &f, CFMap &m)
CanonicalForm compress ( const CanonicalForm & f, CFMap & m )
Definition: cf_map.cc:210
void removeFirst()
Definition: ftmpl_list.cc:287
CanonicalForm content(const CanonicalForm &)
CanonicalForm content ( const CanonicalForm & f )
Definition: cf_gcd.cc:180
T getFirst() const
Definition: ftmpl_list.cc:279
#define M
Definition: sirandom.c:24
CFFList factorize(const CanonicalForm &f, bool issqrfree=false)
factorization over or
Definition: cf_factor.cc:390
const CanonicalForm CFMap CFMap & N
Definition: cfEzgcd.cc:49
CanonicalForm decompress(const CanonicalForm &F, const mpz_t *inverseM, const mpz_t *A)
decompress a bivariate poly
int level() const
Definition: factory.h:132
T & getItem() const
Definition: ftmpl_list.cc:431
int i
Definition: cfEzgcd.cc:123
class CFMap
Definition: cf_map.h:84
void append(const T &)
Definition: ftmpl_list.cc:256
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.
Definition: facFqBivar.cc:8201
return result
Definition: facAbsBiFact.cc:76
bool inCoeffDomain() const

§ 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 780 of file facFqBivar.cc.

781 {
783  {
785  zz_p::init (getCharacteristic());
786  }
787  zz_pX NTLIrredpoly;
788  int i=1, m= 2;
789  // extension of F_p needed
790  if (alpha.level() == 1 && beta.level() == 1 && k == 1)
791  {
792  i= 1;
793  m= 2;
794  } //extension of F_p(alpha) needed but want to factorize over F_p
795  else if (alpha.level() != 1 && beta.level() == 1 && k == 1)
796  {
797  i= 1;
798  m= degree (getMipo (alpha)) + 1;
799  } //extension of F_p(alpha) needed for first time
800  else if (alpha.level() != 1 && beta.level() == 1 && k != 1)
801  {
802  i= 2;
803  m= degree (getMipo (alpha));
804  }
805  else if (alpha.level() != 1 && beta.level() != 1 && k != 1)
806  {
807  m= degree (getMipo (beta));
808  i= degree (getMipo (alpha))/m + 1;
809  }
810  BuildIrred (NTLIrredpoly, i*m);
811  CanonicalForm newMipo= convertNTLzzpX2CF (NTLIrredpoly, Variable (1));
812  return rootOf (newMipo);
813 }
factory&#39;s class for variables
Definition: factory.h:115
factory&#39;s main class
Definition: canonicalform.h:75
CanonicalForm convertNTLzzpX2CF(const zz_pX &poly, const Variable &x)
Definition: NTLconvert.cc:251
int k
Definition: cfEzgcd.cc:93
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
Definition: variable.cc:207
int getCharacteristic()
Definition: cf_char.cc:51
Variable rootOf(const CanonicalForm &, char name='@')
returns a symbolic root of polynomial with name name Use it to define algebraic variables ...
Definition: variable.cc:162
int level() const
Definition: factory.h:132
int m
Definition: cfEzgcd.cc:119
CFListIterator i
Definition: facFqBivar.cc:69
long fac_NTL_char
Definition: NTLconvert.cc:44
int degree(const CanonicalForm &f)

§ 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 935 of file facFqBivar.cc.

939 {
940  CanonicalForm den= 1;
941  earlyFactorDetection (reconstructedFactors, F, factors, adaptedLiftBound,
942  factorsFoundIndex, degs, success, deg, eval, b, den);
943 }
factory&#39;s main class
Definition: canonicalform.h:75
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:816
CanonicalForm den(const CanonicalForm &f)

§ 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 81 of file facFqBivar.cc.

84 {
85  fail= false;
86  Variable x= Variable(2);
87  Variable y= Variable(1);
88  FFRandom genFF;
89  GFRandom genGF;
90  CanonicalForm random, mipo;
91  double bound;
92  int p= getCharacteristic ();
93  if (alpha.level() != 1)
94  {
95  mipo= getMipo (alpha);
96  int d= degree (mipo);
97  bound= pow ((double) p, (double) d);
98  }
99  else if (GF)
100  {
101  int d= getGFDegree();
102  bound= ipower (p, d);
103  }
104  else
105  bound= p;
106 
107  random= 0;
108  do
109  {
110  if (list.length() >= bound)
111  {
112  fail= true;
113  break;
114  }
115  if (list.isEmpty())
116  random= 0;
117  else if (GF)
118  {
119  if (list.length() == 1)
120  random= getGFGenerator();
121  else
122  random= genGF.generate();
123  }
124  else if (list.length() < p || alpha.level() == 1)
125  random= genFF.generate();
126  else if (alpha != x && list.length() >= p)
127  {
128  if (list.length() == p)
129  random= alpha;
130  else
131  {
132  AlgExtRandomF genAlgExt (alpha);
133  random= genAlgExt.generate();
134  }
135  }
136  if (find (list, random)) continue;
137  eval= F (random, x);
138  if (degree (eval) != degree (F, y))
139  { //leading coeff vanishes
140  if (!find (list, random))
141  list.append (random);
142  continue;
143  }
144  if (degree (gcd (deriv (eval, eval.mvar()), eval), eval.mvar()) > 0)
145  { //evaluated polynomial is not squarefree
146  if (!find (list, random))
147  list.append (random);
148  continue;
149  }
150  } while (find (list, random));
151 
152  return random;
153 }
generate random elements in GF
Definition: cf_random.h:31
const CanonicalForm int const CFList const Variable & y
Definition: facAbsFact.cc:57
static CanonicalForm bound(const CFMatrix &M)
Definition: cf_linsys.cc:460
int isEmpty() const
Definition: ftmpl_list.cc:267
CanonicalForm deriv(const CanonicalForm &f, const Variable &x)
return P p
Definition: myNF.cc:203
factory&#39;s class for variables
Definition: factory.h:115
factory&#39;s main class
Definition: canonicalform.h:75
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
Definition: variable.cc:207
int getCharacteristic()
Definition: cf_char.cc:51
template bool find(const List< CanonicalForm > &, const CanonicalForm &)
CanonicalForm generate() const
Definition: cf_random.cc:66
int level() const
Definition: factory.h:132
CanonicalForm generate() const
Definition: cf_random.cc:56
generate random elements in F_p
Definition: cf_random.h:43
CanonicalForm getGFGenerator()
Definition: cf_char.cc:62
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
generate random elements in F_p(alpha)
Definition: cf_random.h:70
int length() const
Definition: ftmpl_list.cc:273
int ipower(int b, int m)
int ipower ( int b, int m )
Definition: cf_util.cc:25
int gcd(int a, int b)
Definition: walkSupport.cc:839
int getGFDegree()
Definition: cf_char.cc:56
Variable x
Definition: cfModGcd.cc:4023
void append(const T &)
Definition: ftmpl_list.cc:256
int degree(const CanonicalForm &f)
Rational pow(const Rational &a, int e)
Definition: GMPrat.cc:418

§ 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 8824 of file facFqBivar.cc.

8825 {
8826 
8827  CanonicalForm A= F;
8828  Variable alpha= info.getAlpha();
8829  Variable beta= info.getBeta();
8830  int k= info.getGFDegree();
8831  char cGFName= info.getGFName();
8832  CanonicalForm delta= info.getDelta();
8833 
8834  bool GF= (CFFactory::gettype() == GaloisFieldDomain);
8835  Variable x= Variable (1);
8836  CFList factors;
8837  if (!GF && alpha == x) // we are in F_p
8838  {
8839  bool extension= true;
8840  int p= getCharacteristic();
8841  if (p*p < (1<<16)) // pass to GF if possible
8842  {
8844  A= A.mapinto();
8845  ExtensionInfo info2= ExtensionInfo (extension);
8846  factors= biFactorize (A, info2);
8847 
8848  CanonicalForm mipo= gf_mipo;
8850  Variable vBuf= rootOf (mipo.mapinto());
8851  for (CFListIterator j= factors; j.hasItem(); j++)
8852  j.getItem()= GF2FalphaRep (j.getItem(), vBuf);
8853  prune (vBuf);
8854  }
8855  else // not able to pass to GF, pass to F_p(\alpha)
8856  {
8857  CanonicalForm mipo= randomIrredpoly (2, x);
8858  Variable v= rootOf (mipo);
8859  ExtensionInfo info2= ExtensionInfo (v);
8860  factors= biFactorize (A, info2);
8861  prune (v);
8862  }
8863  return factors;
8864  }
8865  else if (!GF && (alpha != x)) // we are in F_p(\alpha)
8866  {
8867  if (k == 1) // need factorization over F_p
8868  {
8869  int extDeg= degree (getMipo (alpha));
8870  extDeg++;
8871  CanonicalForm mipo= randomIrredpoly (extDeg, x);
8872  Variable v= rootOf (mipo);
8873  ExtensionInfo info2= ExtensionInfo (v);
8874  factors= biFactorize (A, info2);
8875  prune (v);
8876  }
8877  else
8878  {
8879  if (beta == x)
8880  {
8881  Variable v= chooseExtension (alpha, beta, k);
8882  CanonicalForm primElem, imPrimElem;
8883  bool primFail= false;
8884  Variable vBuf;
8885  primElem= primitiveElement (alpha, vBuf, primFail);
8886  ASSERT (!primFail, "failure in integer factorizer");
8887  if (primFail)
8888  ; //ERROR
8889  else
8890  imPrimElem= mapPrimElem (primElem, alpha, v);
8891 
8892  CFList source, dest;
8893  CanonicalForm bufA= mapUp (A, alpha, v, primElem, imPrimElem,
8894  source, dest);
8895  ExtensionInfo info2= ExtensionInfo (v, alpha, imPrimElem, primElem);
8896  factors= biFactorize (bufA, info2);
8897  prune (v);
8898  }
8899  else
8900  {
8901  Variable v= chooseExtension (alpha, beta, k);
8902  CanonicalForm primElem, imPrimElem;
8903  bool primFail= false;
8904  Variable vBuf;
8905  ASSERT (!primFail, "failure in integer factorizer");
8906  if (primFail)
8907  ; //ERROR
8908  else
8909  imPrimElem= mapPrimElem (delta, beta, v);
8910 
8911  CFList source, dest;
8912  CanonicalForm bufA= mapDown (A, info, source, dest);
8913  source= CFList();
8914  dest= CFList();
8915  bufA= mapUp (bufA, beta, v, delta, imPrimElem, source, dest);
8916  ExtensionInfo info2= ExtensionInfo (v, beta, imPrimElem, delta);
8917  factors= biFactorize (bufA, info2);
8918  prune (v);
8919  }
8920  }
8921  return factors;
8922  }
8923  else // we are in GF (p^k)
8924  {
8925  int p= getCharacteristic();
8926  int extensionDeg= getGFDegree();
8927  bool extension= true;
8928  if (k == 1) // need factorization over F_p
8929  {
8930  extensionDeg++;
8931  if (ipower (p, extensionDeg) < (1<<16))
8932  // pass to GF(p^k+1)
8933  {
8934  CanonicalForm mipo= gf_mipo;
8935  setCharacteristic (p);
8936  Variable vBuf= rootOf (mipo.mapinto());
8937  A= GF2FalphaRep (A, vBuf);
8938  setCharacteristic (p, extensionDeg, 'Z');
8939  ExtensionInfo info2= ExtensionInfo (extension);
8940  factors= biFactorize (A.mapinto(), info2);
8941  prune (vBuf);
8942  }
8943  else // not able to pass to another GF, pass to F_p(\alpha)
8944  {
8945  CanonicalForm mipo= gf_mipo;
8946  setCharacteristic (p);
8947  Variable vBuf= rootOf (mipo.mapinto());
8948  A= GF2FalphaRep (A, vBuf);
8949  Variable v= chooseExtension (vBuf, beta, k);
8950  ExtensionInfo info2= ExtensionInfo (v, extension);
8951  factors= biFactorize (A, info2);
8952  prune (vBuf);
8953  }
8954  }
8955  else // need factorization over GF (p^k)
8956  {
8957  if (ipower (p, 2*extensionDeg) < (1<<16))
8958  // pass to GF (p^2k)
8959  {
8960  setCharacteristic (p, 2*extensionDeg, 'Z');
8961  ExtensionInfo info2= ExtensionInfo (k, cGFName, extension);
8962  factors= biFactorize (GFMapUp (A, extensionDeg), info2);
8963  setCharacteristic (p, extensionDeg, cGFName);
8964  }
8965  else // not able to pass to GF (p^2k), pass to F_p (\alpha)
8966  {
8967  CanonicalForm mipo= gf_mipo;
8968  setCharacteristic (p);
8969  Variable v1= rootOf (mipo.mapinto());
8970  A= GF2FalphaRep (A, v1);
8971  Variable v2= chooseExtension (v1, v1, k);
8972  CanonicalForm primElem, imPrimElem;
8973  bool primFail= false;
8974  Variable vBuf;
8975  primElem= primitiveElement (v1, vBuf, primFail);
8976  ASSERT (!primFail, "failure in integer factorizer");
8977  if (primFail)
8978  ; //ERROR
8979  else
8980  imPrimElem= mapPrimElem (primElem, v1, v2);
8981 
8982  CFList source, dest;
8983  CanonicalForm bufA= mapUp (A, v1, v2, primElem, imPrimElem,
8984  source, dest);
8985  ExtensionInfo info2= ExtensionInfo (v2, v1, imPrimElem, primElem);
8986  factors= biFactorize (bufA, info2);
8987  setCharacteristic (p, k, cGFName);
8988  for (CFListIterator i= factors; i.hasItem(); i++)
8989  i.getItem()= Falpha2GFRep (i.getItem());
8990  prune (v1);
8991  }
8992  }
8993  return factors;
8994  }
8995 }
char getGFName() const
getter
List< CanonicalForm > CFList
Variable getAlpha() const
getter
CanonicalForm Falpha2GFRep(const CanonicalForm &F)
change representation by residue classes modulo a Conway polynomial to representation by primitive el...
Definition: cf_map_ext.cc:170
static CanonicalForm mapDown(const CanonicalForm &F, const Variable &alpha, const CanonicalForm &G, CFList &source, CFList &dest)
the CanonicalForm G is the output of map_up, returns F considered as an element over ...
Definition: cf_map_ext.cc:90
CanonicalForm getDelta() const
getter
int getGFDegree() const
getter
CanonicalForm primitiveElement(const Variable &alpha, Variable &beta, bool &fail)
determine a primitive element of , is a primitive element of a field which is isomorphic to ...
Definition: cf_map_ext.cc:310
return P p
Definition: myNF.cc:203
factory&#39;s class for variables
Definition: factory.h:115
Variable chooseExtension(const Variable &alpha, const Variable &beta, int k)
chooses a field extension.
Definition: facFqBivar.cc:780
CanonicalForm gf_mipo(0)
factory&#39;s main class
Definition: canonicalform.h:75
int k
Definition: cfEzgcd.cc:93
Variable alpha
Definition: facAbsBiFact.cc:52
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
Definition: variable.cc:207
void setCharacteristic(int c)
Definition: cf_char.cc:23
bool delta(X x, Y y, D d)
Definition: TestSuite.h:160
int getCharacteristic()
Definition: cf_char.cc:51
void prune(Variable &alpha)
Definition: variable.cc:261
CanonicalForm mapinto() const
Variable rootOf(const CanonicalForm &, char name='@')
returns a symbolic root of polynomial with name name Use it to define algebraic variables ...
Definition: variable.cc:162
ExtensionInfo contains information about extension.
Definition: ExtensionInfo.h:50
static CanonicalForm mapUp(const Variable &alpha, const Variable &beta)
and is a primitive element, returns the image of
Definition: cf_map_ext.cc:67
int j
Definition: myNF.cc:70
T & getItem() const
Definition: ftmpl_list.cc:431
#define A
Definition: sirandom.c:23
Variable getBeta() const
getter
CFListIterator i
Definition: facFqBivar.cc:69
Variable beta
Definition: facAbsFact.cc:99
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:37
CanonicalForm GF2FalphaRep(const CanonicalForm &F, const Variable &alpha)
changes representation by primitive element to representation by residue classes modulo a Conway poly...
Definition: cf_map_ext.cc:162
int ipower(int b, int m)
int ipower ( int b, int m )
Definition: cf_util.cc:25
static int gettype()
Definition: cf_factory.h:27
CanonicalForm GFMapUp(const CanonicalForm &F, int k)
maps a polynomial over to a polynomial over , d needs to be a multiple of k
Definition: cf_map_ext.cc:207
int getGFDegree()
Definition: cf_char.cc:56
Variable x
Definition: cfModGcd.cc:4023
#define GaloisFieldDomain
Definition: cf_defs.h:22
CFList biFactorize(const CanonicalForm &F, const ExtensionInfo &info)
bivariate factorization over finite fields as decribed in "Factoring multivariate polynomials over a ...
Definition: facFqBivar.cc:8201
CanonicalForm randomIrredpoly(int i, const Variable &x)
computes a random monic irreducible univariate polynomial in x over Fp of degree i via NTL ...
Definition: cf_irred.cc:42
#define ASSERT(expression, message)
Definition: cf_assert.h:99
int degree(const CanonicalForm &f)
CanonicalForm mapPrimElem(const CanonicalForm &primElem, const Variable &alpha, const Variable &beta)
compute the image of a primitive element of in . We assume .
Definition: cf_map_ext.cc:377

§ 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 946 of file facFqBivar.cc.

951 {
952  Variable alpha= info.getAlpha();
953  Variable beta= info.getBeta();
954  CanonicalForm gamma= info.getGamma();
955  CanonicalForm delta= info.getDelta();
956  int k= info.getGFDegree();
957  DegreePattern bufDegs1= degs, bufDegs2;
958  CFList result;
959  CFList T= factors;
960  Variable y= F.mvar();
961  Variable x= Variable (1);
962  CanonicalForm buf= F, LCBuf= LC (buf, x), g, buf2;
963  CanonicalForm M= power (y, deg);
964  adaptedLiftBound= 0;
965  bool trueFactor= false;
966  int d= degree (F), l= 0;
967  CFList source, dest;
968  int degMipoBeta= 1;
969  if (!k && beta.level() != 1)
970  degMipoBeta= degree (getMipo (beta));
971  CanonicalForm quot;
972  for (CFListIterator i= factors; i.hasItem(); i++, l++)
973  {
974  if (!bufDegs1.find (degree (i.getItem(), 1)) || factorsFoundIndex[l] == 1)
975  continue;
976  else
977  {
978  g= mulMod2 (i.getItem(), LCBuf, M);
979  g /= content (g, x);
980  if (fdivides (g, buf, quot))
981  {
982  buf2= g (y - eval, y);
983  buf2 /= Lc (buf2);
984 
985  if (!k && beta == x)
986  {
987  if (degree (buf2, alpha) < degMipoBeta)
988  {
989  appendTestMapDown (reconstructedFactors, buf2, info, source, dest);
990  factorsFoundIndex[l]= 1;
991  buf= quot;
992  d -= degree (g);
993  LCBuf= LC (buf, x);
994  trueFactor= true;
995  }
996  }
997  else
998  {
999  if (!isInExtension (buf2, gamma, k, delta, source, dest))
1000  {
1001  appendTestMapDown (reconstructedFactors, buf2, info, source, dest);
1002  factorsFoundIndex[l]= 1;
1003  buf= quot;
1004  d -= degree (g);
1005  LCBuf= LC (buf, x);
1006  trueFactor= true;
1007  }
1008  }
1009  if (trueFactor)
1010  {
1011  T= Difference (T, CFList (i.getItem()));
1012  F= buf;
1013 
1014  // compute new possible degree pattern
1015  bufDegs2= DegreePattern (T);
1016  bufDegs1.intersect (bufDegs2);
1017  bufDegs1.refine ();
1018  trueFactor= false;
1019  if (bufDegs1.getLength() <= 1)
1020  {
1021  if (!buf.inCoeffDomain())
1022  {
1023  buf= buf (y - eval, y);
1024  buf /= Lc (buf);
1025  appendMapDown (reconstructedFactors, buf, info, source, dest);
1026  F= 1;
1027  }
1028  break;
1029  }
1030  }
1031  }
1032  }
1033  }
1034  adaptedLiftBound= d + 1;
1035  if (adaptedLiftBound < deg)
1036  {
1037  degs= bufDegs1;
1038  success= true;
1039  }
1040  if (bufDegs1.getLength() <= 1)
1041  degs= bufDegs1;
1042 }
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
Variable getAlpha() const
getter
DegreePattern provides a functionality to create, intersect and refine degree patterns.
Definition: DegreePattern.h:31
const CanonicalForm int const CFList const Variable & y
Definition: facAbsFact.cc:57
CanonicalForm getDelta() const
getter
int getGFDegree() const
getter
factory&#39;s class for variables
Definition: factory.h:115
bool isInExtension(const CanonicalForm &F, const CanonicalForm &gamma, const int k, const CanonicalForm &delta, CFList &source, CFList &dest)
tests if F is not contained in a subfield defined by gamma (Fq case) or k (GF case) ...
int find(const int x) const
find an element x
factory&#39;s main class
Definition: canonicalform.h:75
g
Definition: cfModGcd.cc:4031
int k
Definition: cfEzgcd.cc:93
Variable alpha
Definition: facAbsBiFact.cc:52
const CanonicalForm & M
Definition: facFqBivar.cc:58
CanonicalForm Lc(const CanonicalForm &f)
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
Definition: variable.cc:207
bool delta(X x, Y y, D d)
Definition: TestSuite.h:160
CanonicalForm content(const CanonicalForm &)
CanonicalForm content ( const CanonicalForm & f )
Definition: cf_gcd.cc:180
void intersect(const DegreePattern &degPat)
intersect two degree patterns
int status int void * buf
Definition: si_signals.h:59
int level() const
Definition: factory.h:132
T & getItem() const
Definition: ftmpl_list.cc:431
Variable getBeta() const
getter
CanonicalForm mulMod2(const CanonicalForm &A, const CanonicalForm &B, const CanonicalForm &M)
Karatsuba style modular multiplication for bivariate polynomials.
Definition: facMul.cc:2853
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
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
void appendTestMapDown(CFList &factors, const CanonicalForm &f, const ExtensionInfo &info, CFList &source, CFList &dest)
test if g is in a subfield of the current field, if so map it down and append it to factors ...
void refine()
Refine a degree pattern. Assumes that (*this)[0]:= d is the degree of the poly to be factored...
CFListIterator i
Definition: facFqBivar.cc:69
CanonicalForm buf2
Definition: facFqBivar.cc:71
Variable beta
Definition: facAbsFact.cc:99
bool fdivides(const CanonicalForm &f, const CanonicalForm &g)
bool fdivides ( const CanonicalForm & f, const CanonicalForm & g )
int getLength() const
getter
Definition: DegreePattern.h:86
Variable x
Definition: cfModGcd.cc:4023
int degree(const CanonicalForm &f)
static jList * T
Definition: janet.cc:37
CanonicalForm LC(const CanonicalForm &f)
CanonicalForm getGamma() const
getter
template List< Variable > Difference(const List< Variable > &, const List< Variable > &)
int l
Definition: cfEzgcd.cc:94
return result
Definition: facAbsBiFact.cc:76
bool inCoeffDomain() const

§ 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 346 of file facFqBivar.cc.

350 {
351  if (factors.length() == 0)
352  {
353  F= 1;
354  return CFList();
355  }
356  if (F.inCoeffDomain())
357  return CFList();
358 
359  Variable alpha= info.getAlpha();
360  Variable beta= info.getBeta();
361  CanonicalForm gamma= info.getGamma();
362  CanonicalForm delta= info.getDelta();
363  int k= info.getGFDegree();
364 
365  CanonicalForm M= N;
366  int l= degree (N);
367  Variable y= F.mvar();
368  Variable x= Variable (1);
369  CFList source, dest;
370  if (degs.getLength() <= 1 || factors.length() == 1)
371  {
372  CFList result= CFList(mapDown (F(y-eval, y), info, source, dest));
373  F= 1;
374  return result;
375  }
376 
377  DEBOUTLN (cerr, "LC (F, 1)*prodMod (factors, M) == F " <<
378  (mod (LC (F, 1)*prodMod (factors, M), M)/Lc (mod (LC (F, 1)*prodMod (factors, M), M)) == F/Lc (F)));
379  int degMipoBeta= 1;
380  if (!k && beta.level() != 1)
381  degMipoBeta= degree (getMipo (beta));
382 
383  CFList T, S, Diff;
384  T= factors;
385 
386  CFList result;
387  CanonicalForm buf, buf2, quot;
388 
389  buf= F;
390 
391  CanonicalForm g, LCBuf= LC (buf, x);
392  int * v= new int [T.length()];
393  for (int i= 0; i < T.length(); i++)
394  v[i]= 0;
395 
396  CFArray TT;
397  DegreePattern bufDegs1, bufDegs2;
398  bufDegs1= degs;
399  int subsetDeg;
400  TT= copy (factors);
401  bool nosubset= false;
402  bool recombination= false;
403  bool trueFactor= false;
405  CanonicalForm buf0= buf (0, x)*LCBuf;
406  while (T.length() >= 2*s && s <= thres)
407  {
408  while (nosubset == false)
409  {
410  if (T.length() == s)
411  {
412  delete [] v;
413  if (recombination)
414  {
415  T.insert (LCBuf);
416  g= prodMod (T, M);
417  T.removeFirst();
418  g /= content(g);
419  g= g (y - eval, y);
420  g /= Lc (g);
421  appendTestMapDown (result, g, info, source, dest);
422  F= 1;
423  return result;
424  }
425  else
426  {
427  appendMapDown (result, F (y - eval, y), info, source, dest);
428  F= 1;
429  return result;
430  }
431  }
432  S= subset (v, s, TT, nosubset);
433  if (nosubset) break;
434  subsetDeg= subsetDegree (S);
435  // skip those combinations that are not possible
436  if (!degs.find (subsetDeg))
437  continue;
438  else
439  {
440  test= prodMod0 (S, M);
441  test *= LCBuf;
442  test = mod (test, M);
443  if (fdivides (test, buf0))
444  {
445  S.insert (LCBuf);
446  g= prodMod (S, M);
447  S.removeFirst();
448  g /= content (g, x);
449  if (fdivides (g, buf, quot))
450  {
451  buf2= g (y - eval, y);
452  buf2 /= Lc (buf2);
453 
454  if (!k && beta.level() == 1)
455  {
456  if (degree (buf2, alpha) < degMipoBeta)
457  {
458  buf= quot;
459  LCBuf= LC (buf, x);
460  recombination= true;
461  appendTestMapDown (result, buf2, info, source, dest);
462  trueFactor= true;
463  }
464  }
465  else
466  {
467  if (!isInExtension (buf2, gamma, k, delta, source, dest))
468  {
469  buf= quot;
470  LCBuf= LC (buf, x);
471  recombination= true;
472  appendTestMapDown (result, buf2, info, source, dest);
473  trueFactor= true;
474  }
475  }
476  if (trueFactor)
477  {
478  T= Difference (T, S);
479  l -= degree (g);
480  M= power (y, l);
481  buf0= buf (0, x)*LCBuf;
482 
483  // compute new possible degree pattern
484  bufDegs2= DegreePattern (T);
485  bufDegs1.intersect (bufDegs2);
486  bufDegs1.refine ();
487  if (T.length() < 2*s || T.length() == s ||
488  bufDegs1.getLength() == 1)
489  {
490  delete [] v;
491  if (recombination)
492  {
493  buf= buf (y-eval,y);
494  buf /= Lc (buf);
495  appendTestMapDown (result, buf, info, source,
496  dest);
497  F= 1;
498  return result;
499  }
500  else
501  {
502  appendMapDown (result, F (y - eval, y), info, source, dest);
503  F= 1;
504  return result;
505  }
506  }
507  trueFactor= false;
508  TT= copy (T);
509  indexUpdate (v, s, T.length(), nosubset);
510  if (nosubset) break;
511  }
512  }
513  }
514  }
515  }
516  s++;
517  if (T.length() < 2*s || T.length() == s)
518  {
519  delete [] v;
520  if (recombination)
521  {
522  buf= buf (y-eval,y);
523  buf /= Lc (buf);
524  appendTestMapDown (result, buf, info, source, dest);
525  F= 1;
526  return result;
527  }
528  else
529  {
530  appendMapDown (result, F (y - eval, y), info, source, dest);
531  F= 1;
532  return result;
533  }
534  }
535  for (int i= 0; i < T.length(); i++)
536  v[i]= 0;
537  nosubset= false;
538  }
539  if (T.length() < 2*s)
540  {
541  appendMapDown (result, F (y - eval, y), info, source, dest);
542  F= 1;
543  delete [] v;
544  return result;
545  }
546 
547  if (s > thres)
548  {
549  factors= T;
550  F= buf;
551  degs= bufDegs1;
552  }
553 
554  delete [] v;
555  return result;
556 }
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
void indexUpdate(int index [], const int &subsetSize, const int &setSize, bool &noSubset)
update index
List< CanonicalForm > CFList
Variable getAlpha() const
getter
static CanonicalForm mapDown(const CanonicalForm &F, const Variable &alpha, const CanonicalForm &G, CFList &source, CFList &dest)
the CanonicalForm G is the output of map_up, returns F considered as an element over ...
Definition: cf_map_ext.cc:90
const CanonicalForm int s
Definition: facAbsFact.cc:55
DegreePattern provides a functionality to create, intersect and refine degree patterns.
Definition: DegreePattern.h:31
const CanonicalForm int const CFList const Variable & y
Definition: facAbsFact.cc:57
CFArray copy(const CFList &list)
write elements of list into an array
CanonicalForm getDelta() const
getter
int getGFDegree() const
getter
factory&#39;s class for variables
Definition: factory.h:115
bool isInExtension(const CanonicalForm &F, const CanonicalForm &gamma, const int k, const CanonicalForm &delta, CFList &source, CFList &dest)
tests if F is not contained in a subfield defined by gamma (Fq case) or k (GF case) ...
int find(const int x) const
find an element x
factory&#39;s main class
Definition: canonicalform.h:75
g
Definition: cfModGcd.cc:4031
int k
Definition: cfEzgcd.cc:93
Variable alpha
Definition: facAbsBiFact.cc:52
CanonicalForm prodMod0(const CFList &L, const CanonicalForm &M, const modpk &b=modpk())
via divide-and-conquer
const CanonicalForm & M
Definition: facFqBivar.cc:58
void insert(const T &)
Definition: ftmpl_list.cc:193
CanonicalForm Lc(const CanonicalForm &f)
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
Definition: variable.cc:207
bool delta(X x, Y y, D d)
Definition: TestSuite.h:160
void removeFirst()
Definition: ftmpl_list.cc:287
CanonicalForm content(const CanonicalForm &)
CanonicalForm content ( const CanonicalForm & f )
Definition: cf_gcd.cc:180
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...
void intersect(const DegreePattern &degPat)
intersect two degree patterns
const CanonicalForm CFMap CFMap & N
Definition: cfEzgcd.cc:49
int status int void * buf
Definition: si_signals.h:59
int level() const
Definition: factory.h:132
Variable getBeta() const
getter
int subsetDegree(const CFList &S)
compute the sum of degrees in Variable(1) of elements in S
void appendMapDown(CFList &factors, const CanonicalForm &g, const ExtensionInfo &info, CFList &source, CFList &dest)
map g down into a subfield of the current field and append it to factors
CFList recombination(const CFList &factors1, const CFList &factors2, int s, int thres, const CanonicalForm &evalPoint, const Variable &x)
recombination of bivariate factors factors1 s. t. the result evaluated at evalPoint coincides with fa...
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
void appendTestMapDown(CFList &factors, const CanonicalForm &f, const ExtensionInfo &info, CFList &source, CFList &dest)
test if g is in a subfield of the current field, if so map it down and append it to factors ...
void refine()
Refine a degree pattern. Assumes that (*this)[0]:= d is the degree of the poly to be factored...
CFListIterator i
Definition: facFqBivar.cc:69
CanonicalForm test
Definition: cfModGcd.cc:4037
CanonicalForm buf2
Definition: facFqBivar.cc:71
Variable beta
Definition: facAbsFact.cc:99
bool fdivides(const CanonicalForm &f, const CanonicalForm &g)
bool fdivides ( const CanonicalForm & f, const CanonicalForm & g )
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:37
return mod(mulNTL(buf1, buf2, b), M)
int length() const
Definition: ftmpl_list.cc:273
int getLength() const
getter
Definition: DegreePattern.h:86
Variable x
Definition: cfModGcd.cc:4023
#define DEBOUTLN(stream, objects)
Definition: debug.h:49
int degree(const CanonicalForm &f)
static jList * T
Definition: janet.cc:37
CanonicalForm LC(const CanonicalForm &f)
CanonicalForm getGamma() const
getter
template List< Variable > Difference(const List< Variable > &, const List< Variable > &)
return result
Definition: facAbsBiFact.cc:76
int l
Definition: cfEzgcd.cc:94
CanonicalForm prodMod(const CFList &L, const CanonicalForm &M)
product of all elements in L modulo M via divide-and-conquer.
Definition: facMul.cc:3047
bool inCoeffDomain() const

§ 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 561 of file facFqBivar.cc.

566 {
567  if (factors.length() == 0)
568  {
569  F= 1;
570  return CFList ();
571  }
572  if (F.inCoeffDomain())
573  return CFList();
574  Variable y= Variable (2);
575  if (degs.getLength() <= 1 || factors.length() == 1)
576  {
577  CFList result= CFList (F(y-eval,y));
578  F= 1;
579  return result;
580  }
581 #ifdef DEBUGOUTPUT
582  if (b.getp() == 0)
583  DEBOUTLN (cerr, "LC (F, 1)*prodMod (factors, N) == F " <<
584  (mod (LC (F, 1)*prodMod (factors, N),N)/Lc (mod (LC (F, 1)*prodMod (factors, N),N)) == F/Lc(F)));
585  else
586  DEBOUTLN (cerr, "LC (F, 1)*prodMod (factors, N) == F " <<
587  (mod (b(LC (F, 1)*prodMod (factors, N)),N)/Lc (mod (b(LC (F, 1)*prodMod (factors, N)),N)) == F/Lc(F)));
588 #endif
589 
590  CFList T, S;
591 
592  CanonicalForm M= N;
593  int l= degree (N);
594  T= factors;
595  CFList result;
596  Variable x= Variable (1);
597  CanonicalForm denom= den, denQuot;
598  CanonicalForm LCBuf= LC (F, x)*denom;
599  CanonicalForm g, quot, buf= F;
600  int * v= new int [T.length()];
601  for (int i= 0; i < T.length(); i++)
602  v[i]= 0;
603  bool nosubset= false;
604  CFArray TT;
605  DegreePattern bufDegs1, bufDegs2;
606  bufDegs1= degs;
607  int subsetDeg;
608  TT= copy (factors);
609  bool recombination= false;
611  bool isRat= (isOn (SW_RATIONAL) && getCharacteristic() == 0) ||
612  getCharacteristic() > 0;
613  if (!isRat)
614  On (SW_RATIONAL);
615  CanonicalForm buf0= mulNTL (buf (0, x), LCBuf);
616  if (!isRat)
617  Off (SW_RATIONAL);
618  while (T.length() >= 2*s && s <= thres)
619  {
620  while (nosubset == false)
621  {
622  if (T.length() == s)
623  {
624  delete [] v;
625  if (recombination)
626  {
627  T.insert (LCBuf);
628  g= prodMod (T, M);
629  if (b.getp() != 0)
630  g= b(g);
631  T.removeFirst();
632  g /= content (g,x);
633  result.append (g(y-eval,y));
634  F= 1;
635  return result;
636  }
637  else
638  {
639  result= CFList (F(y-eval,y));
640  F= 1;
641  return result;
642  }
643  }
644  S= subset (v, s, TT, nosubset);
645  if (nosubset) break;
646  subsetDeg= subsetDegree (S);
647  // skip those combinations that are not possible
648  if (!degs.find (subsetDeg))
649  continue;
650  else
651  {
652  if (!isRat)
653  On (SW_RATIONAL);
654  test= prodMod0 (S, M);
655  if (!isRat)
656  {
657  test *= bCommonDen (test);
658  Off (SW_RATIONAL);
659  }
660  test= mulNTL (test, LCBuf, b);
661  test= mod (test, M);
662  if (uniFdivides (test, buf0))
663  {
664  if (!isRat)
665  On (SW_RATIONAL);
666  S.insert (LCBuf);
667  g= prodMod (S, M);
668  S.removeFirst();
669  if (!isRat)
670  {
671  g *= bCommonDen(g);
672  Off (SW_RATIONAL);
673  }
674  if (b.getp() != 0)
675  g= b(g);
676  if (!isRat)
677  On (SW_RATIONAL);
678  g /= content (g, x);
679  if (!isRat)
680  {
681  On (SW_RATIONAL);
682  if (!Lc (g).inBaseDomain())
683  g /= Lc (g);
684  g *= bCommonDen (g);
685  Off (SW_RATIONAL);
686  g /= icontent (g);
687  On (SW_RATIONAL);
688  }
689  if (fdivides (g, buf, quot))
690  {
691  denom *= abs (lc (g));
692  recombination= true;
693  result.append (g (y-eval,y));
694  if (b.getp() != 0)
695  {
696  denQuot= bCommonDen (quot);
697  buf= quot*denQuot;
698  Off (SW_RATIONAL);
699  denom /= gcd (denom, denQuot);
700  On (SW_RATIONAL);
701  }
702  else
703  buf= quot;
704  LCBuf= LC (buf, x)*denom;
705  T= Difference (T, S);
706  l -= degree (g);
707  M= power (y, l);
708  buf0= mulNTL (buf (0, x), LCBuf);
709  if (!isRat)
710  Off (SW_RATIONAL);
711  // compute new possible degree pattern
712  bufDegs2= DegreePattern (T);
713  bufDegs1.intersect (bufDegs2);
714  bufDegs1.refine ();
715  if (T.length() < 2*s || T.length() == s ||
716  bufDegs1.getLength() == 1)
717  {
718  delete [] v;
719  if (recombination)
720  {
721  result.append (buf (y-eval,y));
722  F= 1;
723  return result;
724  }
725  else
726  {
727  result= CFList (F (y-eval,y));
728  F= 1;
729  return result;
730  }
731  }
732  TT= copy (T);
733  indexUpdate (v, s, T.length(), nosubset);
734  if (nosubset) break;
735  }
736  if (!isRat)
737  Off (SW_RATIONAL);
738  }
739  }
740  }
741  s++;
742  if (T.length() < 2*s || T.length() == s)
743  {
744  delete [] v;
745  if (recombination)
746  {
747  result.append (buf(y-eval,y));
748  F= 1;
749  return result;
750  }
751  else
752  {
753  result= CFList (F(y-eval,y));
754  F= 1;
755  return result;
756  }
757  }
758  for (int i= 0; i < T.length(); i++)
759  v[i]= 0;
760  nosubset= false;
761  }
762  delete [] v;
763  if (T.length() < 2*s)
764  {
765  result.append (F(y-eval,y));
766  F= 1;
767  return result;
768  }
769 
770  if (s > thres)
771  {
772  factors= T;
773  F= buf;
774  degs= bufDegs1;
775  }
776 
777  return result;
778 }
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
void indexUpdate(int index [], const int &subsetSize, const int &setSize, bool &noSubset)
update index
List< CanonicalForm > CFList
const CanonicalForm const modpk & b
Definition: facFqBivar.cc:59
const CanonicalForm int s
Definition: facAbsFact.cc:55
DegreePattern provides a functionality to create, intersect and refine degree patterns.
Definition: DegreePattern.h:31
const CanonicalForm int const CFList const Variable & y
Definition: facAbsFact.cc:57
CanonicalForm icontent(const CanonicalForm &f)
CanonicalForm icontent ( const CanonicalForm & f )
Definition: cf_gcd.cc:71
CFArray copy(const CFList &list)
write elements of list into an array
bool uniFdivides(const CanonicalForm &A, const CanonicalForm &B)
divisibility test for univariate polys
Definition: facMul.cc:3626
void Off(int sw)
switches
factory&#39;s class for variables
Definition: factory.h:115
int find(const int x) const
find an element x
factory&#39;s main class
Definition: canonicalform.h:75
g
Definition: cfModGcd.cc:4031
CanonicalForm prodMod0(const CFList &L, const CanonicalForm &M, const modpk &b=modpk())
via divide-and-conquer
const CanonicalForm & M
Definition: facFqBivar.cc:58
void insert(const T &)
Definition: ftmpl_list.cc:193
CanonicalForm Lc(const CanonicalForm &f)
int getCharacteristic()
Definition: cf_char.cc:51
Rational abs(const Rational &a)
Definition: GMPrat.cc:443
void removeFirst()
Definition: ftmpl_list.cc:287
CanonicalForm content(const CanonicalForm &)
CanonicalForm content ( const CanonicalForm & f )
Definition: cf_gcd.cc:180
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...
void intersect(const DegreePattern &degPat)
intersect two degree patterns
CanonicalForm lc(const CanonicalForm &f)
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), Z, Q, Q(a), if we are in GF factory&#39;s default multiplication is used. If b!= 0 and getCharacteristic() == 0 the input will be considered as elements over Z/p^k or Z/p^k[t]/(f).
Definition: facMul.cc:407
const CanonicalForm CFMap CFMap & N
Definition: cfEzgcd.cc:49
int status int void * buf
Definition: si_signals.h:59
static const int SW_RATIONAL
set to 1 for computations over Q
Definition: cf_defs.h:28
bool isOn(int sw)
switches
void On(int sw)
switches
int subsetDegree(const CFList &S)
compute the sum of degrees in Variable(1) of elements in S
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 bCommonDen(const CanonicalForm &f)
CanonicalForm bCommonDen ( const CanonicalForm & f )
void refine()
Refine a degree pattern. Assumes that (*this)[0]:= d is the degree of the poly to be factored...
CFListIterator i
Definition: facFqBivar.cc:69
CanonicalForm test
Definition: cfModGcd.cc:4037
bool fdivides(const CanonicalForm &f, const CanonicalForm &g)
bool fdivides ( const CanonicalForm & f, const CanonicalForm & g )
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:37
return mod(mulNTL(buf1, buf2, b), M)
int length() const
Definition: ftmpl_list.cc:273
CanonicalForm den(const CanonicalForm &f)
int getLength() const
getter
Definition: DegreePattern.h:86
int gcd(int a, int b)
Definition: walkSupport.cc:839
Variable x
Definition: cfModGcd.cc:4023
#define DEBOUTLN(stream, objects)
Definition: debug.h:49
void append(const T &)
Definition: ftmpl_list.cc:256
int degree(const CanonicalForm &f)
static jList * T
Definition: janet.cc:37
CanonicalForm LC(const CanonicalForm &f)
template List< Variable > Difference(const List< Variable > &, const List< Variable > &)
int l
Definition: cfEzgcd.cc:94
return result
Definition: facAbsBiFact.cc:76
int getp() const
Definition: fac_util.h:35
CanonicalForm prodMod(const CFList &L, const CanonicalForm &M)
product of all elements in L modulo M via divide-and-conquer.
Definition: facMul.cc:3047
bool inCoeffDomain() const

§ 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 180 of file facFqBivar.h.

183 {
185  CFMap N;
186  CanonicalForm F= compress (G, N);
187 
188  if (substCheck)
189  {
190  bool foundOne= false;
191  int * substDegree= new int [F.level()];
192  for (int i= 1; i <= F.level(); i++)
193  {
194  substDegree[i-1]= substituteCheck (F, Variable (i));
195  if (substDegree [i-1] > 1)
196  {
197  foundOne= true;
198  subst (F, F, substDegree[i-1], Variable (i));
199  }
200  }
201  if (foundOne)
202  {
203  CFFList result= FpBiFactorize (F, false);
204  CFFList newResult, tmp;
206  newResult.insert (result.getFirst());
207  result.removeFirst();
208  for (CFFListIterator i= result; i.hasItem(); i++)
209  {
210  tmp2= i.getItem().factor();
211  for (int j= 1; j <= F.level(); j++)
212  {
213  if (substDegree[j-1] > 1)
214  tmp2= reverseSubst (tmp2, substDegree[j-1], Variable (j));
215  }
216  tmp= FpBiFactorize (tmp2, false);
217  tmp.removeFirst();
218  for (CFFListIterator j= tmp; j.hasItem(); j++)
219  newResult.append (CFFactor (j.getItem().factor(),
220  j.getItem().exp()*i.getItem().exp()));
221  }
222  decompress (newResult, N);
223  delete [] substDegree;
224  return newResult;
225  }
226  delete [] substDegree;
227  }
228 
229  CanonicalForm LcF= Lc (F);
230  CanonicalForm contentX= content (F, 1);
231  CanonicalForm contentY= content (F, 2);
232  F /= (contentX*contentY);
233  CFFList contentXFactors, contentYFactors;
234  contentXFactors= factorize (contentX);
235  contentYFactors= factorize (contentY);
236  if (contentXFactors.getFirst().factor().inCoeffDomain())
237  contentXFactors.removeFirst();
238  if (contentYFactors.getFirst().factor().inCoeffDomain())
239  contentYFactors.removeFirst();
240  decompress (contentXFactors, N);
241  decompress (contentYFactors, N);
242  CFFList result;
243  if (F.inCoeffDomain())
244  {
245  result= Union (contentXFactors, contentYFactors);
246  normalize (result);
247  result.insert (CFFactor (LcF, 1));
248  return result;
249  }
250  mpz_t * M=new mpz_t [4];
251  mpz_init (M[0]);
252  mpz_init (M[1]);
253  mpz_init (M[2]);
254  mpz_init (M[3]);
255 
256  mpz_t * S=new mpz_t [2];
257  mpz_init (S[0]);
258  mpz_init (S[1]);
259 
260  F= compress (F, M, S);
261 
262  TIMING_START (fac_fq_bi_sqrf);
263  CFFList sqrf= FpSqrf (F, false);
264  TIMING_END_AND_PRINT (fac_fq_bi_sqrf,
265  "time for bivariate sqrf factors over Fp: ");
266  CFList bufResult;
267  sqrf.removeFirst();
269  for (CFFListIterator iter= sqrf; iter.hasItem(); iter++)
270  {
271  TIMING_START (fac_fq_bi_factor_sqrf);
272  bufResult= biFactorize (iter.getItem().factor(), info);
273  TIMING_END_AND_PRINT (fac_fq_bi_factor_sqrf,
274  "time to factor bivariate sqrf factors over Fp: ");
275  for (i= bufResult; i.hasItem(); i++)
276  result.append (CFFactor (N (decompress (i.getItem(), M, S)),
277  iter.getItem().exp()));
278  }
279 
280  result= Union (result, contentXFactors);
281  result= Union (result, contentYFactors);
282  normalize (result);
283  result.insert (CFFactor (LcF, 1));
284 
285  mpz_clear (M[0]);
286  mpz_clear (M[1]);
287  mpz_clear (M[2]);
288  mpz_clear (M[3]);
289  delete [] M;
290 
291  mpz_clear (S[0]);
292  mpz_clear (S[1]);
293  delete [] S;
294 
295  return result;
296 }
static poly normalize(poly next_p, ideal add_generators, syStrategy syzstr, int *g_l, int *p_l, int crit_comp)
Definition: syz3.cc:1024
CFFList FpSqrf(const CanonicalForm &F, bool sort=true)
squarefree factorization over . If input is not monic, the leading coefficient is dropped ...
#define TIMING_END_AND_PRINT(t, msg)
Definition: timing.h:89
factory&#39;s class for variables
Definition: factory.h:115
CFFListIterator iter
Definition: facAbsBiFact.cc:54
factory&#39;s main class
Definition: canonicalform.h:75
void insert(const T &)
Definition: ftmpl_list.cc:193
CanonicalForm Lc(const CanonicalForm &f)
CanonicalForm compress(const CanonicalForm &f, CFMap &m)
CanonicalForm compress ( const CanonicalForm & f, CFMap & m )
Definition: cf_map.cc:210
CanonicalForm LcF
Definition: facAbsBiFact.cc:51
void removeFirst()
Definition: ftmpl_list.cc:287
CanonicalForm subst(const CanonicalForm &f, const CFList &a, const CFList &b, const CanonicalForm &Rstar, bool isFunctionField)
CanonicalForm content(const CanonicalForm &)
CanonicalForm content ( const CanonicalForm & f )
Definition: cf_gcd.cc:180
T getFirst() const
Definition: ftmpl_list.cc:279
template List< Variable > Union(const List< Variable > &, const List< Variable > &)
#define M
Definition: sirandom.c:24
CFFList factorize(const CanonicalForm &f, bool issqrfree=false)
factorization over or
Definition: cf_factor.cc:390
ExtensionInfo contains information about extension.
Definition: ExtensionInfo.h:50
const CanonicalForm CFMap CFMap & N
Definition: cfEzgcd.cc:49
int j
Definition: myNF.cc:70
CanonicalForm decompress(const CanonicalForm &F, const mpz_t *inverseM, const mpz_t *A)
decompress a bivariate poly
T & getItem() const
Definition: ftmpl_list.cc:431
const ExtensionInfo & info
< [in] sqrfree poly
CFFList FpBiFactorize(const CanonicalForm &G, bool substCheck=true)
factorize a bivariate polynomial over
Definition: facFqBivar.h:180
int substituteCheck(const CanonicalForm &F, const Variable &x)
check if a substitution x^n->x is possible
int i
Definition: cfEzgcd.cc:123
CFList tmp2
Definition: facFqBivar.cc:70
class CFMap
Definition: cf_map.h:84
#define TIMING_START(t)
Definition: timing.h:87
CanonicalForm reverseSubst(const CanonicalForm &F, const int d, const Variable &x)
reverse a substitution x^d->x
int level() const
level() returns the level of CO.
void append(const T &)
Definition: ftmpl_list.cc:256
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.
Definition: facFqBivar.cc:8201
return result
Definition: facAbsBiFact.cc:76
bool inCoeffDomain() const

§ 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 137 of file facFqBivar.h.

139 {
141  return biSqrfFactorizeHelper (G, info);
142 }
ExtensionInfo contains information about extension.
Definition: ExtensionInfo.h:50
const ExtensionInfo & info
< [in] sqrfree poly
CFList biSqrfFactorizeHelper(const CanonicalForm &G, const ExtensionInfo &info)
Definition: facFqBivar.h:53

§ 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 305 of file facFqBivar.h.

309 {
310  ExtensionInfo info= ExtensionInfo (alpha, false);
311  CFMap N;
312  CanonicalForm F= compress (G, N);
313 
314  if (substCheck)
315  {
316  bool foundOne= false;
317  int * substDegree= new int [F.level()];
318  for (int i= 1; i <= F.level(); i++)
319  {
320  substDegree[i-1]= substituteCheck (F, Variable (i));
321  if (substDegree [i-1] > 1)
322  {
323  foundOne= true;
324  subst (F, F, substDegree[i-1], Variable (i));
325  }
326  }
327  if (foundOne)
328  {
329  CFFList result= FqBiFactorize (F, alpha, false);
330  CFFList newResult, tmp;
332  newResult.insert (result.getFirst());
333  result.removeFirst();
334  for (CFFListIterator i= result; i.hasItem(); i++)
335  {
336  tmp2= i.getItem().factor();
337  for (int j= 1; j <= F.level(); j++)
338  {
339  if (substDegree[j-1] > 1)
340  tmp2= reverseSubst (tmp2, substDegree[j-1], Variable (j));
341  }
342  tmp= FqBiFactorize (tmp2, alpha, false);
343  tmp.removeFirst();
344  for (CFFListIterator j= tmp; j.hasItem(); j++)
345  newResult.append (CFFactor (j.getItem().factor(),
346  j.getItem().exp()*i.getItem().exp()));
347  }
348  decompress (newResult, N);
349  delete [] substDegree;
350  return newResult;
351  }
352  delete [] substDegree;
353  }
354 
355  CanonicalForm LcF= Lc (F);
356  CanonicalForm contentX= content (F, 1);
357  CanonicalForm contentY= content (F, 2);
358  F /= (contentX*contentY);
359  CFFList contentXFactors, contentYFactors;
360  contentXFactors= factorize (contentX, alpha);
361  contentYFactors= factorize (contentY, alpha);
362  if (contentXFactors.getFirst().factor().inCoeffDomain())
363  contentXFactors.removeFirst();
364  if (contentYFactors.getFirst().factor().inCoeffDomain())
365  contentYFactors.removeFirst();
366  decompress (contentXFactors, N);
367  decompress (contentYFactors, N);
368  CFFList result;
369  if (F.inCoeffDomain())
370  {
371  result= Union (contentXFactors, contentYFactors);
372  normalize (result);
373  result.insert (CFFactor (LcF, 1));
374  return result;
375  }
376 
377  mpz_t * M=new mpz_t [4];
378  mpz_init (M[0]);
379  mpz_init (M[1]);
380  mpz_init (M[2]);
381  mpz_init (M[3]);
382 
383  mpz_t * S=new mpz_t [2];
384  mpz_init (S[0]);
385  mpz_init (S[1]);
386 
387  F= compress (F, M, S);
388 
389  TIMING_START (fac_fq_bi_sqrf);
390  CFFList sqrf= FqSqrf (F, alpha, false);
391  TIMING_END_AND_PRINT (fac_fq_bi_sqrf,
392  "time for bivariate sqrf factors over Fq: ");
393  CFList bufResult;
394  sqrf.removeFirst();
396  for (CFFListIterator iter= sqrf; iter.hasItem(); iter++)
397  {
398  TIMING_START (fac_fq_bi_factor_sqrf);
399  bufResult= biFactorize (iter.getItem().factor(), info);
400  TIMING_END_AND_PRINT (fac_fq_bi_factor_sqrf,
401  "time to factor bivariate sqrf factors over Fq: ");
402  for (i= bufResult; i.hasItem(); i++)
403  result.append (CFFactor (N (decompress (i.getItem(), M, S)),
404  iter.getItem().exp()));
405  }
406 
407  result= Union (result, contentXFactors);
408  result= Union (result, contentYFactors);
409  normalize (result);
410  result.insert (CFFactor (LcF, 1));
411 
412  mpz_clear (M[0]);
413  mpz_clear (M[1]);
414  mpz_clear (M[2]);
415  mpz_clear (M[3]);
416  delete [] M;
417 
418  mpz_clear (S[0]);
419  mpz_clear (S[1]);
420  delete [] S;
421 
422  return result;
423 }
static poly normalize(poly next_p, ideal add_generators, syStrategy syzstr, int *g_l, int *p_l, int crit_comp)
Definition: syz3.cc:1024
#define TIMING_END_AND_PRINT(t, msg)
Definition: timing.h:89
factory&#39;s class for variables
Definition: factory.h:115
CFFListIterator iter
Definition: facAbsBiFact.cc:54
factory&#39;s main class
Definition: canonicalform.h:75
CFFList FqSqrf(const CanonicalForm &F, const Variable &alpha, bool sort=true)
squarefree factorization over . If input is not monic, the leading coefficient is dropped ...
void insert(const T &)
Definition: ftmpl_list.cc:193
CanonicalForm Lc(const CanonicalForm &f)
CanonicalForm compress(const CanonicalForm &f, CFMap &m)
CanonicalForm compress ( const CanonicalForm & f, CFMap & m )
Definition: cf_map.cc:210
CanonicalForm LcF
Definition: facAbsBiFact.cc:51
void removeFirst()
Definition: ftmpl_list.cc:287
CanonicalForm subst(const CanonicalForm &f, const CFList &a, const CFList &b, const CanonicalForm &Rstar, bool isFunctionField)
CanonicalForm content(const CanonicalForm &)
CanonicalForm content ( const CanonicalForm & f )
Definition: cf_gcd.cc:180
T getFirst() const
Definition: ftmpl_list.cc:279
template List< Variable > Union(const List< Variable > &, const List< Variable > &)
#define M
Definition: sirandom.c:24
CFFList factorize(const CanonicalForm &f, bool issqrfree=false)
factorization over or
Definition: cf_factor.cc:390
ExtensionInfo contains information about extension.
Definition: ExtensionInfo.h:50
const CanonicalForm CFMap CFMap & N
Definition: cfEzgcd.cc:49
int j
Definition: myNF.cc:70
CanonicalForm decompress(const CanonicalForm &F, const mpz_t *inverseM, const mpz_t *A)
decompress a bivariate poly
T & getItem() const
Definition: ftmpl_list.cc:431
const ExtensionInfo & info
< [in] sqrfree poly
int substituteCheck(const CanonicalForm &F, const Variable &x)
check if a substitution x^n->x is possible
int i
Definition: cfEzgcd.cc:123
CFFList FqBiFactorize(const CanonicalForm &G, const Variable &alpha, bool substCheck=true)
factorize a bivariate polynomial over
Definition: facFqBivar.h:305
CFList tmp2
Definition: facFqBivar.cc:70
class CFMap
Definition: cf_map.h:84
#define TIMING_START(t)
Definition: timing.h:87
CanonicalForm reverseSubst(const CanonicalForm &F, const int d, const Variable &x)
reverse a substitution x^d->x
int level() const
level() returns the level of CO.
void append(const T &)
Definition: ftmpl_list.cc:256
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.
Definition: facFqBivar.cc:8201
return result
Definition: facAbsBiFact.cc:76
bool inCoeffDomain() const

§ 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 150 of file facFqBivar.h.

153 {
154  ExtensionInfo info= ExtensionInfo (alpha, false);
155  return biSqrfFactorizeHelper (G, info);
156 }
ExtensionInfo contains information about extension.
Definition: ExtensionInfo.h:50
const ExtensionInfo & info
< [in] sqrfree poly
CFList biSqrfFactorizeHelper(const CanonicalForm &G, const ExtensionInfo &info)
Definition: facFqBivar.h:53

§ 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 1084 of file facFqBivar.cc.

1085 {
1086  int sizeOfNewtonPoly;
1087  int ** newtonPolyg= newtonPolygon (F, sizeOfNewtonPoly);
1088  int sizeOfRightSide;
1089  int * rightSide= getRightSide(newtonPolyg, sizeOfNewtonPoly, sizeOfRightSide);
1090  int * result= getCombinations(rightSide, sizeOfRightSide, sizeOfOutput,
1091  degreeLC);
1092  delete [] rightSide;
1093  for (int i= 0; i < sizeOfNewtonPoly; i++)
1094  delete [] newtonPolyg[i];
1095  delete [] newtonPolyg;
1096  return result;
1097 }
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:1045
CFListIterator i
Definition: facFqBivar.cc:69
return result
Definition: facAbsBiFact.cc:76

§ 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 432 of file facFqBivar.h.

435 {
437  "GF as base field expected");
439  CFMap N;
440  CanonicalForm F= compress (G, N);
441 
442  if (substCheck)
443  {
444  bool foundOne= false;
445  int * substDegree= new int [F.level()];
446  for (int i= 1; i <= F.level(); i++)
447  {
448  substDegree[i-1]= substituteCheck (F, Variable (i));
449  if (substDegree [i-1] > 1)
450  {
451  foundOne= true;
452  subst (F, F, substDegree[i-1], Variable (i));
453  }
454  }
455  if (foundOne)
456  {
457  CFFList result= GFBiFactorize (F, false);
458  CFFList newResult, tmp;
460  newResult.insert (result.getFirst());
461  result.removeFirst();
462  for (CFFListIterator i= result; i.hasItem(); i++)
463  {
464  tmp2= i.getItem().factor();
465  for (int j= 1; j <= F.level(); j++)
466  {
467  if (substDegree[j-1] > 1)
468  tmp2= reverseSubst (tmp2, substDegree[j-1], Variable (j));
469  }
470  tmp= GFBiFactorize (tmp2, false);
471  tmp.removeFirst();
472  for (CFFListIterator j= tmp; j.hasItem(); j++)
473  newResult.append (CFFactor (j.getItem().factor(),
474  j.getItem().exp()*i.getItem().exp()));
475  }
476  decompress (newResult, N);
477  delete [] substDegree;
478  return newResult;
479  }
480  delete [] substDegree;
481  }
482 
483  CanonicalForm LcF= Lc (F);
484  CanonicalForm contentX= content (F, 1);
485  CanonicalForm contentY= content (F, 2);
486  F /= (contentX*contentY);
487  CFFList contentXFactors, contentYFactors;
488  contentXFactors= factorize (contentX);
489  contentYFactors= factorize (contentY);
490  if (contentXFactors.getFirst().factor().inCoeffDomain())
491  contentXFactors.removeFirst();
492  if (contentYFactors.getFirst().factor().inCoeffDomain())
493  contentYFactors.removeFirst();
494  decompress (contentXFactors, N);
495  decompress (contentYFactors, N);
496  CFFList result;
497  if (F.inCoeffDomain())
498  {
499  result= Union (contentXFactors, contentYFactors);
500  normalize (result);
501  result.insert (CFFactor (LcF, 1));
502  return result;
503  }
504 
505  mpz_t * M=new mpz_t [4];
506  mpz_init (M[0]);
507  mpz_init (M[1]);
508  mpz_init (M[2]);
509  mpz_init (M[3]);
510 
511  mpz_t * S=new mpz_t [2];
512  mpz_init (S[0]);
513  mpz_init (S[1]);
514 
515  F= compress (F, M, S);
516 
517  TIMING_START (fac_fq_bi_sqrf);
518  CFFList sqrf= GFSqrf (F, false);
519  TIMING_END_AND_PRINT (fac_fq_bi_sqrf,
520  "time for bivariate sqrf factors over GF: ");
521  CFList bufResult;
522  sqrf.removeFirst();
524  for (CFFListIterator iter= sqrf; iter.hasItem(); iter++)
525  {
526  TIMING_START (fac_fq_bi_factor_sqrf);
527  bufResult= biFactorize (iter.getItem().factor(), info);
528  TIMING_END_AND_PRINT (fac_fq_bi_factor_sqrf,
529  "time to factor bivariate sqrf factors over GF: ");
530  for (i= bufResult; i.hasItem(); i++)
531  result.append (CFFactor (N (decompress (i.getItem(), M, S)),
532  iter.getItem().exp()));
533  }
534 
535  result= Union (result, contentXFactors);
536  result= Union (result, contentYFactors);
537  normalize (result);
538  result.insert (CFFactor (LcF, 1));
539 
540  mpz_clear (M[0]);
541  mpz_clear (M[1]);
542  mpz_clear (M[2]);
543  mpz_clear (M[3]);
544  delete [] M;
545 
546  mpz_clear (S[0]);
547  mpz_clear (S[1]);
548  delete [] S;
549 
550  return result;
551 }
static poly normalize(poly next_p, ideal add_generators, syStrategy syzstr, int *g_l, int *p_l, int crit_comp)
Definition: syz3.cc:1024
#define TIMING_END_AND_PRINT(t, msg)
Definition: timing.h:89
factory&#39;s class for variables
Definition: factory.h:115
CFFList GFBiFactorize(const CanonicalForm &G, bool substCheck=true)
factorize a bivariate polynomial over GF
Definition: facFqBivar.h:432
CFFListIterator iter
Definition: facAbsBiFact.cc:54
factory&#39;s main class
Definition: canonicalform.h:75
char gf_name
Definition: gfops.cc:52
void insert(const T &)
Definition: ftmpl_list.cc:193
CanonicalForm Lc(const CanonicalForm &f)
CanonicalForm compress(const CanonicalForm &f, CFMap &m)
CanonicalForm compress ( const CanonicalForm & f, CFMap & m )
Definition: cf_map.cc:210
CanonicalForm LcF
Definition: facAbsBiFact.cc:51
void removeFirst()
Definition: ftmpl_list.cc:287
CanonicalForm subst(const CanonicalForm &f, const CFList &a, const CFList &b, const CanonicalForm &Rstar, bool isFunctionField)
CanonicalForm content(const CanonicalForm &)
CanonicalForm content ( const CanonicalForm & f )
Definition: cf_gcd.cc:180
T getFirst() const
Definition: ftmpl_list.cc:279
template List< Variable > Union(const List< Variable > &, const List< Variable > &)
#define M
Definition: sirandom.c:24
CFFList factorize(const CanonicalForm &f, bool issqrfree=false)
factorization over or
Definition: cf_factor.cc:390
ExtensionInfo contains information about extension.
Definition: ExtensionInfo.h:50
CFFList GFSqrf(const CanonicalForm &F, bool sort=true)
squarefree factorization over GF. If input is not monic, the leading coefficient is dropped ...
const CanonicalForm CFMap CFMap & N
Definition: cfEzgcd.cc:49
int j
Definition: myNF.cc:70
CanonicalForm decompress(const CanonicalForm &F, const mpz_t *inverseM, const mpz_t *A)
decompress a bivariate poly
T & getItem() const
Definition: ftmpl_list.cc:431
const ExtensionInfo & info
< [in] sqrfree poly
int substituteCheck(const CanonicalForm &F, const Variable &x)
check if a substitution x^n->x is possible
int i
Definition: cfEzgcd.cc:123
CFList tmp2
Definition: facFqBivar.cc:70
class CFMap
Definition: cf_map.h:84
static int gettype()
Definition: cf_factory.h:27
#define TIMING_START(t)
Definition: timing.h:87
int getGFDegree()
Definition: cf_char.cc:56
#define GaloisFieldDomain
Definition: cf_defs.h:22
CanonicalForm reverseSubst(const CanonicalForm &F, const int d, const Variable &x)
reverse a substitution x^d->x
int level() const
level() returns the level of CO.
#define ASSERT(expression, message)
Definition: cf_assert.h:99
void append(const T &)
Definition: ftmpl_list.cc:256
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.
Definition: facFqBivar.cc:8201
return result
Definition: facAbsBiFact.cc:76
bool inCoeffDomain() const

§ 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 164 of file facFqBivar.h.

166 {
168  "GF as base field expected");
170  return biSqrfFactorizeHelper (G, info);
171 }
char gf_name
Definition: gfops.cc:52
ExtensionInfo contains information about extension.
Definition: ExtensionInfo.h:50
const ExtensionInfo & info
< [in] sqrfree poly
CFList biSqrfFactorizeHelper(const CanonicalForm &G, const ExtensionInfo &info)
Definition: facFqBivar.h:53
static int gettype()
Definition: cf_factory.h:27
int getGFDegree()
Definition: cf_char.cc:56
#define GaloisFieldDomain
Definition: cf_defs.h:22
#define ASSERT(expression, message)
Definition: cf_assert.h:99

§ henselLiftAndEarly() [1/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 1115 of file facFqBivar.cc.

1119 {
1120  Variable alpha= info.getAlpha();
1121  Variable beta= info.getBeta();
1122  CanonicalForm gamma= info.getGamma();
1123  CanonicalForm delta= info.getDelta();
1124  bool extension= info.isInExtension();
1125 
1126  int sizeOfLiftPre;
1127  int * liftPre= getLiftPrecisions (A, sizeOfLiftPre, degree (LC (A, 1), 2));
1128 
1129  Variable x= Variable (1);
1130  Variable y= Variable (2);
1131  CFArray Pi;
1132  CFList diophant;
1133  CFList bufUniFactors= uniFactors;
1134  On (SW_RATIONAL);
1135  CanonicalForm bufA= A;
1136  if (!Lc (A).inBaseDomain())
1137  {
1138  bufA /= Lc (A);
1139  CanonicalForm denBufA= bCommonDen (bufA);
1140  bufA *= denBufA;
1141  Off (SW_RATIONAL);
1142  den /= gcd (den, denBufA);
1143  }
1144  else
1145  {
1146  bufA= A;
1147  Off (SW_RATIONAL);
1148  den /= gcd (den, Lc (A));
1149  }
1150  CanonicalForm lcA0= 0;
1151  bool mipoHasDen= false;
1152  if (getCharacteristic() == 0 && b.getp() != 0)
1153  {
1154  if (alpha.level() == 1)
1155  {
1156  lcA0= lc (A (0, 2));
1157  A *= b.inverse (lcA0);
1158  A= b (A);
1159  for (CFListIterator i= bufUniFactors; i.hasItem(); i++)
1160  i.getItem()= b (i.getItem()*b.inverse (lc (i.getItem())));
1161  }
1162  else
1163  {
1164  lcA0= Lc (A (0,2));
1165  On (SW_RATIONAL);
1166  mipoHasDen= !bCommonDen(getMipo(alpha)).isOne();
1167  Off (SW_RATIONAL);
1168  CanonicalForm lcA0inverse= b.inverse (lcA0);
1169  A *= lcA0inverse;
1170  A= b (A);
1171  // Lc of bufUniFactors is in Z
1172  for (CFListIterator i= bufUniFactors; i.hasItem(); i++)
1173  i.getItem()= b (i.getItem()*b.inverse (lc (i.getItem())));
1174  }
1175  }
1176  bufUniFactors.insert (LC (A, x));
1177  CFMatrix M= CFMatrix (liftBound, bufUniFactors.length() - 1);
1178  earlySuccess= false;
1179  int newLiftBound= 0;
1180 
1181  int smallFactorDeg= tmin (11, liftPre [sizeOfLiftPre- 1] + 1);//this is a tunable parameter
1182  int dummy;
1183  int * factorsFoundIndex= new int [uniFactors.length()];
1184  for (int i= 0; i < uniFactors.length(); i++)
1185  factorsFoundIndex [i]= 0;
1186 
1187  CFList bufBufUniFactors;
1188  Variable v= alpha;
1189  if (smallFactorDeg >= liftBound || degree (A,y) <= 4)
1190  henselLift12 (A, bufUniFactors, liftBound, Pi, diophant, M, b, true);
1191  else if (sizeOfLiftPre > 1 && sizeOfLiftPre < 30)
1192  {
1193  henselLift12 (A, bufUniFactors, smallFactorDeg, Pi, diophant, M, b, true);
1194  if (mipoHasDen)
1195  {
1196  for (CFListIterator iter= bufUniFactors; iter.hasItem(); iter++)
1197  if (hasFirstAlgVar (iter.getItem(), v))
1198  break;
1199  if (v != alpha)
1200  {
1201  bufBufUniFactors= bufUniFactors;
1202  for (CFListIterator iter= bufBufUniFactors; iter.hasItem(); iter++)
1204  A= replacevar (A, alpha, v);
1205  }
1206  }
1207 
1208  if (!extension)
1209  {
1210  if (v==alpha)
1211  earlyFactorDetection (earlyFactors, bufA, bufUniFactors, newLiftBound,
1212  factorsFoundIndex, degs, earlySuccess,
1213  smallFactorDeg, eval, b, den);
1214  else
1215  earlyFactorDetection(earlyFactors, bufA, bufBufUniFactors, newLiftBound,
1216  factorsFoundIndex, degs, earlySuccess,
1217  smallFactorDeg, eval, b, den);
1218  }
1219  else
1220  extEarlyFactorDetection (earlyFactors, bufA, bufUniFactors, newLiftBound,
1221  factorsFoundIndex, degs, earlySuccess, info,
1222  eval, smallFactorDeg);
1223  if (degs.getLength() > 1 && !earlySuccess &&
1224  smallFactorDeg != liftPre [sizeOfLiftPre-1] + 1)
1225  {
1226  if (newLiftBound >= liftPre[sizeOfLiftPre-1]+1)
1227  {
1228  bufUniFactors.insert (LC (A, x));
1229  henselLiftResume12 (A, bufUniFactors, smallFactorDeg,
1230  liftPre[sizeOfLiftPre-1] + 1, Pi, diophant, M, b);
1231  if (v!=alpha)
1232  {
1233  bufBufUniFactors= bufUniFactors;
1234  for (CFListIterator iter= bufBufUniFactors; iter.hasItem(); iter++)
1236  }
1237  if (!extension)
1238  {
1239  if (v==alpha)
1240  earlyFactorDetection (earlyFactors, bufA, bufUniFactors, newLiftBound,
1241  factorsFoundIndex, degs, earlySuccess,
1242  liftPre[sizeOfLiftPre-1] + 1, eval, b, den);
1243  else
1244  earlyFactorDetection (earlyFactors,bufA,bufBufUniFactors,newLiftBound,
1245  factorsFoundIndex, degs, earlySuccess,
1246  liftPre[sizeOfLiftPre-1] + 1, eval, b, den);
1247  }
1248  else
1249  extEarlyFactorDetection (earlyFactors,bufA,bufUniFactors,newLiftBound,
1250  factorsFoundIndex, degs, earlySuccess, info,
1251  eval, liftPre[sizeOfLiftPre-1] + 1);
1252  }
1253  }
1254  else if (earlySuccess)
1255  liftBound= newLiftBound;
1256 
1257  int i= sizeOfLiftPre - 1;
1258  while (degs.getLength() > 1 && !earlySuccess && i - 1 >= 0)
1259  {
1260  if (newLiftBound >= liftPre[i] + 1)
1261  {
1262  bufUniFactors.insert (LC (A, x));
1263  henselLiftResume12 (A, bufUniFactors, liftPre[i] + 1,
1264  liftPre[i-1] + 1, Pi, diophant, M, b);
1265  if (v!=alpha)
1266  {
1267  bufBufUniFactors= bufUniFactors;
1268  for (CFListIterator iter= bufBufUniFactors; iter.hasItem(); iter++)
1270  }
1271  if (!extension)
1272  {
1273  if (v==alpha)
1274  earlyFactorDetection (earlyFactors, bufA, bufUniFactors, newLiftBound,
1275  factorsFoundIndex, degs, earlySuccess,
1276  liftPre[i-1] + 1, eval, b, den);
1277  else
1278  earlyFactorDetection (earlyFactors,bufA,bufBufUniFactors,newLiftBound,
1279  factorsFoundIndex, degs, earlySuccess,
1280  liftPre[i-1] + 1, eval, b, den);
1281  }
1282  else
1283  extEarlyFactorDetection (earlyFactors,bufA,bufUniFactors,newLiftBound,
1284  factorsFoundIndex, degs, earlySuccess, info,
1285  eval, liftPre[i-1] + 1);
1286  }
1287  else
1288  {
1289  liftBound= newLiftBound;
1290  break;
1291  }
1292  i--;
1293  }
1294  if (earlySuccess)
1295  liftBound= newLiftBound;
1296  //after here all factors are lifted to liftPre[sizeOfLiftPre-1]
1297  }
1298  else
1299  {
1300  henselLift12 (A, bufUniFactors, smallFactorDeg, Pi, diophant, M, b, true);
1301  if (mipoHasDen)
1302  {
1303  for (CFListIterator iter= bufUniFactors; iter.hasItem(); iter++)
1304  if (hasFirstAlgVar (iter.getItem(), v))
1305  break;
1306  if (v != alpha)
1307  {
1308  bufBufUniFactors= bufUniFactors;
1309  for (CFListIterator iter= bufBufUniFactors; iter.hasItem(); iter++)
1311  A= replacevar (A, alpha, v);
1312  }
1313  }
1314  if (!extension)
1315  {
1316  if (v==alpha)
1317  earlyFactorDetection (earlyFactors, bufA, bufUniFactors, newLiftBound,
1318  factorsFoundIndex, degs, earlySuccess,
1319  smallFactorDeg, eval, b, den);
1320  else
1321  earlyFactorDetection (earlyFactors, bufA, bufBufUniFactors, newLiftBound,
1322  factorsFoundIndex, degs, earlySuccess,
1323  smallFactorDeg, eval, b, den);
1324  }
1325  else
1326  extEarlyFactorDetection (earlyFactors, bufA, bufUniFactors, newLiftBound,
1327  factorsFoundIndex, degs, earlySuccess, info,
1328  eval, smallFactorDeg);
1329  int i= 1;
1330  while ((degree (A,y)/4)*i + 4 <= smallFactorDeg)
1331  i++;
1332  dummy= tmin (degree (A,y)+1, (degree (A,y)/4)*i+4);
1333  if (degs.getLength() > 1 && !earlySuccess && dummy > smallFactorDeg)
1334  {
1335  bufUniFactors.insert (LC (A, x));
1336  henselLiftResume12 (A, bufUniFactors, smallFactorDeg,
1337  dummy, Pi, diophant, M, b);
1338  if (v!=alpha)
1339  {
1340  bufBufUniFactors= bufUniFactors;
1341  for (CFListIterator iter= bufBufUniFactors; iter.hasItem(); iter++)
1343  }
1344  if (!extension)
1345  {
1346  if (v==alpha)
1347  earlyFactorDetection (earlyFactors, bufA, bufUniFactors, newLiftBound,
1348  factorsFoundIndex, degs, earlySuccess, dummy,eval,
1349  b, den);
1350  else
1351  earlyFactorDetection (earlyFactors, bufA,bufBufUniFactors, newLiftBound,
1352  factorsFoundIndex, degs, earlySuccess, dummy,eval,
1353  b, den);
1354  }
1355  else
1356  extEarlyFactorDetection (earlyFactors, bufA,bufUniFactors, newLiftBound,
1357  factorsFoundIndex, degs, earlySuccess, info,
1358  eval, dummy);
1359  }
1360  while (degs.getLength() > 1 && !earlySuccess && i < 4)
1361  {
1362  if (newLiftBound >= dummy)
1363  {
1364  bufUniFactors.insert (LC (A, x));
1365  dummy= tmin (degree (A,y)+1, (degree (A,y)/4)*(i+1)+4);
1366  henselLiftResume12 (A, bufUniFactors, (degree (A,y)/4)*i + 4,
1367  dummy, Pi, diophant, M, b);
1368  if (v!=alpha)
1369  {
1370  bufBufUniFactors= bufUniFactors;
1371  for (CFListIterator iter= bufBufUniFactors; iter.hasItem(); iter++)
1373  }
1374  if (!extension)
1375  {
1376  if (v==alpha)
1377  earlyFactorDetection (earlyFactors, bufA, bufUniFactors, newLiftBound,
1378  factorsFoundIndex, degs, earlySuccess, dummy,
1379  eval, b, den);
1380  else
1381  earlyFactorDetection (earlyFactors,bufA,bufBufUniFactors,newLiftBound,
1382  factorsFoundIndex, degs, earlySuccess, dummy,
1383  eval, b, den);
1384  }
1385  else
1386  extEarlyFactorDetection (earlyFactors,bufA,bufUniFactors,newLiftBound,
1387  factorsFoundIndex, degs, earlySuccess, info,
1388  eval, dummy);
1389  }
1390  else
1391  {
1392  liftBound= newLiftBound;
1393  break;
1394  }
1395  i++;
1396  }
1397  if (earlySuccess)
1398  liftBound= newLiftBound;
1399  }
1400 
1401  A= bufA;
1402  if (earlyFactors.length() > 0 && degs.getLength() > 1)
1403  {
1404  liftBound= degree (A,y) + 1;
1405  earlySuccess= true;
1406  deleteFactors (bufUniFactors, factorsFoundIndex);
1407  }
1408 
1409  delete [] factorsFoundIndex;
1410  delete [] liftPre;
1411 
1412  return bufUniFactors;
1413 }
void deleteFactors(CFList &factors, int *factorsFoundIndex)
Definition: facFqBivar.cc:1100
Variable getAlpha() const
getter
const CanonicalForm const modpk & b
Definition: facFqBivar.cc:59
const CanonicalForm int const CFList const Variable & y
Definition: facAbsFact.cc:57
CF_NO_INLINE bool isOne() const
CF_INLINE bool CanonicalForm::isOne, isZero () const.
Definition: cf_inline.cc:354
void Off(int sw)
switches
Matrix< CanonicalForm > CFMatrix
CanonicalForm getDelta() const
getter
factory&#39;s class for variables
Definition: factory.h:115
CFFListIterator iter
Definition: facAbsBiFact.cc:54
factory&#39;s main class
Definition: canonicalform.h:75
Variable alpha
Definition: facAbsBiFact.cc:52
const CanonicalForm & M
Definition: facFqBivar.cc:58
void insert(const T &)
Definition: ftmpl_list.cc:193
CanonicalForm Lc(const CanonicalForm &f)
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
Definition: variable.cc:207
bool delta(X x, Y y, D d)
Definition: TestSuite.h:160
int getCharacteristic()
Definition: cf_char.cc:51
CanonicalForm lc(const CanonicalForm &f)
CanonicalForm inverse(const CanonicalForm &f, bool symmetric=true) const
Definition: fac_util.cc:58
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:946
int level() const
Definition: factory.h:132
T & getItem() const
Definition: ftmpl_list.cc:431
#define A
Definition: sirandom.c:23
int * getLiftPrecisions(const CanonicalForm &F, int &sizeOfOutput, int degreeLC)
compute lifting precisions from the shape of the Newton polygon of F
Definition: facFqBivar.cc:1084
Variable getBeta() const
getter
bool hasFirstAlgVar(const CanonicalForm &f, Variable &a)
check if poly f contains an algebraic variable a
Definition: cf_ops.cc:665
static const int SW_RATIONAL
set to 1 for computations over Q
Definition: cf_defs.h:28
void On(int sw)
switches
CanonicalForm bCommonDen(const CanonicalForm &f)
CanonicalForm bCommonDen ( const CanonicalForm & f )
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:816
CFListIterator i
Definition: facFqBivar.cc:69
Variable beta
Definition: facAbsFact.cc:99
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:1148
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:37
int length() const
Definition: ftmpl_list.cc:273
int getLength() const
getter
Definition: DegreePattern.h:86
int gcd(int a, int b)
Definition: walkSupport.cc:839
bool isInExtension() const
getter
Variable x
Definition: cfModGcd.cc:4023
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:1214
int degree(const CanonicalForm &f)
CanonicalForm LC(const CanonicalForm &f)
CanonicalForm replacevar(const CanonicalForm &, const Variable &, const Variable &)
CanonicalForm replacevar ( const CanonicalForm & f, const Variable & x1, const Variable & x2 ) ...
Definition: cf_ops.cc:271
CanonicalForm getGamma() const
getter
int getp() const
Definition: fac_util.h:35
template CanonicalForm tmin(const CanonicalForm &, const CanonicalForm &)

§ henselLiftAndEarly() [2/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 1416 of file facFqBivar.cc.

1420 {
1421  modpk dummy= modpk();
1422  CanonicalForm den= 1;
1423  return henselLiftAndEarly (A, earlySuccess, earlyFactors, degs, liftBound,
1424  uniFactors, info, eval, dummy, den);
1425 }
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:1115
factory&#39;s main class
Definition: canonicalform.h:75
return modpk(p, k)
CanonicalForm den(const CanonicalForm &f)
class to do operations mod p^k for int&#39;s p and k
Definition: fac_util.h:22

§ 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 156 of file facFqBivar.cc.

157 {
158  Variable x= A.mvar();
159  if (A.inCoeffDomain())
160  return CFList();
161  ASSERT (A.isUnivariate(),
162  "univariate polynomial expected or constant expected");
163  CFFList factorsA;
164  if (GF)
165  {
166  int k= getGFDegree();
167  char cGFName= gf_name;
168  CanonicalForm mipo= gf_mipo;
170  Variable beta= rootOf (mipo.mapinto());
171  CanonicalForm buf= GF2FalphaRep (A, beta);
172  if (getCharacteristic() > 2)
173  {
174 #if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
175  nmod_poly_t FLINTmipo, leadingCoeff;
176  fq_nmod_ctx_t fq_con;
177  fq_nmod_poly_t FLINTA;
178  fq_nmod_poly_factor_t FLINTFactorsA;
179 
180  nmod_poly_init (FLINTmipo, getCharacteristic());
181  convertFacCF2nmod_poly_t (FLINTmipo, mipo.mapinto());
182 
183  fq_nmod_ctx_init_modulus (fq_con, FLINTmipo, "Z");
184 
185  convertFacCF2Fq_nmod_poly_t (FLINTA, buf, fq_con);
186  fq_nmod_poly_make_monic (FLINTA, FLINTA, fq_con);
187 
188  fq_nmod_poly_factor_init (FLINTFactorsA, fq_con);
189  nmod_poly_init (leadingCoeff, getCharacteristic());
190 
191  fq_nmod_poly_factor (FLINTFactorsA, leadingCoeff, FLINTA, fq_con);
192 
193  factorsA= convertFLINTFq_nmod_poly_factor2FacCFFList (FLINTFactorsA, x,
194  beta, fq_con);
195 
196  fq_nmod_poly_factor_clear (FLINTFactorsA, fq_con);
197  fq_nmod_poly_clear (FLINTA, fq_con);
198  nmod_poly_clear (FLINTmipo);
199  nmod_poly_clear (leadingCoeff);
200  fq_nmod_ctx_clear (fq_con);
201 #else
203  {
205  zz_p::init (getCharacteristic());
206  }
207  zz_pX NTLMipo= convertFacCF2NTLzzpX (mipo.mapinto());
208  zz_pE::init (NTLMipo);
209  zz_pEX NTLA= convertFacCF2NTLzz_pEX (buf, NTLMipo);
210  MakeMonic (NTLA);
211  vec_pair_zz_pEX_long NTLFactorsA= CanZass (NTLA);
212  zz_pE multi= to_zz_pE (1);
213  factorsA= convertNTLvec_pair_zzpEX_long2FacCFFList (NTLFactorsA, multi,
214  x, beta);
215 #endif
216  }
217  else
218  {
219  GF2X NTLMipo= convertFacCF2NTLGF2X (mipo.mapinto());
220  GF2E::init (NTLMipo);
221  GF2EX NTLA= convertFacCF2NTLGF2EX (buf, NTLMipo);
222  MakeMonic (NTLA);
223  vec_pair_GF2EX_long NTLFactorsA= CanZass (NTLA);
224  GF2E multi= to_GF2E (1);
225  factorsA= convertNTLvec_pair_GF2EX_long2FacCFFList (NTLFactorsA, multi,
226  x, beta);
227  }
228  setCharacteristic (getCharacteristic(), k, cGFName);
229  for (CFFListIterator i= factorsA; i.hasItem(); i++)
230  {
231  buf= i.getItem().factor();
232  buf= Falpha2GFRep (buf);
233  i.getItem()= CFFactor (buf, i.getItem().exp());
234  }
235  prune (beta);
236  }
237  else if (alpha.level() != 1)
238  {
239  if (getCharacteristic() > 2)
240  {
241 #if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
242  nmod_poly_t FLINTmipo, leadingCoeff;
243  fq_nmod_ctx_t fq_con;
244  fq_nmod_poly_t FLINTA;
245  fq_nmod_poly_factor_t FLINTFactorsA;
246 
247  nmod_poly_init (FLINTmipo, getCharacteristic());
248  convertFacCF2nmod_poly_t (FLINTmipo, getMipo (alpha));
249 
250  fq_nmod_ctx_init_modulus (fq_con, FLINTmipo, "Z");
251 
252  convertFacCF2Fq_nmod_poly_t (FLINTA, A, fq_con);
253  fq_nmod_poly_make_monic (FLINTA, FLINTA, fq_con);
254 
255  fq_nmod_poly_factor_init (FLINTFactorsA, fq_con);
256  nmod_poly_init (leadingCoeff, getCharacteristic());
257 
258  fq_nmod_poly_factor (FLINTFactorsA, leadingCoeff, FLINTA, fq_con);
259 
260  factorsA= convertFLINTFq_nmod_poly_factor2FacCFFList (FLINTFactorsA, x,
261  alpha, fq_con);
262 
263  fq_nmod_poly_factor_clear (FLINTFactorsA, fq_con);
264  fq_nmod_poly_clear (FLINTA, fq_con);
265  nmod_poly_clear (FLINTmipo);
266  nmod_poly_clear (leadingCoeff);
267  fq_nmod_ctx_clear (fq_con);
268 #else
270  {
272  zz_p::init (getCharacteristic());
273  }
274  zz_pX NTLMipo= convertFacCF2NTLzzpX (getMipo (alpha));
275  zz_pE::init (NTLMipo);
276  zz_pEX NTLA= convertFacCF2NTLzz_pEX (A, NTLMipo);
277  MakeMonic (NTLA);
278  vec_pair_zz_pEX_long NTLFactorsA= CanZass (NTLA);
279  zz_pE multi= to_zz_pE (1);
280  factorsA= convertNTLvec_pair_zzpEX_long2FacCFFList (NTLFactorsA, multi,
281  x, alpha);
282 #endif
283  }
284  else
285  {
286  GF2X NTLMipo= convertFacCF2NTLGF2X (getMipo (alpha));
287  GF2E::init (NTLMipo);
288  GF2EX NTLA= convertFacCF2NTLGF2EX (A, NTLMipo);
289  MakeMonic (NTLA);
290  vec_pair_GF2EX_long NTLFactorsA= CanZass (NTLA);
291  GF2E multi= to_GF2E (1);
292  factorsA= convertNTLvec_pair_GF2EX_long2FacCFFList (NTLFactorsA, multi,
293  x, alpha);
294  }
295  }
296  else
297  {
298 #ifdef HAVE_FLINT
299  if (degree (A) < 300)
300  {
301  nmod_poly_t FLINTA;
302  convertFacCF2nmod_poly_t (FLINTA, A);
303  nmod_poly_factor_t result;
304  nmod_poly_factor_init (result);
305  mp_limb_t leadingCoeff= nmod_poly_factor (result, FLINTA);
306  factorsA= convertFLINTnmod_poly_factor2FacCFFList (result, leadingCoeff, x);
307  if (factorsA.getFirst().factor().inCoeffDomain())
308  factorsA.removeFirst();
309  nmod_poly_factor_clear (result);
310  nmod_poly_clear (FLINTA);
311  }
312  else
313 #endif
314  if (getCharacteristic() > 2)
315  {
317  {
319  zz_p::init (getCharacteristic());
320  }
321  zz_pX NTLA= convertFacCF2NTLzzpX (A);
322  MakeMonic (NTLA);
323  vec_pair_zz_pX_long NTLFactorsA= CanZass (NTLA);
324  zz_p multi= to_zz_p (1);
325  factorsA= convertNTLvec_pair_zzpX_long2FacCFFList (NTLFactorsA, multi,
326  x);
327  }
328  else
329  {
330  GF2X NTLA= convertFacCF2NTLGF2X (A);
331  vec_pair_GF2X_long NTLFactorsA= CanZass (NTLA);
332  GF2 multi= to_GF2 (1);
333  factorsA= convertNTLvec_pair_GF2X_long2FacCFFList (NTLFactorsA, multi,
334  x);
335  }
336  }
337  CFList uniFactors;
338  for (CFFListIterator i= factorsA; i.hasItem(); i++)
339  uniFactors.append (i.getItem().factor());
340  return uniFactors;
341 }
GF2EX convertFacCF2NTLGF2EX(const CanonicalForm &f, const GF2X &mipo)
CanonicalForm in Z_2(a)[X] to NTL GF2EX.
Definition: NTLconvert.cc:1008
List< CanonicalForm > CFList
CanonicalForm Falpha2GFRep(const CanonicalForm &F)
change representation by residue classes modulo a Conway polynomial to representation by primitive el...
Definition: cf_map_ext.cc:170
nmod_poly_init(FLINTmipo, getCharacteristic())
CFFList convertNTLvec_pair_GF2EX_long2FacCFFList(const vec_pair_GF2EX_long &e, const GF2E &multi, const Variable &x, const Variable &alpha)
NAME: convertNTLvec_pair_GF2EX_long2FacCFFList.
Definition: NTLconvert.cc:956
CFFList convertNTLvec_pair_GF2X_long2FacCFFList(const vec_pair_GF2X_long &e, GF2, const Variable &x)
NAME: convertNTLvec_pair_GF2X_long2FacCFFList.
Definition: NTLconvert.cc:442
factory&#39;s class for variables
Definition: factory.h:115
GF2X convertFacCF2NTLGF2X(const CanonicalForm &f)
NAME: convertFacCF2NTLGF2X.
Definition: NTLconvert.cc:180
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
CanonicalForm gf_mipo(0)
CFFList convertNTLvec_pair_zzpX_long2FacCFFList(const vec_pair_zz_pX_long &e, const zz_p multi, const Variable &x)
Definition: NTLconvert.cc:395
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
factory&#39;s main class
Definition: canonicalform.h:75
char gf_name
Definition: gfops.cc:52
nmod_poly_clear(FLINTmipo)
fq_nmod_ctx_t fq_con
Definition: facHensel.cc:94
int k
Definition: cfEzgcd.cc:93
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
Definition: variable.cc:207
void setCharacteristic(int c)
Definition: cf_char.cc:23
int getCharacteristic()
Definition: cf_char.cc:51
void prune(Variable &alpha)
Definition: variable.cc:261
fq_nmod_ctx_clear(fq_con)
CanonicalForm mapinto() const
CFFList convertNTLvec_pair_zzpEX_long2FacCFFList(const vec_pair_zz_pEX_long &e, const zz_pE &multi, const Variable &x, const Variable &alpha)
Definition: NTLconvert.cc:867
Variable rootOf(const CanonicalForm &, char name='@')
returns a symbolic root of polynomial with name name Use it to define algebraic variables ...
Definition: variable.cc:162
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
convertFacCF2nmod_poly_t(FLINTmipo, M)
int status int void * buf
Definition: si_signals.h:59
int level() const
Definition: factory.h:132
zz_pEX convertFacCF2NTLzz_pEX(const CanonicalForm &f, const zz_pX &mipo)
Definition: NTLconvert.cc:1065
bool isUnivariate() const
T & getItem() const
Definition: ftmpl_list.cc:431
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
fq_nmod_poly_clear(prod, fq_con)
CFListIterator i
Definition: facFqBivar.cc:69
Variable beta
Definition: facAbsFact.cc:99
CanonicalForm GF2FalphaRep(const CanonicalForm &F, const Variable &alpha)
changes representation by primitive element to representation by residue classes modulo a Conway poly...
Definition: cf_map_ext.cc:162
zz_pX convertFacCF2NTLzzpX(const CanonicalForm &f)
Definition: NTLconvert.cc:103
Factor< CanonicalForm > CFFactor
int getGFDegree()
Definition: cf_char.cc:56
Variable x
Definition: cfModGcd.cc:4023
#define ASSERT(expression, message)
Definition: cf_assert.h:99
void append(const T &)
Definition: ftmpl_list.cc:256
long fac_NTL_char
Definition: NTLconvert.cc:44
int degree(const CanonicalForm &f)
return result
Definition: facAbsBiFact.cc:76
bool inCoeffDomain() const
fq_nmod_ctx_init_modulus(fq_con, FLINTmipo, "Z")