My Project
Loading...
Searching...
No Matches
Functions
facFqBivar.h File Reference

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

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

Go to the source code of this file.

Functions

 TIMING_DEFINE_PRINT (fac_fq_bi_sqrf) TIMING_DEFINE_PRINT(fac_fq_bi_factor_sqrf) static const double log2exp
 
CFList biFactorize (const CanonicalForm &F, const ExtensionInfo &info)
 Factorization of a squarefree bivariate polynomials over an arbitrary finite field, information on the current field we work over is in info. info may also contain information about the initial field if initial and current field do not coincide. In this case the current field is an extension of the initial field and the factors returned are factors of F over the initial field.
 
CFList biSqrfFactorizeHelper (const CanonicalForm &G, const ExtensionInfo &info)
 
CFList FpBiSqrfFactorize (const CanonicalForm &G)
 factorize a squarefree bivariate polynomial over $ F_{p} $.
 
CFList FqBiSqrfFactorize (const CanonicalForm &G, const Variable &alpha)
 factorize a squarefree bivariate polynomial over $ F_{p}(\alpha ) $.
 
CFList GFBiSqrfFactorize (const CanonicalForm &G)
 factorize a squarefree bivariate polynomial over GF
 
CFFList FpBiFactorize (const CanonicalForm &G, bool substCheck=true)
 factorize a bivariate polynomial over $ F_{p} $
 
CFFList FqBiFactorize (const CanonicalForm &G, const Variable &alpha, bool substCheck=true)
 factorize a bivariate polynomial over $ F_{p}(\alpha ) $
 
CFFList GFBiFactorize (const CanonicalForm &G, bool substCheck=true)
 factorize a bivariate polynomial over GF
 
CanonicalForm prodMod0 (const CFList &L, const CanonicalForm &M, const modpk &b=modpk())
 $ \prod_{f\in L} {f (0, x)} \ mod\ M $ via divide-and-conquer
 
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 &M, const ExtensionInfo &info, DegreePattern &degs, const CanonicalForm &eval, int s, int thres)
 naive factor recombination over an extension of the initial field. Uses precomputed data to exclude combinations that are not possible.
 
CFList factorRecombination (CFList &factors, CanonicalForm &F, const CanonicalForm &M, DegreePattern &degs, const CanonicalForm &eval, int s, int thres, const modpk &b=modpk(), const CanonicalForm &den=1)
 naive factor recombination. Uses precomputed data to exclude combinations that are not possible.
 
Variable chooseExtension (const Variable &alpha, const Variable &beta, int k)
 chooses a field extension.
 
intgetLiftPrecisions (const CanonicalForm &F, int &sizeOfOutput, int degreeLC)
 compute lifting precisions from the shape of the Newton polygon of F
 
void earlyFactorDetection (CFList &reconstructedFactors, CanonicalForm &F, CFList &factors, int &adaptedLiftBound, int *&factorsFoundIndex, DegreePattern &degs, bool &success, int deg, const CanonicalForm &eval, const modpk &b=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.
 
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.
 
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
 
CFList extBiFactorize (const CanonicalForm &F, const ExtensionInfo &info)
 Factorization over an extension of initial field.
 

Detailed Description

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

Author
Martin Lee

Definition in file facFqBivar.h.

Function Documentation

◆ biFactorize()

CFList biFactorize ( const CanonicalForm & F,
const ExtensionInfo & info )

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

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

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

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

Definition at line 8306 of file facFqBivar.cc.

8307{
8308 if (F.inCoeffDomain())
8309 return CFList(F);
8310
8311 CanonicalForm A= F;
8313
8314 Variable alpha= info.getAlpha();
8315 Variable beta= info.getBeta();
8316 CanonicalForm gamma= info.getGamma();
8317 CanonicalForm delta= info.getDelta();
8318 int k= info.getGFDegree();
8319 bool extension= info.isInExtension();
8320 if (A.isUnivariate())
8321 {
8322 if (extension == false)
8323 return uniFactorizer (F, alpha, GF);
8324 else
8325 {
8326 CFList source, dest;
8327 A= mapDown (A, info, source, dest);
8328 return uniFactorizer (A, beta, GF);
8329 }
8330 }
8331
8332 CFMap N;
8333 A= compress (A, N);
8334 Variable y= A.mvar();
8335
8336 if (y.level() > 2) return CFList (F);
8337 Variable x= Variable (1);
8338
8339 //remove and factorize content
8342
8345
8346 if (!extension)
8347 {
8350 }
8351
8352 //trivial case
8354 if (A.inCoeffDomain())
8355 {
8358 decompress (factors, N);
8359 return factors;
8360 }
8361 else if (A.isUnivariate())
8362 {
8366 decompress (factors, N);
8367 return factors;
8368 }
8369
8370
8371 //check trivial case
8372 if (degree (A) == 1 || degree (A, 1) == 1 ||
8373 (size (A) == 2 && igcd (degree (A), degree (A,1))==1))
8374 {
8375 factors.append (A);
8376
8378 false, false, N);
8379
8380 if (!extension)
8382 return factors;
8383 }
8384
8385 // check derivatives
8386 bool derivXZero= false;
8389 if (derivX.isZero())
8390 derivXZero= true;
8391 else
8392 {
8393 gcdDerivX= gcd (A, derivX);
8394 if (degree (gcdDerivX) > 0)
8395 {
8402 if (!extension)
8404 return factorsG;
8405 }
8406 }
8407 bool derivYZero= false;
8410 if (derivY.isZero())
8411 derivYZero= true;
8412 else
8413 {
8414 gcdDerivY= gcd (A, derivY);
8415 if (degree (gcdDerivY) > 0)
8416 {
8423 if (!extension)
8425 return factorsG;
8426 }
8427 }
8428 //main variable is chosen s.t. the degree in x is minimal
8429 bool swap= false;
8430 if ((degree (A) > degree (A, x)) || derivXZero)
8431 {
8432 if (!derivYZero)
8433 {
8434 A= swapvar (A, y, x);
8438 swap= true;
8439 }
8440 }
8441
8442 int boundsLength;
8443 bool isIrreducible= false;
8445 if (isIrreducible)
8446 {
8447 delete [] bounds;
8448 factors.append (A);
8449
8451 swap, false, N);
8452
8453 if (!extension)
8455 return factors;
8456 }
8457
8458 int minBound= bounds[0];
8459 for (int i= 1; i < boundsLength; i++)
8460 {
8461 if (bounds[i] != 0)
8463 }
8464
8465 int boundsLength2;
8467 int minBound2= bounds2[0];
8468 for (int i= 1; i < boundsLength2; i++)
8469 {
8470 if (bounds2[i] != 0)
8472 }
8473
8474
8475 bool fail= false;
8480
8481 bool fail2= false;
8486 bool swap2= false;
8487
8488 // several univariate factorizations to obtain more information about the
8489 // degree pattern therefore usually less combinations have to be tried during
8490 // the recombination process
8491 int factorNums= 3;
8492 int subCheck1= substituteCheck (A, x);
8493 int subCheck2= substituteCheck (A, y);
8494 bool symmetric= false;
8495
8497 for (int i= 0; i < factorNums; i++)
8498 {
8499 bufAeval= A;
8502 TIMING_END_AND_PRINT (fac_fq_bi_evaluation, "time to find eval point: ");
8503 if (!derivXZero && !fail2 && !symmetric)
8504 {
8505 if (i == 0)
8506 {
8507 buf= swapvar (A, x, y);
8508 symmetric= (A/Lc (A) == buf/Lc (buf));
8509 }
8510 bufAeval2= buf;
8514 "time to find eval point wrt y: ");
8515 }
8516 // first try to change main variable if there is no valid evaluation point
8517 if (fail && (i == 0))
8518 {
8519 if (!derivXZero && !fail2 && !symmetric)
8520 {
8522 int dummy= subCheck2;
8525 tmp= A;
8526 A= buf;
8527 buf= tmp;
8529 swap2= true;
8530 fail= false;
8531 }
8532 else
8533 fail= true;
8534 }
8535
8536 // if there is no valid evaluation point pass to a field extension
8537 if (fail && (i == 0))
8538 {
8541 swap, swap2, N);
8543 delete [] bounds;
8544 delete [] bounds2;
8545 return factors;
8546 }
8547
8548 // there is at least one valid evaluation point
8549 // but we do not compute more univariate factorization over an extension
8550 if (fail && (i != 0))
8551 break;
8552
8553 // univariate factorization
8557 "time for univariate factorization over Fq: ");
8558 DEBOUTLN (cerr, "Lc (bufAeval)*prod (bufUniFactors)== bufAeval " <<
8560
8561 if (!derivXZero && !fail2 && !symmetric)
8562 {
8566 "time for univariate factorization in y over Fq: ");
8567 DEBOUTLN (cerr, "Lc (bufAeval2)*prod (bufUniFactors2)== bufAeval2 " <<
8569 }
8570
8571 if (bufUniFactors.length() == 1 ||
8572 (!fail2 && !derivXZero && !symmetric && (bufUniFactors2.length() == 1)))
8573 {
8574 if (extension)
8575 {
8576 CFList source, dest;
8577 appendMapDown (factors, A, info, source, dest);
8578 }
8579 else
8580 factors.append (A);
8581
8583 swap, swap2, N);
8584
8585 if (!extension)
8587 delete [] bounds;
8588 delete [] bounds2;
8589 return factors;
8590 }
8591
8592 if (i == 0 && !extension)
8593 {
8594 if (subCheck1 > 0)
8595 {
8597
8598 if (subCheck > 1 && (subCheck1%subCheck == 0))
8599 {
8601 subst (bufA, bufA, subCheck, x);
8605 swap, swap2, N);
8606 if (!extension)
8608 delete [] bounds;
8609 delete [] bounds2;
8610 return factors;
8611 }
8612 }
8613
8614 if (!derivXZero && !fail2 && !symmetric && subCheck2 > 0)
8615 {
8617
8618 if (subCheck > 1 && (subCheck2%subCheck == 0))
8619 {
8621 subst (bufA, bufA, subCheck, y);
8625 swap, swap2, N);
8626 if (!extension)
8628 delete [] bounds;
8629 delete [] bounds2;
8630 return factors;
8631 }
8632 }
8633 }
8634
8635 // degree analysis
8637 if (!derivXZero && !fail2 && !symmetric)
8639
8640 if (i == 0)
8641 {
8642 Aeval= bufAeval;
8645 degs= bufDegs;
8646 if (!derivXZero && !fail2 && !symmetric)
8647 {
8651 degs2= bufDegs2;
8652 }
8653 }
8654 else
8655 {
8656 degs.intersect (bufDegs);
8657 if (!derivXZero && !fail2 && !symmetric)
8658 {
8659 degs2.intersect (bufDegs2);
8661 {
8665 }
8666 }
8668 {
8670 Aeval= bufAeval;
8672 }
8673 }
8674 list.append (bufEvaluation);
8675 if (!derivXZero && !fail2 && !symmetric)
8677 }
8679 "total time for univariate factorizations: ");
8680
8681 if (!derivXZero && !fail2 && !symmetric)
8682 {
8685 && degs.getLength() > degs2.getLength() && minBound2 <= minBound))
8686 {
8687 degs= degs2;
8690 Aeval= Aeval2;
8691 A= buf;
8692 swap2= true;
8693 }
8694 }
8695
8696 if (degs.getLength() == 1) // A is irreducible
8697 {
8698 if (extension)
8699 {
8700 CFList source, dest;
8701 appendMapDown (factors, A, info, source, dest);
8702 }
8703 else
8704 factors.append (A);
8706 swap, swap2, N);
8707 if (!extension)
8709 delete [] bounds;
8710 delete [] bounds2;
8711 return factors;
8712 }
8713
8714 int liftBound= degree (A, y) + 1;
8715
8716 if (swap2)
8717 {
8718 delete [] bounds;
8719 bounds= bounds2;
8721 }
8722
8724 A= A (y + evaluation, y);
8726 "time to shift eval to zero: ");
8727
8728 int degMipo= 1;
8729 if (extension && alpha.level() != 1 && k==1)
8731
8732 DEBOUTLN (cerr, "uniFactors= " << uniFactors);
8733
8734 if ((GF && !extension) || (GF && extension && k != 1))
8735 {
8736 bool earlySuccess= false;
8743 "time for bivariate hensel lifting over Fq: ");
8744 DEBOUTLN (cerr, "lifted factors= " << uniFactors);
8745
8747
8749 if (extension)
8751 evaluation, 1, uniFactors.length()/2);
8752 else
8754 uniFactors.length()/2);
8756 "time for naive bivariate factor recombi over Fq: ");
8757
8758 if (earlySuccess)
8760 else if (!earlySuccess && degs.getLength() == 1)
8762 }
8763 else if (degree (A) > 4 && beta.level() == 1 && (2*minBound)/degMipo < 32)
8764 {
8766 if (extension)
8767 {
8770 );
8772 }
8773 else if (alpha.level() == 1 && !GF)
8774 {
8778 }
8779 else if (!extension && (alpha != x || GF))
8780 {
8784 }
8786 "time to bivar lift and LLL recombi over Fq: ");
8787 DEBOUTLN (cerr, "lifted factors= " << uniFactors);
8788 }
8789 else
8790 {
8791 bool earlySuccess= false;
8798 "time for bivar hensel lifting over Fq: ");
8799 DEBOUTLN (cerr, "lifted factors= " << uniFactors);
8800
8802 if (!extension)
8803 {
8807 "time for small subset naive recombi over Fq: ");
8808
8810 if (degree (A) > 0)
8811 {
8812 CFList tmp;
8814 if (alpha.level() == 1)
8817 );
8818 else
8819 {
8820 if (degree (A) > getCharacteristic())
8823 );
8824 else
8827 );
8828 }
8830 "time to increase precision: ");
8832 if (tmp.length() == 0 || (tmp.length() > 0 && uniFactors.length() != 0
8834 )
8835 {
8837 degs.intersect (bufDegs);
8838 degs.refine ();
8840 degs, evaluation, 4,
8841 uniFactors.length()/2
8842 )
8843 );
8844 }
8845 }
8846 }
8847 else
8848 {
8849 if (beta.level() != 1 || k > 1)
8850 {
8851 if (k > 1)
8852 {
8855 );
8856 }
8857 else
8858 {
8860 evaluation, 1, 3
8861 );
8862 if (degree (A) > 0)
8863 {
8866 degs.intersect (bufDegs);
8867 degs.refine ();
8870 1, tmp.length()/2
8871 )
8872 );
8873 }
8874 }
8875 }
8876 else
8877 {
8879 evaluation, 1, 3
8880 );
8882 if (degree (A) > 0)
8883 {
8884 int degMipo;
8886
8887 CFList source, dest;
8890 info2, source, dest, liftBound
8891 );
8893 if (tmp.length() == 0 || (tmp.length() > 0 && uniFactors.length() != 0
8895 )
8896 {
8898 degs.intersect (bufDegs);
8899 degs.refine ();
8902 4, uniFactors.length()/2
8903 )
8904 );
8905 }
8906 }
8907 }
8908 }
8909
8910 if (earlySuccess)
8912 else if (!earlySuccess && degs.getLength() == 1)
8914 }
8915
8916 if (!swap2)
8917 delete [] bounds2;
8918 delete [] bounds;
8919
8921 swap, swap2, N);
8922 if (!extension)
8924
8925 return factors;
8926}
#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:4090
g
Definition cfModGcd.cc:4098
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:74
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:87
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:69
#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)

◆ biSqrfFactorizeHelper()

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

Definition at line 55 of file facFqBivar.h.

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

◆ chooseExtension()

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

chooses a field extension.

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

Definition at line 809 of file facFqBivar.cc.

810{
811 int i=1, m= 2;
812 // extension of F_p needed
813 if (alpha.level() == 1 && beta.level() == 1 && k == 1)
814 {
815 i= 1;
816 m= 2;
817 } //extension of F_p(alpha) needed but want to factorize over F_p
818 else if (alpha.level() != 1 && beta.level() == 1 && k == 1)
819 {
820 i= 1;
821 m= degree (getMipo (alpha)) + 1;
822 } //extension of F_p(alpha) needed for first time
823 else if (alpha.level() != 1 && beta.level() == 1 && k != 1)
824 {
825 i= 2;
826 m= degree (getMipo (alpha));
827 }
828 else if (alpha.level() != 1 && beta.level() != 1 && k != 1)
829 {
830 m= degree (getMipo (beta));
831 i= degree (getMipo (alpha))/m + 1;
832 }
833 #if defined(HAVE_FLINT)
838 #elif defined(HAVE_NTL)
840 {
842 zz_p::init (getCharacteristic());
843 }
847 #else
848 factoryError("NTL/FLINT missing: chooseExtension");
849 #endif
850 return rootOf (newMipo);
851}
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

◆ earlyFactorDetection()

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

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

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

Definition at line 974 of file facFqBivar.cc.

978{
981 factorsFoundIndex, degs, success, deg, eval, b, den);
982}
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:64

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

90{
91 fail= false;
97 double bound;
98 int p= getCharacteristic ();
99 if (alpha.level() != 1)
100 {
101 mipo= getMipo (alpha);
102 int d= degree (mipo);
103 bound= pow ((double) p, (double) d);
104 }
105 else if (GF)
106 {
107 int d= getGFDegree();
108 bound= ipower (p, d);
109 }
110 else
111 bound= p;
112
113 random= 0;
114 do
115 {
116 if (list.length() >= bound)
117 {
118 fail= true;
119 break;
120 }
121 if (list.isEmpty())
122 random= 0;
123 else if (GF)
124 {
125 if (list.length() == 1)
127 else
128 random= genGF.generate();
129 }
130 else if (list.length() < p || alpha.level() == 1)
131 random= genFF.generate();
132 else if (alpha != x && list.length() >= p)
133 {
134 if (list.length() == p)
135 random= alpha;
136 else
137 {
139 random= genAlgExt.generate();
140 }
141 }
142 if (find (list, random)) continue;
143 eval= F (random, x);
144 if (degree (eval) != degree (F, y))
145 { //leading coeff vanishes
146 if (!find (list, random))
147 list.append (random);
148 continue;
149 }
150 if (degree (gcd (deriv (eval, eval.mvar()), eval), eval.mvar()) > 0)
151 { //evaluated polynomial is not squarefree
152 if (!find (list, random))
153 list.append (random);
154 continue;
155 }
156 } while (find (list, random));
157
158 return random;
159}
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:4086
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
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 8931 of file facFqBivar.cc.

8932{
8933
8934 CanonicalForm A= F;
8935 Variable alpha= info.getAlpha();
8936 Variable beta= info.getBeta();
8937 int k= info.getGFDegree();
8938 char cGFName= info.getGFName();
8939 CanonicalForm delta= info.getDelta();
8940
8942 Variable x= Variable (1);
8944 if (!GF && alpha == x) // we are in F_p
8945 {
8946 bool extension= true;
8947 int p= getCharacteristic();
8948 if (p*p < (1<<16)) // pass to GF if possible
8949 {
8951 A= A.mapinto();
8954
8958 for (CFListIterator j= factors; j.hasItem(); j++)
8959 j.getItem()= GF2FalphaRep (j.getItem(), vBuf);
8960 prune (vBuf);
8961 }
8962 else // not able to pass to GF, pass to F_p(\alpha)
8963 {
8965 Variable v= rootOf (mipo);
8968 prune (v);
8969 }
8970 return factors;
8971 }
8972 else if (!GF && (alpha != x)) // we are in F_p(\alpha)
8973 {
8974 if (k == 1) // need factorization over F_p
8975 {
8976 int extDeg= degree (getMipo (alpha));
8977 extDeg++;
8979 Variable v= rootOf (mipo);
8982 prune (v);
8983 }
8984 else
8985 {
8986 if (beta == x)
8987 {
8990 bool primFail= false;
8991 Variable vBuf;
8993 ASSERT (!primFail, "failure in integer factorizer");
8994 if (primFail)
8995 ; //ERROR
8996 else
8998
8999 CFList source, dest;
9001 source, dest);
9004 prune (v);
9005 }
9006 else
9007 {
9010 bool primFail= false;
9011 Variable vBuf;
9012 ASSERT (!primFail, "failure in integer factorizer");
9013 if (primFail)
9014 ; //ERROR
9015 else
9016 imPrimElem= mapPrimElem (delta, beta, v);
9017
9018 CFList source, dest;
9020 source= CFList();
9021 dest= CFList();
9022 bufA= mapUp (bufA, beta, v, delta, imPrimElem, source, dest);
9025 prune (v);
9026 }
9027 }
9028 return factors;
9029 }
9030 else // we are in GF (p^k)
9031 {
9032 int p= getCharacteristic();
9034 bool extension= true;
9035 if (k == 1) // need factorization over F_p
9036 {
9037 extensionDeg++;
9038 if (ipower (p, extensionDeg) < (1<<16))
9039 // pass to GF(p^k+1)
9040 {
9044 A= GF2FalphaRep (A, vBuf);
9047 factors= biFactorize (A.mapinto(), info2);
9048 prune (vBuf);
9049 }
9050 else // not able to pass to another GF, pass to F_p(\alpha)
9051 {
9055 A= GF2FalphaRep (A, vBuf);
9059 prune (vBuf);
9060 }
9061 }
9062 else // need factorization over GF (p^k)
9063 {
9064 if (ipower (p, 2*extensionDeg) < (1<<16))
9065 // pass to GF (p^2k)
9066 {
9071 }
9072 else // not able to pass to GF (p^2k), pass to F_p (\alpha)
9073 {
9077 A= GF2FalphaRep (A, v1);
9080 bool primFail= false;
9081 Variable vBuf;
9083 ASSERT (!primFail, "failure in integer factorizer");
9084 if (primFail)
9085 ; //ERROR
9086 else
9088
9089 CFList source, dest;
9091 source, dest);
9095 for (CFListIterator i= factors; i.hasItem(); i++)
9097 prune (v1);
9098 }
9099 }
9100 return factors;
9101 }
9102}
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
T & getItem() 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 985 of file facFqBivar.cc.

990{
991 Variable alpha= info.getAlpha();
992 Variable beta= info.getBeta();
993 CanonicalForm gamma= info.getGamma();
994 CanonicalForm delta= info.getDelta();
995 int k= info.getGFDegree();
999 Variable y= F.mvar();
1000 Variable x= Variable (1);
1001 CanonicalForm buf= F, LCBuf= LC (buf, x), g, buf2;
1002 CanonicalForm M= power (y, deg);
1004 bool trueFactor= false;
1005 int d= degree (F), l= 0;
1006 CFList source, dest;
1007 int degMipoBeta= 1;
1008 if (!k && beta.level() != 1)
1011 for (CFListIterator i= factors; i.hasItem(); i++, l++)
1012 {
1013 if (!bufDegs1.find (degree (i.getItem(), 1)) || factorsFoundIndex[l] == 1)
1014 continue;
1015 else
1016 {
1017 g= mulMod2 (i.getItem(), LCBuf, M);
1018 g /= content (g, x);
1019 if (fdivides (g, buf, quot))
1020 {
1021 buf2= g (y - eval, y);
1022 buf2 /= Lc (buf2);
1023
1024 if (!k && beta == x)
1025 {
1026 if (degree (buf2, alpha) < degMipoBeta)
1027 {
1029 factorsFoundIndex[l]= 1;
1030 buf= quot;
1031 d -= degree (g);
1032 LCBuf= LC (buf, x);
1033 trueFactor= true;
1034 }
1035 }
1036 else
1037 {
1038 if (!isInExtension (buf2, gamma, k, delta, source, dest))
1039 {
1041 factorsFoundIndex[l]= 1;
1042 buf= quot;
1043 d -= degree (g);
1044 LCBuf= LC (buf, x);
1045 trueFactor= true;
1046 }
1047 }
1048 if (trueFactor)
1049 {
1050 T= Difference (T, CFList (i.getItem()));
1051 F= buf;
1052
1053 // compute new possible degree pattern
1055 bufDegs1.intersect (bufDegs2);
1056 bufDegs1.refine ();
1057 trueFactor= false;
1058 if (bufDegs1.getLength() <= 1)
1059 {
1060 if (!buf.inCoeffDomain())
1061 {
1062 buf= buf (y - eval, y);
1063 buf /= Lc (buf);
1065 F= 1;
1066 }
1067 break;
1068 }
1069 }
1070 }
1071 }
1072 }
1073 adaptedLiftBound= d + 1;
1074 if (adaptedLiftBound < deg)
1075 {
1076 degs= bufDegs1;
1077 success= true;
1078 }
1079 if (bufDegs1.getLength() <= 1)
1080 degs= bufDegs1;
1081}
CanonicalForm LC(const CanonicalForm &f)
int l
Definition cfEzgcd.cc:100
bool fdivides(const CanonicalForm &f, const CanonicalForm &g)
bool fdivides ( const CanonicalForm & f, const CanonicalForm & g )
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
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:76
const CanonicalForm & M
Definition facFqBivar.cc:63
CanonicalForm mulMod2(const CanonicalForm &A, const CanonicalForm &B, const CanonicalForm &M)
Karatsuba style modular multiplication for bivariate polynomials.
Definition facMul.cc:2991
template List< Variable > Difference(const List< Variable > &, const List< Variable > &)
STATIC_VAR jList * T
Definition janet.cc:30

◆ extFactorRecombination()

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

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

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

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

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

Definition at line 373 of file facFqBivar.cc.

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

◆ factorRecombination()

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

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

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

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

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

Definition at line 589 of file facFqBivar.cc.

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

◆ FpBiFactorize()

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

factorize a bivariate polynomial over $ F_{p} $

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

Definition at line 190 of file facFqBivar.h.

193{
195 CFMap N;
197
198 if (substCheck)
199 {
200 bool foundOne= false;
201 int * substDegree= NEW_ARRAY(int,F.level());
202 for (int i= 1; i <= F.level(); i++)
203 {
205 if (substDegree [i-1] > 1)
206 {
207 foundOne= true;
208 subst (F, F, substDegree[i-1], Variable (i));
209 }
210 }
211 if (foundOne)
212 {
213 CFFList result= FpBiFactorize (F, false);
216 newResult.insert (result.getFirst());
218 for (CFFListIterator i= result; i.hasItem(); i++)
219 {
220 tmp2= i.getItem().factor();
221 for (int j= 1; j <= F.level(); j++)
222 {
223 if (substDegree[j-1] > 1)
225 }
226 tmp= FpBiFactorize (tmp2, false);
228 for (CFFListIterator j= tmp; j.hasItem(); j++)
229 newResult.append (CFFactor (j.getItem().factor(),
230 j.getItem().exp()*i.getItem().exp()));
231 }
234 return newResult;
235 }
237 }
238
239 CanonicalForm LcF= Lc (F);
242 F /= (contentX*contentY);
246 if (contentXFactors.getFirst().factor().inCoeffDomain())
248 if (contentYFactors.getFirst().factor().inCoeffDomain())
253 if (F.inCoeffDomain())
254 {
257 result.insert (CFFactor (LcF, 1));
258 return result;
259 }
260 mpz_t * M=new mpz_t [4];
261 mpz_init (M[0]);
262 mpz_init (M[1]);
263 mpz_init (M[2]);
264 mpz_init (M[3]);
265
266 mpz_t * S=new mpz_t [2];
267 mpz_init (S[0]);
268 mpz_init (S[1]);
269
270 F= compress (F, M, S);
271
273 CFFList sqrf= FpSqrf (F, false);
275 "time for bivariate sqrf factors over Fp: ");
279 for (CFFListIterator iter= sqrf; iter.hasItem(); iter++)
280 {
282 bufResult= biFactorize (iter.getItem().factor(), info);
284 "time to factor bivariate sqrf factors over Fp: ");
285 for (i= bufResult; i.hasItem(); i++)
286 result.append (CFFactor (N (decompress (i.getItem(), M, S)),
287 iter.getItem().exp()));
288 }
289
293 result.insert (CFFactor (LcF, 1));
294
295 mpz_clear (M[0]);
296 mpz_clear (M[1]);
297 mpz_clear (M[2]);
298 mpz_clear (M[3]);
299 delete [] M;
300
301 mpz_clear (S[0]);
302 mpz_clear (S[1]);
303 delete [] S;
304
305 return result;
306}
#define DELETE_ARRAY(P)
Definition cf_defs.h:65
#define NEW_ARRAY(T, N)
Definition cf_defs.h:64
CanonicalForm LcF
CFList tmp2
Definition facFqBivar.cc:75
CFFList FpBiFactorize(const CanonicalForm &G, bool substCheck=true)
factorize a bivariate polynomial over
Definition facFqBivar.h:190
CFFList FpSqrf(const CanonicalForm &F, bool sort=true)
squarefree factorization over . If input is not monic, the leading coefficient is dropped

◆ FpBiSqrfFactorize()

CFList FpBiSqrfFactorize ( const CanonicalForm & G)
inline

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

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

Definition at line 141 of file facFqBivar.h.

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

◆ FqBiFactorize()

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

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

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

Definition at line 317 of file facFqBivar.h.

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

◆ FqBiSqrfFactorize()

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

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

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

Definition at line 156 of file facFqBivar.h.

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

◆ getLiftPrecisions()

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

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

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

Definition at line 1123 of file facFqBivar.cc.

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

◆ GFBiFactorize()

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

factorize a bivariate polynomial over GF

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

Definition at line 446 of file facFqBivar.h.

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

◆ GFBiSqrfFactorize()

CFList GFBiSqrfFactorize ( const CanonicalForm & G)
inline

factorize a squarefree bivariate polynomial over GF

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

Definition at line 172 of file facFqBivar.h.

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

◆ henselLiftAndEarly() [1/2]

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

hensel Lifting and early factor detection

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

Definition at line 1458 of file facFqBivar.cc.

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

◆ henselLiftAndEarly() [2/2]

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

hensel Lifting and early factor detection

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

Definition at line 1155 of file facFqBivar.cc.

1159{
1160 Variable alpha= info.getAlpha();
1161 Variable beta= info.getBeta();
1162 CanonicalForm gamma= info.getGamma();
1163 CanonicalForm delta= info.getDelta();
1164 bool extension= info.isInExtension();
1165
1166 int sizeOfLiftPre;
1167 int * liftPre= getLiftPrecisions (A, sizeOfLiftPre, degree (LC (A, 1), 2));
1168
1169 Variable x= Variable (1);
1170 Variable y= Variable (2);
1171 CFArray Pi;
1174 On (SW_RATIONAL);
1176 if (!Lc (A).inBaseDomain())
1177 {
1178 bufA /= Lc (A);
1180 bufA *= denBufA;
1181 Off (SW_RATIONAL);
1182 den /= gcd (den, denBufA);
1183 }
1184 else
1185 {
1186 bufA= A;
1187 Off (SW_RATIONAL);
1188 den /= gcd (den, Lc (A));
1189 }
1191 bool mipoHasDen= false;
1192 if (getCharacteristic() == 0 && b.getp() != 0)
1193 {
1194 if (alpha.level() == 1)
1195 {
1196 lcA0= lc (A (0, 2));
1197 A *= b.inverse (lcA0);
1198 A= b (A);
1200 i.getItem()= b (i.getItem()*b.inverse (lc (i.getItem())));
1201 }
1202 else
1203 {
1204 lcA0= Lc (A (0,2));
1205 On (SW_RATIONAL);
1207 Off (SW_RATIONAL);
1208 CanonicalForm lcA0inverse= b.inverse (lcA0);
1209 A *= lcA0inverse;
1210 A= b (A);
1211 // Lc of bufUniFactors is in Z
1213 i.getItem()= b (i.getItem()*b.inverse (lc (i.getItem())));
1214 }
1215 }
1216 bufUniFactors.insert (LC (A, x));
1218 earlySuccess= false;
1219 int newLiftBound= 0;
1220
1221 int smallFactorDeg= tmin (11, liftPre [sizeOfLiftPre- 1] + 1);//this is a tunable parameter
1222 int dummy;
1223 int * factorsFoundIndex= new int [uniFactors.length()];
1224 for (int i= 0; i < uniFactors.length(); i++)
1225 factorsFoundIndex [i]= 0;
1226
1228 Variable v= alpha;
1229 if (smallFactorDeg >= liftBound || degree (A,y) <= 4)
1231 else if (sizeOfLiftPre > 1 && sizeOfLiftPre < 30)
1232 {
1234 if (mipoHasDen)
1235 {
1236 for (CFListIterator iter= bufUniFactors; iter.hasItem(); iter++)
1237 if (hasFirstAlgVar (iter.getItem(), v))
1238 break;
1239 if (v != alpha)
1240 {
1242 for (CFListIterator iter= bufBufUniFactors; iter.hasItem(); iter++)
1243 iter.getItem()= replacevar (iter.getItem(), v, alpha);
1244 A= replacevar (A, alpha, v);
1245 }
1246 }
1247
1248 if (!extension)
1249 {
1250 if (v==alpha)
1254 else
1258 }
1259 else
1263 if (degs.getLength() > 1 && !earlySuccess &&
1265 {
1267 {
1268 bufUniFactors.insert (LC (A, x));
1270 liftPre[sizeOfLiftPre-1] + 1, Pi, diophant, M, b);
1271 if (v!=alpha)
1272 {
1274 for (CFListIterator iter= bufBufUniFactors; iter.hasItem(); iter++)
1275 iter.getItem()= replacevar (iter.getItem(), v, alpha);
1276 }
1277 if (!extension)
1278 {
1279 if (v==alpha)
1282 liftPre[sizeOfLiftPre-1] + 1, eval, b, den);
1283 else
1286 liftPre[sizeOfLiftPre-1] + 1, eval, b, den);
1287 }
1288 else
1291 eval, liftPre[sizeOfLiftPre-1] + 1);
1292 }
1293 }
1294 else if (earlySuccess)
1296
1297 int i= sizeOfLiftPre - 1;
1298 while (degs.getLength() > 1 && !earlySuccess && i - 1 >= 0)
1299 {
1300 if (newLiftBound >= liftPre[i] + 1)
1301 {
1302 bufUniFactors.insert (LC (A, x));
1304 liftPre[i-1] + 1, Pi, diophant, M, b);
1305 if (v!=alpha)
1306 {
1308 for (CFListIterator iter= bufBufUniFactors; iter.hasItem(); iter++)
1309 iter.getItem()= replacevar (iter.getItem(), v, alpha);
1310 }
1311 if (!extension)
1312 {
1313 if (v==alpha)
1316 liftPre[i-1] + 1, eval, b, den);
1317 else
1320 liftPre[i-1] + 1, eval, b, den);
1321 }
1322 else
1325 eval, liftPre[i-1] + 1);
1326 }
1327 else
1328 {
1330 break;
1331 }
1332 i--;
1333 }
1334 if (earlySuccess)
1336 //after here all factors are lifted to liftPre[sizeOfLiftPre-1]
1337 }
1338 else
1339 {
1341 if (mipoHasDen)
1342 {
1343 for (CFListIterator iter= bufUniFactors; iter.hasItem(); iter++)
1344 if (hasFirstAlgVar (iter.getItem(), v))
1345 break;
1346 if (v != alpha)
1347 {
1349 for (CFListIterator iter= bufBufUniFactors; iter.hasItem(); iter++)
1350 iter.getItem()= replacevar (iter.getItem(), v, alpha);
1351 A= replacevar (A, alpha, v);
1352 }
1353 }
1354 if (!extension)
1355 {
1356 if (v==alpha)
1360 else
1364 }
1365 else
1369 int i= 1;
1370 while ((degree (A,y)/4)*i + 4 <= smallFactorDeg)
1371 i++;
1372 dummy= tmin (degree (A,y)+1, (degree (A,y)/4)*i+4);
1373 if (degs.getLength() > 1 && !earlySuccess && dummy > smallFactorDeg)
1374 {
1375 bufUniFactors.insert (LC (A, x));
1377 dummy, Pi, diophant, M, b);
1378 if (v!=alpha)
1379 {
1381 for (CFListIterator iter= bufBufUniFactors; iter.hasItem(); iter++)
1382 iter.getItem()= replacevar (iter.getItem(), v, alpha);
1383 }
1384 if (!extension)
1385 {
1386 if (v==alpha)
1389 b, den);
1390 else
1393 b, den);
1394 }
1395 else
1398 eval, dummy);
1399 }
1400 while (degs.getLength() > 1 && !earlySuccess && i < 4)
1401 {
1402 if (newLiftBound >= dummy)
1403 {
1404 bufUniFactors.insert (LC (A, x));
1405 dummy= tmin (degree (A,y)+1, (degree (A,y)/4)*(i+1)+4);
1407 dummy, Pi, diophant, M, b);
1408 if (v!=alpha)
1409 {
1411 for (CFListIterator iter= bufBufUniFactors; iter.hasItem(); iter++)
1412 iter.getItem()= replacevar (iter.getItem(), v, alpha);
1413 }
1414 if (!extension)
1415 {
1416 if (v==alpha)
1419 eval, b, den);
1420 else
1423 eval, b, den);
1424 }
1425 else
1428 eval, dummy);
1429 }
1430 else
1431 {
1433 break;
1434 }
1435 i++;
1436 }
1437 if (earlySuccess)
1439 }
1440
1441 A= bufA;
1442 if (earlyFactors.length() > 0 && degs.getLength() > 1)
1443 {
1444 liftBound= degree (A,y) + 1;
1445 earlySuccess= true;
1447 }
1448
1449 delete [] factorsFoundIndex;
1450 delete [] liftPre;
1451
1452 return bufUniFactors;
1453}
CanonicalForm FACTORY_PUBLIC replacevar(const CanonicalForm &, const Variable &, const Variable &)
CanonicalForm replacevar ( const CanonicalForm & f, const Variable & x1, const Variable & x2 )
Definition cf_ops.cc:271
bool hasFirstAlgVar(const CanonicalForm &f, Variable &a)
check if poly f contains an algebraic variable a
Definition cf_ops.cc:679
Matrix< CanonicalForm > CFMatrix
CF_NO_INLINE bool isOne() const
void extEarlyFactorDetection(CFList &reconstructedFactors, CanonicalForm &F, CFList &factors, int &adaptedLiftBound, int *&factorsFoundIndex, DegreePattern &degs, bool &success, const ExtensionInfo &info, const CanonicalForm &eval, int deg)
detects factors of F at stage deg of Hensel lifting. No combinations of more than one factor are test...
void deleteFactors(CFList &factors, int *factorsFoundIndex)
int * getLiftPrecisions(const CanonicalForm &F, int &sizeOfOutput, int degreeLC)
compute lifting precisions from the shape of the Newton polygon of F
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.
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)...

◆ prodMod0()

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

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

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

◆ TIMING_DEFINE_PRINT()

TIMING_DEFINE_PRINT ( fac_fq_bi_sqrf ) const

◆ uniFactorizer()

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

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

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

Definition at line 163 of file facFqBivar.cc.

164{
165 Variable x= A.mvar();
166 if (A.inCoeffDomain())
167 return CFList();
168 ASSERT (A.isUnivariate(),
169 "univariate polynomial expected or constant expected");
171 if (GF)
172 {
173 int k= getGFDegree();
174 char cGFName= gf_name;
179#ifdef HAVE_NTL
180 if (getCharacteristic() > 2)
181#else
182 if (getCharacteristic() > 0)
183#endif
184 {
185#if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
190
193
195
198
201
203
205 beta, fq_con);
206
212#else
214 {
216 zz_p::init (getCharacteristic());
217 }
219 zz_pE::init (NTLMipo);
221 MakeMonic (NTLA);
223 zz_pE multi= to_zz_pE (1);
225 x, beta);
226#endif
227 }
228#ifdef HAVE_NTL
229 else
230 {
232 GF2E::init (NTLMipo);
234 MakeMonic (NTLA);
236 GF2E multi= to_GF2E (1);
238 x, beta);
239 }
240#endif
242 for (CFFListIterator i= factorsA; i.hasItem(); i++)
243 {
244 buf= i.getItem().factor();
246 i.getItem()= CFFactor (buf, i.getItem().exp());
247 }
248 prune (beta);
249 }
250 else if (alpha.level() != 1)
251 {
252#ifdef HAVE_NTL
253 if (getCharacteristic() > 2)
254#else
255 if (getCharacteristic() > 0)
256#endif
257 {
258#if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
263
266
268
271
274
276
278 alpha, fq_con);
279
285#else
287 {
289 zz_p::init (getCharacteristic());
290 }
292 zz_pE::init (NTLMipo);
294 MakeMonic (NTLA);
296 zz_pE multi= to_zz_pE (1);
298 x, alpha);
299#endif
300 }
301#ifdef HAVE_NTL
302 else
303 {
305 GF2E::init (NTLMipo);
307 MakeMonic (NTLA);
309 GF2E multi= to_GF2E (1);
311 x, alpha);
312 }
313#endif
314 }
315 else
316 {
317#ifdef HAVE_FLINT
318#ifdef HAVE_NTL
319 if (degree (A) < 300)
320#endif
321 {
328 if (factorsA.getFirst().factor().inCoeffDomain())
332 }
333#ifdef HAVE_NTL
334 else
335#endif
336#endif /* HAVE_FLINT */
337#ifdef HAVE_NTL
338 if (getCharacteristic() > 2)
339 {
341 {
343 zz_p::init (getCharacteristic());
344 }
346 MakeMonic (NTLA);
348 zz_p multi= to_zz_p (1);
350 x);
351 }
352 else
353 {
356 GF2 multi= to_GF2 (1);
358 x);
359 }
360#endif
361 }
363 for (CFFListIterator i= factorsA; i.hasItem(); i++)
364 uniFactors.append (i.getItem().factor());
365 return uniFactors;
366}
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.
zz_pX convertFacCF2NTLzzpX(const CanonicalForm &f)
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)