My Project
Loading...
Searching...
No Matches
Functions | Variables
facFqBivar.cc File Reference

This file provides functions for factorizing a bivariate polynomial over $ F_{p} $ , $ F_{p}(\alpha ) $ or GF, based on "Modern Computer Algebra, Chapter 15" by J. von zur Gathen & J. Gerhard and "Factoring multivariate polynomials over a finite field" by L. More...

#include "config.h"
#include "cf_assert.h"
#include "cf_util.h"
#include "debug.h"
#include "timing.h"
#include "canonicalform.h"
#include "cf_defs.h"
#include "cf_map_ext.h"
#include "cf_random.h"
#include "facHensel.h"
#include "facMul.h"
#include "cf_map.h"
#include "cf_irred.h"
#include "facFqBivarUtil.h"
#include "facFqBivar.h"
#include "cfNewtonPolygon.h"
#include "NTLconvert.h"
#include "FLINTconvert.h"
#include "flint/nmod_poly_factor.h"
#include "flint/fq_nmod_poly_factor.h"

Go to the source code of this file.

Functions

 TIMING_DEFINE_PRINT (fac_fq_uni_factorizer) TIMING_DEFINE_PRINT(fac_fq_bi_hensel_lift) TIMING_DEFINE_PRINT(fac_fq_bi_factor_recombination) TIMING_DEFINE_PRINT(fac_fq_bi_evaluation) TIMING_DEFINE_PRINT(fac_fq_bi_shift_to_zero) TIMING_DEFINE_PRINT(fac_fq_logarithmic) TIMING_DEFINE_PRINT(fac_fq_compute_lattice_lift) TIMING_DEFINE_PRINT(fac_fq_till_reduced) TIMING_DEFINE_PRINT(fac_fq_reconstruction) TIMING_DEFINE_PRINT(fac_fq_lift) TIMING_DEFINE_PRINT(fac_fq_uni_total) CanonicalForm prodMod0(const CFList &L
 
else if (L.length()==1) return mod(L.getFirst()(0
 
elsegetLast ()(0
 
 for (int j=1;j<=l;j++, i++) tmp1.append(i.getItem())
 
return mod (mulNTL(buf1, buf2, b), M)
 
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)) $.
 
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.
 
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 L Bernardin.
 
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 L Bernardin.
 
Variable chooseExtension (const Variable &alpha, const Variable &beta, int k)
 chooses a field extension.
 
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)
 
void earlyFactorDetection (CFList &reconstructedFactors, CanonicalForm &F, CFList &factors, int &adaptedLiftBound, int *&factorsFoundIndex, DegreePattern &degs, bool &success, int deg, const CanonicalForm &eval, const modpk &b)
 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.
 
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.
 
intgetCombinations (int *rightSide, int sizeOfRightSide, int &sizeOfOutput, int degreeLC)
 
intgetLiftPrecisions (const CanonicalForm &F, int &sizeOfOutput, int degreeLC)
 compute lifting precisions from the shape of the Newton polygon of F
 
void deleteFactors (CFList &factors, int *factorsFoundIndex)
 
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
 
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
 
long isReduced (const mat_zz_p &M)
 
long isReduced (const nmod_mat_t M)
 
long isReduced (const mat_zz_pE &M)
 
intextractZeroOneVecs (const mat_zz_p &M)
 
intextractZeroOneVecs (const nmod_mat_t M)
 
intextractZeroOneVecs (const mat_zz_pE &M)
 
void reconstructionTry (CFList &reconstructedFactors, CanonicalForm &F, const CFList &factors, const int liftBound, int &factorsFound, int *&factorsFoundIndex, mat_zz_pE &N, const CanonicalForm &eval, bool beenInThres)
 
void reconstructionTry (CFList &reconstructedFactors, CanonicalForm &F, const CFList &factors, const int liftBound, int &factorsFound, int *&factorsFoundIndex, mat_zz_p &N, const CanonicalForm &eval, bool beenInThres)
 
void reconstructionTry (CFList &reconstructedFactors, CanonicalForm &F, const CFList &factors, const int liftBound, int &factorsFound, int *&factorsFoundIndex, nmod_mat_t N, const CanonicalForm &eval, bool beenInThres)
 
CFList reconstruction (CanonicalForm &G, CFList &factors, int *zeroOneVecs, int precision, const mat_zz_pE &N, const CanonicalForm &eval)
 
CFList monicReconstruction (CanonicalForm &G, CFList &factors, int *zeroOneVecs, int precision, const mat_zz_pE &N)
 
CFList extReconstruction (CanonicalForm &G, CFList &factors, int *zeroOneVecs, int precision, const mat_zz_p &N, const ExtensionInfo &info, const CanonicalForm &evaluation)
 
CFList extReconstruction (CanonicalForm &G, CFList &factors, int *zeroOneVecs, int precision, const nmod_mat_t N, const ExtensionInfo &info, const CanonicalForm &evaluation)
 
CFList reconstruction (CanonicalForm &G, CFList &factors, int *zeroOneVecs, int precision, const mat_zz_p &N, const CanonicalForm &eval)
 
CFList reconstruction (CanonicalForm &G, CFList &factors, int *zeroOneVecs, int precision, const nmod_mat_t N, const CanonicalForm &eval)
 
void extReconstructionTry (CFList &reconstructedFactors, CanonicalForm &F, const CFList &factors, const int liftBound, int &factorsFound, int *&factorsFoundIndex, mat_zz_p &N, bool beenInThres, const ExtensionInfo &info, const CanonicalForm &evaluation)
 
void extReconstructionTry (CFList &reconstructedFactors, CanonicalForm &F, const CFList &factors, const int liftBound, int &factorsFound, int *&factorsFoundIndex, nmod_mat_t N, bool beenInThres, const ExtensionInfo &info, const CanonicalForm &evaluation)
 
int liftAndComputeLattice (const CanonicalForm &F, int *bounds, int sizeBounds, int start, int liftBound, int minBound, CFList &factors, mat_zz_p &NTLN, CFList &diophant, CFMatrix &M, CFArray &Pi, CFArray &bufQ, bool &irreducible)
 
int liftAndComputeLattice (const CanonicalForm &F, int *bounds, int sizeBounds, int start, int liftBound, int minBound, CFList &factors, nmod_mat_t FLINTN, CFList &diophant, CFMatrix &M, CFArray &Pi, CFArray &bufQ, bool &irreducible)
 
int extLiftAndComputeLattice (const CanonicalForm &F, int *bounds, int sizeBounds, int liftBound, int minBound, int start, CFList &factors, mat_zz_p &NTLN, CFList &diophant, CFMatrix &M, CFArray &Pi, CFArray &bufQ, bool &irreducible, const CanonicalForm &evaluation, const ExtensionInfo &info, CFList &source, CFList &dest)
 
int extLiftAndComputeLattice (const CanonicalForm &F, int *bounds, int sizeBounds, int liftBound, int minBound, int start, CFList &factors, nmod_mat_t FLINTN, CFList &diophant, CFMatrix &M, CFArray &Pi, CFArray &bufQ, bool &irreducible, const CanonicalForm &evaluation, const ExtensionInfo &info, CFList &source, CFList &dest)
 
int liftAndComputeLattice (const CanonicalForm &F, int *bounds, int sizeBounds, int start, int liftBound, int minBound, CFList &factors, mat_zz_pE &NTLN, CFList &diophant, CFMatrix &M, CFArray &Pi, CFArray &bufQ, bool &irreducible)
 
int liftAndComputeLatticeFq2Fp (const CanonicalForm &F, int *bounds, int sizeBounds, int start, int liftBound, int minBound, CFList &factors, nmod_mat_t FLINTN, CFList &diophant, CFMatrix &M, CFArray &Pi, CFArray &bufQ, bool &irreducible, const Variable &alpha)
 
CFList increasePrecision (CanonicalForm &F, CFList &factors, int factorsFound, int oldNumCols, int oldL, int precision, const CanonicalForm &eval)
 
CFList increasePrecision (CanonicalForm &F, CFList &factors, int factorsFound, int oldNumCols, int oldL, const Variable &, int precision, const CanonicalForm &eval)
 
CFList extIncreasePrecision (CanonicalForm &F, CFList &factors, int factorsFound, int oldNumCols, int oldL, const CanonicalForm &evaluation, const ExtensionInfo &info, CFList &source, CFList &dest, int precision)
 
CFList increasePrecision2 (const CanonicalForm &F, CFList &factors, const Variable &alpha, int precision)
 
CFList increasePrecisionFq2Fp (CanonicalForm &F, CFList &factors, int factorsFound, int oldNumCols, int oldL, const Variable &alpha, int precision, const CanonicalForm &eval)
 
CFList increasePrecision (CanonicalForm &F, CFList &factors, int oldL, int l, int d, int *bounds, CFArray &bufQ, nmod_mat_t FLINTN, const CanonicalForm &eval)
 
CFList increasePrecision (CanonicalForm &F, CFList &factors, int oldL, int l, int d, int *bounds, CFArray &bufQ, mat_zz_pE &NTLN, const CanonicalForm &eval)
 
CFList extIncreasePrecision (CanonicalForm &F, CFList &factors, int oldL, int l, int d, int *bounds, CFArray &bufQ, nmod_mat_t FLINTN, const CanonicalForm &evaluation, const ExtensionInfo &info, CFList &source, CFList &dest)
 
CFList increasePrecisionFq2Fp (CanonicalForm &F, CFList &factors, int oldL, int l, int d, int *bounds, CFArray &bufQ, nmod_mat_t FLINTN, const Variable &alpha, const CanonicalForm &eval)
 
CFList furtherLiftingAndIncreasePrecision (CanonicalForm &F, CFList &factors, int l, int liftBound, int d, int *bounds, nmod_mat_t FLINTN, CFList &diophant, CFMatrix &M, CFArray &Pi, CFArray &bufQ, const CanonicalForm &eval)
 
CFList furtherLiftingAndIncreasePrecision (CanonicalForm &F, CFList &factors, int l, int liftBound, int d, int *bounds, mat_zz_pE &NTLN, CFList &diophant, CFMatrix &M, CFArray &Pi, CFArray &bufQ, const CanonicalForm &eval)
 
CFList extFurtherLiftingAndIncreasePrecision (CanonicalForm &F, CFList &factors, int l, int liftBound, int d, int *bounds, nmod_mat_t FLINTN, CFList &diophant, CFMatrix &M, CFArray &Pi, CFArray &bufQ, const CanonicalForm &evaluation, const ExtensionInfo &info, CFList &source, CFList &dest)
 
CFList furtherLiftingAndIncreasePrecisionFq2Fp (CanonicalForm &F, CFList &factors, int l, int liftBound, int d, int *bounds, nmod_mat_t FLINTN, CFList &diophant, CFMatrix &M, CFArray &Pi, CFArray &bufQ, const Variable &alpha, const CanonicalForm &eval)
 
void refineAndRestartLift (const CanonicalForm &F, const nmod_mat_t FLINTN, int liftBound, int l, CFList &factors, CFMatrix &M, CFArray &Pi, CFList &diophant)
 
void refineAndRestartLift (const CanonicalForm &F, const mat_zz_pE &NTLN, int liftBound, int l, CFList &factors, CFMatrix &M, CFArray &Pi, CFList &diophant)
 
CFList earlyReconstructionAndLifting (const CanonicalForm &F, const nmod_mat_t N, CanonicalForm &bufF, CFList &factors, int &l, int &factorsFound, bool beenInThres, CFMatrix &M, CFArray &Pi, CFList &diophant, bool symmetric, const CanonicalForm &evaluation)
 
CFList earlyReconstructionAndLifting (const CanonicalForm &F, const mat_zz_pE &N, CanonicalForm &bufF, CFList &factors, int &l, int &factorsFound, bool beenInThres, CFMatrix &M, CFArray &Pi, CFList &diophant, bool symmetric, const CanonicalForm &evaluation)
 
CFList extEarlyReconstructionAndLifting (const CanonicalForm &F, const nmod_mat_t N, CanonicalForm &bufF, CFList &factors, int &l, int &factorsFound, bool beenInThres, CFMatrix &M, CFArray &Pi, CFList &diophant, const ExtensionInfo &info, const CanonicalForm &evaluation)
 
CFList sieveSmallFactors (const CanonicalForm &G, CFList &uniFactors, DegreePattern &degPat, CanonicalForm &H, CFList &diophant, CFArray &Pi, CFMatrix &M, bool &success, int d, const CanonicalForm &eval)
 
CFList extSieveSmallFactors (const CanonicalForm &G, CFList &uniFactors, DegreePattern &degPat, CanonicalForm &H, CFList &diophant, CFArray &Pi, CFMatrix &M, bool &success, int d, const CanonicalForm &evaluation, const ExtensionInfo &info)
 
CFList henselLiftAndLatticeRecombi (const CanonicalForm &G, const CFList &uniFactors, const Variable &alpha, const DegreePattern &degPat, bool symmetric, const CanonicalForm &eval)
 
ExtensionInfo init4ext (const ExtensionInfo &info, const CanonicalForm &evaluation, int &degMipo)
 
CFList extHenselLiftAndLatticeRecombi (const CanonicalForm &G, const CFList &uniFactors, const ExtensionInfo &extInfo, const DegreePattern &degPat, const CanonicalForm &eval)
 
CFList extBiFactorize (const CanonicalForm &F, const ExtensionInfo &info)
 Factorization over an extension of initial field.
 
CFList biFactorize (const CanonicalForm &F, const ExtensionInfo &info)
 bivariate factorization over finite fields as decribed in "Factoring multivariate polynomials over a finite field" by L Bernardin.
 

Variables

const CanonicalFormM
 
const CanonicalForm const modpkb
 
 else
 
CFListIterator i = L
 
CFList tmp1
 
CFList tmp2 = Difference (L, tmp1)
 
CanonicalForm buf1 = prodMod0 (tmp1, M, b)
 
CanonicalForm buf2 = prodMod0 (tmp2, M, b)
 

Detailed Description

This file provides functions for factorizing a bivariate polynomial over $ F_{p} $ , $ F_{p}(\alpha ) $ or GF, based on "Modern Computer Algebra, Chapter 15" by J. von zur Gathen & J. Gerhard and "Factoring multivariate polynomials over a finite field" by L.

Bernardin. Factor Recombination is described in "Factoring polynomials over global fields" by K. Belabas, M. van Hoeij, J. Klueners, A. Steel

Author
Martin Lee

Definition in file facFqBivar.cc.

Function Documentation

◆ biFactorize()

CFList biFactorize ( const CanonicalForm F,
const ExtensionInfo info 
)

bivariate factorization over finite fields as decribed in "Factoring multivariate polynomials over a finite field" by L Bernardin.

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

8306{
8307 if (F.inCoeffDomain())
8308 return CFList(F);
8309
8310 CanonicalForm A= F;
8312
8313 Variable alpha= info.getAlpha();
8314 Variable beta= info.getBeta();
8315 CanonicalForm gamma= info.getGamma();
8316 CanonicalForm delta= info.getDelta();
8317 int k= info.getGFDegree();
8318 bool extension= info.isInExtension();
8319 if (A.isUnivariate())
8320 {
8321 if (extension == false)
8322 return uniFactorizer (F, alpha, GF);
8323 else
8324 {
8325 CFList source, dest;
8326 A= mapDown (A, info, source, dest);
8327 return uniFactorizer (A, beta, GF);
8328 }
8329 }
8330
8331 CFMap N;
8332 A= compress (A, N);
8333 Variable y= A.mvar();
8334
8335 if (y.level() > 2) return CFList (F);
8336 Variable x= Variable (1);
8337
8338 //remove and factorize content
8341
8344
8345 if (!extension)
8346 {
8349 }
8350
8351 //trivial case
8353 if (A.inCoeffDomain())
8354 {
8357 decompress (factors, N);
8358 return factors;
8359 }
8360 else if (A.isUnivariate())
8361 {
8365 decompress (factors, N);
8366 return factors;
8367 }
8368
8369
8370 //check trivial case
8371 if (degree (A) == 1 || degree (A, 1) == 1 ||
8372 (size (A) == 2 && igcd (degree (A), degree (A,1))==1))
8373 {
8374 factors.append (A);
8375
8377 false, false, N);
8378
8379 if (!extension)
8381 return factors;
8382 }
8383
8384 // check derivatives
8385 bool derivXZero= false;
8388 if (derivX.isZero())
8389 derivXZero= true;
8390 else
8391 {
8392 gcdDerivX= gcd (A, derivX);
8393 if (degree (gcdDerivX) > 0)
8394 {
8401 if (!extension)
8403 return factorsG;
8404 }
8405 }
8406 bool derivYZero= false;
8409 if (derivY.isZero())
8410 derivYZero= true;
8411 else
8412 {
8413 gcdDerivY= gcd (A, derivY);
8414 if (degree (gcdDerivY) > 0)
8415 {
8422 if (!extension)
8424 return factorsG;
8425 }
8426 }
8427 //main variable is chosen s.t. the degree in x is minimal
8428 bool swap= false;
8429 if ((degree (A) > degree (A, x)) || derivXZero)
8430 {
8431 if (!derivYZero)
8432 {
8433 A= swapvar (A, y, x);
8437 swap= true;
8438 }
8439 }
8440
8441 int boundsLength;
8442 bool isIrreducible= false;
8444 if (isIrreducible)
8445 {
8446 delete [] bounds;
8447 factors.append (A);
8448
8450 swap, false, N);
8451
8452 if (!extension)
8454 return factors;
8455 }
8456
8457 int minBound= bounds[0];
8458 for (int i= 1; i < boundsLength; i++)
8459 {
8460 if (bounds[i] != 0)
8462 }
8463
8464 int boundsLength2;
8466 int minBound2= bounds2[0];
8467 for (int i= 1; i < boundsLength2; i++)
8468 {
8469 if (bounds2[i] != 0)
8471 }
8472
8473
8474 bool fail= false;
8479
8480 bool fail2= false;
8485 bool swap2= false;
8486
8487 // several univariate factorizations to obtain more information about the
8488 // degree pattern therefore usually less combinations have to be tried during
8489 // the recombination process
8490 int factorNums= 3;
8491 int subCheck1= substituteCheck (A, x);
8492 int subCheck2= substituteCheck (A, y);
8493 bool symmetric= false;
8494
8496 for (int i= 0; i < factorNums; i++)
8497 {
8498 bufAeval= A;
8501 TIMING_END_AND_PRINT (fac_fq_bi_evaluation, "time to find eval point: ");
8502 if (!derivXZero && !fail2 && !symmetric)
8503 {
8504 if (i == 0)
8505 {
8506 buf= swapvar (A, x, y);
8507 symmetric= (A/Lc (A) == buf/Lc (buf));
8508 }
8509 bufAeval2= buf;
8513 "time to find eval point wrt y: ");
8514 }
8515 // first try to change main variable if there is no valid evaluation point
8516 if (fail && (i == 0))
8517 {
8518 if (!derivXZero && !fail2 && !symmetric)
8519 {
8521 int dummy= subCheck2;
8524 tmp= A;
8525 A= buf;
8526 buf= tmp;
8528 swap2= true;
8529 fail= false;
8530 }
8531 else
8532 fail= true;
8533 }
8534
8535 // if there is no valid evaluation point pass to a field extension
8536 if (fail && (i == 0))
8537 {
8540 swap, swap2, N);
8542 delete [] bounds;
8543 delete [] bounds2;
8544 return factors;
8545 }
8546
8547 // there is at least one valid evaluation point
8548 // but we do not compute more univariate factorization over an extension
8549 if (fail && (i != 0))
8550 break;
8551
8552 // univariate factorization
8556 "time for univariate factorization over Fq: ");
8557 DEBOUTLN (cerr, "Lc (bufAeval)*prod (bufUniFactors)== bufAeval " <<
8559
8560 if (!derivXZero && !fail2 && !symmetric)
8561 {
8565 "time for univariate factorization in y over Fq: ");
8566 DEBOUTLN (cerr, "Lc (bufAeval2)*prod (bufUniFactors2)== bufAeval2 " <<
8568 }
8569
8570 if (bufUniFactors.length() == 1 ||
8571 (!fail2 && !derivXZero && !symmetric && (bufUniFactors2.length() == 1)))
8572 {
8573 if (extension)
8574 {
8575 CFList source, dest;
8576 appendMapDown (factors, A, info, source, dest);
8577 }
8578 else
8579 factors.append (A);
8580
8582 swap, swap2, N);
8583
8584 if (!extension)
8586 delete [] bounds;
8587 delete [] bounds2;
8588 return factors;
8589 }
8590
8591 if (i == 0 && !extension)
8592 {
8593 if (subCheck1 > 0)
8594 {
8596
8597 if (subCheck > 1 && (subCheck1%subCheck == 0))
8598 {
8600 subst (bufA, bufA, subCheck, x);
8604 swap, swap2, N);
8605 if (!extension)
8607 delete [] bounds;
8608 delete [] bounds2;
8609 return factors;
8610 }
8611 }
8612
8613 if (!derivXZero && !fail2 && !symmetric && subCheck2 > 0)
8614 {
8616
8617 if (subCheck > 1 && (subCheck2%subCheck == 0))
8618 {
8620 subst (bufA, bufA, subCheck, y);
8624 swap, swap2, N);
8625 if (!extension)
8627 delete [] bounds;
8628 delete [] bounds2;
8629 return factors;
8630 }
8631 }
8632 }
8633
8634 // degree analysis
8636 if (!derivXZero && !fail2 && !symmetric)
8638
8639 if (i == 0)
8640 {
8641 Aeval= bufAeval;
8644 degs= bufDegs;
8645 if (!derivXZero && !fail2 && !symmetric)
8646 {
8650 degs2= bufDegs2;
8651 }
8652 }
8653 else
8654 {
8655 degs.intersect (bufDegs);
8656 if (!derivXZero && !fail2 && !symmetric)
8657 {
8658 degs2.intersect (bufDegs2);
8660 {
8664 }
8665 }
8667 {
8669 Aeval= bufAeval;
8671 }
8672 }
8673 list.append (bufEvaluation);
8674 if (!derivXZero && !fail2 && !symmetric)
8676 }
8678 "total time for univariate factorizations: ");
8679
8680 if (!derivXZero && !fail2 && !symmetric)
8681 {
8684 && degs.getLength() > degs2.getLength() && minBound2 <= minBound))
8685 {
8686 degs= degs2;
8689 Aeval= Aeval2;
8690 A= buf;
8691 swap2= true;
8692 }
8693 }
8694
8695 if (degs.getLength() == 1) // A is irreducible
8696 {
8697 if (extension)
8698 {
8699 CFList source, dest;
8700 appendMapDown (factors, A, info, source, dest);
8701 }
8702 else
8703 factors.append (A);
8705 swap, swap2, N);
8706 if (!extension)
8708 delete [] bounds;
8709 delete [] bounds2;
8710 return factors;
8711 }
8712
8713 int liftBound= degree (A, y) + 1;
8714
8715 if (swap2)
8716 {
8717 delete [] bounds;
8718 bounds= bounds2;
8720 }
8721
8723 A= A (y + evaluation, y);
8725 "time to shift eval to zero: ");
8726
8727 int degMipo= 1;
8728 if (extension && alpha.level() != 1 && k==1)
8730
8731 DEBOUTLN (cerr, "uniFactors= " << uniFactors);
8732
8733 if ((GF && !extension) || (GF && extension && k != 1))
8734 {
8735 bool earlySuccess= false;
8742 "time for bivariate hensel lifting over Fq: ");
8743 DEBOUTLN (cerr, "lifted factors= " << uniFactors);
8744
8746
8748 if (extension)
8750 evaluation, 1, uniFactors.length()/2);
8751 else
8753 uniFactors.length()/2);
8755 "time for naive bivariate factor recombi over Fq: ");
8756
8757 if (earlySuccess)
8759 else if (!earlySuccess && degs.getLength() == 1)
8761 }
8762 else if (degree (A) > 4 && beta.level() == 1 && (2*minBound)/degMipo < 32)
8763 {
8765 if (extension)
8766 {
8769 );
8771 }
8772 else if (alpha.level() == 1 && !GF)
8773 {
8777 }
8778 else if (!extension && (alpha != x || GF))
8779 {
8783 }
8785 "time to bivar lift and LLL recombi over Fq: ");
8786 DEBOUTLN (cerr, "lifted factors= " << uniFactors);
8787 }
8788 else
8789 {
8790 bool earlySuccess= false;
8797 "time for bivar hensel lifting over Fq: ");
8798 DEBOUTLN (cerr, "lifted factors= " << uniFactors);
8799
8801 if (!extension)
8802 {
8806 "time for small subset naive recombi over Fq: ");
8807
8809 if (degree (A) > 0)
8810 {
8811 CFList tmp;
8813 if (alpha.level() == 1)
8816 );
8817 else
8818 {
8819 if (degree (A) > getCharacteristic())
8822 );
8823 else
8826 );
8827 }
8829 "time to increase precision: ");
8831 if (tmp.length() == 0 || (tmp.length() > 0 && uniFactors.length() != 0
8833 )
8834 {
8836 degs.intersect (bufDegs);
8837 degs.refine ();
8839 degs, evaluation, 4,
8840 uniFactors.length()/2
8841 )
8842 );
8843 }
8844 }
8845 }
8846 else
8847 {
8848 if (beta.level() != 1 || k > 1)
8849 {
8850 if (k > 1)
8851 {
8854 );
8855 }
8856 else
8857 {
8859 evaluation, 1, 3
8860 );
8861 if (degree (A) > 0)
8862 {
8865 degs.intersect (bufDegs);
8866 degs.refine ();
8869 1, tmp.length()/2
8870 )
8871 );
8872 }
8873 }
8874 }
8875 else
8876 {
8878 evaluation, 1, 3
8879 );
8881 if (degree (A) > 0)
8882 {
8883 int degMipo;
8885
8886 CFList source, dest;
8889 info2, source, dest, liftBound
8890 );
8892 if (tmp.length() == 0 || (tmp.length() > 0 && uniFactors.length() != 0
8894 )
8895 {
8897 degs.intersect (bufDegs);
8898 degs.refine ();
8901 4, uniFactors.length()/2
8902 )
8903 );
8904 }
8905 }
8906 }
8907 }
8908
8909 if (earlySuccess)
8911 else if (!earlySuccess && degs.getLength() == 1)
8913 }
8914
8915 if (!swap2)
8916 delete [] bounds2;
8917 delete [] bounds;
8918
8920 swap, swap2, N);
8921 if (!extension)
8923
8924 return factors;
8925}
#define swap(_i, _j)
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
CanonicalForm FACTORY_PUBLIC content(const CanonicalForm &)
CanonicalForm content ( const CanonicalForm & f )
Definition cf_gcd.cc:603
int size(const CanonicalForm &f, const Variable &v)
int size ( const CanonicalForm & f, const Variable & v )
Definition cf_ops.cc:600
int degree(const CanonicalForm &f)
CanonicalForm deriv(const CanonicalForm &f, const Variable &x)
CanonicalForm FACTORY_PUBLIC swapvar(const CanonicalForm &, const Variable &, const Variable &)
swapvar() - swap variables x1 and x2 in f.
Definition cf_ops.cc:168
CanonicalForm Lc(const CanonicalForm &f)
List< CanonicalForm > CFList
int FACTORY_PUBLIC getCharacteristic()
Definition cf_char.cc:70
const CanonicalForm CFMap CFMap & N
Definition cfEzgcd.cc:56
int k
Definition cfEzgcd.cc:99
Variable x
Definition cfModGcd.cc:4082
g
Definition cfModGcd.cc:4090
CanonicalForm decompress(const CanonicalForm &F, const mpz_t *inverseM, const mpz_t *A)
decompress a bivariate poly
#define GaloisFieldDomain
Definition cf_defs.h:18
CanonicalForm compress(const CanonicalForm &f, CFMap &m)
CanonicalForm compress ( const CanonicalForm & f, CFMap & m )
Definition cf_map.cc:210
static CanonicalForm mapDown(const CanonicalForm &F, const Variable &alpha, const CanonicalForm &G, CFList &source, CFList &dest)
the CanonicalForm G is the output of map_up, returns F considered as an element over ,...
int igcd(int a, int b)
Definition cf_util.cc:56
static int gettype()
Definition cf_factory.h:28
class CFMap
Definition cf_map.h:85
factory's main class
bool inCoeffDomain() const
int level() const
level() returns the level of CO.
DegreePattern provides a functionality to create, intersect and refine degree patterns.
ExtensionInfo contains information about extension.
int length() const
void append(const T &)
factory's class for variables
Definition factory.h:127
int level() const
Definition factory.h:143
#define DEBOUTLN(stream, objects)
Definition debug.h:49
Variable alpha
const CanonicalForm int const CFList & evaluation
Definition facAbsFact.cc:52
const CanonicalForm int const CFList const Variable & y
Definition facAbsFact.cc:53
Variable beta
Definition facAbsFact.cc:95
CFFList append(const CFFList &Inputlist, const CFFactor &TheFactor)
CanonicalForm subst(const CanonicalForm &f, const CFList &a, const CFList &b, const CanonicalForm &Rstar, bool isFunctionField)
CFList *& Aeval
<[in] poly
int * computeBounds(const CanonicalForm &F, int &n, bool &isIrreducible)
compute bounds for logarithmic derivative as described in K. Belabas, M. van Hoeij,...
void appendSwapDecompress(CFList &factors1, const CFList &factors2, const CFList &factors3, const bool swap1, const bool swap2, const CFMap &N)
first swap Variables in factors1 if necessary, then append factors2 and factors3 on factors1 and fina...
void appendMapDown(CFList &factors, const CanonicalForm &g, const ExtensionInfo &info, CFList &source, CFList &dest)
map g down into a subfield of the current field and append it to factors
CanonicalForm reverseSubst(const CanonicalForm &F, const int d, const Variable &x)
reverse a substitution x^d->x
int substituteCheck(const CanonicalForm &F, const Variable &x)
check if a substitution x^n->x is possible
int * computeBoundsWrtDiffMainvar(const CanonicalForm &F, int &n, bool &isIrreducible)
as above just wrt to the other variable
CFList biFactorize(const CanonicalForm &F, const ExtensionInfo &info)
bivariate factorization over finite fields as decribed in "Factoring multivariate polynomials over a ...
CFList increasePrecision(CanonicalForm &F, CFList &factors, int factorsFound, int oldNumCols, int oldL, int precision, const CanonicalForm &eval)
CFList extHenselLiftAndLatticeRecombi(const CanonicalForm &G, const CFList &uniFactors, const ExtensionInfo &extInfo, const DegreePattern &degPat, const CanonicalForm &eval)
CFList extBiFactorize(const CanonicalForm &F, const ExtensionInfo &info)
Factorization over an extension of initial field.
CFList increasePrecisionFq2Fp(CanonicalForm &F, CFList &factors, int factorsFound, int oldNumCols, int oldL, const Variable &alpha, int precision, const CanonicalForm &eval)
CFList extIncreasePrecision(CanonicalForm &F, CFList &factors, int factorsFound, int oldNumCols, int oldL, const CanonicalForm &evaluation, const ExtensionInfo &info, CFList &source, CFList &dest, int precision)
CFList henselLiftAndLatticeRecombi(const CanonicalForm &G, const CFList &uniFactors, const Variable &alpha, const DegreePattern &degPat, bool symmetric, const CanonicalForm &eval)
CFListIterator i
Definition facFqBivar.cc:73
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...
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:86
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
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 ...
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...
ExtensionInfo init4ext(const ExtensionInfo &info, const CanonicalForm &evaluation, int &degMipo)
CFList increasePrecision2(const CanonicalForm &F, CFList &factors, const Variable &alpha, int precision)
fq_nmod_poly_t prod
Definition facHensel.cc:100
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
Definition variable.cc:207
template CanonicalForm tmin(const CanonicalForm &, const CanonicalForm &)
template List< Variable > Union(const List< Variable > &, const List< Variable > &)
bool isIrreducible(const CanonicalForm &f)
bool isIrreducible ( const CanonicalForm & f )
#define info
Definition libparse.cc:1256
bool delta(X x, Y y, D d)
Definition TestSuite.h:160
int status int void * buf
Definition si_signals.h:59
#define A
Definition sirandom.c:24
static poly normalize(poly next_p, ideal add_generators, syStrategy syzstr, int *g_l, int *p_l, int crit_comp)
Definition syz3.cc:1027
#define TIMING_START(t)
Definition timing.h:92
#define TIMING_END_AND_PRINT(t, msg)
Definition timing.h:94
int gcd(int a, int b)

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

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

◆ deleteFactors()

void deleteFactors ( CFList factors,
int factorsFoundIndex 
)

Definition at line 1138 of file facFqBivar.cc.

1139{
1140 CFList result;
1141 int i= 0;
1142 for (CFListIterator iter= factors; iter.hasItem(); iter++, i++)
1143 {
1144 if (factorsFoundIndex[i] == 1)
1145 continue;
1146 else
1147 result.append (iter.getItem());
1148 }
1149 factors= result;
1150}
void append(const T &)
CFFListIterator iter
return result

◆ earlyFactorDetection() [1/2]

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

977{
980 factorsFoundIndex, degs, success, deg, eval, b, den);
981}
CanonicalForm den(const CanonicalForm &f)
CFList & eval
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)
const CanonicalForm const modpk & b
Definition facFqBivar.cc:63

◆ earlyFactorDetection() [2/2]

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 at line 854 of file facFqBivar.cc.

858{
863 Variable x= Variable (1);
864 Variable y= Variable (2);
866 CanonicalForm M= power (F.mvar(), deg);
868 int d= degree (F), l= 0;
869 bool isRat= (isOn (SW_RATIONAL) && getCharacteristic() == 0) ||
870 getCharacteristic() > 0;
871 if (!isRat)
872 On (SW_RATIONAL);
873 if (b.getp() != 0)
874 buf *= bCommonDen (buf);
878 if (!isRat)
882
883 for (CFListIterator i= factors; i.hasItem(); i++, l++)
884 {
885 if (!bufDegs1.find (degree (i.getItem(), 1)) || factorsFoundIndex[l] == 1)
886 continue;
887 else
888 {
889 test1= mod (mulNTL (i.getItem() (1,x), LCBuf, b), M);
890 if (uniFdivides (test1, buf1))
891 {
892 test0= mod (mulNTL (i.getItem() (0,x), LCBuf, b), M);
893 if (uniFdivides (test0, buf0))
894 {
895 if (!isRat)
896 On (SW_RATIONAL);
897 g= mulMod2 (i.getItem(), LCBuf, M);
898 if (!isRat)
899 {
900 g *= bCommonDen(g);
902 }
903 if (b.getp() != 0)
904 g= b(g);
905 if (!isRat)
906 On (SW_RATIONAL);
907 g /= content (g, x);
908 if (!isRat)
909 {
910 On (SW_RATIONAL);
911 if (!Lc (g).inBaseDomain())
912 g /= Lc (g);
913 g *= bCommonDen (g);
915 g /= icontent (g);
916 On (SW_RATIONAL);
917 }
918 if (fdivides (g, buf, quot))
919 {
920 den *= abs (lc (g));
923 if (b.getp() != 0)
924 {
928 den /= gcd (den, denQuot);
929 On (SW_RATIONAL);
930 }
931 else
932 buf= quot;
933 d -= degree (g);
934 LCBuf= LC (buf, x)*den;
935 buf0= mulNTL (buf (0,x), LCBuf);
936 buf1= mulNTL (buf (1,x), LCBuf);
937 if (!isRat)
939 T= Difference (T, CFList (i.getItem()));
940 F= buf;
941
942 // compute new possible degree pattern
944 bufDegs1.intersect (bufDegs2);
945 bufDegs1.refine ();
946 if (bufDegs1.getLength() <= 1)
947 {
948 if (!buf.inCoeffDomain())
949 {
951 F= 1;
952 }
953 break;
954 }
955 }
956 if (!isRat)
958 }
959 }
960 }
961 }
962 adaptedLiftBound= d + 1;
963 if (adaptedLiftBound < deg)
964 {
965 degs= bufDegs1;
966 success= true;
967 }
968 if (bufDegs1.getLength() <= 1)
969 degs= bufDegs1;
970}
Rational abs(const Rational &a)
Definition GMPrat.cc:436
bool isOn(int sw)
switches
void On(int sw)
switches
void Off(int sw)
switches
CanonicalForm lc(const CanonicalForm &f)
CanonicalForm FACTORY_PUBLIC icontent(const CanonicalForm &f)
CanonicalForm icontent ( const CanonicalForm & f )
Definition cf_gcd.cc:74
CanonicalForm LC(const CanonicalForm &f)
int l
Definition cfEzgcd.cc:100
CanonicalForm bCommonDen(const CanonicalForm &f)
CanonicalForm bCommonDen ( const CanonicalForm & f )
bool fdivides(const CanonicalForm &f, const CanonicalForm &g)
bool fdivides ( const CanonicalForm & f, const CanonicalForm & g )
static const int SW_RATIONAL
set to 1 for computations over Q
Definition cf_defs.h:31
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
T & getItem() const
return mod(mulNTL(buf1, buf2, b), M)
const CanonicalForm & M
Definition facFqBivar.cc:62
CanonicalForm buf1
Definition facFqBivar.cc:75
CanonicalForm mulNTL(const CanonicalForm &F, const CanonicalForm &G, const modpk &b)
multiplication of univariate polys using FLINT/NTL over F_p, F_q, Z/p^k, Z/p^k[t]/(f),...
Definition facMul.cc:415
bool uniFdivides(const CanonicalForm &A, const CanonicalForm &B)
divisibility test for univariate polys
Definition facMul.cc:3763
CanonicalForm mulMod2(const CanonicalForm &A, const CanonicalForm &B, const CanonicalForm &M)
Karatsuba style modular multiplication for bivariate polynomials.
Definition facMul.cc:2990
template List< Variable > Difference(const List< Variable > &, const List< Variable > &)
STATIC_VAR jList * T
Definition janet.cc:30

◆ earlyReconstructionAndLifting() [1/2]

CFList earlyReconstructionAndLifting ( const CanonicalForm F,
const mat_zz_pE N,
CanonicalForm bufF,
CFList factors,
int l,
int factorsFound,
bool  beenInThres,
CFMatrix M,
CFArray Pi,
CFList diophant,
bool  symmetric,
const CanonicalForm evaluation 
)

Definition at line 6421 of file facFqBivar.cc.

6427{
6428 int sizeOfLiftPre;
6429 int * liftPre= getLiftPrecisions (F, sizeOfLiftPre, degree (LC (F, 1), 2));
6430 Variable y= F.mvar();
6431 factorsFound= 0;
6432 CanonicalForm LCF= LC (F, 1);
6433 CFList result;
6434 int smallFactorDeg= 11;
6435 mat_zz_pE NTLN= N;
6436 int * factorsFoundIndex= new int [NTLN.NumCols()];
6437 for (long i= 0; i < NTLN.NumCols(); i++)
6438 factorsFoundIndex [i]= 0;
6439
6440 if (degree (F) + 1 > smallFactorDeg)
6441 {
6442 if (l < smallFactorDeg)
6443 {
6445 factors.insert (LCF);
6447 TIMING_END_AND_PRINT (fac_fq_lift, "time to lift in reconstruction0: ");
6449 }
6453 );
6454 TIMING_END_AND_PRINT (fac_fq_reconstruction, "time to reconstruct0: ");
6455 if (result.length() == NTLN.NumCols())
6456 {
6457 delete [] liftPre;
6458 delete [] factorsFoundIndex;
6459 return result;
6460 }
6461 }
6462
6463 int i= sizeOfLiftPre - 1;
6464 int dummy= 1;
6465 if (sizeOfLiftPre > 1 && sizeOfLiftPre < 30)
6466 {
6467 while (i > 0)
6468 {
6469 if (l < liftPre[i-1] + 1)
6470 {
6471 factors.insert (LCF);
6473 henselLiftResume12 (F, factors, l, liftPre[i-1] + 1, Pi, diophant, M);
6474 TIMING_END_AND_PRINT (fac_fq_lift, "time to lift in reconstruction1: ");
6475 l= liftPre[i-1] + 1;
6476 }
6477 else
6478 {
6479 i--;
6480 if (i != 0)
6481 continue;
6482 }
6486 );
6487 TIMING_END_AND_PRINT (fac_fq_reconstruction, "time to reconstruct1: ");
6488 if (result.length() == NTLN.NumCols())
6489 {
6490 delete [] liftPre;
6491 delete [] factorsFoundIndex;
6492 return result;
6493 }
6494 i--;
6495 }
6496 }
6497 else
6498 {
6499 i= 1;
6500 while ((degree (F,y)/4+1)*i + 4 <= smallFactorDeg)
6501 i++;
6502 while (i < 5)
6503 {
6504 dummy= tmin (degree (F,y)+1, (degree (F,y)/4+1)*i+4);
6505 if (l < dummy)
6506 {
6507 factors.insert (LCF);
6510 TIMING_END_AND_PRINT (fac_fq_lift, "time to lift in reconstruction2: ");
6511 l= dummy;
6512 if (i == 1 && degree (F)%4==0 && symmetric && factors.length() == 2 &&
6513 LC (F,1).inCoeffDomain() &&
6514 (degree (factors.getFirst(), 1) == degree (factors.getLast(),1)))
6515 {
6516 Variable x= Variable (1);
6518 int m= degree (F)/4+1;
6519 g= factors.getFirst();
6520 h= factors.getLast();
6521 g= mod (g, power (y,m));
6522 h= mod (h, power (y,m));
6523 g= g (y-evaluation, y);
6524 h= h (y-evaluation, y);
6525 gg= mod (swapvar (g,x,y),power (x,m));
6526 gg= gg (y + evaluation, y);
6527 multiplier1= factors.getLast()[m-1][0]/gg[m-1][0];
6528 gg= div (gg, power (y,m));
6529 gg= gg*power (y,m);
6530 hh= mod (swapvar (h,x,y),power (x,m));
6531 hh= hh (y + evaluation, y);
6532 multiplier2= factors.getFirst()[m-1][0]/hh[m-1][0];
6533 hh= div (hh, power (y,m));
6534 hh= hh*power (y,m);
6537 check1= gg (y-evaluation,y);
6538 check2= hh (y-evaluation,y);
6540 check1= swapvar (check1, x, y);
6541 if (check1/Lc (check1) == check2/Lc (check2))
6542 {
6543 result.append (oldcheck1);
6544 result.append (check2);
6545 delete [] liftPre;
6546 delete [] factorsFoundIndex;
6547 return result;
6548 }
6549 }
6550 }
6551 else
6552 {
6553 i++;
6554 if (i < 5)
6555 continue;
6556 }
6560 );
6561 TIMING_END_AND_PRINT (fac_fq_reconstruction, "time to reconstruct2: ");
6562 if (result.length() == NTLN.NumCols())
6563 {
6564 delete [] liftPre;
6565 delete [] factorsFoundIndex;
6566 return result;
6567 }
6568 i++;
6569 }
6570 }
6571
6572 delete [] liftPre;
6573 delete [] factorsFoundIndex;
6574 return result;
6575}
CF_NO_INLINE FACTORY_PUBLIC CanonicalForm div(const CanonicalForm &, const CanonicalForm &)
T getFirst() const
T getLast() const
void insert(const T &)
CanonicalForm LCF
int * getLiftPrecisions(const CanonicalForm &F, int &sizeOfOutput, int degreeLC)
compute lifting precisions from the shape of the Newton polygon of F
void reconstructionTry(CFList &reconstructedFactors, CanonicalForm &F, const CFList &factors, const int liftBound, int &factorsFound, int *&factorsFoundIndex, mat_zz_pE &N, const CanonicalForm &eval, bool beenInThres)
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)...
STATIC_VAR Poly * h
Definition janet.cc:971

◆ earlyReconstructionAndLifting() [2/2]

CFList earlyReconstructionAndLifting ( const CanonicalForm F,
const nmod_mat_t  N,
CanonicalForm bufF,
CFList factors,
int l,
int factorsFound,
bool  beenInThres,
CFMatrix M,
CFArray Pi,
CFList diophant,
bool  symmetric,
const CanonicalForm evaluation 
)

Definition at line 6207 of file facFqBivar.cc.

6222{
6223 int sizeOfLiftPre;
6224 int * liftPre= getLiftPrecisions (F, sizeOfLiftPre, degree (LC (F, 1), 2));
6225
6226 Variable y= F.mvar();
6227 factorsFound= 0;
6228 CanonicalForm LCF= LC (F, 1);
6229 CFList result;
6230 int smallFactorDeg= tmin (11, liftPre [sizeOfLiftPre- 1] + 1);
6231#ifdef HAVE_FLINT
6234 int * factorsFoundIndex= new int [nmod_mat_ncols (FLINTN)];
6235 for (long i= 0; i < nmod_mat_ncols (FLINTN); i++)
6236#else
6237 mat_zz_p NTLN= N;
6238 int * factorsFoundIndex= new int [NTLN.NumCols()];
6239 for (long i= 0; i < NTLN.NumCols(); i++)
6240#endif
6241 factorsFoundIndex [i]= 0;
6242
6243 if (degree (F) + 1 > smallFactorDeg)
6244 {
6245 if (l < smallFactorDeg)
6246 {
6248 factors.insert (LCF);
6250 TIMING_END_AND_PRINT (fac_fq_lift, "time to lift in reconstruction0: ");
6252 }
6253#ifdef HAVE_FLINT
6257 );
6258 TIMING_END_AND_PRINT (fac_fq_reconstruction, "time to reconstruct0: ");
6259 if (result.length() == nmod_mat_ncols (FLINTN))
6260 {
6262#else
6266 );
6267 TIMING_END_AND_PRINT (fac_fq_reconstruction, "time to reconstruct0: ");
6268 if (result.length() == NTLN.NumCols())
6269 {
6270#endif
6271 delete [] liftPre;
6272 delete [] factorsFoundIndex;
6273 return result;
6274 }
6275 }
6276
6277 int i= sizeOfLiftPre - 1;
6278 int dummy= 1;
6279 if (sizeOfLiftPre > 1 && sizeOfLiftPre < 30)
6280 {
6281 while (i > 0)
6282 {
6283 if (l < liftPre[i-1] + 1)
6284 {
6285 factors.insert (LCF);
6287 henselLiftResume12 (F, factors, l, liftPre[i-1] + 1, Pi, diophant, M);
6288 TIMING_END_AND_PRINT (fac_fq_lift, "time to lift in reconstruction1: ");
6289 l= liftPre[i-1] + 1;
6290 }
6291 else
6292 {
6293 i--;
6294 if (i != 0)
6295 continue;
6296 }
6297#ifdef HAVE_FLINT
6301 );
6302 TIMING_END_AND_PRINT (fac_fq_reconstruction, "time to reconstruct1: ");
6303 if (result.length() == nmod_mat_ncols (FLINTN))
6304 {
6306#else
6310 );
6311 TIMING_END_AND_PRINT (fac_fq_reconstruction, "time to reconstruct1: ");
6312 if (result.length() == NTLN.NumCols())
6313 {
6314#endif
6315 delete [] liftPre;
6316 delete [] factorsFoundIndex;
6317 return result;
6318 }
6319 i--;
6320 }
6321 }
6322 else
6323 {
6324 i= 1;
6325 while (((degree (F,y)/4)*i+1) + 4 <= smallFactorDeg)
6326 i++;
6327 while (i < 5)
6328 {
6329 dummy= tmin (degree (F,y)+1, ((degree (F,y)/4)+1)*i+4);
6330 if (l < dummy)
6331 {
6332 factors.insert (LCF);
6335 TIMING_END_AND_PRINT (fac_fq_lift, "time to lift in reconstruction2: ");
6336 l= dummy;
6337 if (i == 1 && degree (F)%4==0 && symmetric && factors.length() == 2 &&
6338 LC (F,1).inCoeffDomain() &&
6339 (degree (factors.getFirst(), 1) == degree (factors.getLast(),1)))
6340 {
6341 Variable x= Variable (1);
6343 int m= degree (F)/4+1;
6344 g= factors.getFirst();
6345 h= factors.getLast();
6346 g= mod (g, power (y,m));
6347 h= mod (h, power (y,m));
6348 g= g (y-evaluation, y);
6349 h= h (y-evaluation, y);
6350 gg= mod (swapvar (g,x,y),power (x,m));
6351 gg= gg (y + evaluation, y);
6352 multiplier1= factors.getLast()[m-1][0]/gg[m-1][0];
6353 gg= div (gg, power (y,m));
6354 gg= gg*power (y,m);
6355 hh= mod (swapvar (h,x,y),power (x,m));
6356 hh= hh (y + evaluation, y);
6357 multiplier2= factors.getFirst()[m-1][0]/hh[m-1][0];
6358 hh= div (hh, power (y,m));
6359 hh= hh*power (y,m);
6362 check1= gg (y-evaluation,y);
6363 check2= hh (y-evaluation,y);
6365 check1= swapvar (check1, x, y);
6366 if (check1/Lc (check1) == check2/Lc (check2))
6367 {
6368#ifdef HAVE_FLINT
6370#endif
6371 result.append (oldcheck1);
6372 result.append (check2);
6373 delete [] liftPre;
6374 delete [] factorsFoundIndex;
6375 return result;
6376 }
6377 }
6378 }
6379 else
6380 {
6381 i++;
6382 if (i < 5)
6383 continue;
6384 }
6385#ifdef HAVE_FLINT
6389 );
6390 TIMING_END_AND_PRINT (fac_fq_reconstruction, "time to reconstruct2: ");
6391 if (result.length() == nmod_mat_ncols (FLINTN))
6392 {
6394#else
6398 );
6399 TIMING_END_AND_PRINT (fac_fq_reconstruction, "time to reconstruct2: ");
6400 if (result.length() == NTLN.NumCols())
6401 {
6402#endif
6403 delete [] liftPre;
6404 delete [] factorsFoundIndex;
6405 return result;
6406 }
6407 i++;
6408 }
6409 }
6410
6411#ifdef HAVE_FLINT
6413#endif
6414 delete [] liftPre;
6415 delete [] factorsFoundIndex;
6416 return result;
6417}

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

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

◆ extBiFactorize()

CFList extBiFactorize ( const CanonicalForm F,
const ExtensionInfo info 
)

Factorization over an extension of initial field.

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

Definition at line 8930 of file facFqBivar.cc.

8931{
8932
8933 CanonicalForm A= F;
8934 Variable alpha= info.getAlpha();
8935 Variable beta= info.getBeta();
8936 int k= info.getGFDegree();
8937 char cGFName= info.getGFName();
8938 CanonicalForm delta= info.getDelta();
8939
8941 Variable x= Variable (1);
8943 if (!GF && alpha == x) // we are in F_p
8944 {
8945 bool extension= true;
8946 int p= getCharacteristic();
8947 if (p*p < (1<<16)) // pass to GF if possible
8948 {
8950 A= A.mapinto();
8953
8957 for (CFListIterator j= factors; j.hasItem(); j++)
8958 j.getItem()= GF2FalphaRep (j.getItem(), vBuf);
8959 prune (vBuf);
8960 }
8961 else // not able to pass to GF, pass to F_p(\alpha)
8962 {
8964 Variable v= rootOf (mipo);
8967 prune (v);
8968 }
8969 return factors;
8970 }
8971 else if (!GF && (alpha != x)) // we are in F_p(\alpha)
8972 {
8973 if (k == 1) // need factorization over F_p
8974 {
8975 int extDeg= degree (getMipo (alpha));
8976 extDeg++;
8978 Variable v= rootOf (mipo);
8981 prune (v);
8982 }
8983 else
8984 {
8985 if (beta == x)
8986 {
8989 bool primFail= false;
8990 Variable vBuf;
8992 ASSERT (!primFail, "failure in integer factorizer");
8993 if (primFail)
8994 ; //ERROR
8995 else
8997
8998 CFList source, dest;
9000 source, dest);
9003 prune (v);
9004 }
9005 else
9006 {
9009 bool primFail= false;
9010 Variable vBuf;
9011 ASSERT (!primFail, "failure in integer factorizer");
9012 if (primFail)
9013 ; //ERROR
9014 else
9015 imPrimElem= mapPrimElem (delta, beta, v);
9016
9017 CFList source, dest;
9019 source= CFList();
9020 dest= CFList();
9021 bufA= mapUp (bufA, beta, v, delta, imPrimElem, source, dest);
9024 prune (v);
9025 }
9026 }
9027 return factors;
9028 }
9029 else // we are in GF (p^k)
9030 {
9031 int p= getCharacteristic();
9033 bool extension= true;
9034 if (k == 1) // need factorization over F_p
9035 {
9036 extensionDeg++;
9037 if (ipower (p, extensionDeg) < (1<<16))
9038 // pass to GF(p^k+1)
9039 {
9043 A= GF2FalphaRep (A, vBuf);
9046 factors= biFactorize (A.mapinto(), info2);
9047 prune (vBuf);
9048 }
9049 else // not able to pass to another GF, pass to F_p(\alpha)
9050 {
9054 A= GF2FalphaRep (A, vBuf);
9058 prune (vBuf);
9059 }
9060 }
9061 else // need factorization over GF (p^k)
9062 {
9063 if (ipower (p, 2*extensionDeg) < (1<<16))
9064 // pass to GF (p^2k)
9065 {
9070 }
9071 else // not able to pass to GF (p^2k), pass to F_p (\alpha)
9072 {
9076 A= GF2FalphaRep (A, v1);
9079 bool primFail= false;
9080 Variable vBuf;
9082 ASSERT (!primFail, "failure in integer factorizer");
9083 if (primFail)
9084 ; //ERROR
9085 else
9087
9088 CFList source, dest;
9090 source, dest);
9094 for (CFListIterator i= factors; i.hasItem(); i++)
9096 prune (v1);
9097 }
9098 }
9099 return factors;
9100 }
9101}
void FACTORY_PUBLIC setCharacteristic(int c)
Definition cf_char.cc:28
#define ASSERT(expression, message)
Definition cf_assert.h:99
CanonicalForm randomIrredpoly(int i, const Variable &x)
computes a random monic irreducible univariate polynomial in x over Fp of degree i via NTL/FLINT
Definition cf_irred.cc:26
CanonicalForm mapPrimElem(const CanonicalForm &primElem, const Variable &alpha, const Variable &beta)
compute the image of a primitive element of in . We assume .
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
static CanonicalForm mapUp(const Variable &alpha, const Variable &beta)
and is a primitive element, returns the image of
Definition cf_map_ext.cc:71
CanonicalForm Falpha2GFRep(const CanonicalForm &F)
change representation by residue classes modulo a Conway polynomial to representation by primitive el...
CanonicalForm GFMapUp(const CanonicalForm &F, int k)
maps a polynomial over to a polynomial over , d needs to be a multiple of k
CanonicalForm GF2FalphaRep(const CanonicalForm &F, const Variable &alpha)
changes representation by primitive element to representation by residue classes modulo a Conway poly...
CanonicalForm mapinto() const
const Variable & v
< [in] a sqrfree bivariate poly
Definition facBivar.h:39
Variable chooseExtension(const Variable &alpha, const Variable &beta, int k)
chooses a field extension.
int j
Definition facHensel.cc:110
void FACTORY_PUBLIC prune(Variable &alpha)
Definition variable.cc:261
INST_VAR CanonicalForm gf_mipo
Definition gfops.cc:56

◆ extEarlyFactorDetection()

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

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

See also
factorRecombination(), earlyFactorDetection()
Parameters
[in,out]reconstructedFactorslist of reconstructed factors
[in,out]Fpoly to be factored, returns poly divided by detected factors in case of success
[in,out]factorslist of factors lifted up to deg, returns a list of factors without detected factors
[in,out]adaptedLiftBoundadapted lift bound
[in,out]factorsFoundIndexfactors already considered
[in,out]degsdegree pattern, is updated whenever we find a factor
[in,out]successindicating success
[in]infoinformation about extension
[in]evalevaluation point
[in]degstage of Hensel lifting

Definition at line 984 of file facFqBivar.cc.

989{
990 Variable alpha= info.getAlpha();
991 Variable beta= info.getBeta();
992 CanonicalForm gamma= info.getGamma();
993 CanonicalForm delta= info.getDelta();
994 int k= info.getGFDegree();
998 Variable y= F.mvar();
999 Variable x= Variable (1);
1000 CanonicalForm buf= F, LCBuf= LC (buf, x), g, buf2;
1001 CanonicalForm M= power (y, deg);
1003 bool trueFactor= false;
1004 int d= degree (F), l= 0;
1005 CFList source, dest;
1006 int degMipoBeta= 1;
1007 if (!k && beta.level() != 1)
1010 for (CFListIterator i= factors; i.hasItem(); i++, l++)
1011 {
1012 if (!bufDegs1.find (degree (i.getItem(), 1)) || factorsFoundIndex[l] == 1)
1013 continue;
1014 else
1015 {
1016 g= mulMod2 (i.getItem(), LCBuf, M);
1017 g /= content (g, x);
1018 if (fdivides (g, buf, quot))
1019 {
1020 buf2= g (y - eval, y);
1021 buf2 /= Lc (buf2);
1022
1023 if (!k && beta == x)
1024 {
1025 if (degree (buf2, alpha) < degMipoBeta)
1026 {
1028 factorsFoundIndex[l]= 1;
1029 buf= quot;
1030 d -= degree (g);
1031 LCBuf= LC (buf, x);
1032 trueFactor= true;
1033 }
1034 }
1035 else
1036 {
1037 if (!isInExtension (buf2, gamma, k, delta, source, dest))
1038 {
1040 factorsFoundIndex[l]= 1;
1041 buf= quot;
1042 d -= degree (g);
1043 LCBuf= LC (buf, x);
1044 trueFactor= true;
1045 }
1046 }
1047 if (trueFactor)
1048 {
1049 T= Difference (T, CFList (i.getItem()));
1050 F= buf;
1051
1052 // compute new possible degree pattern
1054 bufDegs1.intersect (bufDegs2);
1055 bufDegs1.refine ();
1056 trueFactor= false;
1057 if (bufDegs1.getLength() <= 1)
1058 {
1059 if (!buf.inCoeffDomain())
1060 {
1061 buf= buf (y - eval, y);
1062 buf /= Lc (buf);
1064 F= 1;
1065 }
1066 break;
1067 }
1068 }
1069 }
1070 }
1071 }
1072 adaptedLiftBound= d + 1;
1073 if (adaptedLiftBound < deg)
1074 {
1075 degs= bufDegs1;
1076 success= true;
1077 }
1078 if (bufDegs1.getLength() <= 1)
1079 degs= bufDegs1;
1080}
void appendTestMapDown(CFList &factors, const CanonicalForm &f, const ExtensionInfo &info, CFList &source, CFList &dest)
test if g is in a subfield of the current field, if so map it down and append it to factors
bool isInExtension(const CanonicalForm &F, const CanonicalForm &gamma, const int k, const CanonicalForm &delta, CFList &source, CFList &dest)
tests if F is not contained in a subfield defined by gamma (Fq case) or k (GF case)
CanonicalForm buf2
Definition facFqBivar.cc:75

◆ extEarlyReconstructionAndLifting()

CFList extEarlyReconstructionAndLifting ( const CanonicalForm F,
const nmod_mat_t  N,
CanonicalForm bufF,
CFList factors,
int l,
int factorsFound,
bool  beenInThres,
CFMatrix M,
CFArray Pi,
CFList diophant,
const ExtensionInfo info,
const CanonicalForm evaluation 
)

Definition at line 6581 of file facFqBivar.cc.

6598{
6599 int sizeOfLiftPre;
6600 int * liftPre= getLiftPrecisions (F, sizeOfLiftPre, degree (LC (F, 1), 2));
6601 Variable y= F.mvar();
6602 factorsFound= 0;
6603 CanonicalForm LCF= LC (F, 1);
6604 CFList result;
6605 int smallFactorDeg= 11;
6606#ifdef HAVE_FLINT
6609 int * factorsFoundIndex= new int [nmod_mat_ncols (FLINTN)];
6610 for (long i= 0; i < nmod_mat_ncols (FLINTN); i++)
6611#else
6612 mat_zz_p NTLN= N;
6613 int * factorsFoundIndex= new int [NTLN.NumCols()];
6614 for (long i= 0; i < NTLN.NumCols(); i++)
6615#endif
6616 factorsFoundIndex [i]= 0;
6617
6618 if (degree (F) + 1 > smallFactorDeg)
6619 {
6620 if (l < smallFactorDeg)
6621 {
6623 factors.insert (LCF);
6625 TIMING_END_AND_PRINT (fac_fq_lift, "time to lift in reconstruction0: ");
6627 }
6629#ifdef HAVE_FLINT
6633 );
6634#else
6638 );
6639#endif
6640 TIMING_END_AND_PRINT (fac_fq_reconstruction, "time to reconstruct0: ");
6641#ifdef HAVE_FLINT
6642 if (result.length() == nmod_mat_ncols (FLINTN))
6643 {
6645#else
6646 if (result.length() == NTLN.NumCols())
6647 {
6648#endif
6649 delete [] liftPre;
6650 delete [] factorsFoundIndex;
6651 return result;
6652 }
6653 }
6654
6655 int i= sizeOfLiftPre - 1;
6656 int dummy= 1;
6657 if (sizeOfLiftPre > 1 && sizeOfLiftPre < 30)
6658 {
6659 while (i > 0)
6660 {
6661 if (l < liftPre[i-1] + 1)
6662 {
6663 factors.insert (LCF);
6665 henselLiftResume12 (F, factors, l, liftPre[i-1] + 1, Pi, diophant, M);
6666 TIMING_END_AND_PRINT (fac_fq_lift, "time to lift in reconstruction1: ");
6667 l= liftPre[i-1] + 1;
6668 }
6669 else
6670 {
6671 i--;
6672 if (i != 0)
6673 continue;
6674 }
6676#ifdef HAVE_FLINT
6680 );
6681#else
6685 );
6686#endif
6687 TIMING_END_AND_PRINT (fac_fq_reconstruction, "time to reconstruct1: ");
6688#ifdef HAVE_FLINT
6689 if (result.length() == nmod_mat_ncols (FLINTN))
6690 {
6692#else
6693 if (result.length() == NTLN.NumCols())
6694 {
6695#endif
6696 delete [] liftPre;
6697 delete [] factorsFoundIndex;
6698 return result;
6699 }
6700 i--;
6701 }
6702 }
6703 else
6704 {
6705 i= 1;
6706 while ((degree (F,y)/4+1)*i + 4 <= smallFactorDeg)
6707 i++;
6708 while (i < 5)
6709 {
6710 dummy= tmin (degree (F,y)+1, (degree (F,y)/4+1)*i+4);
6711 if (l < dummy)
6712 {
6713 factors.insert (LCF);
6716 TIMING_END_AND_PRINT (fac_fq_lift, "time to lift in reconstruction2: ");
6717 l= dummy;
6718 }
6719 else
6720 {
6721 i++;
6722 if (i < 5)
6723 continue;
6724 }
6726#ifdef HAVE_FLINT
6730 );
6731#else
6735 );
6736#endif
6737 TIMING_END_AND_PRINT (fac_fq_reconstruction, "time to reconstruct2: ");
6738#ifdef HAVE_FLINT
6739 if (result.length() == nmod_mat_ncols (FLINTN))
6740 {
6742#else
6743 if (result.length() == NTLN.NumCols())
6744 {
6745#endif
6746 delete [] liftPre;
6747 delete [] factorsFoundIndex;
6748 return result;
6749 }
6750 i++;
6751 }
6752 }
6753
6754#ifdef HAVE_FLINT
6756#endif
6757 delete [] liftPre;
6758 delete [] factorsFoundIndex;
6759 return result;
6760}
void extReconstructionTry(CFList &reconstructedFactors, CanonicalForm &F, const CFList &factors, const int liftBound, int &factorsFound, int *&factorsFoundIndex, mat_zz_p &N, bool beenInThres, const ExtensionInfo &info, const CanonicalForm &evaluation)

◆ 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 as decribed in "Factoring multivariate polynomials over a finite field" by L Bernardin.

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

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

◆ extFurtherLiftingAndIncreasePrecision()

CFList extFurtherLiftingAndIncreasePrecision ( CanonicalForm F,
CFList factors,
int  l,
int  liftBound,
int  d,
int bounds,
nmod_mat_t  FLINTN,
CFList diophant,
CFMatrix M,
CFArray Pi,
CFArray bufQ,
const CanonicalForm evaluation,
const ExtensionInfo info,
CFList source,
CFList dest 
)

Definition at line 5559 of file facFqBivar.cc.

5578{
5579 CanonicalForm LCF= LC (F, 1);
5580 CFList result;
5581 bool irreducible= false;
5584 CFArray *A = new CFArray [bufFactors.length()];
5585 bool useOldQs= false;
5586 bool hitBound= false;
5588 int degMipo= degree (getMipo (info.getAlpha()));
5589 Variable alpha= info.getAlpha();
5590 int oldL= l; //be careful
5591 int stepSize= 8;
5592 l += tmax (tmin (8, degree (F) + 1 + degree (LC (F, 1))-l),2);
5593 Variable gamma= info.getBeta();
5594 CanonicalForm primElemAlpha= info.getGamma();
5596#ifdef HAVE_FLINT
5599 for (long i=factors.length()-1; i >= 0; i--)
5600 nmod_mat_entry (FLINTN, i, i)= 1;
5601#else
5602 if (NTLN.NumRows() != factors.length()) //refined factors
5603 ident (NTLN, factors.length());
5604#endif
5605 Variable y= F.mvar();
5607 CFMatrix Mat, C;
5609#ifdef HAVE_FLINT
5610 long rank;
5612#else
5614#endif
5616 CFArray buf;
5617 while (l <= liftBound)
5618 {
5621
5622 if (GF)
5624
5625 powX= power (y-gamma, l);
5627 for (int i= 0; i < l*degMipo; i++)
5628 {
5629
5630 imBasis= mod (power (y, i), powX);
5631 imBasis= imBasis (power (y, degMipo), y);
5632 imBasis= imBasis (y, gamma);
5633 iter= imBasis;
5634 for (; iter.hasTerms(); iter++)
5635 Mat (iter.exp()+ 1, i+1)= iter.coeff();
5636 }
5637
5638#ifdef HAVE_FLINT
5643#else
5645 *NTLMat= inv (*NTLMat);
5646#endif
5647
5648 if (GF)
5650
5651 j= bufFactors;
5652 truncF= mod (F, power (y, l));
5653 if (useOldQs)
5654 {
5655 for (int i= 0; i < bufFactors.length(); i++, j++)
5656 A[i]= logarithmicDerivative (truncF, j.getItem(), l, oldL, bufQ[i],
5657 bufQ[i]);
5658 }
5659 else
5660 {
5661 for (int i= 0; i < bufFactors.length(); i++, j++)
5662 A[i]= logarithmicDerivative (truncF, j.getItem(), l, bufQ [i]);
5663 }
5664 for (int i= 0; i < d; i++)
5665 {
5666 if (bounds [i] + 1 <= l/2)
5667 {
5668 int k= tmin (bounds [i] + 1, l/2);
5669 C= CFMatrix (l*degMipo - k, bufFactors.length());
5670 for (int ii= 0; ii < bufFactors.length(); ii++)
5671 {
5672 if (A[ii].size() - 1 >= i)
5673 {
5674 if (GF)
5675 {
5676 A [ii] [i]= A [ii] [i] (y-evaluation, y);
5678 A[ii] [i]= GF2FalphaRep (A[ii] [i], alpha);
5679 if (alpha != gamma)
5681 gamma, source, dest
5682 );
5683#ifdef HAVE_FLINT
5684 buf= getCoeffs (A[ii] [i], k, l, degMipo, gamma, 0, FLINTMatInv);
5685#else
5686 buf= getCoeffs (A[ii] [i], k, l, degMipo, gamma, 0, *NTLMat);
5687#endif
5688 }
5689 else
5690 {
5691 A [ii] [i]= A [ii] [i] (y-evaluation, y);
5692 if (alpha != gamma)
5694 gamma, source, dest
5695 );
5696#ifdef HAVE_FLINT
5697 buf= getCoeffs (A[ii] [i], k, l, degMipo, gamma, 0, FLINTMatInv);
5698#else
5699 buf= getCoeffs (A[ii] [i], k, l, degMipo, gamma, 0, *NTLMat);
5700#endif
5701 }
5702 writeInMatrix (C, buf, ii + 1, 0);
5703 }
5704 if (GF)
5706 }
5707
5708 if (GF)
5710
5711#ifdef HAVE_FLINT
5726 nmod_mat_mul (FLINTN, FLINTC, FLINTK); //no aliasing allowed!!
5727
5731#else
5733 NTLK= (*NTLC)*NTLN;
5734 transpose (NTLK, NTLK);
5735 kernel (NTLK, NTLK);
5736 transpose (NTLK, NTLK);
5737 NTLN *= NTLK;
5738 delete NTLC;
5739#endif
5740
5741 if (GF)
5743
5744#ifdef HAVE_FLINT
5745 if (nmod_mat_ncols (FLINTN) == 1)
5746#else
5747 if (NTLN.NumCols() == 1)
5748#endif
5749 {
5750 irreducible= true;
5751 break;
5752 }
5753 }
5754 }
5755
5756#ifdef HAVE_FLINT
5759 if (nmod_mat_ncols (FLINTN) == 1)
5760#else
5761 delete NTLMat;
5762 if (NTLN.NumCols() == 1)
5763#endif
5764 {
5765 irreducible= true;
5766 break;
5767 }
5768
5769 bufF= F;
5771#ifdef HAVE_FLINT
5775 );
5776#else
5780 );
5781#endif
5782 delete [] zeroOneVecs;
5783 if (result.length() > 0 && degree (bufF) + 1 + degree (LC (bufF, 1)) <= l)
5784 {
5785 F= bufF;
5787 delete [] A;
5788 return result;
5789 }
5790 else
5791 {
5792 bufF= F;
5794 }
5795
5796#ifdef HAVE_FLINT
5797 if (isReduced (FLINTN))
5798#else
5799 if (isReduced (NTLN))
5800#endif
5801 {
5802 int factorsFound= 0;
5803 bufF= F;
5804#ifdef HAVE_FLINT
5805 int* factorsFoundIndex= new int [nmod_mat_ncols (FLINTN)];
5806 for (long i= 0; i < nmod_mat_ncols (FLINTN); i++)
5807#else
5808 int* factorsFoundIndex= new int [NTLN.NumCols()];
5809 for (long i= 0; i < NTLN.NumCols(); i++)
5810#endif
5811 factorsFoundIndex[i]= 0;
5812#ifdef HAVE_FLINT
5813 if (l < degree (bufF) + 1 + degree (LCF))
5816 );
5817 else
5820 FLINTN, false, info, evaluation
5821 );
5823#else
5824 if (l < degree (bufF) + 1 + degree (LCF))
5827 );
5828 else
5831 NTLN, false, info, evaluation
5832 );
5833 if (NTLN.NumCols() == result.length())
5834#endif
5835 {
5836 delete [] A;
5837 delete [] factorsFoundIndex;
5838 return result;
5839 }
5840 delete [] factorsFoundIndex;
5841 }
5842 result= CFList();
5843 oldL= l;
5844 stepSize *= 2;
5845 l += stepSize;
5846 if (l > liftBound)
5847 {
5848 if (!hitBound)
5849 {
5850 l= liftBound;
5851 hitBound= true;
5852 }
5853 else
5854 break;
5855 }
5856 }
5857 if (irreducible)
5858 {
5859 delete [] A;
5860 Variable y= Variable (2);
5861 CanonicalForm tmp= F (y - evaluation, y);
5862 CFList source, dest;
5863 tmp= mapDown (tmp, info, source, dest);
5864 return CFList (tmp);
5865 }
5866 delete [] A;
5868 return CFList();
5869}
void convertFacCFMatrix2nmod_mat_t(nmod_mat_t M, const CFMatrix &m)
conversion of a factory matrix over Z/p to a nmod_mat_t
mat_zz_p * convertFacCFMatrix2NTLmat_zz_p(const CFMatrix &m)
Matrix< CanonicalForm > CFMatrix
static bool irreducible(const CFList &AS)
class to iterate through CanonicalForm's
Definition cf_iter.h:44
CFArray logarithmicDerivative(const CanonicalForm &F, const CanonicalForm &G, int l, CanonicalForm &Q)
compute the coefficients of the logarithmic derivative of G mod Variable (2)^l over Fq
CFArray getCoeffs(const CanonicalForm &F, const int k)
extract coefficients of for where is a variable of level 1
void writeInMatrix(CFMatrix &M, const CFArray &A, const int column, const int startIndex)
write A into M starting at row startIndex
CFList extReconstruction(CanonicalForm &G, CFList &factors, int *zeroOneVecs, int precision, const mat_zz_p &N, const ExtensionInfo &info, const CanonicalForm &evaluation)
int * extractZeroOneVecs(const mat_zz_p &M)
long isReduced(const mat_zz_p &M)
template CanonicalForm tmax(const CanonicalForm &, const CanonicalForm &)

◆ extHenselLiftAndLatticeRecombi()

CFList extHenselLiftAndLatticeRecombi ( const CanonicalForm G,
const CFList uniFactors,
const ExtensionInfo extInfo,
const DegreePattern degPat,
const CanonicalForm eval 
)

Definition at line 7714 of file facFqBivar.cc.

7718{
7723 CanonicalForm F= G;
7724 Variable x= Variable (1);
7725 Variable y= F.mvar();
7727
7728
7729 int degMipo;
7731
7732 CFList source, dest;
7733 CanonicalForm LCF= LC (F, 1);
7734
7735 int d;
7736 bool isIrreducible= false;
7737 int* bounds= computeBounds (F, d, isIrreducible);
7738 if (isIrreducible)
7739 {
7740 delete [] bounds;
7741 CFList source, dest;
7743 tmp= mapDown (tmp, info, source, dest);
7744 return CFList (tmp);
7745 }
7746 int minBound= bounds[0];
7747 for (int i= 1; i < d; i++)
7748 {
7749 if (bounds[i] != 0)
7751 }
7752
7753
7754 CFArray Pi;
7756 int liftBound= tmax ((2*totaldegree (F) - 1)/degMipo + 1, degree (F) + 1 +
7757 degree (LC (F, 1)));
7759
7762 bool success= false;
7764 M, success, minBound + 1, evaluation, info
7765 );
7766
7767 if (smallFactors.length() > 0)
7768 {
7769 if (smallFactors.length() == 1)
7770 {
7771 if (smallFactors.getFirst() == F)
7772 {
7773 delete [] bounds;
7774 CFList source, dest;
7776 tmp= mapDown (tmp, info, source, dest);
7777 return CFList (tmp);
7778 }
7779 }
7780 if (degs.getLength() <= 1)
7781 {
7782 delete [] bounds;
7783 return smallFactors;
7784 }
7785 }
7786
7787 int index;
7789 for (CFListIterator i= smallFactors; i.hasItem(); i++)
7790 {
7791 index= 1;
7792 tmp1= mod (i.getItem(), y - evaluation);
7793 tmp1 /= Lc (tmp1);
7794 for (CFListIterator j= bufUniFactors; j.hasItem(); j++, index++)
7795 {
7796 tmp2= mod (j.getItem(), y);
7797 tmp2 /= Lc (tmp2);
7798 if (tmp1 == tmp2)
7799 {
7800 index++;
7801 j.remove(index);
7802 break;
7803 }
7804 }
7805 }
7806
7807 if (bufUniFactors.isEmpty())
7808 {
7809 delete [] bounds;
7810 return smallFactors;
7811 }
7812
7813 if (success)
7814 {
7815 F= H/Lc(H);
7816 delete [] bounds;
7818 if (isIrreducible)
7819 {
7820 delete [] bounds;
7821 CFList source, dest;
7822 CanonicalForm tmp= F (y - evaluation, y);
7823 tmp= mapDown (tmp, info, source, dest);
7825 return smallFactors;
7826 }
7827 LCF= LC (F, 1);
7828
7829 minBound= bounds[0];
7830 for (int i= 1; i < d; i++)
7831 {
7832 if (bounds[i] != 0)
7834 }
7835 Pi= CFArray();
7836 diophant= CFList();
7837 liftBound=tmax ((2*totaldegree (F) - 1)/degMipo + 1, degree (F) + 1 +
7838 degree (LC (F, 1)));
7841 degs.intersect (bufDegs);
7842 degs.refine();
7843 if (degs.getLength() <= 1)
7844 {
7845 delete [] bounds;
7846 CFList source, dest;
7847 CanonicalForm tmp= F (y - evaluation, y);
7848 tmp= mapDown (tmp, info, source, dest);
7850 return smallFactors;
7851 }
7852 }
7853
7855 int l= 1;
7856
7857#ifdef HAVE_FLINT
7861 for (long i= bufUniFactors.length()-2; i >= 0; i--)
7862 nmod_mat_entry (FLINTN, i, i)= 1;
7863#else
7865 {
7867 zz_p::init (getCharacteristic());
7868 }
7869 zz_pX NTLMipo;
7870 mat_zz_p NTLN;
7871
7872 ident (NTLN, bufUniFactors.length() - 1);
7873#endif
7874 bool irreducible= false;
7876
7877 int oldL;
7879 if (success)
7880 {
7881 int start= 0;
7882#ifdef HAVE_FLINT
7886 );
7887#else
7891 );
7892#endif
7893 }
7894 else
7895 {
7896#ifdef HAVE_FLINT
7900 source, dest
7901 );
7902#else
7906 source, dest
7907 );
7908#endif
7909 }
7911 "time to compute a reduced lattice: ");
7912
7914 if (oldL > liftBound)
7915 {
7916#ifdef HAVE_FLINT
7918#endif
7919 delete [] bounds;
7921 (bufUniFactors, F,
7922 power (y, degree (F) + 1),info,
7924 )
7925 );
7926 }
7927
7928 l= oldL;
7929 if (irreducible)
7930 {
7931#ifdef HAVE_FLINT
7933#endif
7934 delete [] bounds;
7935 CFList source, dest;
7936 CanonicalForm tmp= F (y - evaluation, y);
7937 tmp= mapDown (tmp, info, source, dest);
7938 return Union (CFList (tmp), smallFactors);
7939 }
7940
7942
7943 CFList result;
7944 if (l >= degree (F) + 1)
7945 {
7946 int * factorsFoundIndex;
7947
7948#ifdef HAVE_FLINT
7950 for (long i= 0; i < nmod_mat_ncols (FLINTN); i++)
7951#else
7952 factorsFoundIndex= new int [NTLN.NumCols()];
7953 for (long i= 0; i < NTLN.NumCols(); i++)
7954#endif
7955 factorsFoundIndex[i]= 0;
7956
7957 int factorsFound= 0;
7959
7960#ifdef HAVE_FLINT
7964 );
7965
7966 if (result.length() == nmod_mat_ncols (FLINTN))
7967 {
7969#else
7973 );
7974
7975 if (result.length() == NTLN.NumCols())
7976 {
7977#endif
7978 delete [] factorsFoundIndex;
7979 delete [] bounds;
7980 return Union (result, smallFactors);
7981 }
7982
7983 delete [] factorsFoundIndex;
7984 }
7985 if (l >= liftBound)
7986 {
7987 int * factorsFoundIndex;
7988#ifdef HAVE_FLINT
7990 for (long i= 0; i < nmod_mat_ncols (FLINTN); i++)
7991#else
7992 factorsFoundIndex= new int [NTLN.NumCols()];
7993 for (long i= 0; i < NTLN.NumCols(); i++)
7994#endif
7995 factorsFoundIndex[i]= 0;
7997 int factorsFound= 0;
7998
7999#ifdef HAVE_FLINT
8003 );
8004
8005 if (result.length() == nmod_mat_ncols (FLINTN))
8006 {
8008#else
8012 );
8013
8014 if (result.length() == NTLN.NumCols())
8015 {
8016#endif
8017 delete [] factorsFoundIndex;
8018 delete [] bounds;
8019 return Union (result, smallFactors);
8020 }
8021 delete [] factorsFoundIndex;
8022 }
8023
8024 result= CFList();
8025 bool beenInThres= false;
8026 int thres= 100;
8027#ifdef HAVE_FLINT
8029 {
8031 diophant
8032 );
8033#else
8034 if (l <= thres && bufUniFactors.length() > NTLN.NumCols())
8035 {
8037 diophant
8038 );
8039#endif
8040 beenInThres= true;
8041 }
8042
8043
8045 int factorsFound= 0;
8046
8047#ifdef HAVE_FLINT
8051 );
8052
8053 if (result.length() == nmod_mat_ncols (FLINTN))
8054 {
8056#else
8060 );
8061
8062 if (result.length() == NTLN.NumCols())
8063 {
8064#endif
8065 delete [] bounds;
8066 return Union (result, smallFactors);
8067 }
8068
8069 if (result.length() > 0)
8070 {
8071 if (beenInThres)
8072 {
8073 int index;
8074 for (CFListIterator i= result; i.hasItem(); i++)
8075 {
8076 index= 1;
8077 tmp1= mod (i.getItem(), y-evaluation);
8078 tmp1 /= Lc (tmp1);
8079 for (CFListIterator j= bufUniFactors; j.hasItem(); j++, index++)
8080 {
8081 tmp2= mod (j.getItem(), y);
8082 tmp2 /= Lc (tmp2);
8083 if (tmp1 == tmp2)
8084 {
8085 index++;
8086 j.remove(index);
8087 break;
8088 }
8089 }
8090 }
8091 }
8092 else
8093 {
8094#ifdef HAVE_FLINT
8096#else
8098#endif
8103#ifdef HAVE_FLINT
8104 for (int i= 0; i < nmod_mat_ncols (FLINTN); i++)
8105#else
8106 for (int i= 0; i < NTLN.NumCols(); i++)
8107#endif
8108 {
8109 if (zeroOne [i] == 0)
8110 continue;
8112 buf= 1;
8114#ifdef HAVE_FLINT
8115 for (int j= 0; j < nmod_mat_nrows (FLINTN); j++, iter++)
8116 {
8117 if (!(nmod_mat_entry (FLINTN, j, i) == 0))
8118#else
8119 for (int j= 0; j < NTLN.NumRows(); j++, iter++)
8120 {
8121 if (!IsZero (NTLN (j + 1,i + 1)))
8122#endif
8123 {
8124 factorsConsidered.append (iter.getItem());
8125 buf *= mod (iter.getItem(), y);
8126 }
8127 }
8128 buf /= Lc (buf);
8129 for (iter2= result; iter2.hasItem(); iter2++)
8130 {
8131 CanonicalForm tmp= mod (iter2.getItem(), y - evaluation);
8132 tmp /= Lc (tmp);
8133 if (tmp == buf)
8134 {
8136 break;
8137 }
8138 }
8139 }
8141 delete [] zeroOne;
8142 }
8143
8144 int oldNumCols;
8146 irreducible= false;
8147
8148#ifdef HAVE_FLINT //TODO
8152 source, dest, l
8153 );
8155#else
8156 oldNumCols= NTLN.NumCols();
8159 source, dest, l
8160 );
8161#endif
8162 if (bufUniFactors.isEmpty() || degree (bufF) <= 0)
8163 {
8164 delete [] bounds;
8166 return Union (result, smallFactors);
8167 }
8168
8170 i.getItem()= mod (i.getItem(), y);
8171
8172 delete [] bounds;
8175 degs.intersect (bufDegs);
8176 degs.refine();
8178 if (degs.getLength() == 1 || bufUniFactors.length() == 1)
8179 {
8180 CFList source, dest;
8182 tmp= mapDown (tmp, info, source, dest);
8183 result.append (tmp);
8184 return result;
8185 }
8188 )
8189 );
8190 }
8191
8192 if (l/degMipo < liftBound)
8193 {
8194#ifdef HAVE_FLINT
8196 FLINTN, evaluation, info2, source, dest
8197 );
8198
8199 if (result.length()== nmod_mat_ncols (FLINTN))
8200 {
8202#else
8204 NTLN, evaluation, info2, source, dest
8205 );
8206
8207 if (result.length()== NTLN.NumCols())
8208 {
8209#endif
8210 delete [] bounds;
8212 return result;
8213 }
8214
8215 if (result.isEmpty())
8216 {
8217#ifdef HAVE_FLINT
8220 diophant, M, Pi, bufQ,
8222 dest
8223 );
8224 if (result.length()== nmod_mat_ncols (FLINTN))
8225 {
8227#else
8229 liftBound, d, bounds, NTLN,
8230 diophant, M, Pi, bufQ,
8232 dest
8233 );
8234 if (result.length()== NTLN.NumCols())
8235 {
8236#endif
8237 delete [] bounds;
8239 return result;
8240 }
8241 }
8242 }
8243
8244#ifdef HAVE_FLINT
8246#endif
8247
8248 DEBOUTLN (cerr, "lattice recombination failed");
8249
8251 degs.intersect (bufDegs);
8252 degs.refine();
8253
8254 delete [] bounds;
8256 if (isIrreducible)
8257 {
8258 delete [] bounds;
8259 CFList source, dest;
8260 CanonicalForm tmp= F (y - evaluation, y);
8261 tmp= mapDown (tmp, info, source, dest);
8264 return result;
8265 }
8266 minBound= bounds[0];
8267 for (int i= 1; i < d; i++)
8268 {
8269 if (bounds[i] != 0)
8271 }
8272
8273 if (minBound > 16 || result.length() == 0)
8274 {
8276 CanonicalForm MODl= power (y, degree (F) + 1);
8277 delete [] bounds;
8279 degs, evaluation, 1,
8281 )
8282 );
8283 }
8284 else
8285 {
8288 i.getItem()= mod (i.getItem(), y);
8289 delete [] bounds;
8292 )
8293 );
8294 }
8295}
Array< CanonicalForm > CFArray
int totaldegree(const CanonicalForm &f)
int totaldegree ( const CanonicalForm & f )
Definition cf_ops.cc:523
CanonicalForm H
Definition facAbsFact.cc:60
CFList extFurtherLiftingAndIncreasePrecision(CanonicalForm &F, CFList &factors, int l, int liftBound, int d, int *bounds, nmod_mat_t FLINTN, CFList &diophant, CFMatrix &M, CFArray &Pi, CFArray &bufQ, const CanonicalForm &evaluation, const ExtensionInfo &info, CFList &source, CFList &dest)
CFList tmp1
Definition facFqBivar.cc:74
CFList extEarlyReconstructionAndLifting(const CanonicalForm &F, const nmod_mat_t N, CanonicalForm &bufF, CFList &factors, int &l, int &factorsFound, bool beenInThres, CFMatrix &M, CFArray &Pi, CFList &diophant, const ExtensionInfo &info, const CanonicalForm &evaluation)
CFList tmp2
Definition facFqBivar.cc:74
CFList extSieveSmallFactors(const CanonicalForm &G, CFList &uniFactors, DegreePattern &degPat, CanonicalForm &H, CFList &diophant, CFArray &Pi, CFMatrix &M, bool &success, int d, const CanonicalForm &evaluation, const ExtensionInfo &info)
void refineAndRestartLift(const CanonicalForm &F, const nmod_mat_t FLINTN, int liftBound, int l, CFList &factors, CFMatrix &M, CFArray &Pi, CFList &diophant)
int extLiftAndComputeLattice(const CanonicalForm &F, int *bounds, int sizeBounds, int liftBound, int minBound, int start, CFList &factors, mat_zz_p &NTLN, CFList &diophant, CFMatrix &M, CFArray &Pi, CFArray &bufQ, bool &irreducible, const CanonicalForm &evaluation, const ExtensionInfo &info, CFList &source, CFList &dest)
static BOOLEAN IsZero(number a, const coeffs)
Definition flintcf_Q.cc:384
STATIC_VAR TreeM * G
Definition janet.cc:31
static int index(p_Length length, p_Ord ord)

◆ extIncreasePrecision() [1/2]

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 at line 3828 of file facFqBivar.cc.

3833{
3835 int degMipo= degree (getMipo (info.getAlpha()));
3836 Variable alpha= info.getAlpha();
3837 int d;
3838 bool isIrreducible= false;
3839 int* bounds= computeBounds (F, d, isIrreducible);
3840 if (isIrreducible)
3841 {
3842 delete [] bounds;
3843 Variable y= Variable (2);
3844 CanonicalForm tmp= F (y - evaluation, y);
3845 CFList source, dest;
3846 tmp= mapDown (tmp, info, source, dest);
3847 F= 1;
3848 return CFList (tmp);
3849 }
3850
3851 CFArray * A= new CFArray [factors.length()];
3853#ifdef HAVE_FLINT
3856 for (long i=factors.length()-1; i >= 0; i--)
3857 nmod_mat_entry (FLINTN, i, i)= 1;
3858#else
3860 {
3862 zz_p::init (getCharacteristic());
3863 }
3864 mat_zz_p NTLN;
3865 ident (NTLN, factors.length());
3866#endif
3867 int minBound= bounds[0];
3868 for (int i= 1; i < d; i++)
3869 {
3870 if (bounds[i] != 0)
3872 }
3873 int l= tmax (oldL, 2*((minBound+1)/degMipo+1));
3874 int oldL2= l/2;
3875 int stepSize= 2;
3876 bool useOldQs= false;
3877 bool hitBound= false;
3878 Variable gamma= info.getBeta();
3879 CanonicalForm primElemAlpha= info.getGamma();
3882 Variable y= F.mvar();
3884 CFMatrix Mat, C;
3886#ifdef HAVE_FLINT
3887 long rank;
3889#else
3891#endif
3892 CFArray buf;
3893 while (l <= precision)
3894 {
3895 j= factors;
3896 if (GF)
3898 powX= power (y-gamma, l);
3900 for (int i= 0; i < l*degMipo; i++)
3901 {
3902 imBasis= mod (power (y, i), powX);
3903 imBasis= imBasis (power (y, degMipo), y);
3904 imBasis= imBasis (y, gamma);
3905 iter= imBasis;
3906 for (; iter.hasTerms(); iter++)
3907 Mat (iter.exp()+ 1, i+1)= iter.coeff();
3908 }
3909
3910#ifdef HAVE_FLINT
3915#else
3917 *NTLMat= inv (*NTLMat);
3918#endif
3919
3920 if (GF)
3922
3923 truncF= mod (F, power (y, l));
3924 if (useOldQs)
3925 {
3926 for (int i= 0; i < factors.length(); i++, j++)
3927 A[i]= logarithmicDerivative (truncF, j.getItem(), l, oldL2, bufQ[i],
3928 bufQ[i]
3929 );
3930 }
3931 else
3932 {
3933 for (int i= 0; i < factors.length(); i++, j++)
3934 A[i]= logarithmicDerivative (truncF, j.getItem(), l, bufQ [i]);
3935 }
3936 useOldQs= true;
3937 for (int i= 0; i < d; i++)
3938 {
3939 if (bounds [i] + 1 <= (l/2)*degMipo)
3940 {
3941 int k= tmin (bounds [i] + 1, (l/2)*degMipo);
3942 C= CFMatrix (l*degMipo - k, factors.length());
3943 for (int ii= 0; ii < factors.length(); ii++)
3944 {
3945 if (A[ii].size() - 1 >= i)
3946 {
3947 if (GF)
3948 {
3949 A[ii] [i]= A [ii] [i] (y-evaluation, y);
3951 A[ii] [i]= GF2FalphaRep (A[ii] [i], alpha);
3952 if (alpha != gamma)
3954 gamma, source, dest
3955 );
3956#ifdef HAVE_FLINT
3957 buf= getCoeffs (A[ii] [i], k, l, degMipo, gamma, 0, FLINTMatInv);
3958#else
3959 buf= getCoeffs (A[ii] [i], k, l, degMipo, gamma, 0, *NTLMat);
3960#endif
3961 }
3962 else
3963 {
3964 A [ii] [i]= A [ii] [i] (y-evaluation, y);
3965 if (alpha != gamma)
3967 gamma, source, dest
3968 );
3969#ifdef HAVE_FLINT
3970 buf= getCoeffs (A[ii] [i], k, l, degMipo, gamma, 0, FLINTMatInv);
3971#else
3972 buf= getCoeffs (A[ii] [i], k, l, degMipo, gamma, 0, *NTLMat);
3973#endif
3974 }
3975 writeInMatrix (C, buf, ii + 1, 0);
3976 }
3977 if (GF)
3979 }
3980
3981 if (GF)
3983
3984#ifdef HAVE_FLINT
3999 nmod_mat_mul (FLINTN, FLINTC, FLINTK); //no aliasing allowed!!
4000
4004#else
4006 NTLK= (*NTLC)*NTLN;
4007 transpose (NTLK, NTLK);
4008 kernel (NTLK, NTLK);
4009 transpose (NTLK, NTLK);
4010 NTLN *= NTLK;
4011 delete NTLC;
4012#endif
4013
4014 if (GF)
4016
4017#ifdef HAVE_FLINT
4018 if (nmod_mat_ncols (FLINTN) == 1)
4019 {
4023#else
4024 if (NTLN.NumCols() == 1)
4025 {
4026 delete NTLMat;
4027#endif
4028 Variable y= Variable (2);
4029 CanonicalForm tmp= F (y - evaluation, y);
4030 CFList source, dest;
4031 tmp= mapDown (tmp, info, source, dest);
4032 delete [] A;
4033 delete [] bounds;
4034 F= 1;
4035 return CFList (tmp);
4036 }
4037 }
4038 }
4039
4040#ifdef HAVE_FLINT
4043#else
4044 delete NTLMat;
4045#endif
4046
4047#ifdef HAVE_FLINT
4049 {
4050 if (isReduced (FLINTN))
4051 {
4052 int * factorsFoundIndex= new int [nmod_mat_ncols (FLINTN)];
4053 for (long i= 0; i < nmod_mat_ncols (FLINTN); i++)
4054#else
4055 if (NTLN.NumCols() < oldNumCols - factorsFound)
4056 {
4057 if (isReduced (NTLN))
4058 {
4059 int * factorsFoundIndex= new int [NTLN.NumCols()];
4060 for (long i= 0; i < NTLN.NumCols(); i++)
4061#endif
4062 factorsFoundIndex[i]= 0;
4063 int factorsFound2= 0;
4064 CFList result;
4066#ifdef HAVE_FLINT
4069 );
4070 if (result.length() == nmod_mat_ncols (FLINTN))
4071 {
4073#else
4076 );
4077 if (result.length() == NTLN.NumCols())
4078 {
4079#endif
4080 delete [] factorsFoundIndex;
4081 delete [] A;
4082 delete [] bounds;
4083 F= 1;
4084 return result;
4085 }
4086 delete [] factorsFoundIndex;
4087 }
4088 else if (l == precision)
4089 {
4091#ifdef HAVE_FLINT
4095 );
4097#else
4101 );
4102#endif
4103 F= bufF;
4104 delete [] zeroOne;
4105 delete [] A;
4106 delete [] bounds;
4107 return result;
4108 }
4109 }
4110 oldL2= l;
4111 l += stepSize;
4112 stepSize *= 2;
4113 if (l > precision)
4114 {
4115 if (!hitBound)
4116 {
4117 hitBound= true;
4118 l= precision;
4119 }
4120 else
4121 break;
4122 }
4123 }
4124
4125#ifdef HAVE_FLINT
4127#endif
4128 delete [] bounds;
4129 delete [] A;
4130 return CFList();
4131}

◆ extIncreasePrecision() [2/2]

CFList extIncreasePrecision ( CanonicalForm F,
CFList factors,
int  oldL,
int  l,
int  d,
int bounds,
CFArray bufQ,
nmod_mat_t  FLINTN,
const CanonicalForm evaluation,
const ExtensionInfo info,
CFList source,
CFList dest 
)

Definition at line 4758 of file facFqBivar.cc.

4771{
4772 CFList result= CFList();
4773 CFArray * A= new CFArray [factors.length()];
4774 int oldL2= oldL/2; //be careful
4775 bool hitBound= false;
4776 bool useOldQs= false;
4778 int degMipo= degree (getMipo (info.getAlpha()));
4779 Variable alpha= info.getAlpha();
4780
4781 Variable gamma= info.getBeta();
4782 CanonicalForm primElemAlpha= info.getGamma();
4784#ifdef HAVE_FLINT
4787 for (long i=factors.length()-1; i >= 0; i--)
4788 nmod_mat_entry (FLINTN, i, i)= 1;
4789#else
4790 if (NTLN.NumRows() != factors.length()) //refined factors
4791 ident (NTLN, factors.length());
4792#endif
4793 Variable y= F.mvar();
4796 CFMatrix Mat, C;
4798 CFArray buf;
4799#ifdef HAVE_FLINT
4800 long rank;
4802#else
4804#endif
4806 while (oldL <= l)
4807 {
4808 j= factors;
4809 if (GF)
4811
4812 powX= power (y-gamma, oldL);
4814 for (int i= 0; i < oldL*degMipo; i++)
4815 {
4816 imBasis= mod (power (y, i), powX);
4817 imBasis= imBasis (power (y, degMipo), y);
4818 imBasis= imBasis (y, gamma);
4819 iter= imBasis;
4820 for (; iter.hasTerms(); iter++)
4821 Mat (iter.exp()+ 1, i+1)= iter.coeff();
4822 }
4823
4824#ifdef HAVE_FLINT
4829#else
4831 *NTLMat= inv (*NTLMat);
4832#endif
4833
4834 if (GF)
4836
4837 truncF= mod (F, power (y, oldL));
4838 if (useOldQs)
4839 {
4840 for (int i= 0; i < factors.length(); i++, j++)
4841 A[i]= logarithmicDerivative (truncF, j.getItem(), oldL, oldL2, bufQ[i],
4842 bufQ[i]);
4843 }
4844 else
4845 {
4846 for (int i= 0; i < factors.length(); i++, j++)
4847 A[i]= logarithmicDerivative (truncF, j.getItem(), oldL, bufQ [i]);
4848 }
4849 useOldQs= true;
4850
4851 for (int i= 0; i < d; i++)
4852 {
4853 if (bounds [i] + 1 <= oldL/2)
4854 {
4855 int k= tmin (bounds [i] + 1, oldL/2);
4856 C= CFMatrix (oldL*degMipo - k, factors.length());
4857 for (int ii= 0; ii < factors.length(); ii++)
4858 {
4859 if (A[ii].size() - 1 >= i)
4860 {
4861 if (GF)
4862 {
4863 A [ii] [i]= A [ii] [i] (y-evaluation, y);
4865 A[ii] [i]= GF2FalphaRep (A[ii] [i], alpha);
4866 if (alpha != gamma)
4868 gamma, source, dest
4869 );
4870#ifdef HAVE_FLINT
4871 buf= getCoeffs (A[ii] [i], k, oldL, degMipo, gamma, 0, FLINTMatInv);
4872#else
4873 buf= getCoeffs (A[ii] [i], k, oldL, degMipo, gamma, 0, *NTLMat);
4874#endif
4875 }
4876 else
4877 {
4878 A [ii] [i]= A [ii] [i] (y-evaluation, y);
4879 if (alpha != gamma)
4881 gamma, source, dest
4882 );
4883#ifdef HAVE_FLINT
4884 buf= getCoeffs (A[ii] [i], k, oldL, degMipo, gamma, 0, FLINTMatInv);
4885#else
4886 buf= getCoeffs (A[ii] [i], k, oldL, degMipo, gamma, 0, *NTLMat);
4887#endif
4888 }
4889 writeInMatrix (C, buf, ii + 1, 0);
4890 }
4891 if (GF)
4893 }
4894
4895 if (GF)
4897
4898#ifdef HAVE_FLINT
4913 nmod_mat_mul (FLINTN, FLINTC, FLINTK); //no aliasing allowed!!
4914
4918#else
4920 NTLK= (*NTLC)*NTLN;
4921 transpose (NTLK, NTLK);
4922 kernel (NTLK, NTLK);
4923 transpose (NTLK, NTLK);
4924 NTLN *= NTLK;
4925 delete NTLC;
4926#endif
4927
4928 if (GF)
4930
4931#ifdef HAVE_FLINT
4932 if (nmod_mat_ncols (FLINTN) == 1)
4933 {
4936#else
4937 if (NTLN.NumCols() == 1)
4938 {
4939 delete NTLMat;
4940#endif
4941 Variable y= Variable (2);
4942 CanonicalForm tmp= F (y - evaluation, y);
4943 CFList source, dest;
4944 tmp= mapDown (tmp, info, source, dest);
4945 delete [] A;
4946 return CFList (tmp);
4947 }
4948 }
4949 }
4950
4951#ifdef HAVE_FLINT
4954#else
4955 delete NTLMat;
4956#endif
4957
4958#ifdef HAVE_FLINT
4959 if (nmod_mat_ncols (FLINTN) == 1)
4960#else
4961 if (NTLN.NumCols() == 1)
4962#endif
4963 {
4964 Variable y= Variable (2);
4965 CanonicalForm tmp= F (y - evaluation, y);
4966 CFList source, dest;
4967 tmp= mapDown (tmp, info, source, dest);
4968 delete [] A;
4969 return CFList (tmp);
4970 }
4971
4972 int * zeroOneVecs;
4973 bufF= F;
4975#ifdef HAVE_FLINT
4979 );
4980#else
4984 );
4985#endif
4986 delete [] zeroOneVecs;
4987 if (degree (bufF) + 1 + degree (LC (bufF, 1)) < l && result.length() > 0)
4988 {
4989 F= bufF;
4991 return result;
4992 }
4993
4994 result= CFList();
4995 oldL2= oldL;
4996 oldL *= 2;
4997 if (oldL > l)
4998 {
4999 if (!hitBound)
5000 {
5001 oldL= l;
5002 hitBound= true;
5003 }
5004 else
5005 break;
5006 }
5007 }
5008 delete [] A;
5009 return result;
5010}

◆ extLiftAndComputeLattice() [1/2]

int extLiftAndComputeLattice ( const CanonicalForm F,
int bounds,
int  sizeBounds,
int  liftBound,
int  minBound,
int  start,
CFList factors,
mat_zz_p NTLN,
CFList diophant,
CFMatrix M,
CFArray Pi,
CFArray bufQ,
bool irreducible,
const CanonicalForm evaluation,
const ExtensionInfo info,
CFList source,
CFList dest 
)

Definition at line 2751 of file facFqBivar.cc.

2758{
2760 CanonicalForm LCF= LC (F, 1);
2761 CFArray *A= new CFArray [factors.length() - 1];
2762 bool wasInBounds= false;
2763 bool hitBound= false;
2764 int degMipo;
2766 alpha= info.getAlpha();
2768
2769 Variable gamma= info.getBeta();
2770 CanonicalForm primElemAlpha= info.getGamma();
2772
2773 int stepSize= 2;
2774 int l= ((minBound+1)/degMipo+1)*2;
2775 l= tmax (l, 2);
2776 if (start > l)
2777 l= start;
2778 int oldL= l/2;
2779 bool reduced= false;
2780 Variable y= F.mvar();
2781 Variable x= Variable (1);
2783 CFMatrix Mat, C;
2784 CFArray buf;
2788 while (l <= liftBound)
2789 {
2791 if (start)
2792 {
2793 henselLiftResume12 (F, factors, start, l, Pi, diophant, M);
2794 start= 0;
2795 }
2796 else
2797 {
2798 if (wasInBounds)
2800 else
2801 henselLift12 (F, factors, l, Pi, diophant, M);
2802 }
2804 "time to lift in compute lattice: ");
2805
2806 factors.insert (LCF);
2807
2808 if (GF)
2810
2811 powX= power (y-gamma, l);
2813 for (int i= 0; i < l*degMipo; i++)
2814 {
2815 imBasis= mod (power (y, i), powX);
2816 imBasis= imBasis (power (y, degMipo), y);
2817 imBasis= imBasis (y, gamma);
2818 iter= imBasis;
2819 for (; iter.hasTerms(); iter++)
2820 Mat (iter.exp()+ 1, i+1)= iter.coeff();
2821 }
2822
2824 *NTLMat= inv (*NTLMat);
2825
2826 if (GF)
2828
2829 j= factors;
2830 j++;
2831
2832 truncF= mod (F, power (y, l));
2834 for (int i= 0; i < factors.length() - 1; i++, j++)
2835 {
2836 if (!wasInBounds)
2837 A[i]= logarithmicDerivative (truncF, j.getItem(), l, bufQ[i]);
2838 else
2839 A[i]= logarithmicDerivative (truncF, j.getItem(), l, oldL, bufQ[i],
2840 bufQ[i]);
2841 }
2843 "time to compute logarithmic derivative: ");
2844
2845 for (int i= 0; i < sizeBounds; i++)
2846 {
2847 if (bounds [i] + 1 <= (l/2)*degMipo)
2848 {
2849 wasInBounds= true;
2850 int k= tmin (bounds [i] + 1, (l/2)*degMipo);
2851 C= CFMatrix (l*degMipo - k, factors.length() - 1);
2852
2853 for (int ii= 0; ii < factors.length() - 1; ii++)
2854 {
2855 if (A[ii].size() - 1 >= i)
2856 {
2857 if (GF)
2858 {
2859 A [ii] [i]= A [ii] [i] (y-evaluation, y);
2861 A[ii] [i]= GF2FalphaRep (A[ii] [i], alpha);
2862 if (alpha != gamma)
2864 gamma, source, dest
2865 );
2866 buf= getCoeffs (A[ii] [i], k, l, degMipo, gamma, 0, *NTLMat);
2867 }
2868 else
2869 {
2870 A [ii] [i]= A [ii] [i] (y-evaluation, y);
2871 if (alpha != gamma)
2873 gamma, source, dest
2874 );
2875 buf= getCoeffs (A[ii] [i], k, l, degMipo, gamma, 0, *NTLMat);
2876 }
2877 writeInMatrix (C, buf, ii + 1, 0);
2878 }
2879 if (GF)
2881 }
2882
2883 if (GF)
2885
2887 NTLK= (*NTLC)*NTLN;
2888 transpose (NTLK, NTLK);
2889 kernel (NTLK, NTLK);
2890 transpose (NTLK, NTLK);
2891 NTLN *= NTLK;
2892 delete NTLC;
2893
2894 if (GF)
2896
2897 if (NTLN.NumCols() == 1)
2898 {
2899 irreducible= true;
2900 break;
2901 }
2902 if (isReduced (NTLN))
2903 {
2904 reduced= true;
2905 break;
2906 }
2907 }
2908 }
2909
2910 delete NTLMat;
2911
2912 if (NTLN.NumCols() == 1)
2913 {
2914 irreducible= true;
2915 break;
2916 }
2917 if (reduced)
2918 break;
2919 oldL= l;
2920 l += stepSize;
2921 stepSize *= 2;
2922 if (l > liftBound)
2923 {
2924 if (!hitBound)
2925 {
2926 l= liftBound;
2927 hitBound= true;
2928 }
2929 else
2930 break;
2931 }
2932 }
2933 delete [] A;
2934 if (!wasInBounds)
2935 {
2936 if (start)
2937 henselLiftResume12 (F, factors, start, degree (F) + 1, Pi, diophant, M);
2938 else
2939 henselLift12 (F, factors, degree (F) + 1, Pi, diophant, M);
2940 factors.insert (LCF);
2941 }
2942 return l;
2943}
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.

◆ extLiftAndComputeLattice() [2/2]

int extLiftAndComputeLattice ( const CanonicalForm F,
int bounds,
int  sizeBounds,
int  liftBound,
int  minBound,
int  start,
CFList factors,
nmod_mat_t  FLINTN,
CFList diophant,
CFMatrix M,
CFArray Pi,
CFArray bufQ,
bool irreducible,
const CanonicalForm evaluation,
const ExtensionInfo info,
CFList source,
CFList dest 
)

Definition at line 2950 of file facFqBivar.cc.

2957{
2959 CanonicalForm LCF= LC (F, 1);
2960 CFArray *A= new CFArray [factors.length() - 1];
2961 bool wasInBounds= false;
2962 bool hitBound= false;
2963 int degMipo;
2965 alpha= info.getAlpha();
2967
2968 Variable gamma= info.getBeta();
2969 CanonicalForm primElemAlpha= info.getGamma();
2971
2972 int stepSize= 2;
2973 int l= ((minBound+1)/degMipo+1)*2;
2974 l= tmax (l, 2);
2975 if (start > l)
2976 l= start;
2977 int oldL= l/2;
2978 bool reduced= false;
2979 Variable y= F.mvar();
2980 Variable x= Variable (1);
2982 CFMatrix Mat, C;
2983 CFArray buf;
2985 long rank;
2988 while (l <= liftBound)
2989 {
2990 if (start)
2991 {
2992 henselLiftResume12 (F, factors, start, l, Pi, diophant, M);
2993 start= 0;
2994 }
2995 else
2996 {
2997 if (wasInBounds)
2999 else
3000 henselLift12 (F, factors, l, Pi, diophant, M);
3001 }
3002
3003 factors.insert (LCF);
3004
3005 if (GF)
3007
3008 powX= power (y-gamma, l);
3010 for (int i= 0; i < l*degMipo; i++)
3011 {
3012 imBasis= mod (power (y, i), powX);
3013 imBasis= imBasis (power (y, degMipo), y);
3014 imBasis= imBasis (y, gamma);
3015 iter= imBasis;
3016 for (; iter.hasTerms(); iter++)
3017 Mat (iter.exp()+ 1, i+1)= iter.coeff();
3018 }
3019
3024
3025 if (GF)
3027
3028 j= factors;
3029 j++;
3030
3031 truncF= mod (F, power (y, l));
3032 for (int i= 0; i < factors.length() - 1; i++, j++)
3033 {
3034 if (!wasInBounds)
3035 A[i]= logarithmicDerivative (truncF, j.getItem(), l, bufQ[i]);
3036 else
3037 A[i]= logarithmicDerivative (truncF, j.getItem(), l, oldL, bufQ[i],
3038 bufQ[i]);
3039 }
3040
3041 for (int i= 0; i < sizeBounds; i++)
3042 {
3043 if (bounds [i] + 1 <= (l/2)*degMipo)
3044 {
3045 wasInBounds= true;
3046 int k= tmin (bounds [i] + 1, (l/2)*degMipo);
3047 C= CFMatrix (l*degMipo - k, factors.length() - 1);
3048
3049 for (int ii= 0; ii < factors.length() - 1; ii++)
3050 {
3051 if (A[ii].size() - 1 >= i)
3052 {
3053 if (GF)
3054 {
3055 A [ii] [i]= A [ii] [i] (y-evaluation, y);
3057 A[ii] [i]= GF2FalphaRep (A[ii] [i], alpha);
3058 if (alpha != gamma)
3060 gamma, source, dest
3061 );
3062 buf= getCoeffs (A[ii] [i], k, l, degMipo, gamma, 0, FLINTMatInv);
3063 }
3064 else
3065 {
3066 A [ii] [i]= A [ii] [i] (y-evaluation, y);
3067 if (alpha != gamma)
3069 gamma, source, dest
3070 );
3071 buf= getCoeffs (A[ii] [i], k, l, degMipo, gamma, 0, FLINTMatInv);
3072 }
3073 writeInMatrix (C, buf, ii + 1, 0);
3074 }
3075 if (GF)
3077 }
3078
3079 if (GF)
3081
3096 nmod_mat_mul (FLINTN, FLINTC, FLINTK); //no aliasing allowed!!
3097
3101
3102 if (GF)
3104
3105 if (nmod_mat_ncols (FLINTN) == 1)
3106 {
3107 irreducible= true;
3108 break;
3109 }
3110 if (isReduced (FLINTN))
3111 {
3112 reduced= true;
3113 break;
3114 }
3115 }
3116 }
3117
3120
3121 if (nmod_mat_ncols (FLINTN) == 1)
3122 {
3123 irreducible= true;
3124 break;
3125 }
3126 if (reduced)
3127 break;
3128 oldL= l;
3129 l += stepSize;
3130 stepSize *= 2;
3131 if (l > liftBound)
3132 {
3133 if (!hitBound)
3134 {
3135 l= liftBound;
3136 hitBound= true;
3137 }
3138 else
3139 break;
3140 }
3141 }
3142 delete [] A;
3143 if (!wasInBounds)
3144 {
3145 if (start)
3146 henselLiftResume12 (F, factors, start, degree (F) + 1, Pi, diophant, M);
3147 else
3148 henselLift12 (F, factors, degree (F) + 1, Pi, diophant, M);
3149 factors.insert (LCF);
3150 }
3151 return l;
3152}

◆ extractZeroOneVecs() [1/3]

int * extractZeroOneVecs ( const mat_zz_p M)

Definition at line 1527 of file facFqBivar.cc.

1528{
1529 long i, j;
1530 bool nonZeroOne= false;
1531 int * result= new int [M.NumCols()];
1532 for (i = 1; i <= M.NumCols(); i++)
1533 {
1534 for (j = 1; j <= M.NumRows(); j++)
1535 {
1536 if (!(IsOne (M (j,i)) || IsZero (M (j,i))))
1537 {
1538 nonZeroOne= true;
1539 break;
1540 }
1541 }
1542 if (!nonZeroOne)
1543 result [i - 1]= 1;
1544 else
1545 result [i - 1]= 0;
1546 nonZeroOne= false;
1547 }
1548 return result;
1549}
static BOOLEAN IsOne(number a, const coeffs)
Definition flintcf_Q.cc:388

◆ extractZeroOneVecs() [2/3]

int * extractZeroOneVecs ( const mat_zz_pE M)

Definition at line 1579 of file facFqBivar.cc.

1580{
1581 long i, j;
1582 bool nonZeroOne= false;
1583 int * result= new int [M.NumCols()];
1584 for (i = 1; i <= M.NumCols(); i++)
1585 {
1586 for (j = 1; j <= M.NumRows(); j++)
1587 {
1588 if (!(IsOne (M (j,i)) || IsZero (M (j,i))))
1589 {
1590 nonZeroOne= true;
1591 break;
1592 }
1593 }
1594 if (!nonZeroOne)
1595 result [i - 1]= 1;
1596 else
1597 result [i - 1]= 0;
1598 nonZeroOne= false;
1599 }
1600 return result;
1601}

◆ extractZeroOneVecs() [3/3]

int * extractZeroOneVecs ( const nmod_mat_t  M)

Definition at line 1553 of file facFqBivar.cc.

1554{
1555 long i, j;
1556 bool nonZeroOne= false;
1557 int * result= new int [nmod_mat_ncols (M)];
1558 for (i = 0; i < nmod_mat_ncols (M); i++)
1559 {
1560 for (j = 0; j < nmod_mat_nrows (M); j++)
1561 {
1562 if (!((nmod_mat_entry (M, j, i) == 1) || (nmod_mat_entry (M, j,i) == 0)))
1563 {
1564 nonZeroOne= true;
1565 break;
1566 }
1567 }
1568 if (!nonZeroOne)
1569 result [i]= 1;
1570 else
1571 result [i]= 0;
1572 nonZeroOne= false;
1573 }
1574 return result;
1575}

◆ extReconstruction() [1/2]

CFList extReconstruction ( CanonicalForm G,
CFList factors,
int zeroOneVecs,
int  precision,
const mat_zz_p N,
const ExtensionInfo info,
const CanonicalForm evaluation 
)

Definition at line 1962 of file facFqBivar.cc.

1966{
1967 Variable y= Variable (2);
1968 Variable x= Variable (1);
1969 Variable alpha= info.getAlpha();
1970 Variable beta= info.getBeta();
1971 int k= info.getGFDegree();
1972 CanonicalForm gamma= info.getGamma();
1973 CanonicalForm delta= info.getDelta();
1974 CanonicalForm F= G;
1976 CFList result;
1981 for (long i= 1; i <= N.NumCols(); i++)
1982 {
1983 if (zeroOneVecs [i - 1] == 0)
1984 continue;
1985 iter= factors;
1986 buf= 1;
1988 for (long j= 1; j <= N.NumRows(); j++, iter++)
1989 {
1990 if (!IsZero (N (j,i)))
1991 {
1992 factorsConsidered.append (iter.getItem());
1993 buf= mulMod2 (buf, iter.getItem(), yToL);
1994 }
1995 }
1996 buf= mulMod2 (buf, LC (F,x), yToL);
1997 buf /= content (buf, x);
1998 buf2= buf (y-evaluation, y);
1999 buf2 /= Lc (buf2);
2000 if (!k && beta == x)
2001 {
2002 if (degree (buf2, alpha) < 1)
2003 {
2004 if (fdivides (buf, F, quot))
2005 {
2006 F= quot;
2007 F /= Lc (F);
2008 result.append (buf2);
2010 }
2011 }
2012 }
2013 else
2014 {
2015 CFList source, dest;
2016
2017 if (!isInExtension (buf2, gamma, k, delta, source, dest))
2018 {
2019 if (fdivides (buf, F, quot))
2020 {
2021 F= quot;
2022 F /= Lc (F);
2023 result.append (buf2);
2025 }
2026 }
2027 }
2028 if (degree (F) <= 0)
2029 {
2030 G= F;
2032 return result;
2033 }
2034 }
2035 G= F;
2037 return result;
2038}

◆ extReconstruction() [2/2]

CFList extReconstruction ( CanonicalForm G,
CFList factors,
int zeroOneVecs,
int  precision,
const nmod_mat_t  N,
const ExtensionInfo info,
const CanonicalForm evaluation 
)

Definition at line 2043 of file facFqBivar.cc.

2047{
2048 Variable y= Variable (2);
2049 Variable x= Variable (1);
2050 Variable alpha= info.getAlpha();
2051 Variable beta= info.getBeta();
2052 int k= info.getGFDegree();
2053 CanonicalForm gamma= info.getGamma();
2054 CanonicalForm delta= info.getDelta();
2055 CanonicalForm F= G;
2057 CFList result;
2062 for (long i= 0; i < nmod_mat_ncols(N); i++)
2063 {
2064 if (zeroOneVecs [i] == 0)
2065 continue;
2066 iter= factors;
2067 buf= 1;
2069 for (long j= 0; j < nmod_mat_nrows(N); j++, iter++)
2070 {
2071 if (!(nmod_mat_entry (N, j, i) == 0))
2072 {
2073 factorsConsidered.append (iter.getItem());
2074 buf= mulMod2 (buf, iter.getItem(), yToL);
2075 }
2076 }
2077 buf= mulMod2 (buf, LC (F,x), yToL);
2078 buf /= content (buf, x);
2079 buf2= buf (y-evaluation, y);
2080 buf2 /= Lc (buf2);
2081 if (!k && beta == x)
2082 {
2083 if (degree (buf2, alpha) < 1)
2084 {
2085 if (fdivides (buf, F, quot))
2086 {
2087 F= quot;
2088 F /= Lc (F);
2089 result.append (buf2);
2091 }
2092 }
2093 }
2094 else
2095 {
2096 CFList source, dest;
2097
2098 if (!isInExtension (buf2, gamma, k, delta, source, dest))
2099 {
2100 if (fdivides (buf, F, quot))
2101 {
2102 F= quot;
2103 F /= Lc (F);
2104 result.append (buf2);
2106 }
2107 }
2108 }
2109 if (degree (F) <= 0)
2110 {
2111 G= F;
2113 return result;
2114 }
2115 }
2116 G= F;
2118 return result;
2119}

◆ extReconstructionTry() [1/2]

void extReconstructionTry ( CFList reconstructedFactors,
CanonicalForm F,
const CFList factors,
const int  liftBound,
int factorsFound,
int *&  factorsFoundIndex,
mat_zz_p N,
bool  beenInThres,
const ExtensionInfo info,
const CanonicalForm evaluation 
)

Definition at line 2226 of file facFqBivar.cc.

2231{
2232 Variable y= Variable (2);
2233 Variable x= Variable (1);
2234 Variable alpha= info.getAlpha();
2235 Variable beta= info.getBeta();
2236 int k= info.getGFDegree();
2237 CanonicalForm gamma= info.getGamma();
2238 CanonicalForm delta= info.getDelta();
2240 CFList source, dest;
2241 if (factors.length() == 2)
2242 {
2245 tmp2= factors.getLast();
2246 tmp1= mulMod2 (tmp1, LC (F,x), yToL);
2247 tmp1 /= content (tmp1, x);
2248 tmp2= mulMod2 (tmp2, LC (F,x), yToL);
2249 tmp2 /= content (tmp2, x);
2250 tmp3 = tmp1*tmp2;
2251 if (tmp3/Lc (tmp3) == F/Lc (F))
2252 {
2253 tmp1= tmp1 (y - evaluation, y);
2254 tmp2= tmp2 (y - evaluation, y);
2255 tmp1 /= Lc (tmp1);
2256 tmp2 /= Lc (tmp2);
2257 if (!k && beta == x && degree (tmp2, alpha) < 1 &&
2258 degree (tmp1, alpha) < 1)
2259 {
2260 factorsFound++;
2261 F= 1;
2262 tmp1= mapDown (tmp1, info, source, dest);
2263 tmp2= mapDown (tmp2, info, source, dest);
2266 return;
2267 }
2268 else if (!isInExtension (tmp2, gamma, k, delta, source, dest) &&
2269 !isInExtension (tmp1, gamma, k, delta, source, dest))
2270 {
2271 factorsFound++;
2272 F= 1;
2273 tmp1= mapDown (tmp1, info, source, dest);
2274 tmp2= mapDown (tmp2, info, source, dest);
2277 return;
2278 }
2279 }
2280 }
2283 for (long i= 1; i <= N.NumCols(); i++)
2284 {
2285 if (factorsFoundIndex [i - 1] == 1)
2286 continue;
2287 iter= factors;
2288 if (beenInThres)
2289 {
2290 int count= 1;
2291 while (count < i)
2292 {
2293 count++;
2294 iter++;
2295 }
2296 buf= iter.getItem();
2297 }
2298 else
2299 {
2300 buf= 1;
2301 for (long j= 1; j <= N.NumRows(); j++, iter++)
2302 {
2303 if (!IsZero (N (j,i)))
2304 buf= mulMod2 (buf, iter.getItem(), yToL);
2305 }
2306 }
2307 buf= mulMod2 (buf, LC (F,x), yToL);
2308 buf /= content (buf, x);
2309 buf2= buf (y - evaluation, y);
2310 buf2 /= Lc (buf2);
2311 if (!k && beta == x)
2312 {
2313 if (degree (buf2, alpha) < 1)
2314 {
2315 if (fdivides (buf, F, quot))
2316 {
2317 factorsFoundIndex[i - 1]= 1;
2318 factorsFound++;
2319 F= quot;
2320 F /= Lc (F);
2321 buf2= mapDown (buf2, info, source, dest);
2323 }
2324 }
2325 }
2326 else
2327 {
2328 if (!isInExtension (buf2, gamma, k, delta, source, dest))
2329 {
2330 if (fdivides (buf, F, quot))
2331 {
2332 factorsFoundIndex[i - 1]= 1;
2333 factorsFound++;
2334 F= quot;
2335 F /= Lc (F);
2336 buf2= mapDown (buf2, info, source, dest);
2338 }
2339 }
2340 }
2341 if (degree (F) <= 0)
2342 return;
2343 if (factorsFound + 1 == N.NumCols())
2344 {
2345 CanonicalForm tmp= F (y - evaluation, y);
2346 tmp= mapDown (tmp, info, source, dest);
2348 return;
2349 }
2350 }
2351}
int status int void size_t count
Definition si_signals.h:59

◆ extReconstructionTry() [2/2]

void extReconstructionTry ( CFList reconstructedFactors,
CanonicalForm F,
const CFList factors,
const int  liftBound,
int factorsFound,
int *&  factorsFoundIndex,
nmod_mat_t  N,
bool  beenInThres,
const ExtensionInfo info,
const CanonicalForm evaluation 
)

Definition at line 2356 of file facFqBivar.cc.

2361{
2362 Variable y= Variable (2);
2363 Variable x= Variable (1);
2364 Variable alpha= info.getAlpha();
2365 Variable beta= info.getBeta();
2366 int k= info.getGFDegree();
2367 CanonicalForm gamma= info.getGamma();
2368 CanonicalForm delta= info.getDelta();
2370 CFList source, dest;
2371 if (factors.length() == 2)
2372 {
2375 tmp2= factors.getLast();
2376 tmp1= mulMod2 (tmp1, LC (F,x), yToL);
2377 tmp1 /= content (tmp1, x);
2378 tmp2= mulMod2 (tmp2, LC (F,x), yToL);
2379 tmp2 /= content (tmp2, x);
2380 tmp3 = tmp1*tmp2;
2381 if (tmp3/Lc (tmp3) == F/Lc (F))
2382 {
2383 tmp1= tmp1 (y - evaluation, y);
2384 tmp2= tmp2 (y - evaluation, y);
2385 tmp1 /= Lc (tmp1);
2386 tmp2 /= Lc (tmp2);
2387 if (!k && beta == x && degree (tmp2, alpha) < 1 &&
2388 degree (tmp1, alpha) < 1)
2389 {
2390 factorsFound++;
2391 F= 1;
2392 tmp1= mapDown (tmp1, info, source, dest);
2393 tmp2= mapDown (tmp2, info, source, dest);
2396 return;
2397 }
2398 else if (!isInExtension (tmp2, gamma, k, delta, source, dest) &&
2399 !isInExtension (tmp1, gamma, k, delta, source, dest))
2400 {
2401 factorsFound++;
2402 F= 1;
2403 tmp1= mapDown (tmp1, info, source, dest);
2404 tmp2= mapDown (tmp2, info, source, dest);
2407 return;
2408 }
2409 }
2410 }
2413 for (long i= 0; i < nmod_mat_ncols (N); i++)
2414 {
2415 if (factorsFoundIndex [i] == 1)
2416 continue;
2417 iter= factors;
2418 if (beenInThres)
2419 {
2420 int count= 0;
2421 while (count < i)
2422 {
2423 count++;
2424 iter++;
2425 }
2426 buf= iter.getItem();
2427 }
2428 else
2429 {
2430 buf= 1;
2431 for (long j= 0; j < nmod_mat_nrows (N); j++, iter++)
2432 {
2433 if (!(nmod_mat_entry (N, j, i) == 0))
2434 buf= mulMod2 (buf, iter.getItem(), yToL);
2435 }
2436 }
2437 buf= mulMod2 (buf, LC (F,x), yToL);
2438 buf /= content (buf, x);
2439 buf2= buf (y - evaluation, y);
2440 buf2 /= Lc (buf2);
2441 if (!k && beta == x)
2442 {
2443 if (degree (buf2, alpha) < 1)
2444 {
2445 if (fdivides (buf, F, quot))
2446 {
2447 factorsFoundIndex[i]= 1;
2448 factorsFound++;
2449 F= quot;
2450 F /= Lc (F);
2451 buf2= mapDown (buf2, info, source, dest);
2453 }
2454 }
2455 }
2456 else
2457 {
2458 if (!isInExtension (buf2, gamma, k, delta, source, dest))
2459 {
2460 if (fdivides (buf, F, quot))
2461 {
2462 factorsFoundIndex[i]= 1;
2463 factorsFound++;
2464 F= quot;
2465 F /= Lc (F);
2466 buf2= mapDown (buf2, info, source, dest);
2468 }
2469 }
2470 }
2471 if (degree (F) <= 0)
2472 return;
2473 if (factorsFound + 1 == nmod_mat_nrows (N))
2474 {
2475 CanonicalForm tmp= F (y - evaluation, y);
2476 tmp= mapDown (tmp, info, source, dest);
2478 return;
2479 }
2480 }
2481}

◆ extSieveSmallFactors()

CFList extSieveSmallFactors ( const CanonicalForm G,
CFList uniFactors,
DegreePattern degPat,
CanonicalForm H,
CFList diophant,
CFArray Pi,
CFMatrix M,
bool success,
int  d,
const CanonicalForm evaluation,
const ExtensionInfo info 
)

Definition at line 6811 of file facFqBivar.cc.

6816{
6817 CanonicalForm F= G;
6819 bufUniFactors.insert (LC (F, 1));
6820 int smallFactorDeg= d;
6823 int adaptedLiftBound;
6824 success= false;
6825 int * factorsFoundIndex= new int [uniFactors.length()];
6826 for (int i= 0; i < uniFactors.length(); i++)
6827 factorsFoundIndex [i]= 0;
6832 delete [] factorsFoundIndex;
6833 if (degs.getLength() == 1)
6834 {
6835 degPat= degs;
6836 return earlyFactors;
6837 }
6838 if (success)
6839 {
6840 H= F;
6841 return earlyFactors;
6842 }
6843 Variable y= F.mvar();
6844 int sizeOldF= size (G);
6845 if (size (F) < sizeOldF)
6846 {
6847 H= F;
6848 success= true;
6849 return earlyFactors;
6850 }
6851 else
6852 {
6854 return CFList();
6855 }
6856}
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...

◆ 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 as decribed in "Factoring multivariate polynomials over a finite field" by L Bernardin.

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

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

◆ for()

for ( int  j = 1;j<=l;j++,
i++   
)

◆ furtherLiftingAndIncreasePrecision() [1/2]

CFList furtherLiftingAndIncreasePrecision ( CanonicalForm F,
CFList factors,
int  l,
int  liftBound,
int  d,
int bounds,
mat_zz_pE NTLN,
CFList diophant,
CFMatrix M,
CFArray Pi,
CFArray bufQ,
const CanonicalForm eval 
)

Definition at line 5411 of file facFqBivar.cc.

5417{
5418 CanonicalForm LCF= LC (F, 1);
5419 CFList result;
5420 bool irreducible= false;
5423 CFArray *A = new CFArray [bufFactors.length()];
5424 bool useOldQs= false;
5425 bool hitBound= false;
5426 int oldL= l;
5427 int stepSize= 8; //TODO choose better step size?
5428 l += tmax (tmin (8, degree (F) + 1 + degree (LC (F, 1))-l), 2);
5429 if (NTLN.NumRows() != factors.length()) //refined factors
5430 ident (NTLN, factors.length());
5432 CFArray buf;
5435 Variable y= F.mvar();
5436 while (l <= liftBound)
5437 {
5440 j= bufFactors;
5441 truncF= mod (F, power (y, l));
5442 if (useOldQs)
5443 {
5444 for (int i= 0; i < bufFactors.length(); i++, j++)
5445 A[i]= logarithmicDerivative (truncF, j.getItem(), l, oldL, bufQ[i],
5446 bufQ[i]);
5447 }
5448 else
5449 {
5450 for (int i= 0; i < bufFactors.length(); i++, j++)
5451 A[i]= logarithmicDerivative (truncF, j.getItem(), l, bufQ [i]);
5452 }
5453 for (int i= 0; i < d; i++)
5454 {
5455 if (bounds [i] + 1 <= l/2)
5456 {
5457 int k= tmin (bounds [i] + 1, l/2);
5459 for (int ii= 0; ii < bufFactors.length(); ii++)
5460 {
5461 if (A[ii].size() - 1 >= i)
5462 {
5463 buf= getCoeffs (A[ii] [i], k);
5464 writeInMatrix (C, buf, ii + 1, 0);
5465 }
5466 }
5468 NTLK= (*NTLC)*NTLN;
5469 transpose (NTLK, NTLK);
5470 kernel (NTLK, NTLK);
5471 transpose (NTLK, NTLK);
5472 NTLN *= NTLK;
5473 delete NTLC;
5474 if (NTLN.NumCols() == 1)
5475 {
5476 irreducible= true;
5477 break;
5478 }
5479 }
5480 }
5481 if (NTLN.NumCols() == 1)
5482 {
5483 irreducible= true;
5484 break;
5485 }
5486
5488 bufF= F;
5491 delete [] zeroOneVecs;
5492 if (result.length() > 0 && degree (bufF) + 1 + degree (LC (bufF, 1)) <= l)
5493 {
5494 F= bufF;
5496 delete [] A;
5497 return result;
5498 }
5499 else
5500 {
5501 bufF= F;
5503 }
5504
5505 if (isReduced (NTLN))
5506 {
5507 int factorsFound= 0;
5508 bufF= F;
5509 int* factorsFoundIndex= new int [NTLN.NumCols()];
5510 for (long i= 0; i < NTLN.NumCols(); i++)
5511 factorsFoundIndex[i]= 0;
5512 if (l < liftBound)
5514 factorsFoundIndex, NTLN, eval, false
5515 );
5516 else
5519 NTLN, eval, false
5520 );
5521 if (NTLN.NumCols() == result.length())
5522 {
5523 delete [] A;
5524 delete [] factorsFoundIndex;
5525 return result;
5526 }
5527 delete [] factorsFoundIndex;
5528 }
5529 result= CFList();
5530 oldL= l;
5531 stepSize *= 2;
5532 l += stepSize;
5533 if (l > liftBound)
5534 {
5535 if (!hitBound)
5536 {
5537 l= liftBound;
5538 hitBound= true;
5539 }
5540 else
5541 break;
5542 }
5543 }
5544 if (irreducible)
5545 {
5546 delete [] A;
5547 return CFList (F (y-eval,y));
5548 }
5549 delete [] A;
5551 return CFList();
5552}
mat_zz_pE * convertFacCFMatrix2NTLmat_zz_pE(const CFMatrix &m)
CFList reconstruction(CanonicalForm &G, CFList &factors, int *zeroOneVecs, int precision, const mat_zz_pE &N, const CanonicalForm &eval)

◆ furtherLiftingAndIncreasePrecision() [2/2]

CFList furtherLiftingAndIncreasePrecision ( CanonicalForm F,
CFList factors,
int  l,
int  liftBound,
int  d,
int bounds,
nmod_mat_t  FLINTN,
CFList diophant,
CFMatrix M,
CFArray Pi,
CFArray bufQ,
const CanonicalForm eval 
)

Definition at line 5176 of file facFqBivar.cc.

5191{
5192 CanonicalForm LCF= LC (F, 1);
5193 CFList result;
5194 bool irreducible= false;
5197 CFArray *A = new CFArray [bufFactors.length()];
5198 bool useOldQs= false;
5199 bool hitBound= false;
5200 int oldL= l;
5201 int stepSize= 8; //TODO choose better step size?
5202 l += tmax (tmin (8, degree (F) + 1 + degree (LC (F, 1))-l), 2);
5203#ifdef HAVE_FLINT
5204 if (nmod_mat_nrows (FLINTN) != factors.length()) //refined factors
5205 {
5208 for (long i=factors.length()-1; i >= 0; i--)
5209 nmod_mat_entry (FLINTN, i, i)= 1;
5210 }
5211#else
5212 if (NTLN.NumRows() != factors.length()) //refined factors
5213 ident (NTLN, factors.length());
5214#endif
5216 CFMatrix C;
5217 CFArray buf;
5218#ifdef HAVE_FLINT
5219 long rank;
5221#else
5222 mat_zz_p* NTLC, NTLK;
5223#endif
5225 Variable y= F.mvar();
5226 while (l <= liftBound)
5227 {
5230 j= bufFactors;
5231 truncF= mod (F, power (y, l));
5232 if (useOldQs)
5233 {
5234 for (int i= 0; i < bufFactors.length(); i++, j++)
5235 A[i]= logarithmicDerivative (truncF, j.getItem(), l, oldL, bufQ[i],
5236 bufQ[i]);
5237 }
5238 else
5239 {
5240 for (int i= 0; i < bufFactors.length(); i++, j++)
5241 A[i]= logarithmicDerivative (truncF, j.getItem(), l, bufQ [i]);
5242 }
5243 for (int i= 0; i < d; i++)
5244 {
5245 if (bounds [i] + 1 <= l/2)
5246 {
5247 int k= tmin (bounds [i] + 1, l/2);
5248 C= CFMatrix (l - k, bufFactors.length());
5249 for (int ii= 0; ii < bufFactors.length(); ii++)
5250 {
5251 if (A[ii].size() - 1 >= i)
5252 {
5253 buf= getCoeffs (A[ii] [i], k);
5254 writeInMatrix (C, buf, ii + 1, 0);
5255 }
5256 }
5257#ifdef HAVE_FLINT
5272 nmod_mat_mul (FLINTN, FLINTC, FLINTK); //no aliasing allowed!!
5273
5277#else
5279 NTLK= (*NTLC)*NTLN;
5280 transpose (NTLK, NTLK);
5281 kernel (NTLK, NTLK);
5282 transpose (NTLK, NTLK);
5283 NTLN *= NTLK;
5284 delete NTLC;
5285#endif
5286#ifdef HAVE_FLINT
5287 if (nmod_mat_ncols (FLINTN) == 1)
5288#else
5289 if (NTLN.NumCols() == 1)
5290#endif
5291 {
5292 irreducible= true;
5293 break;
5294 }
5295 }
5296 }
5297
5298#ifdef HAVE_FLINT
5299 if (nmod_mat_ncols (FLINTN) == 1)
5300#else
5301 if (NTLN.NumCols() == 1)
5302#endif
5303 {
5304 irreducible= true;
5305 break;
5306 }
5307
5308#ifdef HAVE_FLINT
5310#else
5312#endif
5313 bufF= F;
5315#ifdef HAVE_FLINT
5317#else
5319#endif
5320 delete [] zeroOneVecs;
5321 if (result.length() > 0 && degree (bufF) + 1 + degree (LC (bufF, 1)) <= l)
5322 {
5323 F= bufF;
5325 delete [] A;
5326 return result;
5327 }
5328 else
5329 {
5330 bufF= F;
5332 }
5333
5334#ifdef HAVE_FLINT
5335 if (isReduced (FLINTN))
5336#else
5337 if (isReduced (NTLN))
5338#endif
5339 {
5340 int factorsFound= 0;
5341 bufF= F;
5342#ifdef HAVE_FLINT
5343 int* factorsFoundIndex= new int [nmod_mat_ncols (FLINTN)];
5344 for (long i= 0; i < nmod_mat_ncols (FLINTN); i++)
5345#else
5346 int* factorsFoundIndex= new int [NTLN.NumCols()];
5347 for (long i= 0; i < NTLN.NumCols(); i++)
5348#endif
5349 factorsFoundIndex[i]= 0;
5350#ifdef HAVE_FLINT
5351 if (l < liftBound)
5354 );
5355 else
5358 FLINTN, eval, false
5359 );
5360
5362#else
5363 if (l < liftBound)
5365 factorsFoundIndex, NTLN, eval, false
5366 );
5367 else
5370 NTLN, eval, false
5371 );
5372
5373 if (NTLN.NumCols() == result.length())
5374#endif
5375 {
5376 delete [] A;
5377 delete [] factorsFoundIndex;
5378 return result;
5379 }
5380 delete [] factorsFoundIndex;
5381 }
5382 result= CFList();
5383 oldL= l;
5384 stepSize *= 2;
5385 l += stepSize;
5386 if (l > liftBound)
5387 {
5388 if (!hitBound)
5389 {
5390 l= liftBound;
5391 hitBound= true;
5392 }
5393 else
5394 break;
5395 }
5396 }
5397 if (irreducible)
5398 {
5399 delete [] A;
5400 return CFList (F (y-eval,y));
5401 }
5402 delete [] A;
5404 return CFList();
5405}

◆ furtherLiftingAndIncreasePrecisionFq2Fp()

CFList furtherLiftingAndIncreasePrecisionFq2Fp ( CanonicalForm F,
CFList factors,
int  l,
int  liftBound,
int  d,
int bounds,
nmod_mat_t  FLINTN,
CFList diophant,
CFMatrix M,
CFArray Pi,
CFArray bufQ,
const Variable alpha,
const CanonicalForm eval 
)

Definition at line 5875 of file facFqBivar.cc.

5892{
5893 CanonicalForm LCF= LC (F, 1);
5894 CFList result;
5895 bool irreducible= false;
5898 CFArray *A = new CFArray [bufFactors.length()];
5899 bool useOldQs= false;
5901 bool hitBound= false;
5902 int oldL= l;
5903 int stepSize= 8; //TODO choose better step size?
5904 l += tmax (tmin (8, degree (F) + 1 + degree (LC (F, 1))-l), 2);
5905#ifdef HAVE_FLINT
5906 if (nmod_mat_nrows (FLINTN) != factors.length()) //refined factors
5907 {
5910 for (long i=factors.length()-1; i >= 0; i--)
5911 nmod_mat_entry (FLINTN, i, i)= 1;
5912 }
5913#else
5914 if (NTLN.NumRows() != factors.length()) //refined factors
5915 ident (NTLN, factors.length());
5916#endif
5918 CFMatrix C;
5919#ifdef HAVE_FLINT
5920 long rank;
5922#else
5923 mat_zz_p* NTLC, NTLK;
5924#endif
5926 Variable y= F.mvar();
5927 while (l <= liftBound)
5928 {
5931 j= bufFactors;
5932 truncF= mod (F, power (y, l));
5933 if (useOldQs)
5934 {
5935 for (int i= 0; i < bufFactors.length(); i++, j++)
5936 A[i]= logarithmicDerivative (truncF, j.getItem(), l, oldL, bufQ[i],
5937 bufQ[i]);
5938 }
5939 else
5940 {
5941 for (int i= 0; i < bufFactors.length(); i++, j++)
5942 A[i]= logarithmicDerivative (truncF, j.getItem(), l, bufQ [i]);
5943 }
5944 for (int i= 0; i < d; i++)
5945 {
5946 if (bounds [i] + 1 <= l/2)
5947 {
5948 int k= tmin (bounds [i] + 1, l/2);
5950 for (int ii= 0; ii < bufFactors.length(); ii++)
5951 {
5952 CFArray buf;
5953 if (A[ii].size() - 1 >= i)
5954 {
5955 buf= getCoeffs (A[ii] [i], k, alpha);
5956 writeInMatrix (C, buf, ii + 1, 0);
5957 }
5958 }
5959#ifdef HAVE_FLINT
5974 nmod_mat_mul (FLINTN, FLINTC, FLINTK); //no aliasing allowed!!
5975
5979#else
5981 NTLK= (*NTLC)*NTLN;
5982 transpose (NTLK, NTLK);
5983 kernel (NTLK, NTLK);
5984 transpose (NTLK, NTLK);
5985 NTLN *= NTLK;
5986 delete NTLC;
5987#endif
5988#ifdef HAVE_FLINT
5989 if (nmod_mat_ncols (FLINTN) == 1)
5990#else
5991 if (NTLN.NumCols() == 1)
5992#endif
5993 {
5994 irreducible= true;
5995 break;
5996 }
5997 }
5998 }
5999#ifdef HAVE_FLINT
6000 if (nmod_mat_ncols (FLINTN) == 1)
6001#else
6002 if (NTLN.NumCols() == 1)
6003#endif
6004 {
6005 irreducible= true;
6006 break;
6007 }
6008
6009#ifdef HAVE_FLINT
6011#else
6013#endif
6016#ifdef HAVE_FLINT
6018#else
6020#endif
6021 delete [] zeroOneVecs;
6022 if (result.length() > 0 && degree (bufF) + 1 + degree (LC (bufF, 1)) <= l)
6023 {
6024 F= bufF;
6026 delete [] A;
6027 return result;
6028 }
6029 else
6030 {
6031 bufF= F;
6033 }
6034
6035#ifdef HAVE_FLINT
6036 if (isReduced (FLINTN))
6037#else
6038 if (isReduced (NTLN))
6039#endif
6040 {
6041 int factorsFound= 0;
6042 bufF= F;
6043#ifdef HAVE_FLINT
6044 int* factorsFoundIndex= new int [nmod_mat_ncols (FLINTN)];
6045 for (long i= 0; i < nmod_mat_ncols (FLINTN); i++)
6046#else
6047 int* factorsFoundIndex= new int [NTLN.NumCols()];
6048 for (long i= 0; i < NTLN.NumCols(); i++)
6049#endif
6050 factorsFoundIndex[i]= 0;
6051#ifdef HAVE_FLINT
6052 if (l < degree (bufF) + 1 + degree (LCF))
6055 );
6056 else
6059 FLINTN, eval, false
6060 );
6062#else
6063 if (l < degree (bufF) + 1 + degree (LCF))
6065 factorsFoundIndex, NTLN, eval, false
6066 );
6067 else
6070 NTLN, eval, false
6071 );
6072 if (NTLN.NumCols() == result.length())
6073#endif
6074 {
6075 delete [] A;
6076 delete [] factorsFoundIndex;
6077 return result;
6078 }
6079 delete [] factorsFoundIndex;
6080 }
6081 result= CFList();
6082 oldL= l;
6083 stepSize *= 2;
6084 l += stepSize;
6085 if (l > liftBound)
6086 {
6087 if (!hitBound)
6088 {
6089 l= liftBound;
6090 hitBound= true;
6091 }
6092 else
6093 break;
6094 }
6095 }
6096 if (irreducible)
6097 {
6098 delete [] A;
6099 return CFList (F (y-eval,y));
6100 }
6101 delete [] A;
6103 return CFList();
6104}

◆ getCombinations()

int * getCombinations ( int rightSide,
int  sizeOfRightSide,
int sizeOfOutput,
int  degreeLC 
)

Definition at line 1083 of file facFqBivar.cc.

1085{
1086 Variable x= Variable (1);
1087 int p= getCharacteristic();
1088 int d= getGFDegree();
1089 char cGFName= gf_name;
1091 CanonicalForm buf= 1;
1092 for (int i= 0; i < sizeOfRightSide; i++)
1093 buf *= (power (x, rightSide [i]) + 1);
1094
1095 int j= 0;
1096 for (CFIterator i= buf; i.hasTerms(); i++, j++)
1097 {
1098 if (i.exp() < degreeLC)
1099 {
1100 j++;
1101 break;
1102 }
1103 }
1104
1105 ASSERT ( j > 1, "j > 1 expected" );
1106
1107 int* result = new int [j - 1];
1108 sizeOfOutput= j - 1;
1109
1110 int i= 0;
1111 for (CFIterator m = buf; i < j - 1; i++, m++)
1112 result [i]= m.exp();
1113
1114 if (d > 1)
1116 else
1118 return result;
1119}
VAR char gf_name
Definition gfops.cc:52

◆ getLast()

else L getLast ( )

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

1123{
1124 int sizeOfNewtonPoly;
1126 int sizeOfRightSide;
1129 degreeLC);
1130 delete [] rightSide;
1131 for (int i= 0; i < sizeOfNewtonPoly; i++)
1132 delete [] newtonPolyg[i];
1133 delete [] newtonPolyg;
1134 return result;
1135}
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 * getCombinations(int *rightSide, int sizeOfRightSide, int &sizeOfOutput, int degreeLC)

◆ henselLiftAndEarly() [1/2]

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

hensel Lifting and early factor detection

Returns
henselLiftAndEarly returns monic (wrt Variable (1)) lifted factors without factors which have been detected at an early stage of Hensel lifting
See also
earlyFactorDetection(), extEarlyFactorDetection()
Parameters
[in,out]Apoly to be factored, returns poly divided by detected factors in case of success
[in,out]earlySuccessindicating success
[in,out]earlyFactorslist of factors detected at early stage of Hensel lifting
[in,out]degsdegree pattern
[in,out]liftBound(adapted) lift bound
[in]uniFactorsunivariate factors
[in]infoinformation about extension
[in]evalevaluation point

Definition at line 1457 of file facFqBivar.cc.

1461{
1462 modpk dummy= modpk();
1463 CanonicalForm den= 1;
1466}
class to do operations mod p^k for int's p and k
Definition fac_util.h:23

◆ henselLiftAndEarly() [2/2]

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

hensel Lifting and early factor detection

Returns
henselLiftAndEarly returns monic (wrt Variable (1)) lifted factors without factors which have been detected at an early stage of Hensel lifting
See also
earlyFactorDetection(), extEarlyFactorDetection()
Parameters
[in,out]Apoly to be factored, returns poly divided by detected factors in case of success
[in,out]earlySuccessindicating success
[in,out]earlyFactorslist of factors detected at early stage of Hensel lifting
[in,out]degsdegree pattern
[in,out]liftBound(adapted) lift bound
[in]uniFactorsunivariate factors
[in]infoinformation about extension
[in]evalevaluation point
[in]bcoeff bound
[in]denbound on the den if over Q(a)

Definition at line 1154 of file facFqBivar.cc.

1158{
1159 Variable alpha= info.getAlpha();
1160 Variable beta= info.getBeta();
1161 CanonicalForm gamma= info.getGamma();
1162 CanonicalForm delta= info.getDelta();
1163 bool extension= info.isInExtension();
1164
1165 int sizeOfLiftPre;
1166 int * liftPre= getLiftPrecisions (A, sizeOfLiftPre, degree (LC (A, 1), 2));
1167
1168 Variable x= Variable (1);
1169 Variable y= Variable (2);
1170 CFArray Pi;
1173 On (SW_RATIONAL);
1175 if (!Lc (A).inBaseDomain())
1176 {
1177 bufA /= Lc (A);
1179 bufA *= denBufA;
1180 Off (SW_RATIONAL);
1181 den /= gcd (den, denBufA);
1182 }
1183 else
1184 {
1185 bufA= A;
1186 Off (SW_RATIONAL);
1187 den /= gcd (den, Lc (A));
1188 }
1190 bool mipoHasDen= false;
1191 if (getCharacteristic() == 0 && b.getp() != 0)
1192 {
1193 if (alpha.level() == 1)
1194 {
1195 lcA0= lc (A (0, 2));
1196 A *= b.inverse (lcA0);
1197 A= b (A);
1199 i.getItem()= b (i.getItem()*b.inverse (lc (i.getItem())));
1200 }
1201 else
1202 {
1203 lcA0= Lc (A (0,2));
1204 On (SW_RATIONAL);
1206 Off (SW_RATIONAL);
1207 CanonicalForm lcA0inverse= b.inverse (lcA0);
1208 A *= lcA0inverse;
1209 A= b (A);
1210 // Lc of bufUniFactors is in Z
1212 i.getItem()= b (i.getItem()*b.inverse (lc (i.getItem())));
1213 }
1214 }
1215 bufUniFactors.insert (LC (A, x));
1217 earlySuccess= false;
1218 int newLiftBound= 0;
1219
1220 int smallFactorDeg= tmin (11, liftPre [sizeOfLiftPre- 1] + 1);//this is a tunable parameter
1221 int dummy;
1222 int * factorsFoundIndex= new int [uniFactors.length()];
1223 for (int i= 0; i < uniFactors.length(); i++)
1224 factorsFoundIndex [i]= 0;
1225
1227 Variable v= alpha;
1228 if (smallFactorDeg >= liftBound || degree (A,y) <= 4)
1230 else if (sizeOfLiftPre > 1 && sizeOfLiftPre < 30)
1231 {
1233 if (mipoHasDen)
1234 {
1235 for (CFListIterator iter= bufUniFactors; iter.hasItem(); iter++)
1236 if (hasFirstAlgVar (iter.getItem(), v))
1237 break;
1238 if (v != alpha)
1239 {
1241 for (CFListIterator iter= bufBufUniFactors; iter.hasItem(); iter++)
1242 iter.getItem()= replacevar (iter.getItem(), v, alpha);
1243 A= replacevar (A, alpha, v);
1244 }
1245 }
1246
1247 if (!extension)
1248 {
1249 if (v==alpha)
1253 else
1257 }
1258 else
1262 if (degs.getLength() > 1 && !earlySuccess &&
1264 {
1266 {
1267 bufUniFactors.insert (LC (A, x));
1269 liftPre[sizeOfLiftPre-1] + 1, Pi, diophant, M, b);
1270 if (v!=alpha)
1271 {
1273 for (CFListIterator iter= bufBufUniFactors; iter.hasItem(); iter++)
1274 iter.getItem()= replacevar (iter.getItem(), v, alpha);
1275 }
1276 if (!extension)
1277 {
1278 if (v==alpha)
1281 liftPre[sizeOfLiftPre-1] + 1, eval, b, den);
1282 else
1285 liftPre[sizeOfLiftPre-1] + 1, eval, b, den);
1286 }
1287 else
1290 eval, liftPre[sizeOfLiftPre-1] + 1);
1291 }
1292 }
1293 else if (earlySuccess)
1295
1296 int i= sizeOfLiftPre - 1;
1297 while (degs.getLength() > 1 && !earlySuccess && i - 1 >= 0)
1298 {
1299 if (newLiftBound >= liftPre[i] + 1)
1300 {
1301 bufUniFactors.insert (LC (A, x));
1303 liftPre[i-1] + 1, Pi, diophant, M, b);
1304 if (v!=alpha)
1305 {
1307 for (CFListIterator iter= bufBufUniFactors; iter.hasItem(); iter++)
1308 iter.getItem()= replacevar (iter.getItem(), v, alpha);
1309 }
1310 if (!extension)
1311 {
1312 if (v==alpha)
1315 liftPre[i-1] + 1, eval, b, den);
1316 else
1319 liftPre[i-1] + 1, eval, b, den);
1320 }
1321 else
1324 eval, liftPre[i-1] + 1);
1325 }
1326 else
1327 {
1329 break;
1330 }
1331 i--;
1332 }
1333 if (earlySuccess)
1335 //after here all factors are lifted to liftPre[sizeOfLiftPre-1]
1336 }
1337 else
1338 {
1340 if (mipoHasDen)
1341 {
1342 for (CFListIterator iter= bufUniFactors; iter.hasItem(); iter++)
1343 if (hasFirstAlgVar (iter.getItem(), v))
1344 break;
1345 if (v != alpha)
1346 {
1348 for (CFListIterator iter= bufBufUniFactors; iter.hasItem(); iter++)
1349 iter.getItem()= replacevar (iter.getItem(), v, alpha);
1350 A= replacevar (A, alpha, v);
1351 }
1352 }
1353 if (!extension)
1354 {
1355 if (v==alpha)
1359 else
1363 }
1364 else
1368 int i= 1;
1369 while ((degree (A,y)/4)*i + 4 <= smallFactorDeg)
1370 i++;
1371 dummy= tmin (degree (A,y)+1, (degree (A,y)/4)*i+4);
1372 if (degs.getLength() > 1 && !earlySuccess && dummy > smallFactorDeg)
1373 {
1374 bufUniFactors.insert (LC (A, x));
1376 dummy, Pi, diophant, M, b);
1377 if (v!=alpha)
1378 {
1380 for (CFListIterator iter= bufBufUniFactors; iter.hasItem(); iter++)
1381 iter.getItem()= replacevar (iter.getItem(), v, alpha);
1382 }
1383 if (!extension)
1384 {
1385 if (v==alpha)
1388 b, den);
1389 else
1392 b, den);
1393 }
1394 else
1397 eval, dummy);
1398 }
1399 while (degs.getLength() > 1 && !earlySuccess && i < 4)
1400 {
1401 if (newLiftBound >= dummy)
1402 {
1403 bufUniFactors.insert (LC (A, x));
1404 dummy= tmin (degree (A,y)+1, (degree (A,y)/4)*(i+1)+4);
1406 dummy, Pi, diophant, M, b);
1407 if (v!=alpha)
1408 {
1410 for (CFListIterator iter= bufBufUniFactors; iter.hasItem(); iter++)
1411 iter.getItem()= replacevar (iter.getItem(), v, alpha);
1412 }
1413 if (!extension)
1414 {
1415 if (v==alpha)
1418 eval, b, den);
1419 else
1422 eval, b, den);
1423 }
1424 else
1427 eval, dummy);
1428 }
1429 else
1430 {
1432 break;
1433 }
1434 i++;
1435 }
1436 if (earlySuccess)
1438 }
1439
1440 A= bufA;
1441 if (earlyFactors.length() > 0 && degs.getLength() > 1)
1442 {
1443 liftBound= degree (A,y) + 1;
1444 earlySuccess= true;
1446 }
1447
1448 delete [] factorsFoundIndex;
1449 delete [] liftPre;
1450
1451 return bufUniFactors;
1452}
CanonicalForm FACTORY_PUBLIC replacevar(const CanonicalForm &, const Variable &, const Variable &)
CanonicalForm replacevar ( const CanonicalForm & f, const Variable & x1, const Variable & x2 )
Definition cf_ops.cc:271
bool hasFirstAlgVar(const CanonicalForm &f, Variable &a)
check if poly f contains an algebraic variable a
Definition cf_ops.cc:679
CF_NO_INLINE bool isOne() const
void deleteFactors(CFList &factors, int *factorsFoundIndex)

◆ henselLiftAndLatticeRecombi()

CFList henselLiftAndLatticeRecombi ( const CanonicalForm G,
const CFList uniFactors,
const Variable alpha,
const DegreePattern degPat,
bool  symmetric,
const CanonicalForm eval 
)

Definition at line 6861 of file facFqBivar.cc.

6865{
6867 CanonicalForm F= G;
6868 CanonicalForm LCF= LC (F, 1);
6869 Variable y= F.mvar();
6870 Variable x= Variable (1);
6871 int d;
6872 bool isIrreducible= false;
6873 int* bounds= computeBounds (F, d, isIrreducible);
6874 if (isIrreducible)
6875 {
6876 delete [] bounds;
6877 return CFList (G);
6878 }
6879 int minBound= bounds[0];
6880 for (int i= 1; i < d; i++)
6881 {
6882 if (bounds[i] != 0)
6884 }
6885
6887 CFArray Pi;
6889 int liftBound= 2*totaldegree (F) - 1;
6891
6894 bool success= false;
6896 success, minBound + 1, eval
6897 );
6898
6899 if (smallFactors.length() > 0)
6900 {
6901 if (smallFactors.length() == 1)
6902 {
6903 if (smallFactors.getFirst() == F)
6904 {
6905 delete [] bounds;
6906 return CFList (G (y-eval,y));
6907 }
6908 }
6909 if (degs.getLength() <= 1)
6910 {
6911 delete [] bounds;
6912 return smallFactors;
6913 }
6914 }
6915
6916 int index;
6918 for (CFListIterator i= smallFactors; i.hasItem(); i++)
6919 {
6920 index= 1;
6921 tmp1= mod (i.getItem(),y-eval);
6922 tmp1 /= Lc (tmp1);
6923 for (CFListIterator j= bufUniFactors; j.hasItem(); j++, index++)
6924 {
6925 tmp2= mod (j.getItem(), y);
6926 tmp2 /= Lc (tmp2);
6927 if (tmp1 == tmp2)
6928 {
6929 index++;
6930 j.remove(index);
6931 break;
6932 }
6933 }
6934 }
6935
6936 if (bufUniFactors.isEmpty())
6937 {
6938 delete [] bounds;
6939 return smallFactors;
6940 }
6941
6942 if (success)
6943 {
6944 F= H;
6945 delete [] bounds;
6947 if (isIrreducible)
6948 {
6949 smallFactors.append (F (y-eval,y));
6950 delete [] bounds;
6951 return smallFactors;
6952 }
6953 LCF= LC (F, 1);
6954
6955 minBound= bounds[0];
6956 for (int i= 1; i < d; i++)
6957 {
6958 if (bounds[i] != 0)
6960 }
6961 Pi= CFArray();
6962 diophant= CFList();
6963 liftBound= 2*totaldegree (F) - 1;
6966 degs.intersect (bufDegs);
6967 degs.refine();
6968 if (degs.getLength() <= 1)
6969 {
6970 smallFactors.append (F (y-eval,y));
6971 delete [] bounds;
6972 return smallFactors;
6973 }
6974 }
6975
6976 bool reduceFq2Fp= (degree (F) > getCharacteristic());
6978 int l= 1;
6979
6980#ifdef HAVE_FLINT
6982#endif
6983
6985 {
6987 zz_p::init (getCharacteristic());
6988 }
6989 mat_zz_p NTLN;
6990
6991 if (alpha.level() != 1)
6992 {
6994 zz_pE::init (NTLMipo);
6995 }
6997
6998 if (alpha.level() == 1)
6999 {
7000#ifdef HAVE_FLINT
7002 for (long i= bufUniFactors.length()-2; i >= 0; i--)
7003 nmod_mat_entry (FLINTN, i, i)= 1;
7004#else
7005 ident (NTLN, bufUniFactors.length() - 1);
7006#endif
7007 }
7008 else
7009 {
7010 if (reduceFq2Fp)
7011#ifdef HAVE_FLINT
7012 {
7014 for (long i= bufUniFactors.length()-2; i >= 0; i--)
7015 nmod_mat_entry (FLINTN, i, i)= 1;
7016 }
7017#else
7018 ident (NTLN, bufUniFactors.length() - 1);
7019#endif
7020 else
7022 }
7023 bool irreducible= false;
7025
7026 int oldL;
7028 if (success)
7029 {
7030 int start= 0;
7031 if (alpha.level() == 1)
7035#else
7037#endif
7039 );
7040 else
7041 {
7042 if (reduceFq2Fp)
7046#else
7048#endif
7050 alpha
7051 );
7052 else
7056 );
7057 }
7058 }
7059 else
7060 {
7061 if (alpha.level() == 1)
7062 {
7066#else
7068#endif
7070 );
7071 }
7072 else
7073 {
7074 if (reduceFq2Fp)
7078 FLINTN, diophant, M, Pi, bufQ,
7079#else
7080 NTLN, diophant, M, Pi, bufQ,
7081#endif
7083 );
7084 else
7087 M, Pi, bufQ, irreducible
7088 );
7089 }
7090 }
7091
7093 "time to compute a reduced lattice: ");
7095 if (oldL > liftBound)
7096 {
7097#ifdef HAVE_FLINT
7098 if (alpha.level() == 1 || (alpha.level() != 1 && reduceFq2Fp))
7100#endif
7101 delete [] bounds;
7102 return Union (smallFactors,
7104 power (y, degree (F) + 1),
7105 degs, eval, 1, bufUniFactors.length()/2
7106 )
7107 );
7108 }
7109
7110 l= oldL;
7111 if (irreducible)
7112 {
7113#ifdef HAVE_FLINT
7114 if (alpha.level() == 1 || (alpha.level() != 1 && reduceFq2Fp))
7116#endif
7117 delete [] bounds;
7118 return Union (CFList (F(y-eval,y)), smallFactors);
7119 }
7120
7122
7123 CFList result;
7124 if (l >= degree (F) + 1)
7125 {
7126 int * factorsFoundIndex;
7127 if (alpha.level() == 1 || (alpha.level() != 1 && reduceFq2Fp))
7128 {
7129#ifdef HAVE_FLINT
7131 for (long i= 0; i < nmod_mat_ncols (FLINTN); i++)
7132#else
7133 factorsFoundIndex= new int [NTLN.NumCols()];
7134 for (long i= 0; i < NTLN.NumCols(); i++)
7135#endif
7136 factorsFoundIndex[i]= 0;
7137 }
7138 else
7139 {
7140 factorsFoundIndex= new int [NTLNe.NumCols()];
7141 for (long i= 0; i < NTLNe.NumCols(); i++)
7142 factorsFoundIndex[i]= 0;
7143 }
7144 int factorsFound= 0;
7146 if (alpha.level() == 1 || (alpha.level() != 1 && reduceFq2Fp))
7150#else
7152#endif
7153 );
7154 else
7157 );
7158 if (alpha.level() == 1 || (alpha.level() != 1 && reduceFq2Fp))
7159 {
7160#ifdef HAVE_FLINT
7161 if (result.length() == nmod_mat_ncols (FLINTN))
7162 {
7163 if (alpha.level() == 1 || (alpha.level() != 1 && reduceFq2Fp))
7165#else
7166 if (result.length() == NTLN.NumCols())
7167 {
7168#endif
7169 delete [] factorsFoundIndex;
7170 delete [] bounds;
7171 return Union (result, smallFactors);
7172 }
7173 }
7174 else
7175 {
7176 if (result.length() == NTLNe.NumCols())
7177 {
7178 delete [] factorsFoundIndex;
7179 delete [] bounds;
7180 return Union (result, smallFactors);
7181 }
7182 }
7183 delete [] factorsFoundIndex;
7184 }
7185 if (l >= liftBound)
7186 {
7187 int * factorsFoundIndex;
7188 if (alpha.level() == 1 || (alpha.level() != 1 && reduceFq2Fp))
7189 {
7190#ifdef HAVE_FLINT
7192 for (long i= 0; i < nmod_mat_ncols (FLINTN); i++)
7193#else
7194 factorsFoundIndex= new int [NTLN.NumCols()];
7195 for (long i= 0; i < NTLN.NumCols(); i++)
7196#endif
7197 factorsFoundIndex[i]= 0;
7198 }
7199 else
7200 {
7201 factorsFoundIndex= new int [NTLNe.NumCols()];
7202 for (long i= 0; i < NTLNe.NumCols(); i++)
7203 factorsFoundIndex[i]= 0;
7204 }
7206 int factorsFound= 0;
7207 if (alpha.level() == 1 || (alpha.level() != 1 && reduceFq2Fp))
7211#else
7213#endif
7214 );
7215 else
7218 );
7219 if (alpha.level() == 1 || (alpha.level() != 1 && reduceFq2Fp))
7220 {
7221#ifdef HAVE_FLINT
7222 if (result.length() == nmod_mat_ncols(FLINTN))
7223 {
7225#else
7226 if (result.length() == NTLN.NumCols())
7227 {
7228#endif
7229 delete [] factorsFoundIndex;
7230 delete [] bounds;
7231 return Union (result, smallFactors);
7232 }
7233 }
7234 else
7235 {
7236 if (result.length() == NTLNe.NumCols())
7237 {
7238 delete [] factorsFoundIndex;
7239 delete [] bounds;
7240 return Union (result, smallFactors);
7241 }
7242 }
7243 delete [] factorsFoundIndex;
7244 }
7245
7246 result= CFList();
7247 bool beenInThres= false;
7248 int thres= 100;
7249 if (l <= thres)
7250 {
7251 if (alpha.level() == 1 || (alpha.level() != 1 && reduceFq2Fp))
7252 {
7253#ifdef HAVE_FLINT
7255 {
7257#else
7258 if (NTLN.NumCols() < bufUniFactors.length())
7259 {
7260 refineAndRestartLift (F, NTLN, liftBound, l, bufUniFactors, M, Pi,
7261#endif
7262 diophant
7263 );
7264 beenInThres= true;
7265 }
7266 }
7267 else
7268 {
7269 if (NTLNe.NumCols() < bufUniFactors.length())
7270 {
7271 refineAndRestartLift (F, NTLNe, liftBound, l, bufUniFactors, M, Pi,
7272 diophant
7273 );
7274 beenInThres= true;
7275 }
7276 }
7277 }
7278
7280 int factorsFound= 0;
7281 if (alpha.level() == 1 || (alpha.level() != 1 && reduceFq2Fp))
7282 {
7283#ifdef HAVE_FLINT
7284 result= earlyReconstructionAndLifting (F, FLINTN, bufF, bufUniFactors, l,
7285#else
7286 result= earlyReconstructionAndLifting (F, NTLN, bufF, bufUniFactors, l,
7287#endif
7288 factorsFound, beenInThres, M, Pi,
7289 diophant, symmetric, eval
7290 );
7291
7292#ifdef HAVE_FLINT
7293 if (result.length() == nmod_mat_ncols (FLINTN))
7294 {
7295 nmod_mat_clear (FLINTN);
7296#else
7297 if (result.length() == NTLN.NumCols())
7298 {
7299#endif
7300 delete [] bounds;
7301 return Union (result, smallFactors);
7302 }
7303 }
7304 else
7305 {
7306 result= earlyReconstructionAndLifting (F, NTLNe, bufF, bufUniFactors, l,
7307 factorsFound, beenInThres, M, Pi,
7308 diophant, symmetric, eval
7309 );
7310
7311 if (result.length() == NTLNe.NumCols())
7312 {
7313 delete [] bounds;
7314 return Union (result, smallFactors);
7315 }
7316 }
7317
7318 if (result.length() > 0)
7319 {
7320 if (beenInThres)
7321 {
7322 int index;
7323 for (CFListIterator i= result; i.hasItem(); i++)
7324 {
7325 index= 1;
7326 tmp1= mod (i.getItem(), y-eval);
7327 tmp1 /= Lc (tmp1);
7328 for (CFListIterator j= bufUniFactors; j.hasItem(); j++, index++)
7329 {
7330 tmp2= mod (j.getItem(), y);
7331 tmp2 /= Lc (tmp2);
7332 if (tmp1 == tmp2)
7333 {
7334 index++;
7335 j.remove(index);
7336 break;
7337 }
7338 }
7339 }
7340 }
7341 else
7342 {
7343 int * zeroOne;
7344 long numCols, numRows;
7345 if (alpha.level() == 1 || (alpha.level() != 1 && reduceFq2Fp))
7346 {
7347#ifdef HAVE_FLINT
7348 numCols= nmod_mat_ncols (FLINTN);
7349 numRows= nmod_mat_nrows (FLINTN);
7350 zeroOne= extractZeroOneVecs (FLINTN);
7351#else
7352 numCols= NTLN.NumCols();
7353 numRows= NTLN.NumRows();
7354 zeroOne= extractZeroOneVecs (NTLN);
7355#endif
7356 }
7357 else
7358 {
7359 numCols= NTLNe.NumCols();
7360 numRows= NTLNe.NumRows();
7361 zeroOne= extractZeroOneVecs (NTLNe);
7362 }
7368 for (int i= 0; i < numCols; i++)
7369 {
7370 if (zeroOne [i] == 0)
7371 continue;
7373 buf= 1;
7375 for (int j= 0; j < numRows; j++, iter++)
7376 {
7377 if (alpha.level() == 1 || (alpha.level() != 1 && reduceFq2Fp))
7378 {
7379#ifdef HAVE_FLINT
7380 if (!(nmod_mat_entry (FLINTN, j,i) == 0))
7381#else
7382 if (!IsZero (NTLN (j + 1,i + 1)))
7383#endif
7384 {
7385 factorsConsidered.append (iter.getItem());
7386 buf *= mod (iter.getItem(), y);
7387 }
7388 }
7389 else
7390 {
7391 if (!IsZero (NTLNe (j + 1,i + 1)))
7392 {
7393 factorsConsidered.append (iter.getItem());
7394 buf *= mod (iter.getItem(), y);
7395 }
7396 }
7397 }
7398 buf /= Lc (buf);
7399 for (iter2= result; iter2.hasItem(); iter2++)
7400 {
7401 tmp= mod (iter2.getItem(), y-eval);
7402 tmp /= Lc (tmp);
7403 if (tmp == buf)
7404 {
7406 break;
7407 }
7408 }
7409 }
7411 delete [] zeroOne;
7412 }
7413
7414 int oldNumCols;
7416 irreducible= false;
7417
7418 if (alpha.level() == 1)
7419 {
7420#ifdef HAVE_FLINT
7422#else
7423 oldNumCols= NTLN.NumCols();
7424#endif
7427 );
7428 }
7429 else
7430 {
7431 if (reduceFq2Fp)
7432 {
7433#ifdef HAVE_FLINT
7435#else
7436 oldNumCols= NTLN.NumCols();
7437#endif
7438
7441 );
7442 }
7443 else
7444 {
7445 oldNumCols= NTLNe.NumCols();
7446
7449 );
7450 }
7451 }
7452
7453 if (bufUniFactors.isEmpty() || degree (bufF) <= 0)
7454 {
7455#ifdef HAVE_FLINT
7456 if (alpha.level() == 1 || (alpha.level() != 1 && reduceFq2Fp))
7458#endif
7459 delete [] bounds;
7461 return Union (result, smallFactors);
7462 }
7463
7465 i.getItem()= mod (i.getItem(), y);
7466
7469 delete [] bounds;
7471 degs.intersect (bufDegs);
7472 degs.refine();
7473 if (degs.getLength() == 1 || bufUniFactors.length() == 1)
7474 {
7475#ifdef HAVE_FLINT
7476 if (alpha.level() == 1 || (alpha.level() != 1 && reduceFq2Fp))
7478#endif
7479 result.append (bufF (y-eval,y));
7480 return result;
7481 }
7482#ifdef HAVE_FLINT
7483 if (alpha.level() == 1 || (alpha.level() != 1 && reduceFq2Fp))
7485#endif
7488 eval
7489 )
7490 );
7491 }
7492
7493 if (l < liftBound)
7494 {
7495 if (alpha.level() == 1)
7496 {
7499 FLINTN, eval
7500#else
7501 NTLN, eval
7502#endif
7503 );
7504 }
7505 else
7506 {
7507 if (reduceFq2Fp)
7508 {
7512#else
7513 bufQ, NTLN, alpha, eval
7514#endif
7515 );
7516 }
7517 else
7518 {
7520 NTLNe, eval
7521 );
7522 }
7523 }
7524 if (alpha.level() == 1 || (alpha.level() != 1 && reduceFq2Fp))
7525 {
7526#ifdef HAVE_FLINT
7527 if (result.length()== nmod_mat_ncols (FLINTN))
7528 {
7530#else
7531 if (result.length()== NTLN.NumCols())
7532 {
7533#endif
7534 delete [] bounds;
7536 return result;
7537 }
7538 }
7539 else
7540 {
7541 if (result.length()== NTLNe.NumCols())
7542 {
7543 delete [] bounds;
7545 return result;
7546 }
7547 }
7548
7549 if (result.isEmpty())
7550 {
7551 if (alpha.level() == 1)
7555#else
7556 liftBound, d, bounds, NTLN,
7557#endif
7558 diophant, M, Pi, bufQ, eval
7559 );
7560 else
7561 {
7562 if (reduceFq2Fp)
7564 liftBound, d, bounds,
7566 FLINTN, diophant, M,
7567#else
7568 NTLN, diophant, M,
7569#endif
7570 Pi, bufQ, alpha, eval
7571 );
7572 else
7574 liftBound, d, bounds,
7575 NTLNe, diophant, M,
7576 Pi, bufQ, eval
7577 );
7578 }
7579
7580 if (alpha.level() == 1 || (alpha.level() != 1 && reduceFq2Fp))
7581 {
7582#ifdef HAVE_FLINT
7583 if (result.length() == nmod_mat_ncols (FLINTN))
7584 {
7586#else
7587 if (result.length() == NTLN.NumCols())
7588 {
7589#endif
7590 delete [] bounds;
7592 return result;
7593 }
7594 }
7595 else
7596 {
7597 if (result.length() == NTLNe.NumCols())
7598 {
7599 delete [] bounds;
7601 return result;
7602 }
7603 }
7604 }
7605 }
7606
7607 DEBOUTLN (cerr, "lattice recombination failed");
7608
7610 degs.intersect (bufDegs);
7611 degs.refine();
7612
7613 delete [] bounds;
7615#ifdef HAVE_FLINT
7616 if (alpha.level() == 1 || (alpha.level() != 1 && reduceFq2Fp))
7618#endif
7619 if (isIrreducible)
7620 {
7621 delete [] bounds;
7623 result.append (F (y-eval,y));
7624 return result;
7625 }
7626 minBound= bounds[0];
7627 for (int i= 1; i < d; i++)
7628 {
7629 if (bounds[i] != 0)
7631 }
7632
7633 if (minBound > 16 || result.length() == 0)
7634 {
7636 CanonicalForm MODl= power (y, degree (F) + 1);
7637 delete [] bounds;
7639 eval, 1, bufUniFactors.length()/2
7640 )
7641 );
7642 }
7643 else
7644 {
7647 i.getItem()= mod (i.getItem(), y);
7648 delete [] bounds;
7651 )
7652 );
7653 }
7654}
zz_pX convertFacCF2NTLzzpX(const CanonicalForm &f)
CFList furtherLiftingAndIncreasePrecision(CanonicalForm &F, CFList &factors, int l, int liftBound, int d, int *bounds, nmod_mat_t FLINTN, CFList &diophant, CFMatrix &M, CFArray &Pi, CFArray &bufQ, const CanonicalForm &eval)
int liftAndComputeLatticeFq2Fp(const CanonicalForm &F, int *bounds, int sizeBounds, int start, int liftBound, int minBound, CFList &factors, nmod_mat_t FLINTN, CFList &diophant, CFMatrix &M, CFArray &Pi, CFArray &bufQ, bool &irreducible, const Variable &alpha)
int liftAndComputeLattice(const CanonicalForm &F, int *bounds, int sizeBounds, int start, int liftBound, int minBound, CFList &factors, mat_zz_p &NTLN, CFList &diophant, CFMatrix &M, CFArray &Pi, CFArray &bufQ, bool &irreducible)
CFList sieveSmallFactors(const CanonicalForm &G, CFList &uniFactors, DegreePattern &degPat, CanonicalForm &H, CFList &diophant, CFArray &Pi, CFMatrix &M, bool &success, int d, const CanonicalForm &eval)
CFList furtherLiftingAndIncreasePrecisionFq2Fp(CanonicalForm &F, CFList &factors, int l, int liftBound, int d, int *bounds, nmod_mat_t FLINTN, CFList &diophant, CFMatrix &M, CFArray &Pi, CFArray &bufQ, const Variable &alpha, const CanonicalForm &eval)

◆ if()

else if ( L.  length() = = 1)

◆ increasePrecision() [1/4]

CFList increasePrecision ( CanonicalForm F,
CFList factors,
int  factorsFound,
int  oldNumCols,
int  oldL,
const Variable ,
int  precision,
const CanonicalForm eval 
)

Definition at line 3686 of file facFqBivar.cc.

3690{
3691 int d;
3692 bool isIrreducible= false;
3693 Variable y= F.mvar();
3694 int* bounds= computeBounds (F, d, isIrreducible);
3695 if (isIrreducible)
3696 {
3697 delete [] bounds;
3698 CanonicalForm G= F;
3699 F= 1;
3700 return CFList (G (y-eval,y));
3701 }
3702 CFArray * A= new CFArray [factors.length()];
3705 ident (NTLN, factors.length());
3706 int minBound= bounds[0];
3707 for (int i= 1; i < d; i++)
3708 {
3709 if (bounds[i] != 0)
3711 }
3712 int l= tmax (2*(minBound + 1), oldL);
3713 int oldL2= l/2;
3714 int stepSize= 2;
3715 bool useOldQs= false;
3716 bool hitBound= false;
3718 CFMatrix C;
3720 CFArray buf;
3722 while (l <= precision)
3723 {
3724 j= factors;
3725 truncF= mod (F, power (y,l));
3726 if (useOldQs)
3727 {
3728 for (int i= 0; i < factors.length(); i++, j++)
3729 A[i]= logarithmicDerivative (truncF, j.getItem(), l, oldL2, bufQ[i],
3730 bufQ[i]
3731 );
3732 }
3733 else
3734 {
3735 for (int i= 0; i < factors.length(); i++, j++)
3736 A[i]= logarithmicDerivative (truncF, j.getItem(), l, bufQ [i]);
3737 }
3738 useOldQs= true;
3739 for (int i= 0; i < d; i++)
3740 {
3741 if (bounds [i] + 1 <= l/2)
3742 {
3743 int k= tmin (bounds [i] + 1, l/2);
3744 C= CFMatrix (l - k, factors.length());
3745 for (int ii= 0; ii < factors.length(); ii++)
3746 {
3747 if (A[ii].size() - 1 >= i)
3748 {
3749 buf= getCoeffs (A[ii] [i], k);
3750 writeInMatrix (C, buf, ii + 1, 0);
3751 }
3752 }
3754 NTLK= (*NTLC)*NTLN;
3755 transpose (NTLK, NTLK);
3756 kernel (NTLK, NTLK);
3757 transpose (NTLK, NTLK);
3758 NTLN *= NTLK;
3759 delete NTLC;
3760 if (NTLN.NumCols() == 1)
3761 {
3762 delete [] A;
3763 delete [] bounds;
3764 CanonicalForm G= F;
3765 F= 1;
3766 return CFList (G (y-eval,y));
3767 }
3768 }
3769 }
3770
3771 if (NTLN.NumCols() < oldNumCols - factorsFound)
3772 {
3773 if (isReduced (NTLN))
3774 {
3775 int * factorsFoundIndex= new int [NTLN.NumCols()];
3776 for (long i= 0; i < NTLN.NumCols(); i++)
3777 factorsFoundIndex[i]= 0;
3778 int factorsFound2= 0;
3779 CFList result;
3782 factorsFoundIndex, NTLN, eval, false);
3783 if (result.length() == NTLN.NumCols())
3784 {
3785 delete [] factorsFoundIndex;
3786 delete [] A;
3787 delete [] bounds;
3788 F= 1;
3789 return result;
3790 }
3791 delete [] factorsFoundIndex;
3792 }
3793 else if (l == precision)
3794 {
3798 F= bufF;
3799 delete [] zeroOne;
3800 delete [] A;
3801 delete [] bounds;
3802 return result;
3803 }
3804 }
3805 oldL2= l;
3806 l += stepSize;
3807 stepSize *= 2;
3808 if (l > precision)
3809 {
3810 if (!hitBound)
3811 {
3812 l= precision;
3813 hitBound= true;
3814 }
3815 else
3816 break;
3817 }
3818 }
3819 delete [] bounds;
3820 delete [] A;
3821 return CFList();
3822}

◆ increasePrecision() [2/4]

CFList increasePrecision ( CanonicalForm F,
CFList factors,
int  factorsFound,
int  oldNumCols,
int  oldL,
int  precision,
const CanonicalForm eval 
)

Definition at line 3477 of file facFqBivar.cc.

3481{
3482 int d;
3483 bool isIrreducible= false;
3484 int* bounds= computeBounds (F, d, isIrreducible);
3485 Variable y= F.mvar();
3486 if (isIrreducible)
3487 {
3488 delete [] bounds;
3489 CanonicalForm G= F;
3490 F= 1;
3491 return CFList (G (y-eval, y));
3492 }
3493 CFArray * A= new CFArray [factors.length()];
3495#ifdef HAVE_FLINT
3498 for (long i=factors.length()-1; i >= 0; i--)
3499 nmod_mat_entry (FLINTN, i, i)= 1;
3500#else
3501 mat_zz_p NTLN;
3502 ident (NTLN, factors.length());
3503#endif
3504 int minBound= bounds[0];
3505 for (int i= 1; i < d; i++)
3506 {
3507 if (bounds[i] != 0)
3509 }
3510 int l= tmax (2*(minBound + 1), oldL);
3511 int oldL2= l/2;
3512 int stepSize= 2;
3513 bool useOldQs= false;
3514 bool hitBound= false;
3516 CFMatrix C;
3517 CFArray buf;
3518#ifdef HAVE_FLINT
3519 long rank;
3521#else
3522 mat_zz_p* NTLC, NTLK;
3523#endif
3525 while (l <= precision)
3526 {
3527 j= factors;
3528 truncF= mod (F, power (y,l));
3529 if (useOldQs)
3530 {
3531 for (int i= 0; i < factors.length(); i++, j++)
3532 A[i]= logarithmicDerivative (truncF, j.getItem(), l, oldL2, bufQ[i],
3533 bufQ[i]
3534 );
3535 }
3536 else
3537 {
3538 for (int i= 0; i < factors.length(); i++, j++)
3539 A[i]= logarithmicDerivative (truncF, j.getItem(), l, bufQ [i]);
3540 }
3541 useOldQs= true;
3542 for (int i= 0; i < d; i++)
3543 {
3544 if (bounds [i] + 1 <= l/2)
3545 {
3546 int k= tmin (bounds [i] + 1, l/2);
3547 C= CFMatrix (l - k, factors.length());
3548 for (int ii= 0; ii < factors.length(); ii++)
3549 {
3550 if (A[ii].size() - 1 >= i)
3551 {
3552 buf= getCoeffs (A[ii] [i], k);
3553 writeInMatrix (C, buf, ii + 1, 0);
3554 }
3555 }
3556#ifdef HAVE_FLINT
3571 nmod_mat_mul (FLINTN, FLINTC, FLINTK); //no aliasing allowed!!
3572
3576#else
3578 NTLK= (*NTLC)*NTLN;
3579 transpose (NTLK, NTLK);
3580 kernel (NTLK, NTLK);
3581 transpose (NTLK, NTLK);
3582 NTLN *= NTLK;
3583 delete NTLC;
3584#endif
3585#ifdef HAVE_FLINT
3586 if (nmod_mat_ncols (FLINTN) == 1)
3587 {
3589#else
3590 if (NTLN.NumCols() == 1)
3591 {
3592#endif
3593 delete [] A;
3594 delete [] bounds;
3595 CanonicalForm G= F;
3596 F= 1;
3597 return CFList (G (y-eval,y));
3598 }
3599 }
3600 }
3601
3602#ifdef HAVE_FLINT
3604 {
3605 if (isReduced (FLINTN))
3606 {
3607 int * factorsFoundIndex= new int [nmod_mat_ncols (FLINTN)];
3608 for (long i= 0; i < nmod_mat_ncols (FLINTN); i++)
3609#else
3610 if (NTLN.NumCols() < oldNumCols - factorsFound)
3611 {
3612 if (isReduced (NTLN))
3613 {
3614 int * factorsFoundIndex= new int [NTLN.NumCols()];
3615 for (long i= 0; i < NTLN.NumCols(); i++)
3616#endif
3617 factorsFoundIndex[i]= 0;
3618 int factorsFound2= 0;
3619 CFList result;
3621#ifdef HAVE_FLINT
3624 );
3625 if (result.length() == nmod_mat_ncols (FLINTN))
3626 {
3628#else
3630 factorsFoundIndex, NTLN, eval, false
3631 );
3632 if (result.length() == NTLN.NumCols())
3633 {
3634#endif
3635 delete [] factorsFoundIndex;
3636 delete [] A;
3637 delete [] bounds;
3638 F= 1;
3639 return result;
3640 }
3641 delete [] factorsFoundIndex;
3642 }
3643 else if (l == precision)
3644 {
3646#ifdef HAVE_FLINT
3650#else
3653#endif
3654 F= bufF;
3655 delete [] zeroOne;
3656 delete [] A;
3657 delete [] bounds;
3658 return result;
3659 }
3660 }
3661 oldL2= l;
3662 l += stepSize;
3663 stepSize *= 2;
3664 if (l > precision)
3665 {
3666 if (!hitBound)
3667 {
3668 l= precision;
3669 hitBound= true;
3670 }
3671 else
3672 break;
3673 }
3674 }
3675#ifdef HAVE_FLINT
3677#endif
3678 delete [] bounds;
3679 delete [] A;
3680 return CFList();
3681}

◆ increasePrecision() [3/4]

CFList increasePrecision ( CanonicalForm F,
CFList factors,
int  oldL,
int  l,
int  d,
int bounds,
CFArray bufQ,
mat_zz_pE NTLN,
const CanonicalForm eval 
)

Definition at line 4649 of file facFqBivar.cc.

4653{
4654 CFList result= CFList();
4655 CFArray * A= new CFArray [factors.length()];
4656 int oldL2= oldL/2;
4657 bool hitBound= false;
4658 bool useOldQs= false;
4659 if (NTLN.NumRows() != factors.length()) //refined factors
4660 ident (NTLN, factors.length());
4662 CFMatrix C;
4663 CFArray buf;
4667 Variable y= F.mvar();
4668 while (oldL <= l)
4669 {
4670 j= factors;
4671 truncF= mod (F, power (y, oldL));
4672 if (useOldQs)
4673 {
4674 for (int i= 0; i < factors.length(); i++, j++)
4675 A[i]= logarithmicDerivative (truncF, j.getItem(), oldL, oldL2, bufQ[i],
4676 bufQ[i]
4677 );
4678 }
4679 else
4680 {
4681 for (int i= 0; i < factors.length(); i++, j++)
4682 A[i]= logarithmicDerivative (truncF, j.getItem(), oldL, bufQ [i]);
4683 }
4684 useOldQs= true;
4685
4686 for (int i= 0; i < d; i++)
4687 {
4688 if (bounds [i] + 1 <= oldL/2)
4689 {
4690 int k= tmin (bounds [i] + 1, oldL/2);
4691 C= CFMatrix (oldL - k, factors.length());
4692 for (int ii= 0; ii < factors.length(); ii++)
4693 {
4694 if (A[ii].size() - 1 >= i)
4695 {
4696 buf= getCoeffs (A[ii] [i], k);
4697 writeInMatrix (C, buf, ii + 1, 0);
4698 }
4699 }
4701 NTLK= (*NTLC)*NTLN;
4702 transpose (NTLK, NTLK);
4703 kernel (NTLK, NTLK);
4704 transpose (NTLK, NTLK);
4705 NTLN *= NTLK;
4706 delete NTLC;
4707
4708 if (NTLN.NumCols() == 1)
4709 {
4710 delete [] A;
4711 return CFList (F (y-eval,y));
4712 }
4713 }
4714 }
4715 if (NTLN.NumCols() == 1)
4716 {
4717 delete [] A;
4718 return CFList (F (y-eval,y));
4719 }
4720
4721 int * zeroOneVecs;
4723 bufF= F;
4726 delete [] zeroOneVecs;
4727 if (degree (bufF) + 1 + degree (LC (bufF, 1)) < l && result.length() > 0)
4728 {
4729 F= bufF;
4731 delete [] A;
4732 return result;
4733 }
4734
4735 result= CFList();
4736 oldL2= oldL;
4737 oldL *= 2;
4738 if (oldL > l)
4739 {
4740 if (!hitBound)
4741 {
4742 oldL= l;
4743 hitBound= true;
4744 }
4745 else
4746 break;
4747 }
4748 }
4749 delete [] A;
4750 return result;
4751}

◆ increasePrecision() [4/4]

CFList increasePrecision ( CanonicalForm F,
CFList factors,
int  oldL,
int  l,
int  d,
int bounds,
CFArray bufQ,
nmod_mat_t  FLINTN,
const CanonicalForm eval 
)

Definition at line 4480 of file facFqBivar.cc.

4491{
4492 CFList result= CFList();
4493 CFArray * A= new CFArray [factors.length()];
4494 int oldL2= oldL/2;
4495 bool hitBound= false;
4496#ifdef HAVE_FLINT
4497 if (nmod_mat_nrows (FLINTN) != factors.length()) //refined factors
4498 {
4501 for (long i=factors.length()-1; i >= 0; i--)
4502 nmod_mat_entry (FLINTN, i, i)= 1;
4504 }
4505#else
4506 if (NTLN.NumRows() != factors.length()) //refined factors
4507 {
4508 ident (NTLN, factors.length());
4510 }
4511#endif
4512 bool useOldQs= false;
4514 CFMatrix C;
4515 CFArray buf;
4516#ifdef HAVE_FLINT
4517 long rank;
4519#else
4520 mat_zz_p* NTLC, NTLK;
4521#endif
4524 Variable y= F.mvar();
4525 while (oldL <= l)
4526 {
4527 j= factors;
4528 truncF= mod (F, power (y, oldL));
4529 if (useOldQs)
4530 {
4531 for (int i= 0; i < factors.length(); i++, j++)
4532 A[i]= logarithmicDerivative (truncF, j.getItem(), oldL, oldL2, bufQ[i],
4533 bufQ[i]
4534 );
4535 }
4536 else
4537 {
4538 for (int i= 0; i < factors.length(); i++, j++)
4539 A[i]= logarithmicDerivative (truncF, j.getItem(), oldL, bufQ [i]);
4540 }
4541 useOldQs= true;
4542
4543 for (int i= 0; i < d; i++)
4544 {
4545 if (bounds [i] + 1 <= oldL/2)
4546 {
4547 int k= tmin (bounds [i] + 1, oldL/2);
4548 C= CFMatrix (oldL - k, factors.length());
4549 for (int ii= 0; ii < factors.length(); ii++)
4550 {
4551 if (A[ii].size() - 1 >= i)
4552 {
4553 buf= getCoeffs (A[ii] [i], k);
4554 writeInMatrix (C, buf, ii + 1, 0);
4555 }
4556 }
4557#ifdef HAVE_FLINT
4572 nmod_mat_mul (FLINTN, FLINTC, FLINTK); //no aliasing allowed!!
4573
4577#else
4579 NTLK= (*NTLC)*NTLN;
4580 transpose (NTLK, NTLK);
4581 kernel (NTLK, NTLK);
4582 transpose (NTLK, NTLK);
4583 NTLN *= NTLK;
4584 delete NTLC;
4585#endif
4586#ifdef HAVE_FLINT
4587 if (nmod_mat_ncols (FLINTN) == 1)
4588#else
4589 if (NTLN.NumCols() == 1)
4590#endif
4591 {
4592 delete [] A;
4593 return CFList (F (y-eval,y));
4594 }
4595 }
4596 }
4597#ifdef HAVE_FLINT
4598 if (nmod_mat_ncols (FLINTN) == 1)
4599#else
4600 if (NTLN.NumCols() == 1)
4601#endif
4602 {
4603 delete [] A;
4604 return CFList (F (y-eval,y));
4605 }
4606 int * zeroOneVecs;
4607#ifdef HAVE_FLINT
4609#else
4611#endif
4612 bufF= F;
4614#ifdef HAVE_FLINT
4616#else
4618#endif
4619 delete [] zeroOneVecs;
4620 if (degree (bufF) + 1 + degree (LC (bufF, 1)) < oldL && result.length() > 0)
4621 {
4622 F= bufF;
4624 delete [] A;
4625 return result;
4626 }
4627
4628 result= CFList();
4629 oldL2= oldL;
4630 oldL *= 2;
4631 if (oldL > l)
4632 {
4633 if (!hitBound)
4634 {
4635 oldL= l;
4636 hitBound= true;
4637 }
4638 else
4639 break;
4640 }
4641 }
4642 delete [] A;
4643 return result;
4644}

◆ increasePrecision2()

CFList increasePrecision2 ( const CanonicalForm F,
CFList factors,
const Variable alpha,
int  precision 
)

Definition at line 4136 of file facFqBivar.cc.

4138{
4139 int d;
4140 bool isIrreducible= false;
4141 int* bounds= computeBounds (F, d, isIrreducible);
4142 if (isIrreducible)
4143 {
4144 delete [] bounds;
4145 return CFList (F);
4146 }
4147 CFArray * A= new CFArray [factors.length()];
4150 {
4152 zz_p::init (getCharacteristic());
4153 }
4155 zz_pE::init (NTLMipo);
4157 ident (NTLN, factors.length());
4158 int minBound= bounds[0];
4159 for (int i= 1; i < d; i++)
4160 {
4161 if (bounds[i] != 0)
4163 }
4164 int l= tmin (2*(minBound + 1), precision);
4165 int oldL= l/2;
4166 int stepSize= 2;
4167 bool useOldQs= false;
4168 bool hitBound= false;
4170 CFMatrix C;
4171 CFArray buf;
4173 Variable y= F.mvar();
4175 while (l <= precision)
4176 {
4177 j= factors;
4178 truncF= mod (F, power (y, l));
4179 if (useOldQs)
4180 {
4181 for (int i= 0; i < factors.length(); i++, j++)
4182 A[i]= logarithmicDerivative (truncF, j.getItem(), l, oldL, bufQ[i], bufQ[i]);
4183 }
4184 else
4185 {
4186 for (int i= 0; i < factors.length(); i++, j++)
4187 A[i]= logarithmicDerivative (truncF, j.getItem(), l, bufQ [i]);
4188 }
4189 useOldQs= true;
4190 for (int i= 0; i < d; i++)
4191 {
4192 if (bounds [i] + 1 <= l/2)
4193 {
4194 int k= tmin (bounds [i] + 1, l/2);
4195 C= CFMatrix (l - k, factors.length());
4196 for (int ii= 0; ii < factors.length(); ii++)
4197 {
4198 if (A[ii].size() - 1 >= i)
4199 {
4200 buf= getCoeffs (A[ii] [i], k);
4201 writeInMatrix (C, buf, ii + 1, 0);
4202 }
4203 }
4205 NTLK= (*NTLC)*NTLN;
4206 transpose (NTLK, NTLK);
4207 kernel (NTLK, NTLK);
4208 transpose (NTLK, NTLK);
4209 NTLN *= NTLK;
4210 delete NTLC;
4211
4212 if (NTLN.NumCols() == 1)
4213 {
4214 delete [] A;
4215 delete [] bounds;
4216 return CFList (F);
4217 }
4218 }
4219 }
4220
4221 if (isReduced (NTLN) || l == precision)
4222 {
4227 NTLN
4228 );
4229 if (result.length() != NTLN.NumCols() && l != precision)
4231 if (result.length() == NTLN.NumCols())
4232 {
4233 delete [] zeroOne;
4234 delete [] A;
4235 delete [] bounds;
4236 return result;
4237 }
4238 if (l == precision)
4239 {
4240 delete [] zeroOne;
4241 delete [] A;
4242 delete [] bounds;
4243 return Union (result, factors);
4244 }
4245 delete [] zeroOne;
4246 }
4247 oldL= l;
4248 l += stepSize;
4249 stepSize *= 2;
4250 if (l > precision)
4251 {
4252 if (!hitBound)
4253 {
4254 l= precision;
4255 hitBound= true;
4256 }
4257 else
4258 break;
4259 }
4260 }
4261 delete [] bounds;
4262 delete [] A;
4263 return CFList();
4264}
CFList monicReconstruction(CanonicalForm &G, CFList &factors, int *zeroOneVecs, int precision, const mat_zz_pE &N)

◆ increasePrecisionFq2Fp() [1/2]

CFList increasePrecisionFq2Fp ( CanonicalForm F,
CFList factors,
int  factorsFound,
int  oldNumCols,
int  oldL,
const Variable alpha,
int  precision,
const CanonicalForm eval 
)

Definition at line 4269 of file facFqBivar.cc.

4273{
4274 int d;
4275 bool isIrreducible= false;
4276 Variable y= F.mvar();
4277 int* bounds= computeBounds (F, d, isIrreducible);
4278 if (isIrreducible)
4279 {
4280 delete [] bounds;
4281 CanonicalForm G= F;
4282 F= 1;
4283 return CFList (G (y-eval,y));
4284 }
4286 CFArray * A= new CFArray [factors.length()];
4288#ifdef HAVE_FLINT
4291 for (long i=factors.length()-1; i >= 0; i--)
4292 nmod_mat_entry (FLINTN, i, i)= 1;
4293#else
4294 mat_zz_p NTLN;
4295 ident (NTLN, factors.length());
4296#endif
4297 int minBound= bounds[0];
4298 for (int i= 1; i < d; i++)
4299 {
4300 if (bounds[i] != 0)
4302 }
4303 int l= tmax (2*(minBound + 1), oldL);
4304 int oldL2= l/2;
4305 int stepSize= 2;
4306 bool useOldQs= false;
4307 bool hitBound= false;
4309 CFMatrix C;
4310#ifdef HAVE_FLINT
4311 long rank;
4313#else
4314 mat_zz_p* NTLC, NTLK;
4315#endif
4316 CFArray buf;
4318 while (l <= precision)
4319 {
4320 j= factors;
4321 truncF= mod (F, power (y, l));
4322 if (useOldQs)
4323 {
4324 for (int i= 0; i < factors.length(); i++, j++)
4325 A[i]= logarithmicDerivative (truncF, j.getItem(), l, oldL2, bufQ[i],
4326 bufQ[i]
4327 );
4328 }
4329 else
4330 {
4331 for (int i= 0; i < factors.length(); i++, j++)
4332 A[i]= logarithmicDerivative (truncF, j.getItem(), l, bufQ [i]);
4333 }
4334 useOldQs= true;
4335 for (int i= 0; i < d; i++)
4336 {
4337 if (bounds [i] + 1 <= l/2)
4338 {
4339 int k= tmin (bounds [i] + 1, l/2);
4340 C= CFMatrix ((l - k)*extensionDeg, factors.length());
4341 for (int ii= 0; ii < factors.length(); ii++)
4342 {
4343 if (A[ii].size() - 1 >= i)
4344 {
4345 buf= getCoeffs (A[ii] [i], k, alpha);
4346 writeInMatrix (C, buf, ii + 1, 0);
4347 }
4348 }
4349#ifdef HAVE_FLINT
4364 nmod_mat_mul (FLINTN, FLINTC, FLINTK); //no aliasing allowed!!
4365
4369#else
4371 NTLK= (*NTLC)*NTLN;
4372 transpose (NTLK, NTLK);
4373 kernel (NTLK, NTLK);
4374 transpose (NTLK, NTLK);
4375 NTLN *= NTLK;
4376 delete NTLC;
4377#endif
4378#ifdef HAVE_FLINT
4379 if (nmod_mat_ncols (FLINTN) == 1)
4380 {
4382#else
4383 if (NTLN.NumCols() == 1)
4384 {
4385#endif
4386 delete [] A;
4387 delete [] bounds;
4388 CanonicalForm G= F;
4389 F= 1;
4390 return CFList (G (y-eval,y));
4391 }
4392 }
4393 }
4394
4395#ifdef HAVE_FLINT
4397 {
4398 if (isReduced (FLINTN))
4399 {
4400 int * factorsFoundIndex= new int [nmod_mat_ncols (FLINTN)];
4401 for (long i= 0; i < nmod_mat_ncols (FLINTN); i++)
4402#else
4403 if (NTLN.NumCols() < oldNumCols - factorsFound)
4404 {
4405 if (isReduced (NTLN))
4406 {
4407 int * factorsFoundIndex= new int [NTLN.NumCols()];
4408 for (long i= 0; i < NTLN.NumCols(); i++)
4409#endif
4410 factorsFoundIndex[i]= 0;
4411 int factorsFound2= 0;
4412 CFList result;
4414#ifdef HAVE_FLINT
4417 );
4418 if (result.length() == nmod_mat_ncols (FLINTN))
4419 {
4421#else
4423 factorsFoundIndex, NTLN, eval, false
4424 );
4425 if (result.length() == NTLN.NumCols())
4426 {
4427#endif
4428 delete [] factorsFoundIndex;
4429 delete [] A;
4430 delete [] bounds;
4431 F= 1;
4432 return result;
4433 }
4434 delete [] factorsFoundIndex;
4435 }
4436 else if (l == precision)
4437 {
4439#ifdef HAVE_FLINT
4443#else
4446#endif
4447 F= bufF;
4448 delete [] zeroOne;
4449 delete [] A;
4450 delete [] bounds;
4451 return result;
4452 }
4453 }
4454 oldL2= l;
4455 l += stepSize;
4456 stepSize *= 2;
4457 if (l > precision)
4458 {
4459 if (!hitBound)
4460 {
4461 hitBound= true;
4462 l= precision;
4463 }
4464 else
4465 break;
4466 }
4467 }
4468#ifdef HAVE_FLINT
4470#endif
4471 delete [] bounds;
4472 delete [] A;
4473 return CFList();
4474}

◆ increasePrecisionFq2Fp() [2/2]

CFList increasePrecisionFq2Fp ( CanonicalForm F,
CFList factors,
int  oldL,
int  l,
int  d,
int bounds,
CFArray bufQ,
nmod_mat_t  FLINTN,
const Variable alpha,
const CanonicalForm eval 
)

Definition at line 5016 of file facFqBivar.cc.

5027{
5028 CFList result= CFList();
5029 CFArray * A= new CFArray [factors.length()];
5031 int oldL2= oldL/2;
5032 bool hitBound= false;
5033 bool useOldQs= false;
5034#ifdef HAVE_FLINT
5035 if (nmod_mat_nrows (FLINTN) != factors.length()) //refined factors
5036 {
5039 for (long i=factors.length()-1; i >= 0; i--)
5040 nmod_mat_entry (FLINTN, i, i)= 1;
5041 }
5042#else
5043 if (NTLN.NumRows() != factors.length()) //refined factors
5044 ident (NTLN, factors.length());
5045#endif
5047 CFMatrix C;
5048 CFArray buf;
5049#ifdef HAVE_FLINT
5050 long rank;
5052#else
5053 mat_zz_p* NTLC, NTLK;
5054#endif
5057 Variable y= F.mvar();
5058 while (oldL <= l)
5059 {
5060 j= factors;
5061 truncF= mod (F, power (y, oldL));
5062 if (useOldQs)
5063 {
5064 for (int i= 0; i < factors.length(); i++, j++)
5065 A[i]= logarithmicDerivative (truncF, j.getItem(), oldL, oldL2, bufQ[i],
5066 bufQ[i]
5067 );
5068 }
5069 else
5070 {
5071 for (int i= 0; i < factors.length(); i++, j++)
5072 A[i]= logarithmicDerivative (truncF, j.getItem(), oldL, bufQ [i]);
5073 }
5074 useOldQs= true;
5075
5076 for (int i= 0; i < d; i++)
5077 {
5078 if (bounds [i] + 1 <= oldL/2)
5079 {
5080 int k= tmin (bounds [i] + 1, oldL/2);
5082 for (int ii= 0; ii < factors.length(); ii++)
5083 {
5084 if (A[ii].size() - 1 >= i)
5085 {
5086 buf= getCoeffs (A[ii] [i], k, alpha);
5087 writeInMatrix (C, buf, ii + 1, 0);
5088 }
5089 }
5090#ifdef HAVE_FLINT
5105 nmod_mat_mul (FLINTN, FLINTC, FLINTK); //no aliasing allowed!!
5106
5110#else
5112 NTLK= (*NTLC)*NTLN;
5113 transpose (NTLK, NTLK);
5114 kernel (NTLK, NTLK);
5115 transpose (NTLK, NTLK);
5116 NTLN *= NTLK;
5117 delete NTLC;
5118#endif
5119#ifdef HAVE_FLINT
5120 if (nmod_mat_ncols (FLINTN) == 1)
5121#else
5122 if (NTLN.NumCols() == 1)
5123#endif
5124 {
5125 delete [] A;
5126 return CFList (F(y-eval,y));
5127 }
5128 }
5129 }
5130
5131 int * zeroOneVecs;
5132#ifdef HAVE_FLINT
5134#else
5136#endif
5137
5138 bufF= F;
5140#ifdef HAVE_FLINT
5142#else
5144#endif
5145 delete [] zeroOneVecs;
5146 if (degree (bufF) + 1 + degree (LC (bufF, 1)) < l && result.length() > 0)
5147 {
5148 F= bufF;
5150 delete [] A;
5151 return result;
5152 }
5153
5154 result= CFList();
5155 oldL2= oldL;
5156 oldL *= 2;
5157 if (oldL > l)
5158 {
5159 if (!hitBound)
5160 {
5161 oldL= l;
5162 hitBound= true;
5163 }
5164 else
5165 break;
5166 }
5167 }
5168 delete [] A;
5169 return result;
5170}

◆ init4ext()

ExtensionInfo init4ext ( const ExtensionInfo info,
const CanonicalForm evaluation,
int degMipo 
)

Definition at line 7659 of file facFqBivar.cc.

7662{
7664 Variable alpha= info.getAlpha();
7665 if (GF)
7666 {
7670 GFMipo.mapinto();
7671 alpha= rootOf (GFMipo);
7673 }
7674 else
7675 {
7676 alpha= info.getAlpha();
7678 }
7679
7682 if ((!GF && evaluation != alpha) || (GF && evaluation != getGFGenerator()))
7683 {
7685 if (GF)
7686 {
7689 }
7690 else
7693 gamma= rootOf (mipo);
7695 bool fail= false;
7698
7699 if (GF)
7701 }
7702 else
7703 gamma= alpha;
7705 imPrimElemAlpha, 1, info.getGFName(), true
7706 );
7707
7708 return info2;
7709}
CanonicalForm findMinPoly(const CanonicalForm &F, const Variable &alpha)
compute minimal polynomial of via NTL
CanonicalForm map(const CanonicalForm &primElem, const Variable &alpha, const CanonicalForm &F, const Variable &beta)
map from to such that is mapped onto

◆ isReduced() [1/3]

long isReduced ( const mat_zz_p M)

Definition at line 1470 of file facFqBivar.cc.

1471{
1472 long i, j, nonZero;
1473 for (i = 1; i <= M.NumRows(); i++)
1474 {
1475 nonZero= 0;
1476 for (j = 1; j <= M.NumCols(); j++)
1477 {
1478 if (!IsZero (M (i,j)))
1479 nonZero++;
1480 }
1481 if (nonZero != 1)
1482 return 0;
1483 }
1484 return 1;
1485}

◆ isReduced() [2/3]

long isReduced ( const mat_zz_pE M)

Definition at line 1508 of file facFqBivar.cc.

1509{
1510 long i, j, nonZero;
1511 for (i = 1; i <= M.NumRows(); i++)
1512 {
1513 nonZero= 0;
1514 for (j = 1; j <= M.NumCols(); j++)
1515 {
1516 if (!IsZero (M (i,j)))
1517 nonZero++;
1518 }
1519 if (nonZero != 1)
1520 return 0;
1521 }
1522 return 1;
1523}

◆ isReduced() [3/3]

long isReduced ( const nmod_mat_t  M)

Definition at line 1489 of file facFqBivar.cc.

1490{
1491 long i, j, nonZero;
1492 for (i = 1; i <= nmod_mat_nrows(M); i++)
1493 {
1494 nonZero= 0;
1495 for (j = 1; j <= nmod_mat_ncols (M); j++)
1496 {
1497 if (!(nmod_mat_entry (M, i-1, j-1)==0))
1498 nonZero++;
1499 }
1500 if (nonZero != 1)
1501 return 0;
1502 }
1503 return 1;
1504}

◆ liftAndComputeLattice() [1/3]

int liftAndComputeLattice ( const CanonicalForm F,
int bounds,
int  sizeBounds,
int  start,
int  liftBound,
int  minBound,
CFList factors,
mat_zz_p NTLN,
CFList diophant,
CFMatrix M,
CFArray Pi,
CFArray bufQ,
bool irreducible 
)

Definition at line 2487 of file facFqBivar.cc.

2492{
2493 CanonicalForm LCF= LC (F, 1);
2494 CFArray *A= new CFArray [factors.length() - 1];
2495 bool wasInBounds= false;
2496 bool hitBound= false;
2497 int l= (minBound+1)*2;
2498 int stepSize= 2;
2499 int oldL= l/2;
2500 bool reduced= false;
2501 mat_zz_p NTLK, *NTLC;
2502 CFMatrix C;
2503 CFArray buf;
2506 Variable y= F.mvar();
2507 while (l <= liftBound)
2508 {
2510 if (start)
2511 {
2512 henselLiftResume12 (F, factors, start, l, Pi, diophant, M);
2513 start= 0;
2514 }
2515 else
2516 {
2517 if (wasInBounds)
2519 else
2520 henselLift12 (F, factors, l, Pi, diophant, M);
2521 }
2523 "time to lift in compute lattice: ");
2524
2525 factors.insert (LCF);
2526 j= factors;
2527 j++;
2528
2529 truncF= mod (F, power (y, l));
2531 for (int i= 0; i < factors.length() - 1; i++, j++)
2532 {
2533 if (!wasInBounds)
2534 A[i]= logarithmicDerivative (truncF, j.getItem(), l, bufQ[i]);
2535 else
2536 A[i]= logarithmicDerivative (truncF, j.getItem(), l, oldL, bufQ[i],
2537 bufQ[i]);
2538 }
2540 "time to compute logarithmic derivative: ");
2541
2542 for (int i= 0; i < sizeBounds; i++)
2543 {
2544 if (bounds [i] + 1 <= l/2)
2545 {
2546 wasInBounds= true;
2547 int k= tmin (bounds [i] + 1, l/2);
2548 C= CFMatrix (l - k, factors.length() - 1);
2549 for (int ii= 0; ii < factors.length() - 1; ii++)
2550 {
2551 if (A[ii].size() - 1 >= i)
2552 {
2553 buf= getCoeffs (A[ii] [i], k);
2554 writeInMatrix (C, buf, ii + 1, 0);
2555 }
2556 }
2558 NTLK= (*NTLC)*NTLN;
2559 transpose (NTLK, NTLK);
2560 kernel (NTLK, NTLK);
2561 transpose (NTLK, NTLK);
2562 NTLN *= NTLK;
2563 delete NTLC;
2564
2565 if (NTLN.NumCols() == 1)
2566 {
2567 irreducible= true;
2568 break;
2569 }
2570 if (isReduced (NTLN) && l > (minBound+1)*2)
2571 {
2572 reduced= true;
2573 break;
2574 }
2575 }
2576 }
2577
2578 if (irreducible)
2579 break;
2580 if (reduced)
2581 break;
2582 oldL= l;
2583 l += stepSize;
2584 stepSize *= 2;
2585 if (l > liftBound)
2586 {
2587 if (!hitBound)
2588 {
2589 l= liftBound;
2590 hitBound= true;
2591 }
2592 else
2593 break;
2594 }
2595 }
2596 delete [] A;
2597 if (!wasInBounds)
2598 {
2599 if (start)
2600 henselLiftResume12 (F, factors, start, degree (F) + 1, Pi, diophant, M);
2601 else
2602 henselLift12 (F, factors, degree (F) + 1, Pi, diophant, M);
2603 factors.insert (LCF);
2604 }
2605 return l;
2606}

◆ liftAndComputeLattice() [2/3]

int liftAndComputeLattice ( const CanonicalForm F,
int bounds,
int  sizeBounds,
int  start,
int  liftBound,
int  minBound,
CFList factors,
mat_zz_pE NTLN,
CFList diophant,
CFMatrix M,
CFArray Pi,
CFArray bufQ,
bool irreducible 
)

Definition at line 3159 of file facFqBivar.cc.

3164{
3165 CanonicalForm LCF= LC (F, 1);
3166 CFArray *A= new CFArray [factors.length() - 1];
3167 bool wasInBounds= false;
3168 bool hitBound= false;
3169 int l= (minBound+1)*2;
3170 int stepSize= 2;
3171 int oldL= l/2;
3172 bool reduced= false;
3175 CFArray buf;
3176 CFMatrix C;
3177 Variable y= F.mvar();
3179 while (l <= liftBound)
3180 {
3182 if (start)
3183 {
3184 henselLiftResume12 (F, factors, start, l, Pi, diophant, M);
3185 start= 0;
3186 }
3187 else
3188 {
3189 if (wasInBounds)
3191 else
3192 henselLift12 (F, factors, l, Pi, diophant, M);
3193 }
3195 "time to lift in compute lattice: ");
3196
3197 factors.insert (LCF);
3198 j= factors;
3199 j++;
3200
3201 truncF= mod (F, power (y,l));
3203 for (int i= 0; i < factors.length() - 1; i++, j++)
3204 {
3205 if (l == (minBound+1)*2)
3206 {
3207 A[i]= logarithmicDerivative (truncF, j.getItem(), l, bufQ[i]);
3208 }
3209 else
3210 {
3211 A[i]= logarithmicDerivative (truncF, j.getItem(), l, oldL, bufQ[i],
3212 bufQ[i]
3213 );
3214 }
3215 }
3217 "time to compute logarithmic derivative: ");
3218
3219 for (int i= 0; i < sizeBounds; i++)
3220 {
3221 if (bounds [i] + 1 <= l/2)
3222 {
3223 wasInBounds= true;
3224 int k= tmin (bounds [i] + 1, l/2);
3225 C= CFMatrix (l - k, factors.length() - 1);
3226 for (int ii= 0; ii < factors.length() - 1; ii++)
3227 {
3228
3229 if (A[ii].size() - 1 >= i)
3230 {
3231 buf= getCoeffs (A[ii] [i], k);
3232 writeInMatrix (C, buf, ii + 1, 0);
3233 }
3234 }
3235
3237 NTLK= (*NTLC)*NTLN;
3238 transpose (NTLK, NTLK);
3239 kernel (NTLK, NTLK);
3240 transpose (NTLK, NTLK);
3241 NTLN *= NTLK;
3242 delete NTLC;
3243
3244 if (NTLN.NumCols() == 1)
3245 {
3246 irreducible= true;
3247 break;
3248 }
3249 if (isReduced (NTLN) && l > (minBound+1)*2)
3250 {
3251 reduced= true;
3252 break;
3253 }
3254 }
3255 }
3256
3257 if (NTLN.NumCols() == 1)
3258 {
3259 irreducible= true;
3260 break;
3261 }
3262 if (reduced)
3263 break;
3264 oldL= l;
3265 l += stepSize;
3266 stepSize *= 2;
3267 if (l > liftBound)
3268 {
3269 if (!hitBound)
3270 {
3271 l= liftBound;
3272 hitBound= true;
3273 }
3274 else
3275 break;
3276 }
3277 }
3278 delete [] A;
3279 if (!wasInBounds)
3280 {
3281 if (start)
3282 henselLiftResume12 (F, factors, start, degree (F) + 1, Pi, diophant, M);
3283 else
3284 henselLift12 (F, factors, degree (F) + 1, Pi, diophant, M);
3285 factors.insert (LCF);
3286 }
3287 return l;
3288}

◆ liftAndComputeLattice() [3/3]

int liftAndComputeLattice ( const CanonicalForm F,
int bounds,
int  sizeBounds,
int  start,
int  liftBound,
int  minBound,
CFList factors,
nmod_mat_t  FLINTN,
CFList diophant,
CFMatrix M,
CFArray Pi,
CFArray bufQ,
bool irreducible 
)

Definition at line 2612 of file facFqBivar.cc.

2617{
2618 CanonicalForm LCF= LC (F, 1);
2619 CFArray *A= new CFArray [factors.length() - 1];
2620 bool wasInBounds= false;
2621 bool hitBound= false;
2622 int l= (minBound+1)*2;
2623 int stepSize= 2;
2624 int oldL= l/2;
2625 bool reduced= false;
2626 long rank;
2628 CFMatrix C;
2629 CFArray buf;
2632 Variable y= F.mvar();
2633 while (l <= liftBound)
2634 {
2636 if (start)
2637 {
2638 henselLiftResume12 (F, factors, start, l, Pi, diophant, M);
2639 start= 0;
2640 }
2641 else
2642 {
2643 if (wasInBounds)
2645 else
2646 henselLift12 (F, factors, l, Pi, diophant, M);
2647 }
2649 "time to lift in compute lattice: ");
2650
2651 factors.insert (LCF);
2652 j= factors;
2653 j++;
2654
2655 truncF= mod (F, power (y, l));
2657 for (int i= 0; i < factors.length() - 1; i++, j++)
2658 {
2659 if (!wasInBounds)
2660 A[i]= logarithmicDerivative (truncF, j.getItem(), l, bufQ[i]);
2661 else
2662 A[i]= logarithmicDerivative (truncF, j.getItem(), l, oldL, bufQ[i],
2663 bufQ[i]);
2664 }
2666 "time to compute logarithmic derivative: ");
2667
2668 for (int i= 0; i < sizeBounds; i++)
2669 {
2670 if (bounds [i] + 1 <= l/2)
2671 {
2672 wasInBounds= true;
2673 int k= tmin (bounds [i] + 1, l/2);
2674 C= CFMatrix (l - k, factors.length() - 1);
2675 for (int ii= 0; ii < factors.length() - 1; ii++)
2676 {
2677 if (A[ii].size() - 1 >= i)
2678 {
2679 buf= getCoeffs (A[ii] [i], k);
2680 writeInMatrix (C, buf, ii + 1, 0);
2681 }
2682 }
2683
2698 nmod_mat_mul (FLINTN, FLINTC, FLINTK); //no aliasing allowed!!
2699
2703 if (nmod_mat_ncols (FLINTN) == 1)
2704 {
2705 irreducible= true;
2706 break;
2707 }
2708 if (isReduced (FLINTN) && l > (minBound+1)*2)
2709 {
2710 reduced= true;
2711 break;
2712 }
2713 }
2714 }
2715
2716 if (irreducible)
2717 break;
2718 if (reduced)
2719 break;
2720 oldL= l;
2721 l += stepSize;
2722 stepSize *= 2;
2723 if (l > liftBound)
2724 {
2725 if (!hitBound)
2726 {
2727 l= liftBound;
2728 hitBound= true;
2729 }
2730 else
2731 break;
2732 }
2733 }
2734 delete [] A;
2735 if (!wasInBounds)
2736 {
2737 if (start)
2738 henselLiftResume12 (F, factors, start, degree (F) + 1, Pi, diophant, M);
2739 else
2740 henselLift12 (F, factors, degree (F) + 1, Pi, diophant, M);
2741 factors.insert (LCF);
2742 }
2743 return l;
2744}

◆ liftAndComputeLatticeFq2Fp()

int liftAndComputeLatticeFq2Fp ( const CanonicalForm F,
int bounds,
int  sizeBounds,
int  start,
int  liftBound,
int  minBound,
CFList factors,
nmod_mat_t  FLINTN,
CFList diophant,
CFMatrix M,
CFArray Pi,
CFArray bufQ,
bool irreducible,
const Variable alpha 
)

Definition at line 3294 of file facFqBivar.cc.

3309{
3310 CanonicalForm LCF= LC (F, 1);
3311 CFArray *A= new CFArray [factors.length() - 1];
3312 bool wasInBounds= false;
3313 int l= (minBound+1)*2;
3314 int oldL= l/2;
3315 int stepSize= 2;
3316 bool hitBound= false;
3318 bool reduced= false;
3320 CFMatrix C;
3321 CFArray buf;
3322#ifdef HAVE_FLINT
3323 long rank;
3325#else
3326 mat_zz_p* NTLC, NTLK;
3327#endif
3328 Variable y= F.mvar();
3330 while (l <= liftBound)
3331 {
3333 if (start)
3334 {
3335 henselLiftResume12 (F, factors, start, l, Pi, diophant, M);
3336 start= 0;
3337 }
3338 else
3339 {
3340 if (wasInBounds)
3342 else
3343 henselLift12 (F, factors, l, Pi, diophant, M);
3344 }
3346 "time to lift in compute lattice: ");
3347
3348 factors.insert (LCF);
3349 j= factors;
3350 j++;
3351
3352 truncF= mod (F, power (y,l));
3354 for (int i= 0; i < factors.length() - 1; i++, j++)
3355 {
3356 if (l == (minBound+1)*2)
3357 {
3358 A[i]= logarithmicDerivative (truncF, j.getItem(), l, bufQ[i]);
3359 }
3360 else
3361 {
3362 A[i]= logarithmicDerivative (truncF, j.getItem(), l, oldL, bufQ[i],
3363 bufQ[i]
3364 );
3365 }
3366 }
3368 "time to compute logarithmic derivative: ");
3369
3370 for (int i= 0; i < sizeBounds; i++)
3371 {
3372 if (bounds [i] + 1 <= l/2)
3373 {
3374 wasInBounds= true;
3375 int k= tmin (bounds [i] + 1, l/2);
3376 C= CFMatrix ((l - k)*extensionDeg, factors.length() - 1);
3377 for (int ii= 0; ii < factors.length() - 1; ii++)
3378 {
3379 if (A[ii].size() - 1 >= i)
3380 {
3381 buf= getCoeffs (A[ii] [i], k, alpha);
3382 writeInMatrix (C, buf, ii + 1, 0);
3383 }
3384 }
3385
3386#ifdef HAVE_FLINT
3401 nmod_mat_mul (FLINTN, FLINTC, FLINTK); //no aliasing allowed!!
3402
3406#else
3408 NTLK= (*NTLC)*NTLN;
3409 transpose (NTLK, NTLK);
3410 kernel (NTLK, NTLK);
3411 transpose (NTLK, NTLK);
3412 NTLN *= NTLK;
3413 delete NTLC;
3414#endif
3415
3416#ifdef HAVE_FLINT
3417 if (nmod_mat_nrows (FLINTN) == 1)
3418#else
3419 if (NTLN.NumCols() == 1)
3420#endif
3421 {
3422 irreducible= true;
3423 break;
3424 }
3425#ifdef HAVE_FLINT
3426 if (isReduced (FLINTN) && l > (minBound+1)*2)
3427#else
3428 if (isReduced (NTLN) && l > (minBound+1)*2)
3429#endif
3430 {
3431 reduced= true;
3432 break;
3433 }
3434 }
3435 }
3436
3437#ifdef HAVE_FLINT
3438 if (nmod_mat_ncols (FLINTN) == 1)
3439#else
3440 if (NTLN.NumCols() == 1)
3441#endif
3442 {
3443 irreducible= true;
3444 break;
3445 }
3446 if (reduced)
3447 break;
3448 oldL= l;
3449 l += stepSize;
3450 stepSize *= 2;
3451 if (l > liftBound)
3452 {
3453 if (!hitBound)
3454 {
3455 l= liftBound;
3456 hitBound= true;
3457 }
3458 else
3459 break;
3460 }
3461 }
3462 delete [] A;
3463 if (!wasInBounds)
3464 {
3465 if (start)
3466 henselLiftResume12 (F, factors, start, degree (F) + 1, Pi, diophant, M);
3467 else
3468 henselLift12 (F, factors, degree (F) + 1, Pi, diophant, M);
3469 factors.insert (LCF);
3470 }
3471 return l;
3472}

◆ mod()

return mod ( mulNTL(buf1, buf2, b ,
M   
)

◆ monicReconstruction()

CFList monicReconstruction ( CanonicalForm G,
CFList factors,
int zeroOneVecs,
int  precision,
const mat_zz_pE N 
)

Definition at line 1909 of file facFqBivar.cc.

1912{
1913 Variable y= Variable (2);
1914 Variable x= Variable (1);
1915 CanonicalForm F= G;
1918 CFList result;
1922 for (long i= 1; i <= N.NumCols(); i++)
1923 {
1924 if (zeroOneVecs [i - 1] == 0)
1925 continue;
1926 iter= factors;
1927 buf= 1;
1929 for (long j= 1; j <= N.NumRows(); j++, iter++)
1930 {
1931 if (!IsZero (N (j,i)))
1932 {
1933 factorsConsidered.append (iter.getItem());
1934 buf= mulMod2 (buf, iter.getItem(), yToL);
1935 }
1936 }
1937 buf2= buf;
1938 buf= mulMod2 (buf, LC (F,x), yToL);
1939 buf /= content (buf, x);
1940 if (fdivides (buf, F, quot))
1941 {
1942 F= quot;
1943 F /= Lc (F);
1944 result.append (buf2);
1946 }
1947 if (degree (F) <= 0)
1948 {
1949 G= F;
1951 return result;
1952 }
1953 }
1954 G= F;
1956 return result;
1957}

◆ reconstruction() [1/3]

CFList reconstruction ( CanonicalForm G,
CFList factors,
int zeroOneVecs,
int  precision,
const mat_zz_p N,
const CanonicalForm eval 
)

Definition at line 2124 of file facFqBivar.cc.

2126{
2127 Variable y= Variable (2);
2128 Variable x= Variable (1);
2129 CanonicalForm F= G;
2132 CFList result;
2136 for (long i= 1; i <= N.NumCols(); i++)
2137 {
2138 if (zeroOneVecs [i - 1] == 0)
2139 continue;
2140 iter= factors;
2141 buf= 1;
2143 for (long j= 1; j <= N.NumRows(); j++, iter++)
2144 {
2145 if (!IsZero (N (j,i)))
2146 {
2147 factorsConsidered.append (iter.getItem());
2148 buf= mulMod2 (buf, iter.getItem(), yToL);
2149 }
2150 }
2151 buf= mulMod2 (buf, LC (F,x), yToL);
2152 buf /= content (buf, x);
2153 if (fdivides (buf, F, quot))
2154 {
2155 F= quot;
2156 F /= Lc (F);
2157 result.append (buf (y-eval,y));
2159 }
2160 if (degree (F) <= 0)
2161 {
2162 G= F;
2164 return result;
2165 }
2166 }
2167 G= F;
2169 return result;
2170}

◆ reconstruction() [2/3]

CFList reconstruction ( CanonicalForm G,
CFList factors,
int zeroOneVecs,
int  precision,
const mat_zz_pE N,
const CanonicalForm eval 
)

Definition at line 1858 of file facFqBivar.cc.

1861{
1862 Variable y= Variable (2);
1863 Variable x= Variable (1);
1864 CanonicalForm F= G;
1870 for (long i= 1; i <= N.NumCols(); i++)
1871 {
1872 if (zeroOneVecs [i - 1] == 0)
1873 continue;
1874 iter= factors;
1875 buf= 1;
1877 for (long j= 1; j <= N.NumRows(); j++, iter++)
1878 {
1879 if (!IsZero (N (j,i)))
1880 {
1881 factorsConsidered.append (iter.getItem());
1882 buf= mulMod2 (buf, iter.getItem(), yToL);
1883 }
1884 }
1885 buf= mulMod2 (buf, LC (F,x), yToL);
1886 buf /= content (buf, x);
1887 if (fdivides (buf, F, quot))
1888 {
1889 F= quot;
1890 F /= Lc (F);
1891 result.append (buf (y-eval,y));
1893 }
1894 if (degree (F) <= 0)
1895 {
1896 G= F;
1898 return result;
1899 }
1900 }
1901 G= F;
1903 return result;
1904}

◆ reconstruction() [3/3]

CFList reconstruction ( CanonicalForm G,
CFList factors,
int zeroOneVecs,
int  precision,
const nmod_mat_t  N,
const CanonicalForm eval 
)

Definition at line 2175 of file facFqBivar.cc.

2177{
2178 Variable y= Variable (2);
2179 Variable x= Variable (1);
2180 CanonicalForm F= G;
2183 CFList result;
2187 for (long i= 0; i < nmod_mat_ncols (N); i++)
2188 {
2189 if (zeroOneVecs [i] == 0)
2190 continue;
2191 iter= factors;
2192 buf= 1;
2194 for (long j= 0; j < nmod_mat_nrows (N); j++, iter++)
2195 {
2196 if (!(nmod_mat_entry (N, j, i) == 0))
2197 {
2198 factorsConsidered.append (iter.getItem());
2199 buf= mulMod2 (buf, iter.getItem(), yToL);
2200 }
2201 }
2202 buf= mulMod2 (buf, LC (F,x), yToL);
2203 buf /= content (buf, x);
2204 if (fdivides (buf, F, quot))
2205 {
2206 F= quot;
2207 F /= Lc (F);
2208 result.append (buf (y-eval,y));
2210 }
2211 if (degree (F) <= 0)
2212 {
2213 G= F;
2215 return result;
2216 }
2217 }
2218 G= F;
2220 return result;
2221}

◆ reconstructionTry() [1/3]

void reconstructionTry ( CFList reconstructedFactors,
CanonicalForm F,
const CFList factors,
const int  liftBound,
int factorsFound,
int *&  factorsFoundIndex,
mat_zz_p N,
const CanonicalForm eval,
bool  beenInThres 
)

Definition at line 1690 of file facFqBivar.cc.

1695{
1696 Variable y= Variable (2);
1697 Variable x= Variable (1);
1699 CanonicalForm bufF= F (y-eval, y);
1700 if (factors.length() == 2)
1701 {
1704 tmp2= factors.getLast();
1705 tmp1= mulMod2 (tmp1, LC (F,x), yToL);
1706 tmp1 /= content (tmp1, x);
1707 tmp1= tmp1 (y-eval, y);
1708 tmp2= mulMod2 (tmp2, LC (F,x), yToL);
1709 tmp2 /= content (tmp2, x);
1710 tmp2= tmp2 (y-eval,y);
1711 tmp3 = tmp1*tmp2;
1712 if (tmp3/Lc (tmp3) == bufF/Lc (bufF))
1713 {
1714 factorsFound++;
1715 F= 1;
1718 return;
1719 }
1720 }
1723 for (long i= 1; i <= N.NumCols(); i++)
1724 {
1725 if (factorsFoundIndex [i - 1] == 1)
1726 continue;
1727 iter= factors;
1728 if (beenInThres)
1729 {
1730 int count= 1;
1731 while (count < i)
1732 {
1733 count++;
1734 iter++;
1735 }
1736 buf= iter.getItem();
1737 }
1738 else
1739 {
1740 buf= 1;
1741 for (long j= 1; j <= N.NumRows(); j++, iter++)
1742 {
1743 if (!IsZero (N (j,i)))
1744 buf= mulMod2 (buf, iter.getItem(), yToL);
1745 }
1746 }
1747 buf= mulMod2 (buf, LC (F,x), yToL);
1748 buf /= content (buf, x);
1749 buf= buf (y-eval,y);
1750 if (fdivides (buf, bufF, quot))
1751 {
1752 factorsFoundIndex[i - 1]= 1;
1753 factorsFound++;
1754 bufF= quot;
1755 bufF /= Lc (bufF);
1757 }
1758 if (degree (bufF) <= 0)
1759 return;
1760 if (factorsFound + 1 == N.NumCols())
1761 {
1763 F=1;
1764 return;
1765 }
1766 }
1767 if (reconstructedFactors.length() != 0)
1768 F= bufF (y+eval,y);
1769}

◆ reconstructionTry() [2/3]

void reconstructionTry ( CFList reconstructedFactors,
CanonicalForm F,
const CFList factors,
const int  liftBound,
int factorsFound,
int *&  factorsFoundIndex,
mat_zz_pE N,
const CanonicalForm eval,
bool  beenInThres 
)

Definition at line 1606 of file facFqBivar.cc.

1611{
1612 Variable y= Variable (2);
1613 Variable x= Variable (1);
1615 CanonicalForm bufF= F (y-eval, y);
1616 if (factors.length() == 2)
1617 {
1620 tmp2= factors.getLast();
1621 tmp1= mulMod2 (tmp1, LC (F,x), yToL);
1622 tmp1 /= content (tmp1, x);
1623 tmp1= tmp1 (y-eval, y);
1624 tmp2= mulMod2 (tmp2, LC (F,x), yToL);
1625 tmp2 /= content (tmp2, x);
1626 tmp2= tmp2 (y-eval, y);
1627 tmp3 = tmp1*tmp2;
1628 if (tmp3/Lc (tmp3) == bufF/Lc (bufF))
1629 {
1630 factorsFound++;
1631 F= 1;
1634 return;
1635 }
1636 }
1639 for (long i= 1; i <= N.NumCols(); i++)
1640 {
1641 if (factorsFoundIndex [i - 1] == 1)
1642 continue;
1643 iter= factors;
1644 if (beenInThres)
1645 {
1646 int count= 1;
1647 while (count < i)
1648 {
1649 count++;
1650 iter++;
1651 }
1652 buf= iter.getItem();
1653 }
1654 else
1655 {
1656 buf= 1;
1657 for (long j= 1; j <= N.NumRows(); j++, iter++)
1658 {
1659 if (!IsZero (N (j,i)))
1660 buf= mulMod2 (buf, iter.getItem(), yToL);
1661 }
1662 }
1663 buf= mulMod2 (buf, LC (F,x), yToL);
1664 buf /= content (buf, x);
1665 buf= buf (y-eval,y);
1666 if (fdivides (buf, bufF, quot))
1667 {
1668 factorsFoundIndex[i - 1]= 1;
1669 factorsFound++;
1670 bufF= quot;
1671 bufF /= Lc (bufF);
1673 }
1674 if (degree (bufF) <= 0)
1675 return;
1676 if (factorsFound + 1 == N.NumCols())
1677 {
1679 F= 1;
1680 return;
1681 }
1682 }
1683 if (reconstructedFactors.length() != 0)
1684 F= bufF (y+eval,y);
1685}

◆ reconstructionTry() [3/3]

void reconstructionTry ( CFList reconstructedFactors,
CanonicalForm F,
const CFList factors,
const int  liftBound,
int factorsFound,
int *&  factorsFoundIndex,
nmod_mat_t  N,
const CanonicalForm eval,
bool  beenInThres 
)

Definition at line 1774 of file facFqBivar.cc.

1779{
1780 Variable y= Variable (2);
1781 Variable x= Variable (1);
1783 CanonicalForm bufF= F (y-eval, y);
1784 if (factors.length() == 2)
1785 {
1788 tmp2= factors.getLast();
1789 tmp1= mulMod2 (tmp1, LC (F,x), yToL);
1790 tmp1 /= content (tmp1, x);
1791 tmp1= tmp1 (y-eval, y);
1792 tmp2= mulMod2 (tmp2, LC (F,x), yToL);
1793 tmp2 /= content (tmp2, x);
1794 tmp2= tmp2 (y-eval, y);
1795 tmp3 = tmp1*tmp2;
1796 if (tmp3/Lc (tmp3) == bufF/Lc (bufF))
1797 {
1798 factorsFound++;
1799 F= 1;
1802 return;
1803 }
1804 }
1807 for (long i= 0; i < nmod_mat_ncols (N); i++)
1808 {
1809 if (factorsFoundIndex [i] == 1)
1810 continue;
1811 iter= factors;
1812 if (beenInThres)
1813 {
1814 int count= 0;
1815 while (count < i)
1816 {
1817 count++;
1818 iter++;
1819 }
1820 buf= iter.getItem();
1821 }
1822 else
1823 {
1824 buf= 1;
1825 for (long j= 0; j < nmod_mat_nrows (N); j++, iter++)
1826 {
1827 if (!(nmod_mat_entry (N, j, i) == 0))
1828 buf= mulMod2 (buf, iter.getItem(), yToL);
1829 }
1830 }
1831 buf= mulMod2 (buf, LC (F,x), yToL);
1832 buf /= content (buf, x);
1833 buf= buf (y-eval,y);
1834 if (fdivides (buf, bufF, quot))
1835 {
1836 factorsFoundIndex[i]= 1;
1837 factorsFound++;
1838 bufF= quot;
1839 bufF /= Lc (bufF);
1841 }
1842 if (degree (F) <= 0)
1843 return;
1844 if (factorsFound + 1 == nmod_mat_ncols (N))
1845 {
1846 F= 1;
1848 return;
1849 }
1850 }
1851 if (reconstructedFactors.length() != 0)
1852 F= bufF (y+eval,y);
1853}

◆ refineAndRestartLift() [1/2]

void refineAndRestartLift ( const CanonicalForm F,
const mat_zz_pE NTLN,
int  liftBound,
int  l,
CFList factors,
CFMatrix M,
CFArray Pi,
CFList diophant 
)

Definition at line 6175 of file facFqBivar.cc.

6179{
6181 Variable y= Variable (2);
6182 CanonicalForm LCF= LC (F, 1);
6185 for (long i= 1; i <= NTLN.NumCols(); i++)
6186 {
6187 iter= factors;
6188 buf= 1;
6189 for (long j= 1; j <= NTLN.NumRows(); j++, iter++)
6190 {
6191 if (!IsZero (NTLN (j,i)))
6192 buf= mulNTL (buf, mod (iter.getItem(), y));
6193 }
6195 }
6198 Pi= CFArray();
6199 diophant= CFList();
6200 factors.insert (LCF);
6201 henselLift12 (F, factors, l, Pi, diophant, M);
6202}

◆ refineAndRestartLift() [2/2]

void refineAndRestartLift ( const CanonicalForm F,
const nmod_mat_t  FLINTN,
int  liftBound,
int  l,
CFList factors,
CFMatrix M,
CFArray Pi,
CFList diophant 
)

Definition at line 6142 of file facFqBivar.cc.

6146{
6148 Variable y= Variable (2);
6149 CanonicalForm LCF= LC (F, 1);
6152 for (long i= 0; i < nmod_mat_ncols (FLINTN); i++)
6153 {
6154 iter= factors;
6155 buf= 1;
6156 for (long j= 0; j < nmod_mat_nrows (FLINTN); j++, iter++)
6157 {
6158 if (!(nmod_mat_entry (FLINTN,j,i) == 0))
6159 buf= mulNTL (buf, mod (iter.getItem(), y));
6160 }
6162 }
6165 Pi= CFArray();
6166 diophant= CFList();
6167 factors.insert (LCF);
6168 henselLift12 (F, factors, l, Pi, diophant, M);
6169}

◆ sieveSmallFactors()

CFList sieveSmallFactors ( const CanonicalForm G,
CFList uniFactors,
DegreePattern degPat,
CanonicalForm H,
CFList diophant,
CFArray Pi,
CFMatrix M,
bool success,
int  d,
const CanonicalForm eval 
)

Definition at line 6764 of file facFqBivar.cc.

6768{
6769 CanonicalForm F= G;
6771 bufUniFactors.insert (LC (F, 1));
6772 int smallFactorDeg= d;
6775 int adaptedLiftBound;
6776 success= false;
6777 int * factorsFoundIndex= new int [uniFactors.length()];
6778 for (int i= 0; i < uniFactors.length(); i++)
6779 factorsFoundIndex [i]= 0;
6783 delete [] factorsFoundIndex;
6784 if (degs.getLength() == 1)
6785 {
6786 degPat= degs;
6787 return earlyFactors;
6788 }
6789 if (success)
6790 {
6791 H= F;
6792 return earlyFactors;
6793 }
6794 int sizeOldF= size (G);
6795 if (size (F) < sizeOldF)
6796 {
6797 H= F;
6798 success= true;
6799 return earlyFactors;
6800 }
6801 else
6802 {
6804 return CFList();
6805 }
6806}

◆ TIMING_DEFINE_PRINT()

TIMING_DEFINE_PRINT ( fac_fq_uni_factorizer  ) 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 162 of file facFqBivar.cc.

163{
164 Variable x= A.mvar();
165 if (A.inCoeffDomain())
166 return CFList();
167 ASSERT (A.isUnivariate(),
168 "univariate polynomial expected or constant expected");
170 if (GF)
171 {
172 int k= getGFDegree();
173 char cGFName= gf_name;
178#ifdef HAVE_NTL
179 if (getCharacteristic() > 2)
180#else
181 if (getCharacteristic() > 0)
182#endif
183 {
184#if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
189
192
194
197
200
202
204 beta, fq_con);
205
211#else
213 {
215 zz_p::init (getCharacteristic());
216 }
218 zz_pE::init (NTLMipo);
220 MakeMonic (NTLA);
222 zz_pE multi= to_zz_pE (1);
224 x, beta);
225#endif
226 }
227#ifdef HAVE_NTL
228 else
229 {
231 GF2E::init (NTLMipo);
233 MakeMonic (NTLA);
235 GF2E multi= to_GF2E (1);
237 x, beta);
238 }
239#endif
241 for (CFFListIterator i= factorsA; i.hasItem(); i++)
242 {
243 buf= i.getItem().factor();
245 i.getItem()= CFFactor (buf, i.getItem().exp());
246 }
247 prune (beta);
248 }
249 else if (alpha.level() != 1)
250 {
251#ifdef HAVE_NTL
252 if (getCharacteristic() > 2)
253#else
254 if (getCharacteristic() > 0)
255#endif
256 {
257#if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
262
265
267
270
273
275
277 alpha, fq_con);
278
284#else
286 {
288 zz_p::init (getCharacteristic());
289 }
291 zz_pE::init (NTLMipo);
293 MakeMonic (NTLA);
295 zz_pE multi= to_zz_pE (1);
297 x, alpha);
298#endif
299 }
300#ifdef HAVE_NTL
301 else
302 {
304 GF2E::init (NTLMipo);
306 MakeMonic (NTLA);
308 GF2E multi= to_GF2E (1);
310 x, alpha);
311 }
312#endif
313 }
314 else
315 {
316#ifdef HAVE_FLINT
317#ifdef HAVE_NTL
318 if (degree (A) < 300)
319#endif
320 {
327 if (factorsA.getFirst().factor().inCoeffDomain())
331 }
332#ifdef HAVE_NTL
333 else
334#endif
335#endif /* HAVE_FLINT */
336#ifdef HAVE_NTL
337 if (getCharacteristic() > 2)
338 {
340 {
342 zz_p::init (getCharacteristic());
343 }
345 MakeMonic (NTLA);
347 zz_p multi= to_zz_p (1);
349 x);
350 }
351 else
352 {
355 GF2 multi= to_GF2 (1);
357 x);
358 }
359#endif
360 }
362 for (CFFListIterator i= factorsA; i.hasItem(); i++)
363 uniFactors.append (i.getItem().factor());
364 return uniFactors;
365}
CFFList convertFLINTFq_nmod_poly_factor2FacCFFList(const fq_nmod_poly_factor_t fac, const Variable &x, const Variable &alpha, const fq_nmod_ctx_t fq_con)
conversion of a FLINT factorization over Fq (for word size p) to a CFFList
void convertFacCF2Fq_nmod_poly_t(fq_nmod_poly_t result, const CanonicalForm &f, const fq_nmod_ctx_t ctx)
conversion of a factory univariate poly over F_q to a FLINT fq_nmod_poly_t
CFFList convertFLINTnmod_poly_factor2FacCFFList(const nmod_poly_factor_t fac, const mp_limb_t leadingCoeff, const Variable &x)
conversion of a FLINT factorization over Z/p (for word size p) to a CFFList
CFFList convertNTLvec_pair_GF2X_long2FacCFFList(const vec_pair_GF2X_long &e, GF2, const Variable &x)
NAME: convertNTLvec_pair_GF2X_long2FacCFFList.
zz_pEX convertFacCF2NTLzz_pEX(const CanonicalForm &f, const zz_pX &mipo)
CFFList convertNTLvec_pair_zzpEX_long2FacCFFList(const vec_pair_zz_pEX_long &e, const zz_pE &cont, const Variable &x, const Variable &alpha)
CFFList convertNTLvec_pair_GF2EX_long2FacCFFList(const vec_pair_GF2EX_long &e, const GF2E &cont, const Variable &x, const Variable &alpha)
NAME: convertNTLvec_pair_GF2EX_long2FacCFFList.
CFFList convertNTLvec_pair_zzpX_long2FacCFFList(const vec_pair_zz_pX_long &e, const zz_p cont, const Variable &x)
GF2EX convertFacCF2NTLGF2EX(const CanonicalForm &f, const GF2X &mipo)
CanonicalForm in Z_2(a)[X] to NTL GF2EX.
GF2X convertFacCF2NTLGF2X(const CanonicalForm &f)
NAME: convertFacCF2NTLGF2X.
Factor< CanonicalForm > CFFactor
fq_nmod_ctx_t fq_con
Definition facHensel.cc:99
fq_nmod_ctx_clear(fq_con)
fq_nmod_ctx_init_modulus(fq_con, FLINTmipo, "Z")
convertFacCF2nmod_poly_t(FLINTmipo, M)
nmod_poly_clear(FLINTmipo)
fq_nmod_poly_clear(prod, fq_con)

Variable Documentation

◆ b

else L b
Initial value:
{
if (L.isEmpty())
return 1

Definition at line 62 of file facFqBivar.cc.

◆ buf1

buf1 = prodMod0 (tmp1, M, b)

Definition at line 75 of file facFqBivar.cc.

◆ buf2

buf2 = prodMod0 (tmp2, M, b)

Definition at line 75 of file facFqBivar.cc.

◆ else

else
Initial value:
{
int l= L.length()/2

Definition at line 70 of file facFqBivar.cc.

◆ i

Definition at line 73 of file facFqBivar.cc.

◆ M

else L M

Definition at line 62 of file facFqBivar.cc.

◆ tmp1

CFList tmp1

Definition at line 74 of file facFqBivar.cc.

◆ tmp2

tmp2 = Difference (L, tmp1)

Definition at line 74 of file facFqBivar.cc.