My Project
Loading...
Searching...
No Matches
Functions | Variables
facFqFactorize.h File Reference

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

#include "timing.h"
#include "facFqBivar.h"
#include "DegreePattern.h"
#include "ExtensionInfo.h"
#include "cf_util.h"
#include "facFqSquarefree.h"
#include "facFqBivarUtil.h"

Go to the source code of this file.

Functions

 TIMING_DEFINE_PRINT (fac_fq_squarefree) TIMING_DEFINE_PRINT(fac_fq_factor_squarefree) CFList multiFactorize(const CanonicalForm &F
 Factorization over a finite field. More...
 
CFList FpSqrfFactorize (const CanonicalForm &F)
 factorize a squarefree multivariate polynomial over $ F_{p} $ More...
 
CFList FqSqrfFactorize (const CanonicalForm &F, const Variable &alpha)
 factorize a squarefree multivariate polynomial over $ F_{p} (\alpha ) $ More...
 
CFList GFSqrfFactorize (const CanonicalForm &F)
 factorize a squarefree multivariate polynomial over GF More...
 
CFFList FpFactorize (const CanonicalForm &G, bool substCheck=true)
 factorize a multivariate polynomial over $ F_{p} $ More...
 
CFFList FqFactorize (const CanonicalForm &G, const Variable &alpha, bool substCheck=true)
 factorize a multivariate polynomial over $ F_{p} (\alpha ) $ More...
 
CFFList GFFactorize (const CanonicalForm &G, bool substCheck=true)
 factorize a multivariate polynomial over GF More...
 
CFList extFactorRecombination (const CFList &factors, const CanonicalForm &F, const CFList &M, const ExtensionInfo &info, const CFList &evaluation)
 Naive factor recombination for multivariate factorization over an extension of the initial field. No precomputed is used to exclude combinations. More...
 
CFList factorRecombination (const CanonicalForm &F, const CFList &factors, const CFList &M)
 Naive factor recombination for multivariate factorization. No precomputed is used to exclude combinations. More...
 
CFList recombination (const CFList &factors1, const CFList &factors2, int s, int thres, const CanonicalForm &evalPoint, const Variable &x)
 recombination of bivariate factors factors1 s. t. the result evaluated at evalPoint coincides with factors2 More...
 
int liftBoundAdaption (const CanonicalForm &F, const CFList &factors, bool &success, const int deg, const CFList &MOD, const int bound)
 Lift bound adaption. Essentially an early factor detection but only the lift bound is adapted. More...
 
int extLiftBoundAdaption (const CanonicalForm &F, const CFList &factors, bool &success, const ExtensionInfo &info, const CFList &eval, const int deg, const CFList &MOD, const int bound)
 Lift bound adaption over an extension of the initial field. Essentially an early factor detection but only the lift bound is adapted. More...
 
CFList earlyFactorDetect (CanonicalForm &F, CFList &factors, int &adaptedLiftBound, bool &success, const int deg, const CFList &MOD, const int bound)
 detects factors of F at stage deg of Hensel lifting. No combinations of more than one factor are tested. Lift bound is adapted. More...
 
CFList extEarlyFactorDetect (CanonicalForm &F, CFList &factors, int &adaptedLiftBound, bool &success, const ExtensionInfo &info, const CFList &eval, const int deg, const CFList &MOD, const int bound)
 detects factors of F at stage deg of Hensel lifting. No combinations of more than one factor are tested. Lift bound is adapted. More...
 
CFList evalPoints (const CanonicalForm &F, CFList &eval, const Variable &alpha, CFList &list, const bool &GF, bool &fail)
 evaluation point search for multivariate factorization, looks for a (F.level() - 1)-tuple such that the resulting univariate polynomial has main variable Variable (1), is squarefree and its degree coincides with degree(F) and the bivariate one is primitive wrt. Variable(1), and successively evaluated polynomials have the same degree in their main variable as F has, fails if there are no valid evaluation points, eval contains the intermediate evaluated polynomials. More...
 
CFList henselLiftAndEarly (CanonicalForm &A, CFList &MOD, int *&liftBounds, bool &earlySuccess, CFList &earlyFactors, const CFList &Aeval, const CFList &biFactors, const CFList &evaluation, const ExtensionInfo &info)
 hensel Lifting and early factor detection More...
 
CFList extFactorize (const CanonicalForm &F, const ExtensionInfo &info)
 Factorization over an extension of initial field. More...
 
CanonicalForm lcmContent (const CanonicalForm &A, CFList &contentAi)
 compute the LCM of the contents of A wrt to each variable occuring in A. More...
 
CanonicalForm myCompress (const CanonicalForm &F, CFMap &N)
 compress a polynomial s.t. $ deg_{x_{i}} (F) >= deg_{x_{i+1}} (F) $ and no gaps between the variables occur More...
 
void evaluationWRTDifferentSecondVars (CFList *&Aeval, const CFList &evaluation, const CanonicalForm &A)
 evaluate a poly A with main variable at level 1 at an evaluation point in K^(n-1) wrt different second variables. If this evaluation is valid (see evalPoints) then Aeval contains A successively evaluated at this point, otherwise this entry is empty More...
 
void refineBiFactors (const CanonicalForm &A, CFList &biFactors, CFList *const &factors, const CFList &evaluation, int minFactorsLength)
 refine a bivariate factorization of A with l factors to one with minFactorsLength if possible More...
 
CFList buildUniFactors (const CFList &biFactors, const CanonicalForm &evalPoint, const Variable &y)
 plug in evalPoint for y in a list of polys More...
 
void sortByUniFactors (CFList *&Aeval, int AevalLength, CFList &uniFactors, CFList &biFactors, const CFList &evaluation)
 sort bivariate factors in Aeval such that their corresponding univariate factors coincide with uniFactors, uniFactors and biFactors may get recombined if necessary More...
 
void getLeadingCoeffs (const CanonicalForm &A, CFList *&Aeval)
 extract leading coefficients wrt Variable(1) from bivariate factors obtained from factorizations of A wrt different second variables More...
 
void prepareLeadingCoeffs (CFList *&LCs, CanonicalForm &A, CFList &Aeval, int n, const CFList &leadingCoeffs, const CFList &biFactors, const CFList &evaluation)
 normalize precomputed leading coefficients such that leading coefficients evaluated at evaluation in K^(n-2) equal the leading coeffs wrt Variable(1) of bivariate factors and change A and Aeval accordingly More...
 
CFList leadingCoeffReconstruction (const CanonicalForm &F, const CFList &factors, const CFList &M)
 obtain factors of F by reconstructing their leading coeffs More...
 
CFList distributeContent (const CFList &L, const CFList *differentSecondVarFactors, int length)
 distribute content More...
 
void gcdFreeBasis (CFFList &factors1, CFFList &factors2)
 gcd free basis of two lists of factors More...
 
CFList precomputeLeadingCoeff (const CanonicalForm &LCF, const CFList &LCFFactors, const Variable &alpha, const CFList &evaluation, CFList *&differentSecondVarLCs, int lSecondVarLCs, Variable &y)
 computes a list l of length length(LCFFactors)+1 of polynomials such that prod (l)=LCF, note that the first entry of l may be non constant. Intended to be used to precompute coefficients of a polynomial f from its bivariate factorizations. More...
 
void changeSecondVariable (CanonicalForm &A, CFList &biFactors, CFList &evaluation, CFList *&oldAeval, int lengthAeval2, const CFList &uniFactors, const Variable &w)
 changes the second variable to be w and updates all relevant data More...
 
void distributeLCmultiplier (CanonicalForm &A, CFList &leadingCoeffs, CFList &biFactors, const CFList &evaluation, const CanonicalForm &LCmultipler)
 distributes a divisor LCmultiplier of LC(A,1) on the bivariate factors and the precomputed leading coefficients More...
 
void LCHeuristic (CanonicalForm &A, const CanonicalForm &LCmultiplier, CFList &biFactors, CFList *&leadingCoeffs, const CFList *oldAeval, int lengthAeval, const CFList &evaluation, const CFList &oldBiFactors)
 heuristic to distribute LCmultiplier onto factors based on the variables that occur in LCmultiplier and in the leading coeffs of bivariate factors More...
 
void LCHeuristicCheck (const CFList &LCs, const CFList &contents, CanonicalForm &A, const CanonicalForm &oldA, CFList &leadingCoeffs, bool &foundTrueMultiplier)
 checks if prod(LCs)==LC (oldA,1) and if so divides elements of leadingCoeffs by elements in contents, sets A to oldA and sets foundTrueMultiplier to true More...
 
void LCHeuristic2 (const CanonicalForm &LCmultiplier, const CFList &factors, CFList &leadingCoeffs, CFList &contents, CFList &LCs, bool &foundTrueMultiplier)
 heuristic to distribute LCmultiplier onto factors based on the contents of factors. factors are assumed to come from LucksWangSparseHeuristic. If not successful contents will contain the content of each element of factors and LCs will contain the LC of each element of factors divided by its content More...
 
void LCHeuristic3 (const CanonicalForm &LCmultiplier, const CFList &factors, const CFList &oldBiFactors, const CFList &contents, const CFList *oldAeval, CanonicalForm &A, CFList *&leadingCoeffs, int lengthAeval, bool &foundMultiplier)
 heuristic to remove LCmultiplier from a factor based on the contents of factors. factors are assumed to come from LucksWangSparseHeuristic. More...
 
void LCHeuristic4 (const CFList &oldBiFactors, const CFList *oldAeval, const CFList &contents, const CFList &factors, const CanonicalForm &testVars, int lengthAeval, CFList *&leadingCoeffs, CanonicalForm &A, CanonicalForm &LCmultiplier, bool &foundMultiplier)
 heuristic to remove factors of LCmultiplier from factors. More precisely checks if elements of contents divide LCmultiplier. Assumes LCHeuristic3 is run before it and was successful. More...
 

Variables

const ExtensionInfoinfo
 < [in] sqrfree poly More...
 

Detailed Description

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

Author
Martin Lee

Definition in file facFqFactorize.h.

Function Documentation

◆ buildUniFactors()

CFList buildUniFactors ( const CFList biFactors,
const CanonicalForm evalPoint,
const Variable y 
)

plug in evalPoint for y in a list of polys

Returns
returns a list of the evaluated polys, these evaluated polys are made monic
Parameters
[in]biFactorsa list of polys
[in]evalPointsome evaluation point
[in]ysome variable

Definition at line 2320 of file facFqFactorize.cc.

2322{
2323 CFList result;
2324 CanonicalForm tmp;
2325 for (CFListIterator i= biFactors; i.hasItem(); i++)
2326 {
2327 tmp= mod (i.getItem(), y - evalPoint);
2328 tmp /= Lc (tmp);
2329 result.append (tmp);
2330 }
2331 return result;
2332}
CF_NO_INLINE FACTORY_PUBLIC CanonicalForm mod(const CanonicalForm &, const CanonicalForm &)
CanonicalForm Lc(const CanonicalForm &f)
int i
Definition: cfEzgcd.cc:132
static void evalPoint(const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &FEval, CanonicalForm &GEval, CFGenerator &evalPoint)
factory's main class
Definition: canonicalform.h:86
return result
Definition: facAbsBiFact.cc:75
const CanonicalForm int const CFList const Variable & y
Definition: facAbsFact.cc:53

◆ changeSecondVariable()

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

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

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

Definition at line 2543 of file facFqFactorize.cc.

2546{
2547 Variable y= Variable (2);
2548 A= swapvar (A, y, w);
2549 int i= A.level();
2552 {
2553 if (i == w.level())
2554 {
2556 iter.getItem()= evaluation.getLast();
2557 evaluation.removeLast();
2558 evaluation.append (evalPoint);
2559 break;
2560 }
2561 }
2562 for (i= 0; i < lengthAeval2; i++)
2563 {
2564 if (oldAeval[i].isEmpty())
2565 continue;
2566 if (oldAeval[i].getFirst().level() == w.level())
2567 {
2568 CFArray tmp= copy (oldAeval[i]);
2569 oldAeval[i]= biFactors;
2570 for (CFListIterator iter= oldAeval[i]; iter.hasItem(); iter++)
2571 iter.getItem()= swapvar (iter.getItem(), w, y);
2572 for (int ii= 0; ii < tmp.size(); ii++)
2573 tmp[ii]= swapvar (tmp[ii], w, y);
2574 CFArray tmp2= CFArray (tmp.size());
2576 for (int ii= 0; ii < tmp.size(); ii++)
2577 {
2578 buf= tmp[ii] (evaluation.getLast(),y);
2579 buf /= Lc (buf);
2580 tmp2[findItem (uniFactors, buf)-1]=tmp[ii];
2581 }
2582 biFactors= CFList();
2583 for (int j= 0; j < tmp2.size(); j++)
2584 biFactors.append (tmp2[j]);
2585 }
2586 }
2587}
Array< CanonicalForm > CFArray
CanonicalForm FACTORY_PUBLIC swapvar(const CanonicalForm &, const Variable &, const Variable &)
swapvar() - swap variables x1 and x2 in f.
Definition: cf_ops.cc:168
int level(const CanonicalForm &f)
List< CanonicalForm > CFList
int findItem(const CFList &list, const CanonicalForm &item)
helper function
Definition: cf_map_ext.cc:41
int size() const
Definition: ftmpl_array.cc:92
int level() const
level() returns the level of CO.
T & getItem() const
Definition: ftmpl_list.cc:431
void append(const T &)
Definition: ftmpl_list.cc:256
factory's class for variables
Definition: variable.h:33
CFFListIterator iter
Definition: facAbsBiFact.cc:53
const CanonicalForm int const CFList & evaluation
Definition: facAbsFact.cc:52
const CanonicalForm & w
Definition: facAbsFact.cc:51
CFArray copy(const CFList &list)
write elements of list into an array
CFList tmp2
Definition: facFqBivar.cc:72
int j
Definition: facHensel.cc:110
int status int void * buf
Definition: si_signals.h:59
#define A
Definition: sirandom.c:24

◆ distributeContent()

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

distribute content

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

Definition at line 1294 of file facFqFactorize.cc.

1297{
1298 CFList l= L;
1299 CanonicalForm content= l.getFirst();
1300
1301 if (content.inCoeffDomain())
1302 return l;
1303
1304 if (l.length() == 1)
1305 {
1306 CFList result;
1307 for (int i= 0; i < length; i++)
1308 {
1309 if (differentSecondVarFactors[i].isEmpty())
1310 continue;
1311 if (result.isEmpty())
1312 {
1313 result= differentSecondVarFactors[i];
1315 content /= iter.getItem();
1316 }
1317 else
1318 {
1319 CFListIterator iter1= result;
1320 for (CFListIterator iter2= differentSecondVarFactors[i];iter2.hasItem();
1321 iter2++, iter1++)
1322 {
1323 iter1.getItem() *= iter2.getItem();
1324 content /= iter2.getItem();
1325 }
1326 }
1327 }
1328 result.insert (content);
1329 return result;
1330 }
1331
1332 Variable v;
1333 CFListIterator iter1, iter2;
1334 CanonicalForm tmp, g;
1335 CFList multiplier;
1336 for (int i= 0; i < length; i++)
1337 {
1338 if (differentSecondVarFactors[i].isEmpty())
1339 continue;
1340 iter1= l;
1341 iter1++;
1342
1343 tmp= 1;
1344 for (iter2= differentSecondVarFactors[i]; iter2.hasItem();
1345 iter2++, iter1++)
1346 {
1347 if (iter2.getItem().inCoeffDomain())
1348 {
1349 multiplier.append (1);
1350 continue;
1351 }
1352 v= iter2.getItem().mvar();
1353 if (degree (iter2.getItem()) == degree (iter1.getItem(),v))
1354 {
1355 multiplier.append (1);
1356 continue;
1357 }
1358 g= gcd (iter2.getItem(), content);
1359 if (!g.inCoeffDomain())
1360 {
1361 tmp *= g;
1362 multiplier.append (g);
1363 }
1364 else
1365 multiplier.append (1);
1366 }
1367 if (!tmp.isOne() && fdivides (tmp, content))
1368 {
1369 iter1= l;
1370 iter1++;
1371 content /= tmp;
1372 for (iter2= multiplier; iter2.hasItem(); iter1++, iter2++)
1373 iter1.getItem() *= iter2.getItem();
1374 }
1375 multiplier= CFList();
1376 }
1377
1378 l.removeFirst();
1379 l.insert (content);
1380 return l;
1381}
CanonicalForm FACTORY_PUBLIC content(const CanonicalForm &)
CanonicalForm content ( const CanonicalForm & f )
Definition: cf_gcd.cc:603
int degree(const CanonicalForm &f)
int l
Definition: cfEzgcd.cc:100
g
Definition: cfModGcd.cc:4090
bool fdivides(const CanonicalForm &f, const CanonicalForm &g)
bool fdivides ( const CanonicalForm & f, const CanonicalForm & g )
CF_NO_INLINE bool isOne() const
bool inCoeffDomain() const
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:39
static BOOLEAN length(leftv result, leftv arg)
Definition: interval.cc:257
int gcd(int a, int b)
Definition: walkSupport.cc:836

◆ distributeLCmultiplier()

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

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

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

Definition at line 2590 of file facFqFactorize.cc.

2593{
2594 CanonicalForm tmp= power (LCmultipler, biFactors.length() - 1);
2595 A *= tmp;
2596 tmp= LCmultipler;
2597 CFListIterator iter= leadingCoeffs;
2598 for (;iter.hasItem(); iter++)
2599 iter.getItem() *= LCmultipler;
2601 for (int i= A.level(); i > 2; i--, iter++)
2602 tmp= tmp (iter.getItem(), i);
2603 if (!tmp.inCoeffDomain())
2604 {
2605 for (CFListIterator i= biFactors; i.hasItem(); i++)
2606 {
2607 i.getItem() *= tmp/LC (i.getItem(), 1);
2608 i.getItem() /= Lc (i.getItem());
2609 }
2610 }
2611}
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
CanonicalForm LC(const CanonicalForm &f)
int length() const
Definition: ftmpl_list.cc:273

◆ earlyFactorDetect()

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

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

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

Definition at line 611 of file facFqFactorize.cc.

614{
616 CFList T= factors;
618 Variable y= F.mvar();
619 Variable x= Variable (1);
620 CanonicalForm LCBuf= LC (buf, x);
621 CanonicalForm g, quot;
622 CFList M= MOD;
623 M.append (power (y, deg));
624 adaptedLiftBound= 0;
625 int d= bound;
626 int e= 0;
627 int nBuf;
628 for (CFListIterator i= factors; i.hasItem(); i++)
629 {
630 g= mulMod (i.getItem(), LCBuf, M);
631 g /= myContent (g);
632 if (fdivides (g, buf, quot))
633 {
634 result.append (g);
635 nBuf= degree (g, y) + degree (LC (g, x), y);
636 d -= nBuf;
637 e= tmax (e, nBuf);
638 buf= quot;
639 LCBuf= LC (buf, x);
640 T= Difference (T, CFList (i.getItem()));
641 }
642 }
643 adaptedLiftBound= d;
644
645 if (adaptedLiftBound < deg)
646 {
647 if (adaptedLiftBound < degree (F) + 1)
648 {
649 if (d == 1)
650 adaptedLiftBound= tmin (e + 1, deg);
651 else
652 adaptedLiftBound= deg;
653 }
654 factors= T;
655 F= buf;
656 success= true;
657 }
658 return result;
659}
Variable x
Definition: cfModGcd.cc:4082
static CanonicalForm bound(const CFMatrix &M)
Definition: cf_linsys.cc:460
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
static CanonicalForm myContent(const CanonicalForm &F)
CanonicalForm mulMod(const CanonicalForm &A, const CanonicalForm &B, const CFList &MOD)
Karatsuba style modular multiplication for multivariate polynomials.
Definition: facMul.cc:3080
template CanonicalForm tmax(const CanonicalForm &, const CanonicalForm &)
template CanonicalForm tmin(const CanonicalForm &, const CanonicalForm &)
template List< Variable > Difference(const List< Variable > &, const List< Variable > &)
STATIC_VAR jList * T
Definition: janet.cc:30
#define M
Definition: sirandom.c:25

◆ evalPoints()

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

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

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

Definition at line 750 of file facFqFactorize.cc.

752{
753 int k= F.level() - 1;
754 Variable x= Variable (1);
755 CanonicalForm LCF=LC (F, x);
757
759 FFRandom genFF;
760 GFRandom genGF;
761 int p= getCharacteristic ();
762 if (p < CHAR_THRESHOLD)
763 {
764 if (!GF && alpha.level() == 1)
765 {
766 fail= true;
767 return CFList();
768 }
769 else if (!GF && alpha.level() != 1)
770 {
771 if ((p == 2 && degree (getMipo (alpha)) < 6) ||
772 (p == 3 && degree (getMipo (alpha)) < 4) ||
773 (p == 5 && degree (getMipo (alpha)) < 3))
774 {
775 fail= true;
776 return CFList();
777 }
778 }
779 }
780 double bound;
781 if (alpha != x)
782 {
783 bound= pow ((double) p, (double) degree (getMipo(alpha)));
784 bound *= (double) k;
785 }
786 else if (GF)
787 {
788 bound= pow ((double) p, (double) getGFDegree());
789 bound *= (double) k;
790 }
791 else
792 bound= pow ((double) p, (double) k);
793
794 CanonicalForm random;
796 do
797 {
798 random= 0;
799 // possible overflow if list.length() does not fit into a int
800 if (list.length() >= bound)
801 {
802 fail= true;
803 break;
804 }
805 for (int i= 0; i < k; i++)
806 {
807 if (list.isEmpty())
808 result.append (0);
809 else if (GF)
810 {
811 result.append (genGF.generate());
812 random += result.getLast()*power (x, i);
813 }
814 else if (alpha.level() != 1)
815 {
816 AlgExtRandomF genAlgExt (alpha);
817 result.append (genAlgExt.generate());
818 random += result.getLast()*power (x, i);
819 }
820 else
821 {
822 result.append (genFF.generate());
823 random += result.getLast()*power (x, i);
824 }
825 }
826 if (find (list, random))
827 {
828 result= CFList();
829 continue;
830 }
831 int l= F.level();
832 eval.insert (F);
834 bool bad= false;
835 for (CFListIterator i= result; i.hasItem(); i++, l--)
836 {
837 eval.insert (eval.getFirst()(i.getItem(), l));
838 LCFeval.insert (LCFeval.getFirst()(i.getItem(), l));
839 if (degree (eval.getFirst(), l - 1) != degree (F, l - 1))
840 {
841 if (!find (list, random))
842 list.append (random);
843 result= CFList();
844 eval= CFList();
845 LCFeval= CFList();
846 bad= true;
847 break;
848 }
849 if ((l != 2) && (degree (LCFeval.getFirst(), l-1) != degree (LCF, l-1)))
850 {
851 if (!find (list, random))
852 list.append (random);
853 result= CFList();
854 eval= CFList();
855 LCFeval= CFList();
856 bad= true;
857 break;
858 }
859 }
860
861 if (bad)
862 continue;
863
864 if (degree (eval.getFirst()) != degree (F, 1))
865 {
866 if (!find (list, random))
867 list.append (random);
868 result= CFList();
869 LCFeval= CFList();
870 eval= CFList();
871 continue;
872 }
873
876 if (degree (gcd_deriv) > 0)
877 {
878 if (!find (list, random))
879 list.append (random);
880 result= CFList();
881 LCFeval= CFList();
882 eval= CFList();
883 continue;
884 }
886 i++;
887 CanonicalForm contentx= content (i.getItem(), x);
888 if (degree (contentx) > 0)
889 {
890 if (!find (list, random))
891 list.append (random);
892 result= CFList();
893 LCFeval= CFList();
894 eval= CFList();
895 continue;
896 }
897
898 contentx= content (i.getItem());
899 if (degree (contentx) > 0)
900 {
901 if (!find (list, random))
902 list.append (random);
903 result= CFList();
904 LCFeval= CFList();
905 eval= CFList();
906 continue;
907 }
908
909 if (list.length() >= bound)
910 {
911 fail= true;
912 break;
913 }
914 } while (find (list, random));
915
916 if (!eval.isEmpty())
918
919 return result;
920}
Rational pow(const Rational &a, int e)
Definition: GMPrat.cc:411
CanonicalForm deriv(const CanonicalForm &f, const Variable &x)
int getGFDegree()
Definition: cf_char.cc:75
int FACTORY_PUBLIC getCharacteristic()
Definition: cf_char.cc:70
int k
Definition: cfEzgcd.cc:99
int p
Definition: cfModGcd.cc:4078
generate random elements in F_p(alpha)
Definition: cf_random.h:70
generate random elements in F_p
Definition: cf_random.h:44
CanonicalForm generate() const
Definition: cf_random.cc:68
generate random elements in GF
Definition: cf_random.h:32
CanonicalForm generate() const
Definition: cf_random.cc:78
T getFirst() const
Definition: ftmpl_list.cc:279
void removeFirst()
Definition: ftmpl_list.cc:287
void insert(const T &)
Definition: ftmpl_list.cc:193
int isEmpty() const
Definition: ftmpl_list.cc:267
int level() const
Definition: variable.h:49
Variable alpha
Definition: facAbsBiFact.cc:51
CanonicalForm contentx
CanonicalForm gcd_deriv
Definition: facFactorize.cc:58
CFList LCFeval
Definition: facFactorize.cc:53
CanonicalForm LCF
Definition: facFactorize.cc:52
CanonicalForm deriv_x
Definition: facFactorize.cc:58
bool bad
Definition: facFactorize.cc:64
CFList & eval
Definition: facFactorize.cc:47
#define CHAR_THRESHOLD
template bool find(const List< CanonicalForm > &, const CanonicalForm &)
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
Definition: variable.cc:207

◆ evaluationWRTDifferentSecondVars()

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

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

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

Definition at line 1965 of file facFqFactorize.cc.

1967{
1968 CanonicalForm tmp;
1969 CFList tmp2;
1971 bool preserveDegree= true;
1972 Variable x= Variable (1);
1973 int j, degAi, degA1= degree (A,1);
1974 for (int i= A.level(); i > 2; i--)
1975 {
1976 tmp= A;
1977 tmp2= CFList();
1979 preserveDegree= true;
1980 degAi= degree (A,i);
1981 for (j= A.level(); j > 1; j--, iter++)
1982 {
1983 if (j == i)
1984 continue;
1985 else
1986 {
1987 tmp= tmp (iter.getItem(), j);
1988 tmp2.insert (tmp);
1989 if ((degree (tmp, i) != degAi) ||
1990 (degree (tmp, 1) != degA1))
1991 {
1992 preserveDegree= false;
1993 break;
1994 }
1995 }
1996 }
1997 if (!content(tmp,1).inCoeffDomain())
1998 preserveDegree= false;
1999 if (!content(tmp).inCoeffDomain())
2000 preserveDegree= false;
2001 if (!(gcd (deriv (tmp,x), tmp)).inCoeffDomain())
2002 preserveDegree= false;
2003 if (preserveDegree)
2004 Aeval [i - 3]= tmp2;
2005 else
2006 Aeval [i - 3]= CFList();
2007 }
2008}
CFList *& Aeval
<[in] poly
Definition: facFactorize.h:31

◆ extEarlyFactorDetect()

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

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

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

Definition at line 664 of file facFqFactorize.cc.

667{
668 Variable alpha= info.getAlpha();
669 Variable beta= info.getBeta();
670 CanonicalForm gamma= info.getGamma();
671 CanonicalForm delta= info.getDelta();
672 int k= info.getGFDegree();
674 CFList T= factors;
676 Variable y= F.mvar();
677 Variable x= Variable (1);
678 CanonicalForm LCBuf= LC (buf, x);
679 CanonicalForm g, gg, quot;
680 CFList M= MOD;
681 M.append (power (y, deg));
682 adaptedLiftBound= 0;
683 int d= bound;
684 int e= 0;
685 int nBuf;
686 CFList source, dest;
687
688 int degMipoBeta= 1;
689 if (!k && beta.level() != 1)
690 degMipoBeta= degree (getMipo (beta));
691
692 for (CFListIterator i= factors; i.hasItem(); i++)
693 {
694 g= mulMod (i.getItem(), LCBuf, M);
695 g /= myContent (g);
696 if (fdivides (g, buf, quot))
697 {
698 gg= reverseShift (g, eval);
699 gg /= Lc (gg);
700 if (!k && beta == x)
701 {
702 if (degree (gg, alpha) < degMipoBeta)
703 {
704 appendTestMapDown (result, gg, info, source, dest);
705 buf= quot;
706 nBuf= degree (g, y) + degree (LC (g, x), y);
707 d -= nBuf;
708 e= tmax (e, nBuf);
709 LCBuf= LC (buf, x);
710 T= Difference (T, CFList (i.getItem()));
711 }
712 }
713 else
714 {
715 if (!isInExtension (gg, gamma, k, delta, source, dest))
716 {
717 appendTestMapDown (result, gg, info, source, dest);
718 buf= quot;
719 nBuf= degree (g, y) + degree (LC (g, x), y);
720 d -= nBuf;
721 e= tmax (e, nBuf);
722 LCBuf= LC (buf, x);
723 T= Difference (T, CFList (i.getItem()));
724 }
725 }
726 }
727 }
728 adaptedLiftBound= d;
729
730 if (adaptedLiftBound < deg)
731 {
732 if (adaptedLiftBound < degree (F) + 1)
733 {
734 if (d == 1)
735 adaptedLiftBound= tmin (e + 1, deg);
736 else
737 adaptedLiftBound= deg;
738 }
739 success= true;
740 factors= T;
741 F= buf;
742 }
743 return result;
744}
Variable beta
Definition: facAbsFact.cc:95
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 reverseShift(const CanonicalForm &F, const CFList &evaluation, int l)
reverse shifting the evaluation point to zero
#define info
Definition: libparse.cc:1256
bool delta(X x, Y y, D d)
Definition: TestSuite.h:160

◆ extFactorize()

CFList extFactorize ( const CanonicalForm F,
const ExtensionInfo info 
)

Factorization over an extension of initial field.

Returns
extFactorize returns factorization of F over initial field
See also
extBiFactorize(), multiFactorize()

Factorization over an extension of initial field.

Parameters
[in]Fpoly to be factored
[in]infoinfo about extension

Definition at line 3660 of file facFqFactorize.cc.

3661{
3662 CanonicalForm A= F;
3663
3664 Variable alpha= info.getAlpha();
3665 Variable beta= info.getBeta();
3666 int k= info.getGFDegree();
3667 char cGFName= info.getGFName();
3668 CanonicalForm delta= info.getDelta();
3669 bool GF= (CFFactory::gettype() == GaloisFieldDomain);
3670 Variable w= Variable (1);
3671
3672 CFList factors;
3673 if (!GF && alpha == w) // we are in F_p
3674 {
3675 CFList factors;
3676 bool extension= true;
3677 int p= getCharacteristic();
3678 if (p < 7)
3679 {
3680 if (p == 2)
3682 else if (p == 3)
3684 else if (p == 5)
3686 ExtensionInfo info= ExtensionInfo (extension);
3687 A= A.mapinto();
3688 factors= multiFactorize (A, info);
3689
3692 Variable vBuf= rootOf (mipo.mapinto());
3693 for (CFListIterator j= factors; j.hasItem(); j++)
3694 j.getItem()= GF2FalphaRep (j.getItem(), vBuf);
3695 prune (vBuf);
3696 }
3697 else if (p >= 7 && p*p < (1<<16)) // pass to GF if possible
3698 {
3700 ExtensionInfo info= ExtensionInfo (extension);
3701 A= A.mapinto();
3702 factors= multiFactorize (A, info);
3703
3706 Variable vBuf= rootOf (mipo.mapinto());
3707 for (CFListIterator j= factors; j.hasItem(); j++)
3708 j.getItem()= GF2FalphaRep (j.getItem(), vBuf);
3709 prune (vBuf);
3710 }
3711 else // not able to pass to GF, pass to F_p(\alpha)
3712 {
3714 Variable v= rootOf (mipo);
3716 factors= multiFactorize (A, info);
3717 prune (v);
3718 }
3719 return factors;
3720 }
3721 else if (!GF && (alpha != w)) // we are in F_p(\alpha)
3722 {
3723 if (k == 1) // need factorization over F_p
3724 {
3725 int extDeg= degree (getMipo (alpha));
3726 extDeg++;
3728 Variable v= rootOf (mipo);
3730 factors= multiFactorize (A, info);
3731 prune (v);
3732 }
3733 else
3734 {
3735 if (beta == w)
3736 {
3738 CanonicalForm primElem, imPrimElem;
3739 bool primFail= false;
3740 Variable vBuf;
3741 primElem= primitiveElement (alpha, vBuf, primFail);
3742 ASSERT (!primFail, "failure in integer factorizer");
3743 if (primFail)
3744 ; //ERROR
3745 else
3746 imPrimElem= mapPrimElem (primElem, alpha, v);
3747
3748 CFList source, dest;
3749 CanonicalForm bufA= mapUp (A, alpha, v, primElem, imPrimElem,
3750 source, dest);
3751 ExtensionInfo info= ExtensionInfo (v, alpha, imPrimElem, primElem);
3752 factors= multiFactorize (bufA, info);
3753 prune (v);
3754 }
3755 else
3756 {
3758 CanonicalForm primElem, imPrimElem;
3759 bool primFail= false;
3760 Variable vBuf;
3761 ASSERT (!primFail, "failure in integer factorizer");
3762 if (primFail)
3763 ; //ERROR
3764 else
3765 imPrimElem= mapPrimElem (delta, beta, v);
3766
3767 CFList source, dest;
3768 CanonicalForm bufA= mapDown (A, info, source, dest);
3769 source= CFList();
3770 dest= CFList();
3771 bufA= mapUp (bufA, beta, v, delta, imPrimElem, source, dest);
3772 ExtensionInfo info= ExtensionInfo (v, beta, imPrimElem, delta);
3773 factors= multiFactorize (bufA, info);
3774 prune (v);
3775 }
3776 }
3777 return factors;
3778 }
3779 else // we are in GF (p^k)
3780 {
3781 int p= getCharacteristic();
3782 int extensionDeg= getGFDegree();
3783 bool extension= true;
3784 if (k == 1) // need factorization over F_p
3785 {
3786 extensionDeg++;
3787 if (pow ((double) p, (double) extensionDeg) < (1<<16))
3788 // pass to GF(p^k+1)
3789 {
3792 Variable vBuf= rootOf (mipo.mapinto());
3793 A= GF2FalphaRep (A, vBuf);
3794 setCharacteristic (p, extensionDeg, 'Z');
3795 ExtensionInfo info= ExtensionInfo (extension);
3796 factors= multiFactorize (A.mapinto(), info);
3797 prune (vBuf);
3798 }
3799 else // not able to pass to another GF, pass to F_p(\alpha)
3800 {
3803 Variable vBuf= rootOf (mipo.mapinto());
3804 A= GF2FalphaRep (A, vBuf);
3805 Variable v= chooseExtension (vBuf, beta, k);
3806 ExtensionInfo info= ExtensionInfo (v, extension);
3807 factors= multiFactorize (A, info);
3808 prune (vBuf);
3809 }
3810 }
3811 else // need factorization over GF (p^k)
3812 {
3813 if (pow ((double) p, (double) 2*extensionDeg) < (1<<16))
3814 // pass to GF(p^2k)
3815 {
3816 setCharacteristic (p, 2*extensionDeg, 'Z');
3817 ExtensionInfo info= ExtensionInfo (k, cGFName, extension);
3818 factors= multiFactorize (GFMapUp (A, extensionDeg), info);
3819 setCharacteristic (p, extensionDeg, cGFName);
3820 }
3821 else // not able to pass to GF (p^2k), pass to F_p (\alpha)
3822 {
3825 Variable v1= rootOf (mipo.mapinto());
3826 A= GF2FalphaRep (A, v1);
3827 Variable v2= chooseExtension (v1, v1, k);
3828 CanonicalForm primElem, imPrimElem;
3829 bool primFail= false;
3830 Variable vBuf;
3831 primElem= primitiveElement (v1, v1, primFail);
3832 if (primFail)
3833 ; //ERROR
3834 else
3835 imPrimElem= mapPrimElem (primElem, v1, v2);
3836 CFList source, dest;
3837 CanonicalForm bufA= mapUp (A, v1, v2, primElem, imPrimElem,
3838 source, dest);
3839 ExtensionInfo info= ExtensionInfo (v2, v1, imPrimElem, primElem);
3840 factors= multiFactorize (bufA, info);
3841 setCharacteristic (p, k, cGFName);
3842 for (CFListIterator i= factors; i.hasItem(); i++)
3843 i.getItem()= Falpha2GFRep (i.getItem());
3844 prune (v1);
3845 }
3846 }
3847 return factors;
3848 }
3849}
void FACTORY_PUBLIC setCharacteristic(int c)
Definition: cf_char.cc:28
static Variable chooseExtension(const Variable &alpha)
Definition: cfModGcd.cc:420
#define ASSERT(expression, message)
Definition: cf_assert.h:99
#define GaloisFieldDomain
Definition: cf_defs.h:18
CanonicalForm randomIrredpoly(int i, const Variable &x)
computes a random monic irreducible univariate polynomial in x over Fp of degree i via NTL/FLINT
Definition: cf_irred.cc:26
CanonicalForm mapPrimElem(const CanonicalForm &primElem, const Variable &alpha, const Variable &beta)
compute the image of a primitive element of in . We assume .
Definition: cf_map_ext.cc:450
CanonicalForm primitiveElement(const Variable &alpha, Variable &beta, bool &fail)
determine a primitive element of , is a primitive element of a field which is isomorphic to
Definition: cf_map_ext.cc:342
static CanonicalForm mapDown(const CanonicalForm &F, const Variable &alpha, const CanonicalForm &G, CFList &source, CFList &dest)
the CanonicalForm G is the output of map_up, returns F considered as an element over ,...
Definition: cf_map_ext.cc:123
static CanonicalForm mapUp(const Variable &alpha, const Variable &beta)
and is a primitive element, returns the image of
Definition: cf_map_ext.cc:70
CanonicalForm Falpha2GFRep(const CanonicalForm &F)
change representation by residue classes modulo a Conway polynomial to representation by primitive el...
Definition: cf_map_ext.cc:203
CanonicalForm GFMapUp(const CanonicalForm &F, int k)
maps a polynomial over to a polynomial over , d needs to be a multiple of k
Definition: cf_map_ext.cc:240
CanonicalForm GF2FalphaRep(const CanonicalForm &F, const Variable &alpha)
changes representation by primitive element to representation by residue classes modulo a Conway poly...
Definition: cf_map_ext.cc:195
static int gettype()
Definition: cf_factory.h:28
CanonicalForm mapinto() const
ExtensionInfo contains information about extension.
Definition: ExtensionInfo.h:51
CanonicalForm mipo
Definition: facAlgExt.cc:57
CFList multiFactorize(const CanonicalForm &F, const ExtensionInfo &info)
INST_VAR CanonicalForm gf_mipo
Definition: gfops.cc:56
void prune(Variable &alpha)
Definition: variable.cc:261
Variable rootOf(const CanonicalForm &mipo, char name)
returns a symbolic root of polynomial with name name Use it to define algebraic variables
Definition: variable.cc:162

◆ extFactorRecombination()

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

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

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

Definition at line 215 of file facFqFactorize.cc.

218{
219 Variable alpha= info.getAlpha();
220 Variable beta= info.getBeta();
221 CanonicalForm gamma= info.getGamma();
222 CanonicalForm delta= info.getDelta();
223 int k= info.getGFDegree();
224 CFList source, dest;
225 if (factors.length() == 1)
226 {
228 return CFList (mapDown (buf, info, source, dest));
229 }
230 if (factors.length() < 1)
231 return CFList();
232
233 int degMipoBeta= 1;
234 if (!k && beta.level() != 1)
235 degMipoBeta= degree (getMipo (beta));
236
237 CFList T, S;
238 T= factors;
239
240 int s= 1;
243
244 buf= F;
245
246 Variable x= Variable (1);
247 CanonicalForm g, LCBuf= LC (buf, x);
248 CanonicalForm buf2, quot;
249 int * v= new int [T.length()];
250 for (int i= 0; i < T.length(); i++)
251 v[i]= 0;
252 bool noSubset= false;
253 CFArray TT;
254 TT= copy (factors);
255 bool recombination= false;
256 bool trueFactor= false;
257 while (T.length() >= 2*s)
258 {
259 while (noSubset == false)
260 {
261 if (T.length() == s)
262 {
263 delete [] v;
264 if (recombination)
265 {
266 T.insert (LCBuf);
267 g= prodMod (T, M);
268 T.removeFirst();
269 result.append (g/myContent (g));
271 g /= Lc (g);
272 appendTestMapDown (result, g, info, source, dest);
273 return result;
274 }
275 else
276 {
278 return CFList (buf);
279 }
280 }
281
282 S= subset (v, s, TT, noSubset);
283 if (noSubset) break;
284
285 S.insert (LCBuf);
286 g= prodMod (S, M);
287 S.removeFirst();
288 g /= myContent (g);
289 if (fdivides (g, buf, quot))
290 {
292 buf2 /= Lc (buf2);
293 if (!k && beta == x)
294 {
295 if (degree (buf2, alpha) < degMipoBeta)
296 {
297 appendTestMapDown (result, buf2, info, source, dest);
298 buf= quot;
299 LCBuf= LC (buf, x);
300 recombination= true;
301 trueFactor= true;
302 }
303 }
304 else
305 {
306 if (!isInExtension (buf2, gamma, k, delta, source, dest))
307 {
308 appendTestMapDown (result, buf2, info, source, dest);
309 buf /= g;
310 LCBuf= LC (buf, x);
311 recombination= true;
312 trueFactor= true;
313 }
314 }
315
316 if (trueFactor)
317 {
318 T= Difference (T, S);
319
320 if (T.length() < 2*s || T.length() == s)
321 {
323 buf /= Lc (buf);
324 appendTestMapDown (result, buf, info, source, dest);
325 delete [] v;
326 return result;
327 }
328 trueFactor= false;
329 TT= copy (T);
330 indexUpdate (v, s, T.length(), noSubset);
331 if (noSubset) break;
332 }
333 }
334 }
335 s++;
336 if (T.length() < 2*s || T.length() == s)
337 {
339 appendTestMapDown (result, buf, info, source, dest);
340 delete [] v;
341 return result;
342 }
343 for (int i= 0; i < T.length(); i++)
344 v[i]= 0;
345 noSubset= false;
346 }
347 if (T.length() < 2*s)
348 {
350 appendMapDown (result, buf, info, source, dest);
351 }
352
353 delete [] v;
354 return result;
355}
const CanonicalForm int s
Definition: facAbsFact.cc:51
void indexUpdate(int index[], const int &subsetSize, const int &setSize, bool &noSubset)
update index
void appendMapDown(CFList &factors, const CanonicalForm &g, const ExtensionInfo &info, CFList &source, CFList &dest)
map g down into a subfield of the current field and append it to factors
CFList 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 buf2
Definition: facFqBivar.cc:73
CFList recombination(const CFList &factors1, const CFList &factors2, int s, int thres, const CanonicalForm &evalPoint, const Variable &x)
recombination of bivariate factors factors1 s. t. the result evaluated at evalPoint coincides with fa...
CanonicalForm prodMod(const CFList &L, const CanonicalForm &M)
product of all elements in L modulo M via divide-and-conquer.
Definition: facMul.cc:3180

◆ extLiftBoundAdaption()

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

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

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

Definition at line 513 of file facFqFactorize.cc.

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

◆ factorRecombination()

CFList factorRecombination ( const CanonicalForm F,
const CFList factors,
const CFList M 
)

Naive factor recombination for multivariate factorization. No precomputed is used to exclude combinations.

Returns
factorRecombination returns a list of factors of F
See also
extFactorRecombination()
Parameters
[in]Fpoly to be factored
[in]factorslist of lifted factors that are monic wrt Variable (1)
[in]Ma list of powers of Variables

Definition at line 360 of file facFqFactorize.cc.

362{
363 if (factors.length() == 1)
364 return CFList(F);
365 if (factors.length() < 1)
366 return CFList();
367
368 CFList T, S;
369
370 T= factors;
371
372 int s= 1;
374 CanonicalForm LCBuf= LC (F, Variable (1));
375 CanonicalForm g, buf= F;
376 int * v= new int [T.length()];
377 for (int i= 0; i < T.length(); i++)
378 v[i]= 0;
379 bool noSubset= false;
380 CFArray TT;
381 TT= copy (factors);
382 Variable y= F.level() - 1;
383 bool recombination= false;
384 CanonicalForm h, quot;
385 while (T.length() >= 2*s)
386 {
387 while (noSubset == false)
388 {
389 if (T.length() == s)
390 {
391 delete [] v;
392 if (recombination)
393 {
394 T.insert (LC (buf));
395 g= prodMod (T, M);
396 result.append (g/myContent (g));
397 return result;
398 }
399 else
400 return CFList (F);
401 }
402 S= subset (v, s, TT, noSubset);
403 if (noSubset) break;
404 S.insert (LCBuf);
405 g= prodMod (S, M);
406 S.removeFirst();
407 g /= myContent (g);
408 if (fdivides (g, buf, quot))
409 {
410 recombination= true;
411 result.append (g);
412 buf= quot;
413 LCBuf= LC (buf, Variable(1));
414 T= Difference (T, S);
415 if (T.length() < 2*s || T.length() == s)
416 {
417 result.append (buf);
418 delete [] v;
419 return result;
420 }
421 TT= copy (T);
422 indexUpdate (v, s, T.length(), noSubset);
423 if (noSubset) break;
424 }
425 }
426 s++;
427 if (T.length() < 2*s || T.length() == s)
428 {
429 result.append (buf);
430 delete [] v;
431 return result;
432 }
433 for (int i= 0; i < T.length(); i++)
434 v[i]= 0;
435 noSubset= false;
436 }
437 if (T.length() < 2*s)
438 result.append (F);
439
440 delete [] v;
441 return result;
442}
STATIC_VAR Poly * h
Definition: janet.cc:971

◆ FpFactorize()

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

factorize a multivariate polynomial over $ F_{p} $

Returns
FpFactorize returns a list of monic factors with multiplicity, the first element is the leading coefficient.
See also
FqFactorize(), GFFactorize()
Parameters
[in]Ga multivariate poly
[in]substCheckenables substitute check

Definition at line 101 of file facFqFactorize.h.

104{
105 if (getNumVars (G) == 2)
106 return FpBiFactorize (G, substCheck);
107
108 CanonicalForm F= G;
109 if (substCheck)
110 {
111 bool foundOne= false;
112 int * substDegree= NEW_ARRAY(int,F.level());
113 for (int i= 1; i <= F.level(); i++)
114 {
115 if (degree (F, i) > 0)
116 {
117 substDegree[i-1]= substituteCheck (F, Variable (i));
118 if (substDegree [i-1] > 1)
119 {
120 foundOne= true;
121 subst (F, F, substDegree[i-1], Variable (i));
122 }
123 }
124 else
125 substDegree[i-1]= -1;
126 }
127 if (foundOne)
128 {
129 CFFList result= FpFactorize (F, false);
130 CFFList newResult, tmp;
132 newResult.insert (result.getFirst());
133 result.removeFirst();
134 for (CFFListIterator i= result; i.hasItem(); i++)
135 {
136 tmp2= i.getItem().factor();
137 for (int j= 1; j <= G.level(); j++)
138 {
139 if (substDegree[j-1] > 1)
140 tmp2= reverseSubst (tmp2, substDegree[j-1], Variable (j));
141 }
142 tmp= FpFactorize (tmp2, false);
143 tmp.removeFirst();
144 for (CFFListIterator j= tmp; j.hasItem(); j++)
145 newResult.append (CFFactor (j.getItem().factor(),
146 j.getItem().exp()*i.getItem().exp()));
147 }
148 DELETE_ARRAY(substDegree);
149 return newResult;
150 }
151 DELETE_ARRAY(substDegree);
152 }
153
155 Variable a= Variable (1);
156 CanonicalForm LcF= Lc (F);
157 TIMING_START (fac_fq_squarefree);
158 CFFList sqrf= FpSqrf (F, false);
159 TIMING_END_AND_PRINT (fac_fq_squarefree,
160 "time for squarefree factorization over Fq: ");
162 CFList bufResult;
163 sqrf.removeFirst();
165 for (CFFListIterator iter= sqrf; iter.hasItem(); iter++)
166 {
167 TIMING_START (fac_fq_factor_squarefree);
168 bufResult= multiFactorize (iter.getItem().factor(), info);
169 TIMING_END_AND_PRINT (fac_fq_factor_squarefree,
170 "time to factorize sqrfree factor over Fq: ");
171 for (i= bufResult; i.hasItem(); i++)
172 result.append (CFFactor (i.getItem(), iter.getItem().exp()));
173 }
174 result.insert (CFFactor (LcF, 1));
175 return result;
176}
int getNumVars(const CanonicalForm &f)
int getNumVars ( const CanonicalForm & f )
Definition: cf_ops.cc:314
#define DELETE_ARRAY(P)
Definition: cf_defs.h:65
#define NEW_ARRAY(T, N)
Definition: cf_defs.h:64
CanonicalForm LcF
Definition: facAbsBiFact.cc:50
CanonicalForm subst(const CanonicalForm &f, const CFList &a, const CFList &b, const CanonicalForm &Rstar, bool isFunctionField)
CFList multiFactorize(const CanonicalForm &F, const Variable &v)
Factorization over Q (a)
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
CFFList FpBiFactorize(const CanonicalForm &G, bool substCheck=true)
factorize a bivariate polynomial over
Definition: facFqBivar.h:190
CFFList FpFactorize(const CanonicalForm &G, bool substCheck=true)
factorize a multivariate polynomial over
const ExtensionInfo & info
< [in] sqrfree poly
CFFList FpSqrf(const CanonicalForm &F, bool sort=true)
squarefree factorization over . If input is not monic, the leading coefficient is dropped
STATIC_VAR TreeM * G
Definition: janet.cc:31
#define TIMING_START(t)
Definition: timing.h:92
#define TIMING_END_AND_PRINT(t, msg)
Definition: timing.h:94

◆ FpSqrfFactorize()

CFList FpSqrfFactorize ( const CanonicalForm F)
inline

factorize a squarefree multivariate polynomial over $ F_{p} $

Returns
FpSqrfFactorize returns a list of monic factors, the first element is the leading coefficient.
See also
FqSqrfFactorize(), GFSqrfFactorize()
Parameters
[in]Fa multivariate poly

Definition at line 47 of file facFqFactorize.h.

49{
50 if (getNumVars (F) == 2)
51 return FpBiSqrfFactorize (F);
54 result.insert (Lc(F));
55 return result;
56}
CFList FpBiSqrfFactorize(const CanonicalForm &G)
factorize a squarefree bivariate polynomial over .
Definition: facFqBivar.h:141

◆ FqFactorize()

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

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

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

Definition at line 184 of file facFqFactorize.h.

188{
189 if (getNumVars (G) == 2)
190 return FqBiFactorize (G, alpha, substCheck);
191
192 CanonicalForm F= G;
193 if (substCheck)
194 {
195 bool foundOne= false;
196 int * substDegree= NEW_ARRAY(int,F.level());
197 for (int i= 1; i <= F.level(); i++)
198 {
199 if (degree (F, i) > 0)
200 {
201 substDegree[i-1]= substituteCheck (F, Variable (i));
202 if (substDegree [i-1] > 1)
203 {
204 foundOne= true;
205 subst (F, F, substDegree[i-1], Variable (i));
206 }
207 }
208 else
209 substDegree[i-1]= -1;
210 }
211 if (foundOne)
212 {
213 CFFList result= FqFactorize (F, alpha, false);
214 CFFList newResult, tmp;
216 newResult.insert (result.getFirst());
217 result.removeFirst();
218 for (CFFListIterator i= result; i.hasItem(); i++)
219 {
220 tmp2= i.getItem().factor();
221 for (int j= 1; j <= G.level(); j++)
222 {
223 if (substDegree[j-1] > 1)
224 tmp2= reverseSubst (tmp2, substDegree[j-1], Variable (j));
225 }
226 tmp= FqFactorize (tmp2, alpha, false);
227 tmp.removeFirst();
228 for (CFFListIterator j= tmp; j.hasItem(); j++)
229 newResult.append (CFFactor (j.getItem().factor(),
230 j.getItem().exp()*i.getItem().exp()));
231 }
232 DELETE_ARRAY(substDegree);
233 return newResult;
234 }
235 DELETE_ARRAY(substDegree);
236 }
237
239 CanonicalForm LcF= Lc (F);
240 TIMING_START (fac_fq_squarefree);
241 CFFList sqrf= FqSqrf (F, alpha, false);
242 TIMING_END_AND_PRINT (fac_fq_squarefree,
243 "time for squarefree factorization over Fq: ");
245 CFList bufResult;
246 sqrf.removeFirst();
248 for (CFFListIterator iter= sqrf; iter.hasItem(); iter++)
249 {
250 TIMING_START (fac_fq_factor_squarefree);
251 bufResult= multiFactorize (iter.getItem().factor(), info);
252 TIMING_END_AND_PRINT (fac_fq_factor_squarefree,
253 "time to factorize sqrfree factor over Fq: ");
254 for (i= bufResult; i.hasItem(); i++)
255 result.append (CFFactor (i.getItem(), iter.getItem().exp()));
256 }
257 result.insert (CFFactor (LcF, 1));
258 return result;
259}
CFFList FqBiFactorize(const CanonicalForm &G, const Variable &alpha, bool substCheck=true)
factorize a bivariate polynomial over
Definition: facFqBivar.h:317
CFFList FqFactorize(const CanonicalForm &G, const Variable &alpha, bool substCheck=true)
factorize a multivariate polynomial over
CFFList FqSqrf(const CanonicalForm &F, const Variable &alpha, bool sort=true)
squarefree factorization over . If input is not monic, the leading coefficient is dropped

◆ FqSqrfFactorize()

CFList FqSqrfFactorize ( const CanonicalForm F,
const Variable alpha 
)
inline

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

Returns
FqSqrfFactorize returns a list of monic factors, the first element is the leading coefficient.
See also
FpSqrfFactorize(), GFSqrfFactorize()
Parameters
[in]Fa multivariate poly
[in]alphaalgebraic variable

Definition at line 64 of file facFqFactorize.h.

67{
68 if (getNumVars (F) == 2)
69 return FqBiSqrfFactorize (F, alpha);
72 result.insert (Lc(F));
73 return result;
74}
CFList FqBiSqrfFactorize(const CanonicalForm &G, const Variable &alpha)
factorize a squarefree bivariate polynomial over .
Definition: facFqBivar.h:156

◆ gcdFreeBasis()

void gcdFreeBasis ( CFFList factors1,
CFFList factors2 
)

gcd free basis of two lists of factors

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

Definition at line 1268 of file facFqFactorize.cc.

1269{
1271 int k= factors1.length();
1272 int l= factors2.length();
1273 int n= 0;
1274 int m;
1276 for (CFFListIterator i= factors1; (n < k && i.hasItem()); i++, n++)
1277 {
1278 m= 0;
1279 for (j= factors2; (m < l && j.hasItem()); j++, m++)
1280 {
1281 g= gcd (i.getItem().factor(), j.getItem().factor());
1282 if (degree (g,1) > 0)
1283 {
1284 j.getItem()= CFFactor (j.getItem().factor()/g, j.getItem().exp());
1285 i.getItem()= CFFactor (i.getItem().factor()/g, i.getItem().exp());
1286 factors1.append (CFFactor (g, i.getItem().exp()));
1287 factors2.append (CFFactor (g, j.getItem().exp()));
1288 }
1289 }
1290 }
1291}
Factor< CanonicalForm > CFFactor
int m
Definition: cfEzgcd.cc:128
const CFList & factors2

◆ getLeadingCoeffs()

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

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

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

Definition at line 2232 of file facFqFactorize.cc.

2234{
2236 CFList LCs;
2237 for (int j= 0; j < A.level() - 2; j++)
2238 {
2239 if (!Aeval[j].isEmpty())
2240 {
2241 LCs= CFList();
2242 for (iter= Aeval[j]; iter.hasItem(); iter++)
2243 LCs.append (LC (iter.getItem(), 1));
2244 //normalize (LCs);
2245 Aeval[j]= LCs;
2246 }
2247 }
2248}

◆ GFFactorize()

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

factorize a multivariate polynomial over GF

Returns
GFFactorize returns a list of monic factors with multiplicity, the first element is the leading coefficient.
See also
FpFactorize(), FqFactorize()
Parameters
[in]Ga multivariate poly
[in]substCheckenables substitute check

Definition at line 267 of file facFqFactorize.h.

270{
272 "GF as base field expected");
273 if (getNumVars (G) == 2)
274 return GFBiFactorize (G, substCheck);
275
276 CanonicalForm F= G;
277 if (substCheck)
278 {
279 bool foundOne= false;
280 int * substDegree= NEW_ARRAY(int,F.level());
281 for (int i= 1; i <= F.level(); i++)
282 {
283 if (degree (F, i) > 0)
284 {
285 substDegree[i-1]= substituteCheck (F, Variable (i));
286 if (substDegree [i-1] > 1)
287 {
288 foundOne= true;
289 subst (F, F, substDegree[i-1], Variable (i));
290 }
291 }
292 else
293 substDegree[i-1]= -1;
294 }
295 if (foundOne)
296 {
297 CFFList result= GFFactorize (F, false);
298 CFFList newResult, tmp;
300 newResult.insert (result.getFirst());
301 result.removeFirst();
302 for (CFFListIterator i= result; i.hasItem(); i++)
303 {
304 tmp2= i.getItem().factor();
305 for (int j= 1; j <= G.level(); j++)
306 {
307 if (substDegree[j-1] > 1)
308 tmp2= reverseSubst (tmp2, substDegree[j-1], Variable (j));
309 }
310 tmp= GFFactorize (tmp2, false);
311 tmp.removeFirst();
312 for (CFFListIterator j= tmp; j.hasItem(); j++)
313 newResult.append (CFFactor (j.getItem().factor(),
314 j.getItem().exp()*i.getItem().exp()));
315 }
316 DELETE_ARRAY(substDegree);
317 return newResult;
318 }
319 DELETE_ARRAY(substDegree);
320 }
321
322 Variable a= Variable (1);
324 CanonicalForm LcF= Lc (F);
325 CFFList sqrf= GFSqrf (F, false);
327 CFList bufResult;
328 sqrf.removeFirst();
330 for (CFFListIterator iter= sqrf; iter.hasItem(); iter++)
331 {
332 bufResult= multiFactorize (iter.getItem().factor(), info);
333 for (i= bufResult; i.hasItem(); i++)
334 result.append (CFFactor (i.getItem(), iter.getItem().exp()));
335 }
336 result.insert (CFFactor (LcF, 1));
337 return result;
338}
CFFList GFBiFactorize(const CanonicalForm &G, bool substCheck=true)
factorize a bivariate polynomial over GF
Definition: facFqBivar.h:446
CFFList GFFactorize(const CanonicalForm &G, bool substCheck=true)
factorize a multivariate polynomial over GF
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

◆ GFSqrfFactorize()

CFList GFSqrfFactorize ( const CanonicalForm F)
inline

factorize a squarefree multivariate polynomial over GF

Returns
GFSqrfFactorize returns a list of monic factors, the first element is the leading coefficient.
See also
FpSqrfFactorize(), FqSqrfFactorize()
Parameters
[in]Fa multivariate poly

Definition at line 82 of file facFqFactorize.h.

84{
86 "GF as base field expected");
87 if (getNumVars (F) == 2)
88 return GFBiSqrfFactorize (F);
91 result.insert (Lc(F));
92 return result;
93}
CFList GFBiSqrfFactorize(const CanonicalForm &G)
factorize a squarefree bivariate polynomial over GF
Definition: facFqBivar.h:172

◆ henselLiftAndEarly()

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

hensel Lifting and early factor detection

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

Definition at line 984 of file facFqFactorize.cc.

988{
989 bool extension= info.isInExtension();
990 CFList bufFactors= biFactors;
991 bufFactors.insert (LC (Aeval.getFirst(), 1));
992
993 sortList (bufFactors, Variable (1));
994
995 CFList diophant;
996 CFArray Pi;
997 int smallFactorDeg= 11; //tunable parameter
999 int adaptedLiftBound= 0;
1000 int liftBound= liftBounds[1];
1001
1002 earlySuccess= false;
1003 CFList earlyReconstFactors;
1005 j++;
1006 CanonicalForm buf= j.getItem();
1007 CFMatrix Mat= CFMatrix (liftBound, bufFactors.length() - 1);
1008 MOD= CFList (power (Variable (2), liftBounds[0]));
1009 if (smallFactorDeg >= liftBound)
1010 {
1011 result= henselLift23 (Aeval, bufFactors, liftBounds, diophant, Pi, Mat);
1012 }
1013 else if (smallFactorDeg >= degree (buf) + 1)
1014 {
1015 liftBounds[1]= degree (buf) + 1;
1016 result= henselLift23 (Aeval, bufFactors, liftBounds, diophant, Pi, Mat);
1017 if (Aeval.length() == 2)
1018 {
1019 if (!extension)
1020 earlyFactors= earlyFactorDetect
1021 (buf, result, adaptedLiftBound, earlySuccess,
1022 degree (buf) + 1, MOD, liftBound);
1023 else
1024 earlyFactors= extEarlyFactorDetect
1025 (buf, result, adaptedLiftBound, earlySuccess,
1027 (buf) + 1, MOD, liftBound);
1028 }
1029 else
1030 {
1031 if (!extension)
1032 adaptedLiftBound= liftBoundAdaption (buf, result, earlySuccess,
1033 degree (buf) + 1, MOD, liftBound);
1034 else
1035 adaptedLiftBound= extLiftBoundAdaption (buf, result, earlySuccess, info,
1036 evaluation, degree (buf) + 1,
1037 MOD, liftBound);
1038 }
1039 if (!earlySuccess)
1040 {
1041 result.insert (LC (buf, 1));
1042 liftBounds[1]= adaptedLiftBound;
1043 liftBound= adaptedLiftBound;
1044 henselLiftResume (buf, result, degree (buf) + 1, liftBound,
1045 Pi, diophant, Mat, MOD);
1046 }
1047 else
1048 liftBounds[1]= adaptedLiftBound;
1049 }
1050 else if (smallFactorDeg < degree (buf) + 1)
1051 {
1052 liftBounds[1]= smallFactorDeg;
1053 result= henselLift23 (Aeval, bufFactors, liftBounds, diophant, Pi, Mat);
1054 if (Aeval.length() == 2)
1055 {
1056 if (!extension)
1057 earlyFactors= earlyFactorDetect (buf, result, adaptedLiftBound,
1058 earlySuccess, smallFactorDeg, MOD,
1059 liftBound);
1060 else
1061 earlyFactors= extEarlyFactorDetect (buf, result, adaptedLiftBound,
1062 earlySuccess, info, evaluation,
1063 smallFactorDeg, MOD, liftBound);
1064 }
1065 else
1066 {
1067 if (!extension)
1068 adaptedLiftBound= liftBoundAdaption (buf, result, earlySuccess,
1069 smallFactorDeg, MOD, liftBound);
1070 else
1071 adaptedLiftBound= extLiftBoundAdaption (buf, result, earlySuccess, info,
1072 evaluation, smallFactorDeg, MOD,
1073 liftBound);
1074 }
1075
1076 if (!earlySuccess)
1077 {
1078 result.insert (LC (buf, 1));
1079 henselLiftResume (buf, result, smallFactorDeg, degree (buf) + 1,
1080 Pi, diophant, Mat, MOD);
1081 if (Aeval.length() == 2)
1082 {
1083 if (!extension)
1084 earlyFactors= earlyFactorDetect (buf, result, adaptedLiftBound,
1085 earlySuccess, degree (buf) + 1,
1086 MOD, liftBound);
1087 else
1088 earlyFactors= extEarlyFactorDetect (buf, result, adaptedLiftBound,
1089 earlySuccess, info, evaluation,
1090 degree (buf) + 1, MOD,
1091 liftBound);
1092 }
1093 else
1094 {
1095 if (!extension)
1096 adaptedLiftBound= liftBoundAdaption (buf, result, earlySuccess,
1097 degree (buf) + 1, MOD,liftBound);
1098 else
1099 adaptedLiftBound= extLiftBoundAdaption (buf, result, earlySuccess,
1101 degree (buf) + 1, MOD,
1102 liftBound);
1103 }
1104 if (!earlySuccess)
1105 {
1106 result.insert (LC (buf, 1));
1107 liftBounds[1]= adaptedLiftBound;
1108 liftBound= adaptedLiftBound;
1109 henselLiftResume (buf, result, degree (buf) + 1, liftBound,
1110 Pi, diophant, Mat, MOD);
1111 }
1112 else
1113 liftBounds[1]= adaptedLiftBound;
1114 }
1115 else
1116 liftBounds[1]= adaptedLiftBound;
1117 }
1118
1119 MOD.append (power (Variable (3), liftBounds[1]));
1120
1121 if (Aeval.length() > 2)
1122 {
1124 j++;
1125 CFList bufEval;
1126 bufEval.append (j.getItem());
1127 j++;
1128 int liftBoundsLength= Aeval.getLast().level() - 1;
1129 for (int i= 2; i <= liftBoundsLength && j.hasItem(); i++, j++)
1130 {
1131 earlySuccess= false;
1132 result.insert (LC (bufEval.getFirst(), 1));
1133 bufEval.append (j.getItem());
1134 liftBound= liftBounds[i];
1135 Mat= CFMatrix (liftBounds[i], result.length() - 1);
1136
1137 buf= j.getItem();
1138 if (smallFactorDeg >= liftBound)
1139 result= henselLift (bufEval, result, MOD, diophant, Pi, Mat,
1140 liftBounds[i - 1], liftBounds[i]);
1141 else if (smallFactorDeg >= degree (buf) + 1)
1142 {
1143 result= henselLift (bufEval, result, MOD, diophant, Pi, Mat,
1144 liftBounds[i - 1], degree (buf) + 1);
1145
1146 if (Aeval.length() == i + 1)
1147 {
1148 if (!extension)
1149 earlyFactors= earlyFactorDetect
1150 (buf, result, adaptedLiftBound, earlySuccess,
1151 degree (buf) + 1, MOD, liftBound);
1152 else
1153 earlyFactors= extEarlyFactorDetect
1154 (buf, result, adaptedLiftBound, earlySuccess,
1155 info, evaluation, degree (buf) + 1, MOD, liftBound);
1156 }
1157 else
1158 {
1159 if (!extension)
1160 adaptedLiftBound= liftBoundAdaption
1161 (buf, result, earlySuccess, degree (buf)
1162 + 1, MOD, liftBound);
1163 else
1164 adaptedLiftBound= extLiftBoundAdaption
1165 (buf, result, earlySuccess, info, evaluation,
1166 degree (buf) + 1, MOD, liftBound);
1167 }
1168
1169 if (!earlySuccess)
1170 {
1171 result.insert (LC (buf, 1));
1172 liftBounds[i]= adaptedLiftBound;
1173 liftBound= adaptedLiftBound;
1174 henselLiftResume (buf, result, degree (buf) + 1, liftBound,
1175 Pi, diophant, Mat, MOD);
1176 }
1177 else
1178 {
1179 liftBounds[i]= adaptedLiftBound;
1180 }
1181 }
1182 else if (smallFactorDeg < degree (buf) + 1)
1183 {
1184 result= henselLift (bufEval, result, MOD, diophant, Pi, Mat,
1185 liftBounds[i - 1], smallFactorDeg);
1186
1187 if (Aeval.length() == i + 1)
1188 {
1189 if (!extension)
1190 earlyFactors= earlyFactorDetect
1191 (buf, result, adaptedLiftBound, earlySuccess,
1192 smallFactorDeg, MOD, liftBound);
1193 else
1194 earlyFactors= extEarlyFactorDetect
1195 (buf, result, adaptedLiftBound, earlySuccess,
1196 info, evaluation, smallFactorDeg, MOD, liftBound);
1197 }
1198 else
1199 {
1200 if (!extension)
1201 adaptedLiftBound= liftBoundAdaption
1202 (buf, result, earlySuccess,
1203 smallFactorDeg, MOD, liftBound);
1204 else
1205 adaptedLiftBound= extLiftBoundAdaption
1206 (buf, result, earlySuccess, info, evaluation,
1207 smallFactorDeg, MOD, liftBound);
1208 }
1209
1210 if (!earlySuccess)
1211 {
1212 result.insert (LC (buf, 1));
1213 henselLiftResume (buf, result, smallFactorDeg,
1214 degree (buf) + 1, Pi, diophant, Mat, MOD);
1215 if (Aeval.length() == i + 1)
1216 {
1217 if (!extension)
1218 earlyFactors= earlyFactorDetect
1219 (buf, result, adaptedLiftBound, earlySuccess,
1220 degree (buf) + 1, MOD, liftBound);
1221 else
1222 earlyFactors= extEarlyFactorDetect
1223 (buf, result, adaptedLiftBound, earlySuccess,
1224 info, evaluation, degree (buf) + 1, MOD,
1225 liftBound);
1226 }
1227 else
1228 {
1229 if (!extension)
1230 adaptedLiftBound= liftBoundAdaption
1231 (buf, result, earlySuccess, degree
1232 (buf) + 1, MOD, liftBound);
1233 else
1234 adaptedLiftBound= extLiftBoundAdaption
1235 (buf, result, earlySuccess, info, evaluation,
1236 degree (buf) + 1, MOD, liftBound);
1237 }
1238
1239 if (!earlySuccess)
1240 {
1241 result.insert (LC (buf, 1));
1242 liftBounds[i]= adaptedLiftBound;
1243 liftBound= adaptedLiftBound;
1244 henselLiftResume (buf, result, degree (buf) + 1, liftBound,
1245 Pi, diophant, Mat, MOD);
1246 }
1247 else
1248 liftBounds[i]= adaptedLiftBound;
1249 }
1250 else
1251 liftBounds[i]= adaptedLiftBound;
1252 }
1253 MOD.append (power (Variable (i + 2), liftBounds[i]));
1254 bufEval.removeFirst();
1255 }
1256 bufFactors= result;
1257 }
1258 else
1259 bufFactors= result;
1260
1261 if (earlySuccess)
1262 A= buf;
1263 return result;
1264}
Matrix< CanonicalForm > CFMatrix
T getLast() const
Definition: ftmpl_list.cc:309
int liftBoundAdaption(const CanonicalForm &F, const CFList &factors, bool &success, const int deg, const CFList &MOD, const int bound)
Lift bound adaption. Essentially an early factor detection but only the lift bound is adapted.
CFList extEarlyFactorDetect(CanonicalForm &F, CFList &factors, int &adaptedLiftBound, bool &success, const ExtensionInfo &info, const CFList &eval, const int deg, const CFList &MOD, const int bound)
detects factors of F at stage deg of Hensel lifting. No combinations of more than one factor are test...
int extLiftBoundAdaption(const CanonicalForm &F, const CFList &factors, bool &success, const ExtensionInfo &info, const CFList &eval, const int deg, const CFList &MOD, const int bound)
Lift bound adaption over an extension of the initial field. Essentially an early factor detection but...
CFList earlyFactorDetect(CanonicalForm &F, CFList &factors, int &adaptedLiftBound, bool &success, const int deg, const CFList &MOD, const int bound)
detects factors of F at stage deg of Hensel lifting. No combinations of more than one factor are test...
CFList henselLift23(const CFList &eval, const CFList &factors, int *l, CFList &diophant, CFArray &Pi, CFMatrix &M)
Hensel lifting from bivariate to trivariate.
Definition: facHensel.cc:1785
CFList henselLift(const CFList &F, const CFList &factors, const CFList &MOD, CFList &diophant, CFArray &Pi, CFMatrix &M, int lOld, int lNew)
Hensel lifting.
Definition: facHensel.cc:1852
void henselLiftResume(const CanonicalForm &F, CFList &factors, int start, int end, CFArray &Pi, const CFList &diophant, CFMatrix &M, const CFList &MOD)
resume Hensel lifting.
Definition: facHensel.cc:1827
void sortList(CFList &list, const Variable &x)
sort a list of polynomials by their degree in x.
Definition: facHensel.cc:449

◆ LCHeuristic()

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

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

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

Definition at line 2614 of file facFqFactorize.cc.

2618{
2619 CFListIterator iter, iter2;
2620 int index;
2621 Variable xx;
2622 CFList vars1;
2623 CFFList sqrfMultiplier= sqrFree (LCmultiplier);
2624 if (sqrfMultiplier.getFirst().factor().inCoeffDomain())
2625 sqrfMultiplier.removeFirst();
2626 sqrfMultiplier= sortCFFListByNumOfVars (sqrfMultiplier);
2627 xx= Variable (2);
2628 for (iter= oldBiFactors; iter.hasItem(); iter++)
2629 vars1.append (power (xx, degree (LC (iter.getItem(),1), xx)));
2630 for (int i= 0; i < lengthAeval; i++)
2631 {
2632 if (oldAeval[i].isEmpty())
2633 continue;
2634 xx= oldAeval[i].getFirst().mvar();
2635 iter2= vars1;
2636 for (iter= oldAeval[i]; iter.hasItem(); iter++, iter2++)
2637 iter2.getItem() *= power (xx, degree (LC (iter.getItem(),1), xx));
2638 }
2639 CanonicalForm tmp, quot1, quot2, quot3;
2640 iter2= vars1;
2641 for (iter= leadingCoeffs[lengthAeval-1]; iter.hasItem(); iter++, iter2++)
2642 {
2643 tmp= iter.getItem()/LCmultiplier;
2644 for (int i=1; i <= tmp.level(); i++)
2645 {
2646 if (degree (tmp,i) > 0 && (degree (iter2.getItem(),i) > degree (tmp,i)))
2647 iter2.getItem() /= power (Variable (i), degree (tmp,i));
2648 }
2649 }
2650 int multi;
2651 for (CFFListIterator ii= sqrfMultiplier; ii.hasItem(); ii++)
2652 {
2653 multi= 0;
2654 for (iter= vars1; iter.hasItem(); iter++)
2655 {
2656 tmp= iter.getItem();
2657 while (fdivides (myGetVars (ii.getItem().factor()), tmp))
2658 {
2659 multi++;
2660 tmp /= myGetVars (ii.getItem().factor());
2661 }
2662 }
2663 if (multi == ii.getItem().exp())
2664 {
2665 index= 1;
2666 for (iter= vars1; iter.hasItem(); iter++, index++)
2667 {
2668 while (fdivides (myGetVars (ii.getItem().factor()), iter.getItem()))
2669 {
2670 int index2= 1;
2671 for (iter2= leadingCoeffs[lengthAeval-1]; iter2.hasItem();iter2++,
2672 index2++)
2673 {
2674 if (index2 == index)
2675 continue;
2676 else
2677 {
2678 tmp= ii.getItem().factor();
2679 if (fdivides (tmp, iter2.getItem(), quot1))
2680 {
2682 for (int jj= A.level(); jj > 2; jj--, iter3++)
2683 tmp= tmp (iter3.getItem(), jj);
2684 if (!tmp.inCoeffDomain())
2685 {
2686 int index3= 1;
2687 for (iter3= biFactors; iter3.hasItem(); iter3++, index3++)
2688 {
2689 if (index3 == index2)
2690 {
2691 if (fdivides (tmp, iter3.getItem(), quot2))
2692 {
2693 if (fdivides (ii.getItem().factor(), A, quot3))
2694 {
2695 A = quot3;
2696 iter2.getItem() = quot2;
2697 iter3.getItem() = quot3;
2698 iter3.getItem() /= Lc (iter3.getItem());
2699 break;
2700 }
2701 }
2702 }
2703 }
2704 }
2705 }
2706 }
2707 }
2708 iter.getItem() /= getVars (ii.getItem().factor());
2709 }
2710 }
2711 }
2712 else
2713 {
2714 index= 1;
2715 for (iter= vars1; iter.hasItem(); iter++, index++)
2716 {
2717 if (!fdivides (myGetVars (ii.getItem().factor()), iter.getItem()))
2718 {
2719 int index2= 1;
2720 for (iter2= leadingCoeffs[lengthAeval-1];iter2.hasItem();iter2++,
2721 index2++)
2722 {
2723 if (index2 == index)
2724 {
2725 tmp= power (ii.getItem().factor(), ii.getItem().exp());
2726 if (fdivides (tmp, A, quot1))
2727 {
2728 if (fdivides (tmp, iter2.getItem()))
2729 {
2731 for (int jj= A.level(); jj > 2; jj--, iter3++)
2732 tmp= tmp (iter3.getItem(), jj);
2733 if (!tmp.inCoeffDomain())
2734 {
2735 int index3= 1;
2736 for (iter3= biFactors; iter3.hasItem(); iter3++, index3++)
2737 {
2738 if (index3 == index2)
2739 {
2740 if (fdivides (tmp, iter3.getItem(), quot3))
2741 {
2742 A = quot1;
2743 iter2.getItem() = quot2;
2744 iter3.getItem() = quot3;
2745 iter3.getItem() /= Lc (iter3.getItem());
2746 break;
2747 }
2748 }
2749 }
2750 }
2751 }
2752 }
2753 }
2754 }
2755 }
2756 }
2757 }
2758 }
2759}
CanonicalForm getVars(const CanonicalForm &f)
CanonicalForm getVars ( const CanonicalForm & f )
Definition: cf_ops.cc:350
CFFList FACTORY_PUBLIC sqrFree(const CanonicalForm &f, bool sort=false)
squarefree factorization
Definition: cf_factor.cc:957
CFFList sortCFFListByNumOfVars(CFFList &F)
sort CFFList by the number variables in a factor
CanonicalForm myGetVars(const CanonicalForm &F)
like getVars but including multiplicities
static int index(p_Length length, p_Ord ord)
Definition: p_Procs_Impl.h:592

◆ LCHeuristic2()

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

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

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

Definition at line 2778 of file facFqFactorize.cc.

2781{
2782 CanonicalForm cont;
2783 int index= 1;
2784 CFListIterator iter2;
2785 for (CFListIterator iter= factors; iter.hasItem(); iter++, index++)
2786 {
2787 cont= content (iter.getItem(), 1);
2788 cont= gcd (cont, LCmultiplier);
2789 contents.append (cont);
2790 if (cont.inCoeffDomain()) // trivial content->LCmultiplier needs to go there
2791 {
2792 foundTrueMultiplier= true;
2793 int index2= 1;
2794 for (iter2= leadingCoeffs; iter2.hasItem(); iter2++, index2++)
2795 {
2796 if (index2 == index)
2797 continue;
2798 iter2.getItem() /= LCmultiplier;
2799 }
2800 break;
2801 }
2802 else
2803 LCs.append (LC (iter.getItem()/cont, 1));
2804 }
2805}

◆ LCHeuristic3()

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

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

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

Definition at line 2808 of file facFqFactorize.cc.

2812{
2813 int index= 1;
2814 CFListIterator iter, iter2= factors;
2815 for (iter= contents; iter.hasItem(); iter++, iter2++, index++)
2816 {
2817 if (fdivides (iter.getItem(), LCmultiplier))
2818 {
2819 if ((LCmultiplier/iter.getItem()).inCoeffDomain() &&
2820 !isOnlyLeadingCoeff(iter2.getItem())) //content divides LCmultiplier completely and factor consists of more terms than just the leading coeff
2821 {
2822 Variable xx= Variable (2);
2823 CanonicalForm vars;
2824 vars= power (xx, degree (LC (getItem(oldBiFactors, index),1),
2825 xx));
2826 for (int i= 0; i < lengthAeval; i++)
2827 {
2828 if (oldAeval[i].isEmpty())
2829 continue;
2830 xx= oldAeval[i].getFirst().mvar();
2831 vars *= power (xx, degree (LC (getItem(oldAeval[i], index),1),
2832 xx));
2833 }
2834 if (vars.level() <= 2)
2835 {
2836 int index2= 1;
2837 for (CFListIterator iter3= leadingCoeffs[lengthAeval-1];
2838 iter3.hasItem(); iter3++, index2++)
2839 {
2840 if (index2 == index)
2841 {
2842 iter3.getItem() /= LCmultiplier;
2843 break;
2844 }
2845 }
2846 A /= LCmultiplier;
2847 foundMultiplier= true;
2848 iter.getItem()= 1;
2849 }
2850 }
2851 }
2852 }
2853}
CanonicalForm getItem(const CFList &list, const int &pos)
helper function
Definition: cf_map_ext.cc:53
bool isOnlyLeadingCoeff(const CanonicalForm &F)
check if F consists of more than just the leading coeff wrt. Variable (1)

◆ LCHeuristic4()

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

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

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

Definition at line 2856 of file facFqFactorize.cc.

2861{
2862 int index=1;
2863 CFListIterator iter, iter2= factors;
2864 for (iter= contents; iter.hasItem(); iter++, iter2++, index++)
2865 {
2866 if (!iter.getItem().isOne() &&
2867 fdivides (iter.getItem(), LCmultiplier))
2868 {
2869 if (!isOnlyLeadingCoeff (iter2.getItem())) // factor is more than just leading coeff
2870 {
2871 int index2= 1;
2872 for (iter2= leadingCoeffs[lengthAeval-1]; iter2.hasItem();
2873 iter2++, index2++)
2874 {
2875 if (index2 == index)
2876 {
2877 iter2.getItem() /= iter.getItem();
2878 foundMultiplier= true;
2879 break;
2880 }
2881 }
2882 A /= iter.getItem();
2883 LCmultiplier /= iter.getItem();
2884 iter.getItem()= 1;
2885 }
2886 else if (fdivides (getVars (LCmultiplier), testVars))//factor consists of just leading coeff
2887 {
2888 Variable xx= Variable (2);
2889 CanonicalForm vars;
2890 vars= power (xx, degree (LC (getItem(oldBiFactors, index),1),
2891 xx));
2892 for (int i= 0; i < lengthAeval; i++)
2893 {
2894 if (oldAeval[i].isEmpty())
2895 continue;
2896 xx= oldAeval[i].getFirst().mvar();
2897 vars *= power (xx, degree (LC (getItem(oldAeval[i], index),1),
2898 xx));
2899 }
2900 if (myGetVars(content(getItem(leadingCoeffs[lengthAeval-1],index),1))
2901 /myGetVars (LCmultiplier) == vars)
2902 {
2903 int index2= 1;
2904 for (iter2= leadingCoeffs[lengthAeval-1]; iter2.hasItem();
2905 iter2++, index2++)
2906 {
2907 if (index2 == index)
2908 {
2909 iter2.getItem() /= LCmultiplier;
2910 foundMultiplier= true;
2911 break;
2912 }
2913 }
2914 A /= LCmultiplier;
2915 iter.getItem()= 1;
2916 }
2917 }
2918 }
2919 }
2920}

◆ LCHeuristicCheck()

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

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

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

Definition at line 2762 of file facFqFactorize.cc.

2765{
2766 CanonicalForm pLCs= prod (LCs);
2767 if (fdivides (pLCs, LC (oldA,1)) && (LC(oldA,1)/pLCs).inCoeffDomain()) // check if the product of the lead coeffs of the primitive factors equals the lead coeff of the old A
2768 {
2769 A= oldA;
2770 CFListIterator iter2= leadingCoeffs;
2771 for (CFListIterator iter= contents; iter.hasItem(); iter++, iter2++)
2772 iter2.getItem() /= iter.getItem();
2773 foundTrueMultiplier= true;
2774 }
2775}
fq_nmod_poly_t prod
Definition: facHensel.cc:100

◆ lcmContent()

CanonicalForm lcmContent ( const CanonicalForm A,
CFList contentAi 
)

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

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

Definition at line 965 of file facFqFactorize.cc.

966{
967 int i= A.level();
969 contentAi.append (content (buf, i));
970 buf /= contentAi.getLast();
971 contentAi.append (content (buf, i - 1));
972 CanonicalForm result= lcm (contentAi.getFirst(), contentAi.getLast());
973 for (i= i - 2; i > 0; i--)
974 {
975 contentAi.append (content (buf, i));
976 buf /= contentAi.getLast();
977 result= lcm (result, contentAi.getLast());
978 }
979 return result;
980}
int lcm(unsigned long *l, unsigned long *a, unsigned long *b, unsigned long p, int dega, int degb)
Definition: minpoly.cc:709

◆ leadingCoeffReconstruction()

CFList leadingCoeffReconstruction ( const CanonicalForm F,
const CFList factors,
const CFList M 
)

obtain factors of F by reconstructing their leading coeffs

Returns
returns the reconstructed factors
See also
factorRecombination()
Parameters
[in]Fpoly to be factored
[in]factorsfactors of f monic wrt Variable (1)
[in]Ma list of powers of Variables

◆ liftBoundAdaption()

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

Lift bound adaption. Essentially an early factor detection but only the lift bound is adapted.

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

Definition at line 447 of file facFqFactorize.cc.

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

◆ myCompress()

CanonicalForm myCompress ( const CanonicalForm F,
CFMap N 
)

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

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

Definition at line 133 of file facFqFactorize.cc.

134{
135 int n= F.level();
136 int * degsf= NEW_ARRAY(int,n + 1);
137 int ** swap= new int* [n + 1];
138 for (int i= 0; i <= n; i++)
139 {
140 degsf[i]= 0;
141 swap [i]= new int [3];
142 swap [i] [0]= 0;
143 swap [i] [1]= 0;
144 swap [i] [2]= 0;
145 }
146 int i= 1;
147 n= 1;
148 degsf= degrees (F, degsf);
149
151 while ( i <= F.level() )
152 {
153 while( degsf[i] == 0 ) i++;
154 swap[n][0]= i;
155 swap[n][1]= size (LC (F,i));
156 swap[n][2]= degsf [i];
157 if (i != n)
159 n++; i++;
160 }
161
162 int buf1, buf2, buf3;
163 n--;
164
165 for (i= 1; i < n; i++)
166 {
167 for (int j= 1; j < n - i + 1; j++)
168 {
169 if (swap[j][1] > swap[j + 1][1])
170 {
171 buf1= swap [j + 1] [0];
172 buf2= swap [j + 1] [1];
173 buf3= swap [j + 1] [2];
174 swap[j + 1] [0]= swap[j] [0];
175 swap[j + 1] [1]= swap[j] [1];
176 swap[j + 1] [2]= swap[j] [2];
177 swap[j][0]= buf1;
178 swap[j][1]= buf2;
179 swap[j][2]= buf3;
180 result= swapvar (result, Variable (j + 1), Variable (j));
181 }
182 else if (swap[j][1] == swap[j + 1][1] && swap[j][2] < swap[j + 1][2])
183 {
184 buf1= swap [j + 1] [0];
185 buf2= swap [j + 1] [1];
186 buf3= swap [j + 1] [2];
187 swap[j + 1] [0]= swap[j] [0];
188 swap[j + 1] [1]= swap[j] [1];
189 swap[j + 1] [2]= swap[j] [2];
190 swap[j][0]= buf1;
191 swap[j][1]= buf2;
192 swap[j][2]= buf3;
193 result= swapvar (result, Variable (j + 1), Variable (j));
194 }
195 }
196 }
197
198 for (i= n; i > 0; i--)
199 {
200 if (i != swap[i] [0])
201 N.newpair (Variable (i), Variable (swap[i] [0]));
202 }
203
204 for (i= F.level(); i >=0 ; i--)
205 delete [] swap[i];
206 delete [] swap;
207
209
210 return result;
211}
#define swap(_i, _j)
int size(const CanonicalForm &f, const Variable &v)
int size ( const CanonicalForm & f, const Variable & v )
Definition: cf_ops.cc:600
int * degrees(const CanonicalForm &f, int *degs=0)
int * degrees ( const CanonicalForm & f, int * degs )
Definition: cf_ops.cc:493
const CanonicalForm CFMap CFMap & N
Definition: cfEzgcd.cc:56
int * degsf
Definition: cfEzgcd.cc:59
CanonicalForm buf1
Definition: facFqBivar.cc:73

◆ precomputeLeadingCoeff()

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

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

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

Definition at line 1478 of file facFqFactorize.cc.

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

◆ prepareLeadingCoeffs()

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

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

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

Definition at line 2381 of file facFqFactorize.cc.

2384{
2385 CFList l= leadingCoeffs;
2386 LCs [n-3]= l;
2389 for (int i= n - 1; i > 2; i--, iter++)
2390 {
2391 for (j= l; j.hasItem(); j++)
2392 j.getItem()= j.getItem() (iter.getItem(), i + 1);
2393 LCs [i - 3]= l;
2394 }
2395 l= LCs [0];
2396 for (CFListIterator i= l; i.hasItem(); i++)
2397 i.getItem()= i.getItem() (iter.getItem(), 3);
2398 CFListIterator ii= biFactors;
2399 CFList normalizeFactor;
2400 for (CFListIterator i= l; i.hasItem(); i++, ii++)
2401 normalizeFactor.append (Lc (LC (ii.getItem(), 1))/Lc (i.getItem()));
2402 for (int i= 0; i < n-2; i++)
2403 {
2404 ii= normalizeFactor;
2405 for (j= LCs [i]; j.hasItem(); j++, ii++)
2406 j.getItem() *= ii.getItem();
2407 }
2408
2410
2411 CanonicalForm hh= 1/Lc (Aeval.getFirst());
2412
2413 for (iter= Aeval; iter.hasItem(); iter++)
2414 iter.getItem() *= hh;
2415
2416 A *= hh;
2417}

◆ recombination()

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

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

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

Definition at line 2113 of file facFqFactorize.cc.

2115{
2116 CFList T, S;
2117
2118 T= factors1;
2119 CFList result;
2121 int * v= new int [T.length()];
2122 for (int i= 0; i < T.length(); i++)
2123 v[i]= 0;
2124 bool nosubset= false;
2125 CFArray TT;
2126 TT= copy (factors1);
2127 int recombinations= 0;
2128 while (T.length() >= 2*s && s <= thres)
2129 {
2130 while (nosubset == false)
2131 {
2132 if (T.length() == s)
2133 {
2134 delete [] v;
2135 if (recombinations == factors2.length() - 1)
2136 result.append (prod (T));
2137 else
2138 result= Union (result, T);
2139 return result;
2140 }
2141 S= subset (v, s, TT, nosubset);
2142 if (nosubset) break;
2143 buf= prodEval (S, evalPoint, x);
2144 buf /= Lc (buf);
2145 if (find (factors2, buf))
2146 {
2147 recombinations++;
2148 T= Difference (T, S);
2149 result.append (prod (S));
2150 TT= copy (T);
2151 indexUpdate (v, s, T.length(), nosubset);
2152 if (nosubset) break;
2153 }
2154 }
2155 s++;
2156 if (T.length() < 2*s || T.length() == s)
2157 {
2158 if (recombinations == factors2.length() - 1)
2159 result.append (prod (T));
2160 else
2161 result= Union (result, T);
2162 delete [] v;
2163 return result;
2164 }
2165 for (int i= 0; i < T.length(); i++)
2166 v[i]= 0;
2167 nosubset= false;
2168 }
2169
2170 delete [] v;
2171 if (T.length() < 2*s)
2172 {
2173 result= Union (result, T);
2174 return result;
2175 }
2176
2177 return result;
2178}
static CanonicalForm prodEval(const CFList &l, const CanonicalForm &evalPoint, const Variable &v)
template List< Variable > Union(const List< Variable > &, const List< Variable > &)

◆ refineBiFactors()

void refineBiFactors ( const CanonicalForm A,
CFList biFactors,
CFList *const factors,
const CFList evaluation,
int  minFactorsLength 
)

refine a bivariate factorization of A with l factors to one with minFactorsLength if possible

Parameters
[in]Asome poly
[in,out]biFactorslist of bivariate to be refined, returns refined factors
[in]factorslist of bivariate factorizations of A wrt different second variables
[in]evaluationthe evaluation point
[in]minFactorsLengththe minimal number of factors

Definition at line 2334 of file facFqFactorize.cc.

2337{
2338 CFListIterator iter, iter2;
2340 int i;
2341 Variable v;
2342 Variable y= Variable (2);
2343 CFList list;
2344 bool leaveLoop= false;
2345 for (int j= 0; j < A.level() - 2; j++)
2346 {
2347 if (Aeval[j].length() == minFactorsLength)
2348 {
2349 i= A.level();
2350
2351 for (iter= evaluation; iter.hasItem(); iter++, i--)
2352 {
2353 for (iter2= Aeval[j]; iter2.hasItem(); iter2++)
2354 {
2355 if (i == iter2.getItem().level())
2356 {
2358 leaveLoop= true;
2359 break;
2360 }
2361 }
2362 if (leaveLoop)
2363 {
2364 leaveLoop= false;
2365 break;
2366 }
2367 }
2368
2369 v= Variable (i);
2370 list= buildUniFactors (Aeval[j], evalPoint, v);
2371
2372 biFactors= recombination (biFactors, list, 1,
2373 biFactors.length() - list.length() + 1,
2374 evaluation.getLast(), y);
2375 return;
2376 }
2377 }
2378}
CFList int & minFactorsLength
[in,out] minimal length of bivariate factors
Definition: facFactorize.h:33
CFList buildUniFactors(const CFList &biFactors, const CanonicalForm &evalPoint, const Variable &y)
plug in evalPoint for y in a list of polys

◆ sortByUniFactors()

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

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

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

Definition at line 2250 of file facFqFactorize.cc.

2254{
2256 int i;
2257 CFListIterator iter, iter2;
2258 Variable v;
2259 CFList LCs, buf;
2260 CFArray l;
2261 int pos, index, checklength;
2262 bool leaveLoop=false;
2263recurse:
2264 for (int j= 0; j < AevalLength; j++)
2265 {
2266 if (!Aeval[j].isEmpty())
2267 {
2268 i= evaluation.length() + 1;
2269 for (iter= evaluation; iter.hasItem(); iter++, i--)
2270 {
2271 for (iter2= Aeval[j]; iter2.hasItem(); iter2++)
2272 {
2273 if (i == iter2.getItem().level())
2274 {
2276 leaveLoop= true;
2277 break;
2278 }
2279 }
2280 if (leaveLoop)
2281 {
2282 leaveLoop= false;
2283 break;
2284 }
2285 }
2286
2287 v= Variable (i);
2288 if (Aeval[j].length() > uniFactors.length())
2289 Aeval[j]= recombination (Aeval[j], uniFactors, 1,
2290 Aeval[j].length() - uniFactors.length() + 1,
2291 evalPoint, v);
2292
2293 checklength= biFactors.length();
2294 Aeval[j]= checkOneToOne (Aeval[j], uniFactors, biFactors, evalPoint, v);
2295 if (checklength > biFactors.length())
2296 {
2297 uniFactors= buildUniFactors (biFactors, evaluation.getLast(),
2298 Variable (2));
2299 goto recurse;
2300 }
2301
2303 l= CFArray (uniFactors.length());
2304 index= 1;
2305 for (iter= buf; iter.hasItem(); iter++, index++)
2306 {
2307 pos= findItem (uniFactors, iter.getItem());
2308 if (pos)
2309 l[pos-1]= getItem (Aeval[j], index);
2310 }
2311 buf= conv (l);
2312 Aeval [j]= buf;
2313
2315 }
2316 }
2317}
CFList checkOneToOne(const CFList &factors1, const CFList &factors2, CFList &factors3, const CanonicalForm &evalPoint, const Variable &x)
check if univariate factors factors2 of factors3 coincide with univariate factors of factors1 and rec...
CFList conv(const CFArray &A)

◆ TIMING_DEFINE_PRINT()

TIMING_DEFINE_PRINT ( fac_fq_squarefree  ) const &

Factorization over a finite field.

Returns
multiFactorize returns a factorization of F
See also
biFactorize(), extFactorize()

Variable Documentation

◆ info

< [in] sqrfree poly

< [in] info about extension

Definition at line 37 of file facFqFactorize.h.