My Project
Loading...
Searching...
No Matches
Macros | Functions
facFqFactorize.cc File Reference

This file implements functions for factoring a multivariate polynomial over a finite field. More...

#include "config.h"
#include "cf_assert.h"
#include "debug.h"
#include "timing.h"
#include "facFqFactorizeUtil.h"
#include "facFqFactorize.h"
#include "cf_random.h"
#include "facHensel.h"
#include "cf_irred.h"
#include "cf_map_ext.h"
#include "facSparseHensel.h"
#include "facMul.h"
#include "cfUnivarGcd.h"

Go to the source code of this file.

Macros

#define CHAR_THRESHOLD   8
 

Functions

 TIMING_DEFINE_PRINT (fac_fq_bi_factorizer) TIMING_DEFINE_PRINT(fac_fq_hensel_lift) TIMING_DEFINE_PRINT(fac_fq_factor_recombination) TIMING_DEFINE_PRINT(fac_fq_shift_to_zero) TIMING_DEFINE_PRINT(fac_fq_precompute_leadcoeff) TIMING_DEFINE_PRINT(fac_fq_evaluation) TIMING_DEFINE_PRINT(fac_fq_recover_factors) TIMING_DEFINE_PRINT(fac_fq_preprocess_and_content) TIMING_DEFINE_PRINT(fac_fq_bifactor_total) TIMING_DEFINE_PRINT(fac_fq_luckswang) TIMING_DEFINE_PRINT(fac_fq_lcheuristic) TIMING_DEFINE_PRINT(fac_fq_content) TIMING_DEFINE_PRINT(fac_fq_check_mainvar) TIMING_DEFINE_PRINT(fac_fq_compress) static inline CanonicalForm listGCD(const CFList &L)
 
static CanonicalForm myContent (const CanonicalForm &F)
 
static CanonicalForm listGCD (const CFList &L)
 
static CanonicalForm myContent (const CanonicalForm &F, const Variable &x)
 
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...
 
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...
 
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...
 
static int newMainVariableSearch (CanonicalForm &A, CFList &Aeval, CFList &evaluation, const Variable &alpha, const int lev, CanonicalForm &g)
 
CanonicalForm lcmContent (const CanonicalForm &A, CFList &contentAi)
 compute the LCM of the contents of A wrt to each variable occuring in A. 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...
 
void gcdFreeBasis (CFFList &factors1, CFFList &factors2)
 gcd free basis of two lists of factors More...
 
CFList distributeContent (const CFList &L, const CFList *differentSecondVarFactors, int length)
 distribute content More...
 
int testFactors (const CanonicalForm &G, const CFList &uniFactors, const Variable &alpha, CanonicalForm &sqrfPartF, CFList &factors, CFFList *&bufSqrfFactors, CFList &evalSqrfPartF, const CFArray &evalPoint)
 
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 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...
 
static CanonicalForm prodEval (const CFList &l, const CanonicalForm &evalPoint, const Variable &v)
 
void checkHelper (const CanonicalForm &f1, CFList &factors1, CFList &factors2, CFList &l1, CFList &l2)
 
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 recombine if necessary. The recombined factors of factors1 are returned and factors3 is recombined accordingly. 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...
 
void factorizationWRTDifferentSecondVars (const CanonicalForm &A, CFList *&Aeval, const ExtensionInfo &info, int &minFactorsLength, bool &irred)
 
CFList conv (const CFArray &A)
 
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 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...
 
CFList buildUniFactors (const CFList &biFactors, const CanonicalForm &evalPoint, const Variable &y)
 plug in evalPoint for y in a list of polys More...
 
void refineBiFactors (const CanonicalForm &A, CFList &biFactors, CFList *const &Aeval, const CFList &evaluation, int minFactorsLength)
 refine a bivariate factorization of A with l factors to one with minFactorsLength if possible 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 extNonMonicFactorRecombination (const CFList &factors, const CanonicalForm &F, const ExtensionInfo &info)
 
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...
 
CFList extFactorize (const CanonicalForm &F, const ExtensionInfo &info)
 multivariate factorization over an extension of the initial field More...
 
CFList multiFactorize (const CanonicalForm &F, const ExtensionInfo &info)
 

Detailed Description

This file implements functions for factoring a multivariate polynomial over a finite field.

ABSTRACT: "Efficient Multivariate Factorization over Finite Fields" by L. Bernardin & M. Monagon. Precomputation of leading coefficients is described in "Sparse Hensel lifting" by E. Kaltofen

Author
Martin Lee

Definition in file facFqFactorize.cc.

Macro Definition Documentation

◆ CHAR_THRESHOLD

#define CHAR_THRESHOLD   8

Definition at line 748 of file facFqFactorize.cc.

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

◆ checkHelper()

void checkHelper ( const CanonicalForm f1,
CFList factors1,
CFList factors2,
CFList l1,
CFList l2 
)

Definition at line 2021 of file facFqFactorize.cc.

2023{
2024 CanonicalForm g1= f1, g2;
2025 CFListIterator iter1= factors1, iter2= factors2;
2026 for (; iter1.hasItem(); iter1++, iter2++)
2027 {
2028 g2= gcd (g1, iter1.getItem());
2029 if (!g2.inCoeffDomain())
2030 {
2031 l1.append (iter1.getItem());
2032 l2.append (iter2.getItem());
2033 g1 /= g2;
2034 }
2035 }
2036 factors1= Difference (factors1, l1);
2038}
const CFList & factors2
template List< Variable > Difference(const List< Variable > &, const List< Variable > &)
int gcd(int a, int b)
Definition: walkSupport.cc:836

◆ checkOneToOne()

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 recombine if necessary. The recombined factors of factors1 are returned and factors3 is recombined accordingly.

Definition at line 2045 of file facFqFactorize.cc.

2047{
2048 CFList uniFactorsOfFactors1;
2049 CFList result, result2;
2050 CFList bad1= factors2;
2051 CFListIterator iter, iter2, iter3;
2052 CanonicalForm tmp;
2053 int pos;
2054
2055 for (iter= factors1; iter.hasItem(); iter++)
2056 {
2057 tmp= iter.getItem() (evalPoint, x);
2058 tmp /= Lc (tmp);
2059 if ((pos= findItem (factors2, tmp)))
2060 {
2061 result2.append (getItem (factors3, pos));
2062 result.append (iter.getItem());
2063 bad1= Difference (bad1, CFList (tmp));
2064 }
2065 else
2066 uniFactorsOfFactors1.append (tmp);
2067 }
2068
2069 CFList bad2, bad3;
2070 bad2= Difference (factors1, result);
2071 bad3= Difference (factors3, result2);
2072 CFList tmp2, tmp3;
2073 CanonicalForm g1, g2, g3, g4;
2074
2075 while (!uniFactorsOfFactors1.isEmpty())
2076 {
2077 tmp= uniFactorsOfFactors1.getFirst();
2078 checkHelper (tmp, bad1, bad3, tmp2, tmp3);
2079 g1= prod (tmp2);
2080 g2= prod (tmp3);
2081 tmp2= CFList();
2082 tmp3= CFList();
2083 checkHelper (g1, uniFactorsOfFactors1, bad2, tmp2, tmp3);
2084 g3= prod (tmp2);
2085 g4= prod (tmp3);
2086 tmp2= CFList();
2087 tmp3= CFList();
2088 do
2089 {
2090 checkHelper (g3, bad1, bad3, tmp2, tmp3);
2091 g1 *= prod (tmp2);
2092 g2 *= prod (tmp3);
2093 tmp2= CFList();
2094 tmp3= CFList();
2095 checkHelper (g1, uniFactorsOfFactors1, bad2, tmp2, tmp3);
2096 g3 *= prod (tmp2);
2097 g4 *= prod (tmp3);
2098 tmp2= CFList();
2099 tmp3= CFList();
2100 } while (!bad2.isEmpty() && !bad3.isEmpty());
2101 result.append (g4);
2102 result2.append (g2);
2103 }
2104
2105 if (factors3.length() != result2.length())
2106 factors3= result2;
2107 return result;
2108}
Variable x
Definition: cfModGcd.cc:4082
CanonicalForm getItem(const CFList &list, const int &pos)
helper function
Definition: cf_map_ext.cc:53
T getFirst() const
Definition: ftmpl_list.cc:279
int length() const
Definition: ftmpl_list.cc:273
int isEmpty() const
Definition: ftmpl_list.cc:267
void checkHelper(const CanonicalForm &f1, CFList &factors1, CFList &factors2, CFList &l1, CFList &l2)
fq_nmod_poly_t prod
Definition: facHensel.cc:100

◆ conv()

CFList conv ( const CFArray A)

Definition at line 2223 of file facFqFactorize.cc.

2224{
2225 CFList result;
2226 for (int i= A.max(); i >= A.min(); i--)
2227 result.insert (A[i]);
2228 return result;
2229}

◆ 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

◆ 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)

◆ 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}
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 &)
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
void removeFirst()
Definition: ftmpl_list.cc:287
void insert(const T &)
Definition: ftmpl_list.cc:193
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 
)

multivariate factorization over an extension of the initial field

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}

◆ extNonMonicFactorRecombination()

CFList extNonMonicFactorRecombination ( const CFList factors,
const CanonicalForm F,
const ExtensionInfo info 
)

Definition at line 2420 of file facFqFactorize.cc.

2422{
2423 Variable alpha= info.getAlpha();
2424 Variable beta= info.getBeta();
2425 CanonicalForm gamma= info.getGamma();
2426 CanonicalForm delta= info.getDelta();
2427 int k= info.getGFDegree();
2428 CFList source, dest;
2429
2430 int degMipoBeta= 1;
2431 if (!k && beta != Variable(1))
2432 degMipoBeta= degree (getMipo (beta));
2433
2434 CFList T, S;
2435 T= factors;
2436 int s= 1;
2437 CFList result;
2438 CanonicalForm quot, buf= F;
2439
2442 int * v= new int [T.length()];
2443 for (int i= 0; i < T.length(); i++)
2444 v[i]= 0;
2445 bool noSubset= false;
2446 CFArray TT;
2447 TT= copy (factors);
2448 bool recombination= false;
2449 bool trueFactor= false;
2450 while (T.length() >= 2*s)
2451 {
2452 while (noSubset == false)
2453 {
2454 if (T.length() == s)
2455 {
2456 delete [] v;
2457 if (recombination)
2458 {
2459 g= prod (T);
2460 T.removeFirst();
2461 g /= myContent (g);
2462 g /= Lc (g);
2463 appendTestMapDown (result, g, info, source, dest);
2464 return result;
2465 }
2466 else
2467 return CFList (buf/myContent(buf));
2468 }
2469
2470 S= subset (v, s, TT, noSubset);
2471 if (noSubset) break;
2472
2473 g= prod (S);
2474 g /= myContent (g);
2475 if (fdivides (g, buf, quot))
2476 {
2477 buf2= g;
2478 buf2 /= Lc (buf2);
2479 if (!k && beta.level() == 1)
2480 {
2481 if (degree (buf2, alpha) < degMipoBeta)
2482 {
2483 appendTestMapDown (result, buf2, info, source, dest);
2484 buf= quot;
2485 recombination= true;
2486 trueFactor= true;
2487 }
2488 }
2489 else
2490 {
2491 if (!isInExtension (buf2, gamma, k, delta, source, dest))
2492 {
2493 appendTestMapDown (result, buf2, info, source, dest);
2494 buf= quot;
2495 recombination= true;
2496 trueFactor= true;
2497 }
2498 }
2499 if (trueFactor)
2500 {
2501 T= Difference (T, S);
2502
2503 if (T.length() < 2*s || T.length() == s)
2504 {
2505 delete [] v;
2506 buf /= myContent (buf);
2507 buf /= Lc (buf);
2508 appendTestMapDown (result, buf, info, source, dest);
2509 return result;
2510 }
2511 trueFactor= false;
2512 TT= copy (T);
2513 indexUpdate (v, s, T.length(), noSubset);
2514 if (noSubset) break;
2515 }
2516 }
2517 }
2518 s++;
2519 if (T.length() < 2*s || T.length() == s)
2520 {
2521 delete [] v;
2522 buf /= myContent (buf);
2523 buf /= Lc (buf);
2524 appendTestMapDown (result, buf, info, source, dest);
2525 return result;
2526 }
2527 for (int i= 0; i < T.length(); i++)
2528 v[i]= 0;
2529 noSubset= false;
2530 }
2531 if (T.length() < 2*s)
2532 {
2533 buf= F/myContent (F);
2534 buf /= Lc (buf);
2535 appendMapDown (result, buf, info, source, dest);
2536 }
2537
2538 delete [] v;
2539 return result;
2540}

◆ factorizationWRTDifferentSecondVars()

void factorizationWRTDifferentSecondVars ( const CanonicalForm A,
CFList *&  Aeval,
const ExtensionInfo info,
int &  minFactorsLength,
bool &  irred 
)

Definition at line 2183 of file facFqFactorize.cc.

2186{
2187 Variable x= Variable (1);
2189 irred= false;
2190 CFList factors;
2191 Variable v;
2192 for (int j= 0; j < A.level() - 2; j++)
2193 {
2194 if (!Aeval[j].isEmpty())
2195 {
2196 v= Variable (Aeval[j].getFirst().level());
2198 factors= GFBiSqrfFactorize (Aeval[j].getFirst());
2199 else if (info.getAlpha().level() == 1)
2200 factors= FpBiSqrfFactorize (Aeval[j].getFirst());
2201 else
2202 factors= FqBiSqrfFactorize (Aeval[j].getFirst(), info.getAlpha());
2203
2204 factors.removeFirst();
2205 if (minFactorsLength == 0)
2206 minFactorsLength= factors.length();
2207 else
2209
2210 if (factors.length() == 1)
2211 {
2212 irred= true;
2213 return;
2214 }
2215 sortList (factors, x);
2216 Aeval [j]= factors;
2217 }
2218 }
2219}
CFList int & minFactorsLength
[in,out] minimal length of bivariate factors
Definition: facFactorize.h:33
CFList int bool & irred
[in,out] Is A irreducible?
Definition: facFactorize.h:34
CFList FqBiSqrfFactorize(const CanonicalForm &G, const Variable &alpha)
factorize a squarefree bivariate polynomial over .
Definition: facFqBivar.h:156
CFList FpBiSqrfFactorize(const CanonicalForm &G)
factorize a squarefree bivariate polynomial over .
Definition: facFqBivar.h:141
CFList GFBiSqrfFactorize(const CanonicalForm &G)
factorize a squarefree bivariate polynomial over GF
Definition: facFqBivar.h:172
void sortList(CFList &list, const Variable &x)
sort a list of polynomials by their degree in x.
Definition: facHensel.cc:449

◆ 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

◆ 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

◆ 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}

◆ 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

◆ 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}
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}

◆ 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

◆ 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}

◆ listGCD()

static CanonicalForm listGCD ( const CFList L)
inlinestatic

Definition at line 74 of file facFqFactorize.cc.

75{
76 if (L.length() == 0)
77 return 0;
78 if (L.length() == 1)
79 return L.getFirst();
80 if (L.length() == 2)
81 return gcd (L.getFirst(), L.getLast());
82 else
83 {
84 CFList lHi, lLo;
85 CanonicalForm resultHi, resultLo;
86 int length= L.length()/2;
87 int j= 0;
88 for (CFListIterator i= L; j < length; i++, j++)
89 lHi.append (i.getItem());
90 lLo= Difference (L, lHi);
91 resultHi= listGCD (lHi);
92 resultLo= listGCD (lLo);
93 if (resultHi.isOne() || resultLo.isOne())
94 return 1;
95 return gcd (resultHi, resultLo);
96 }
97}
static CanonicalForm listGCD(const CFList &L)

◆ multiFactorize()

CFList multiFactorize ( const CanonicalForm F,
const ExtensionInfo info 
)

Definition at line 2928 of file facFqFactorize.cc.

2929{
2930 if (F.inCoeffDomain())
2931 return CFList (F);
2932
2933 TIMING_START (fac_fq_preprocess_and_content);
2934 // compress and find main Variable
2935 CFMap N;
2936 TIMING_START (fac_fq_compress)
2938 TIMING_END_AND_PRINT (fac_fq_compress, "time to compress poly over Fq: ")
2939
2940 A /= Lc (A); // make monic
2941
2942 Variable alpha= info.getAlpha();
2943 Variable beta= info.getBeta();
2944 CanonicalForm gamma= info.getGamma();
2945 CanonicalForm delta= info.getDelta();
2946 bool extension= info.isInExtension();
2947 bool GF= (CFFactory::gettype() == GaloisFieldDomain);
2948 //univariate case
2949 if (F.isUnivariate())
2950 {
2951 if (extension == false)
2952 return uniFactorizer (F, alpha, GF);
2953 else
2954 {
2955 CFList source, dest;
2956 A= mapDown (F, info, source, dest);
2957 return uniFactorizer (A, beta, GF);
2958 }
2959 }
2960
2961 //bivariate case
2962 if (A.level() == 2)
2963 {
2965 if (buf.getFirst().inCoeffDomain())
2966 buf.removeFirst();
2967 return buf;
2968 }
2969
2970 Variable x= Variable (1);
2971 Variable y= Variable (2);
2972
2973 // remove content
2974 TIMING_START (fac_fq_content);
2975 CFList contentAi;
2976 CanonicalForm lcmCont= lcmContent (A, contentAi);
2977 A /= lcmCont;
2978 TIMING_END_AND_PRINT (fac_fq_content, "time to extract content over Fq: ");
2979
2980 // trivial after content removal
2981 CFList contentAFactors;
2982 if (A.inCoeffDomain())
2983 {
2984 for (CFListIterator i= contentAi; i.hasItem(); i++)
2985 {
2986 if (i.getItem().inCoeffDomain())
2987 continue;
2988 else
2989 {
2990 lcmCont /= i.getItem();
2991 contentAFactors=
2992 Union (multiFactorize (lcmCont, info),
2993 multiFactorize (i.getItem(), info));
2994 break;
2995 }
2996 }
2997 decompress (contentAFactors, N);
2998 if (!extension)
2999 normalize (contentAFactors);
3000 return contentAFactors;
3001 }
3002
3003 // factorize content
3004 TIMING_START (fac_fq_content);
3005 contentAFactors= multiFactorize (lcmCont, info);
3006 TIMING_END_AND_PRINT (fac_fq_content, "time to factor content over Fq: ");
3007
3008 // univariate after content removal
3009 CFList factors;
3010 if (A.isUnivariate ())
3011 {
3012 factors= uniFactorizer (A, alpha, GF);
3013 append (factors, contentAFactors);
3014 decompress (factors, N);
3015 return factors;
3016 }
3017
3018 // check main variable
3019 TIMING_START (fac_fq_check_mainvar);
3020 int swapLevel= 0;
3021 CanonicalForm derivZ;
3022 CanonicalForm gcdDerivZ;
3023 CanonicalForm bufA= A;
3024 Variable z;
3025 for (int i= 1; i <= A.level(); i++)
3026 {
3027 z= Variable (i);
3028 derivZ= deriv (bufA, z);
3029 if (derivZ.isZero())
3030 {
3031 if (i == 1)
3032 swapLevel= 1;
3033 else
3034 continue;
3035 }
3036 else
3037 {
3038 gcdDerivZ= gcd (bufA, derivZ);
3039 if (degree (gcdDerivZ) > 0 && !derivZ.isZero())
3040 {
3041 CanonicalForm g= bufA/gcdDerivZ;
3042 CFList factorsG=
3044 multiFactorize (gcdDerivZ, info));
3045 appendSwapDecompress (factorsG, contentAFactors, N, swapLevel, x);
3046 if (!extension)
3047 normalize (factorsG);
3048 return factorsG;
3049 }
3050 else
3051 {
3052 if (swapLevel == 1)
3053 {
3054 swapLevel= i;
3055 bufA= swapvar (A, x, z);
3056 }
3057 A= bufA;
3058 break;
3059 }
3060 }
3061 }
3062 TIMING_END_AND_PRINT (fac_fq_check_mainvar,
3063 "time to check main var over Fq: ");
3064 TIMING_END_AND_PRINT (fac_fq_preprocess_and_content,
3065 "time to preprocess poly and extract content over Fq: ");
3066
3067 CFList Aeval, list, evaluation, bufEvaluation, bufAeval;
3068 bool fail= false;
3069 int swapLevel2= 0;
3070 //int level;
3071 int factorNums= 3;
3072 CFList biFactors, bufBiFactors;
3073 CanonicalForm evalPoly;
3074 int lift, bufLift, lengthAeval2= A.level()-2;
3075 double logarithm= (double) ilog2 (totaldegree (A));
3076 logarithm /= log2exp;
3077 logarithm= ceil (logarithm);
3078 if (factorNums < (int) logarithm)
3079 factorNums= (int) logarithm;
3080 CFList* bufAeval2= new CFList [lengthAeval2];
3081 CFList* Aeval2= new CFList [lengthAeval2];
3082 int counter;
3083 int differentSecondVar= 0;
3084 // several bivariate factorizations
3085 TIMING_START (fac_fq_bifactor_total);
3086 for (int i= 0; i < factorNums; i++)
3087 {
3088 counter= 0;
3089 bufA= A;
3090 bufAeval= CFList();
3091 TIMING_START (fac_fq_evaluation);
3092 bufEvaluation= evalPoints (bufA, bufAeval, alpha, list, GF, fail);
3093 TIMING_END_AND_PRINT (fac_fq_evaluation,
3094 "time to find evaluation point over Fq: ");
3095 evalPoly= 0;
3096
3097 if (fail && (i == 0))
3098 {
3099 /*if (!swapLevel) //uncomment to reenable search for new main variable
3100 level= 2;
3101 else
3102 level= swapLevel + 1;*/
3103
3104 //CanonicalForm g;
3105 //swapLevel2= newMainVariableSearch (A, Aeval, evaluation, alpha, level, g);
3106
3107 /*if (!swapLevel2) // need to pass to an extension
3108 {*/
3109 factors= extFactorize (A, info);
3110 appendSwapDecompress (factors, contentAFactors, N, swapLevel, x);
3111 normalize (factors);
3112 delete [] bufAeval2;
3113 delete [] Aeval2;
3114 return factors;
3115 /*}
3116 else
3117 {
3118 if (swapLevel2 == -1)
3119 {
3120 CFList factorsG=
3121 Union (multiFactorize (g, info),
3122 multiFactorize (A/g, info));
3123 appendSwapDecompress (factorsG, contentAFactors, N, swapLevel, x);
3124 if (!extension)
3125 normalize (factorsG);
3126 delete [] bufAeval2;
3127 delete [] Aeval2;
3128 return factorsG;
3129 }
3130 fail= false;
3131 bufAeval= Aeval;
3132 bufA= A;
3133 bufEvaluation= evaluation;
3134 }*/ //end uncomment
3135 }
3136 else if (fail && (i > 0))
3137 break;
3138
3139 TIMING_START (fac_fq_evaluation);
3140 evaluationWRTDifferentSecondVars (bufAeval2, bufEvaluation, A);
3141 TIMING_END_AND_PRINT (fac_fq_evaluation,
3142 "time for evaluation wrt diff second vars over Fq: ");
3143
3144 for (int j= 0; j < lengthAeval2; j++)
3145 {
3146 if (!bufAeval2[j].isEmpty())
3147 counter++;
3148 }
3149
3150 bufLift= degree (A, y) + 1 + degree (LC(A, x), y);
3151
3152 TIMING_START (fac_fq_bi_factorizer);
3153 if (!GF && alpha.level() == 1)
3154 bufBiFactors= FpBiSqrfFactorize (bufAeval.getFirst());
3155 else if (GF)
3156 bufBiFactors= GFBiSqrfFactorize (bufAeval.getFirst());
3157 else
3158 bufBiFactors= FqBiSqrfFactorize (bufAeval.getFirst(), alpha);
3159 TIMING_END_AND_PRINT (fac_fq_bi_factorizer,
3160 "time for bivariate factorization: ");
3161 bufBiFactors.removeFirst();
3162
3163 if (bufBiFactors.length() == 1)
3164 {
3165 if (extension)
3166 {
3167 CFList source, dest;
3168 A= mapDown (A, info, source, dest);
3169 }
3170 factors.append (A);
3171 appendSwapDecompress (factors, contentAFactors, N, swapLevel,
3172 swapLevel2, x);
3173 if (!extension)
3174 normalize (factors);
3175 delete [] bufAeval2;
3176 delete [] Aeval2;
3177 return factors;
3178 }
3179
3180 if (i == 0)
3181 {
3182 Aeval= bufAeval;
3183 evaluation= bufEvaluation;
3184 biFactors= bufBiFactors;
3185 lift= bufLift;
3186 for (int j= 0; j < lengthAeval2; j++)
3187 Aeval2 [j]= bufAeval2 [j];
3188 differentSecondVar= counter;
3189 }
3190 else
3191 {
3192 if (bufBiFactors.length() < biFactors.length() ||
3193 ((bufLift < lift) && (bufBiFactors.length() == biFactors.length())) ||
3194 counter > differentSecondVar)
3195 {
3196 Aeval= bufAeval;
3197 evaluation= bufEvaluation;
3198 biFactors= bufBiFactors;
3199 lift= bufLift;
3200 for (int j= 0; j < lengthAeval2; j++)
3201 Aeval2 [j]= bufAeval2 [j];
3202 differentSecondVar= counter;
3203 }
3204 }
3205 int k= 0;
3206 for (CFListIterator j= bufEvaluation; j.hasItem(); j++, k++)
3207 evalPoly += j.getItem()*power (x, k);
3208 list.append (evalPoly);
3209 }
3210
3211 delete [] bufAeval2;
3212
3213 sortList (biFactors, x);
3214
3215 int minFactorsLength;
3216 bool irred= false;
3217 TIMING_START (fac_fq_bi_factorizer);
3219 TIMING_END_AND_PRINT (fac_fq_bi_factorizer,
3220 "time for bivariate factorization wrt diff second vars over Fq: ");
3221
3222 TIMING_END_AND_PRINT (fac_fq_bifactor_total,
3223 "total time for eval and bivar factors over Fq: ");
3224 if (irred)
3225 {
3226 if (extension)
3227 {
3228 CFList source, dest;
3229 A= mapDown (A, info, source, dest);
3230 }
3231 factors.append (A);
3232 appendSwapDecompress (factors, contentAFactors, N, swapLevel,
3233 swapLevel2, x);
3234 if (!extension)
3235 normalize (factors);
3236 delete [] Aeval2;
3237 return factors;
3238 }
3239
3240 if (minFactorsLength == 0)
3241 minFactorsLength= biFactors.length();
3242 else if (biFactors.length() > minFactorsLength)
3243 refineBiFactors (A, biFactors, Aeval2, evaluation, minFactorsLength);
3245
3246 CFList uniFactors= buildUniFactors (biFactors, evaluation.getLast(), y);
3247
3248 sortByUniFactors (Aeval2, lengthAeval2, uniFactors, biFactors, evaluation);
3249
3251
3252 if (minFactorsLength == 1)
3253 {
3254 if (extension)
3255 {
3256 CFList source, dest;
3257 A= mapDown (A, info, source, dest);
3258 }
3259 factors.append (A);
3260 appendSwapDecompress (factors, contentAFactors, N, swapLevel,
3261 swapLevel2, x);
3262 if (!extension)
3263 normalize (factors);
3264 delete [] Aeval2;
3265 return factors;
3266 }
3267
3268 if (differentSecondVar == lengthAeval2)
3269 {
3270 bool zeroOccured= false;
3272 {
3273 if (iter.getItem().isZero())
3274 {
3275 zeroOccured= true;
3276 break;
3277 }
3278 }
3279 if (!zeroOccured)
3280 {
3281 factors= sparseHeuristic (A, biFactors, Aeval2, evaluation,
3283 if (factors.length() == biFactors.length())
3284 {
3285 if (extension)
3286 factors= extNonMonicFactorRecombination (factors, A, info);
3287
3288 appendSwapDecompress (factors, contentAFactors, N, swapLevel,
3289 swapLevel2, x);
3290 if (!extension)
3291 normalize (factors);
3292 delete [] Aeval2;
3293 return factors;
3294 }
3295 else
3296 factors= CFList();
3297 //TODO case where factors.length() > 0
3298 }
3299 }
3300
3301 CFList * oldAeval= new CFList [lengthAeval2]; //TODO use bufAeval2 for this
3302 for (int i= 0; i < lengthAeval2; i++)
3303 oldAeval[i]= Aeval2[i];
3304
3305 getLeadingCoeffs (A, Aeval2);
3306
3307 CFList biFactorsLCs;
3308 for (CFListIterator i= biFactors; i.hasItem(); i++)
3309 biFactorsLCs.append (LC (i.getItem(), 1));
3310
3311 Variable v;
3312 TIMING_START (fac_fq_precompute_leadcoeff);
3313 CFList leadingCoeffs= precomputeLeadingCoeff (LC (A, 1), biFactorsLCs, alpha,
3314 evaluation, Aeval2, lengthAeval2, v);
3315
3316 if (v.level() != 1)
3317 changeSecondVariable (A, biFactors, evaluation, oldAeval, lengthAeval2,
3318 uniFactors, v);
3319
3320 CanonicalForm oldA= A;
3321 CFList oldBiFactors= biFactors;
3322
3323 CanonicalForm LCmultiplier= leadingCoeffs.getFirst();
3324 bool LCmultiplierIsConst= LCmultiplier.inCoeffDomain();
3325 leadingCoeffs.removeFirst();
3326
3327 if (!LCmultiplierIsConst)
3328 distributeLCmultiplier (A, leadingCoeffs, biFactors, evaluation, LCmultiplier);
3329
3330 //prepare leading coefficients
3331 CFList* leadingCoeffs2= new CFList [lengthAeval2];
3332 prepareLeadingCoeffs (leadingCoeffs2, A, Aeval, A.level(), leadingCoeffs,
3333 biFactors, evaluation);
3334
3336 CFList bufLeadingCoeffs2= leadingCoeffs2[lengthAeval2-1];
3337 bufBiFactors= biFactors;
3338 bufA= A;
3339 CanonicalForm testVars, bufLCmultiplier= LCmultiplier;
3340 if (!LCmultiplierIsConst)
3341 {
3342 testVars= Variable (2);
3343 for (int i= 0; i < lengthAeval2; i++)
3344 {
3345 if (!oldAeval[i].isEmpty())
3346 testVars *= oldAeval[i].getFirst().mvar();
3347 }
3348 }
3349 TIMING_END_AND_PRINT(fac_fq_precompute_leadcoeff,
3350 "time to precompute LC over Fq: ");
3351
3352 TIMING_START (fac_fq_luckswang);
3353 CFList bufFactors= CFList();
3354 bool LCheuristic= false;
3355 if (LucksWangSparseHeuristic (A, biFactors, 2, leadingCoeffs2[lengthAeval2-1],
3356 factors))
3357 {
3358 int check= biFactors.length();
3359 int * index= new int [factors.length()];
3360 CFList oldFactors= factors;
3361 factors= recoverFactors (A, factors, index);
3362
3363 if (check == factors.length())
3364 {
3365 if (extension)
3366 factors= extNonMonicFactorRecombination (factors, bufA, info);
3367
3368 if (v.level() != 1)
3369 {
3370 for (iter= factors; iter.hasItem(); iter++)
3371 iter.getItem()= swapvar (iter.getItem(), v, y);
3372 }
3373
3374 appendSwapDecompress (factors, contentAFactors, N, swapLevel,
3375 swapLevel2, x);
3376 if (!extension)
3377 normalize (factors);
3378 delete [] index;
3379 delete [] Aeval2;
3380 TIMING_END_AND_PRINT (fac_fq_luckswang,
3381 "time for successful LucksWang over Fq: ");
3382 return factors;
3383 }
3384 else if (factors.length() > 0)
3385 {
3386 int oneCount= 0;
3387 CFList l;
3388 for (int i= 0; i < check; i++)
3389 {
3390 if (index[i] == 1)
3391 {
3392 iter=biFactors;
3393 for (int j=1; j <= i-oneCount; j++)
3394 iter++;
3395 iter.remove (1);
3396 for (int j= 0; j < lengthAeval2; j++)
3397 {
3398 l= leadingCoeffs2[j];
3399 iter= l;
3400 for (int k=1; k <= i-oneCount; k++)
3401 iter++;
3402 iter.remove (1);
3403 leadingCoeffs2[j]=l;
3404 }
3405 oneCount++;
3406 }
3407 }
3408 bufFactors= factors;
3409 factors= CFList();
3410 }
3411 else if (!LCmultiplierIsConst && factors.length() == 0)
3412 {
3413 LCheuristic= true;
3414 factors= oldFactors;
3415 CFList contents, LCs;
3416 bool foundTrueMultiplier= false;
3417 LCHeuristic2 (LCmultiplier, factors, leadingCoeffs2[lengthAeval2-1],
3418 contents, LCs, foundTrueMultiplier);
3419 if (foundTrueMultiplier)
3420 {
3421 A= oldA;
3422 leadingCoeffs= leadingCoeffs2[lengthAeval2-1];
3423 for (int i= lengthAeval2-1; i > -1; i--)
3424 leadingCoeffs2[i]= CFList();
3425 prepareLeadingCoeffs (leadingCoeffs2, A, Aeval, A.level(),
3426 leadingCoeffs, biFactors, evaluation);
3427 }
3428 else
3429 {
3430 bool foundMultiplier= false;
3431 LCHeuristic3 (LCmultiplier, factors, oldBiFactors, contents, oldAeval,
3432 A, leadingCoeffs2, lengthAeval2, foundMultiplier);
3433
3434 // coming from above: divide out more LCmultiplier if possible
3435 if (foundMultiplier)
3436 {
3437 foundMultiplier= false;
3438 LCHeuristic4 (oldBiFactors, oldAeval, contents, factors, testVars,
3439 lengthAeval2, leadingCoeffs2, A, LCmultiplier,
3440 foundMultiplier);
3441 }
3442 else
3443 {
3444 LCHeuristicCheck (LCs, contents, A, oldA,
3445 leadingCoeffs2[lengthAeval2-1], foundMultiplier);
3446 if (!foundMultiplier && fdivides (getVars (LCmultiplier), testVars))
3447 {
3448 LCHeuristic (A, LCmultiplier, biFactors, leadingCoeffs2, oldAeval,
3449 lengthAeval2, evaluation, oldBiFactors);
3450 }
3451 }
3452
3453 // patch everything together again
3454 leadingCoeffs= leadingCoeffs2[lengthAeval2-1];
3455 for (int i= lengthAeval2-1; i > -1; i--)
3456 leadingCoeffs2[i]= CFList();
3457 prepareLeadingCoeffs (leadingCoeffs2, A, Aeval, A.level(),leadingCoeffs,
3458 biFactors, evaluation);
3459 }
3460 factors= CFList();
3461 if (!fdivides (LC (oldA,1),prod (leadingCoeffs2[lengthAeval2-1])))
3462 {
3463 LCheuristic= false;
3464 A= bufA;
3465 biFactors= bufBiFactors;
3466 leadingCoeffs2[lengthAeval2-1]= bufLeadingCoeffs2;
3467 LCmultiplier= bufLCmultiplier;
3468 }
3469 }
3470 else
3471 factors= CFList();
3472 delete [] index;
3473 }
3474 TIMING_END_AND_PRINT (fac_fq_luckswang, "time for LucksWang over Fq: ");
3475
3476 TIMING_START (fac_fq_lcheuristic);
3477 if (!LCheuristic && !LCmultiplierIsConst && bufFactors.isEmpty()
3478 && fdivides (getVars (LCmultiplier), testVars))
3479 {
3480 LCheuristic= true;
3481 LCHeuristic (A, LCmultiplier, biFactors, leadingCoeffs2, oldAeval,
3482 lengthAeval2, evaluation, oldBiFactors);
3483
3484 leadingCoeffs= leadingCoeffs2[lengthAeval2-1];
3485 for (int i= lengthAeval2-1; i > -1; i--)
3486 leadingCoeffs2[i]= CFList();
3487 prepareLeadingCoeffs (leadingCoeffs2, A, Aeval, A.level(),leadingCoeffs,
3488 biFactors, evaluation);
3489
3490 if (!fdivides (LC (oldA,1),prod (leadingCoeffs2[lengthAeval2-1])))
3491 {
3492 LCheuristic= false;
3493 A= bufA;
3494 biFactors= bufBiFactors;
3495 leadingCoeffs2[lengthAeval2-1]= bufLeadingCoeffs2;
3496 LCmultiplier= bufLCmultiplier;
3497 }
3498 }
3499 TIMING_END_AND_PRINT (fac_fq_lcheuristic, "time for Lc heuristic over Fq: ");
3500
3501tryAgainWithoutHeu:
3502 TIMING_START (fac_fq_shift_to_zero);
3504
3505 for (iter= biFactors; iter.hasItem(); iter++)
3506 iter.getItem()= iter.getItem () (y + evaluation.getLast(), y);
3507
3508 for (int i= 0; i < lengthAeval2-1; i++)
3509 leadingCoeffs2[i]= CFList();
3510 for (iter= leadingCoeffs2[lengthAeval2-1]; iter.hasItem(); iter++)
3511 {
3513 for (int i= A.level() - 4; i > -1; i--)
3514 {
3515 if (i + 1 == lengthAeval2-1)
3516 leadingCoeffs2[i].append (iter.getItem() (0, i + 4));
3517 else
3518 leadingCoeffs2[i].append (leadingCoeffs2[i+1].getLast() (0, i + 4));
3519 }
3520 }
3521 TIMING_END_AND_PRINT (fac_fq_shift_to_zero,
3522 "time to shift evaluation point to zero: ");
3523
3524 CFArray Pi;
3525 CFList diophant;
3526 int* liftBounds= new int [A.level() - 1];
3527 int liftBoundsLength= A.level() - 1;
3528 for (int i= 0; i < liftBoundsLength; i++)
3529 liftBounds [i]= degree (A, i + 2) + 1;
3530
3532 bool noOneToOne= false;
3533 TIMING_START (fac_fq_hensel_lift);
3534 factors= nonMonicHenselLift (Aeval, biFactors, leadingCoeffs2, diophant,
3535 Pi, liftBounds, liftBoundsLength, noOneToOne);
3536 TIMING_END_AND_PRINT (fac_fq_hensel_lift,
3537 "time for non monic hensel lifting over Fq: ");
3538
3539 if (!noOneToOne)
3540 {
3541 int check= factors.length();
3542 A= oldA;
3543 TIMING_START (fac_fq_recover_factors);
3544 factors= recoverFactors (A, factors, evaluation);
3545 TIMING_END_AND_PRINT (fac_fq_recover_factors,
3546 "time to recover factors over Fq: ");
3547 if (check != factors.length())
3548 noOneToOne= true;
3549 else
3550 factors= Union (factors, bufFactors);
3551
3552 if (extension && !noOneToOne)
3553 factors= extNonMonicFactorRecombination (factors, A, info);
3554 }
3555 if (noOneToOne)
3556 {
3557 if (!LCmultiplierIsConst && LCheuristic)
3558 {
3559 A= bufA;
3560 biFactors= bufBiFactors;
3561 leadingCoeffs2[lengthAeval2-1]= bufLeadingCoeffs2;
3562 delete [] liftBounds;
3563 LCheuristic= false;
3564 goto tryAgainWithoutHeu;
3565 //something probably went wrong in the heuristic
3566 }
3567
3568 A= shift2Zero (oldA, Aeval, evaluation);
3569 biFactors= oldBiFactors;
3570 for (iter= biFactors; iter.hasItem(); iter++)
3571 iter.getItem()= iter.getItem () (y + evaluation.getLast(), y);
3572 CanonicalForm LCA= LC (Aeval.getFirst(), 1);
3573 CanonicalForm yToLift= power (y, lift);
3574 CFListIterator i= biFactors;
3575 lift= degree (i.getItem(), 2) + degree (LC (i.getItem(), 1)) + 1;
3576 i++;
3577
3578 for (; i.hasItem(); i++)
3579 lift= tmax (lift,
3580 degree (i.getItem(), 2) + degree (LC (i.getItem(), 1)) + 1);
3581
3582 lift= tmax (degree (Aeval.getFirst() , 2) + 1, lift);
3583
3584 i= biFactors;
3585 yToLift= power (y, lift);
3586 CanonicalForm dummy;
3587 for (; i.hasItem(); i++)
3588 {
3589 LCA= LC (i.getItem(), 1);
3590 extgcd (LCA, yToLift, LCA, dummy);
3591 i.getItem()= mod (i.getItem()*LCA, yToLift);
3592 }
3593
3594 liftBoundsLength= F.level() - 1;
3595 liftBounds= liftingBounds (A, lift);
3596
3597 CFList MOD;
3598 bool earlySuccess;
3599 CFList earlyFactors, liftedFactors;
3600 TIMING_START (fac_fq_hensel_lift);
3601 liftedFactors= henselLiftAndEarly
3602 (A, MOD, liftBounds, earlySuccess, earlyFactors,
3603 Aeval, biFactors, evaluation, info);
3604 TIMING_END_AND_PRINT (fac_fq_hensel_lift,
3605 "time for hensel lifting over Fq: ");
3606
3607 if (!extension)
3608 {
3609 TIMING_START (fac_fq_factor_recombination);
3610 factors= factorRecombination (A, liftedFactors, MOD);
3611 TIMING_END_AND_PRINT (fac_fq_factor_recombination,
3612 "time for factor recombination: ");
3613 }
3614 else
3615 {
3616 TIMING_START (fac_fq_factor_recombination);
3617 factors= extFactorRecombination (liftedFactors, A, MOD, info, evaluation);
3618 TIMING_END_AND_PRINT (fac_fq_factor_recombination,
3619 "time for factor recombination: ");
3620 }
3621
3622 if (earlySuccess)
3623 factors= Union (factors, earlyFactors);
3624 if (!extension)
3625 {
3626 for (CFListIterator i= factors; i.hasItem(); i++)
3627 {
3628 int kk= Aeval.getLast().level();
3629 for (CFListIterator j= evaluation; j.hasItem(); j++, kk--)
3630 {
3631 if (i.getItem().level() < kk)
3632 continue;
3633 i.getItem()= i.getItem() (Variable (kk) - j.getItem(), kk);
3634 }
3635 }
3636 }
3637 }
3638
3639 if (v.level() != 1)
3640 {
3641 for (CFListIterator iter= factors; iter.hasItem(); iter++)
3642 iter.getItem()= swapvar (iter.getItem(), v, y);
3643 }
3644
3645 swap (factors, swapLevel, swapLevel2, x);
3646 append (factors, contentAFactors);
3647 decompress (factors, N);
3648 if (!extension)
3649 normalize (factors);
3650
3651 delete[] liftBounds;
3652
3653 return factors;
3654}
#define swap(_i, _j)
int ilog2(const CanonicalForm &a)
int totaldegree(const CanonicalForm &f)
int totaldegree ( const CanonicalForm & f )
Definition: cf_ops.cc:523
const CanonicalForm CFMap CFMap & N
Definition: cfEzgcd.cc:56
static const double log2exp
Definition: cfEzgcd.cc:45
CanonicalForm decompress(const CanonicalForm &F, const mpz_t *inverseM, const mpz_t *A)
decompress a bivariate poly
CanonicalForm extgcd(const CanonicalForm &f, const CanonicalForm &g, CanonicalForm &a, CanonicalForm &b)
CanonicalForm extgcd ( const CanonicalForm & f, const CanonicalForm & g, CanonicalForm & a,...
Definition: cfUnivarGcd.cc:174
class CFMap
Definition: cf_map.h:85
CF_NO_INLINE bool isZero() const
void remove(int moveright)
Definition: ftmpl_list.cc:526
CFFList append(const CFFList &Inputlist, const CFFactor &TheFactor)
void appendSwapDecompress(CFList &factors1, const CFList &factors2, const CFList &factors3, const bool swap1, const bool swap2, const CFMap &N)
first swap Variables in factors1 if necessary, then append factors2 and factors3 on factors1 and fina...
else L getLast()(0
CFList uniFactorizer(const CanonicalForm &A, const Variable &alpha, const bool &GF)
Univariate factorization of squarefree monic polys over finite fields via NTL. If the characteristic ...
Definition: facFqBivar.cc:160
CFList biSqrfFactorizeHelper(const CanonicalForm &G, const ExtensionInfo &info)
Definition: facFqBivar.h: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
int * liftingBounds(const CanonicalForm &A, const int &bivarLiftBound)
compute lifting bounds
CFList factorRecombination(const CanonicalForm &F, const CFList &factors, const CFList &M)
Naive factor recombination for multivariate factorization. No precomputed is used to exclude combinat...
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,...
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,...
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 co...
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 secon...
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 ...
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....
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 conten...
CanonicalForm myCompress(const CanonicalForm &F, CFMap &N)
compress a polynomial s.t. and no gaps between the variables occur
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
void factorizationWRTDifferentSecondVars(const CanonicalForm &A, CFList *&Aeval, const ExtensionInfo &info, int &minFactorsLength, bool &irred)
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 uniFac...
CanonicalForm lcmContent(const CanonicalForm &A, CFList &contentAi)
compute the LCM of the contents of A wrt to each variable occuring in A.
void getLeadingCoeffs(const CanonicalForm &A, CFList *&Aeval)
extract leading coefficients wrt Variable(1) from bivariate factors obtained from factorizations of A...
CFList extFactorize(const CanonicalForm &F, const ExtensionInfo &info)
multivariate factorization over an extension of the initial field
CFList extNonMonicFactorRecombination(const CFList &factors, const CanonicalForm &F, const ExtensionInfo &info)
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 ...
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
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 a...
void refineBiFactors(const CanonicalForm &A, CFList &biFactors, CFList *const &Aeval, const CFList &evaluation, int minFactorsLength)
refine a bivariate factorization of A with l factors to one with minFactorsLength if possible
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....
CFList buildUniFactors(const CFList &biFactors, const CanonicalForm &evalPoint, const Variable &y)
plug in evalPoint for y in a list of polys
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 t...
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
int LucksWangSparseHeuristic(const CanonicalForm &F, const CFList &factors, int level, const CFList &leadingCoeffs, CFList &result)
sparse heuristic lifting by Wang and Lucks
CFList sparseHeuristic(const CanonicalForm &A, const CFList &biFactors, CFList *&moreBiFactors, const CFList &evaluation, int minFactorsLength)
sparse heuristic which patches together bivariate factors of A wrt. different second variables by the...
if(!FE_OPT_NO_SHELL_FLAG)(void) system(sys)
template List< Variable > Union(const List< Variable > &, const List< Variable > &)
VAR int check
Definition: libparse.cc:1106
ideal lift(const ideal J, const ring r, const ideal inI, const ring s)
Definition: lift.cc:26
const signed long ceil(const ampf< Precision > &x)
Definition: amp.h:788
static poly normalize(poly next_p, ideal add_generators, syStrategy syzstr, int *g_l, int *p_l, int crit_comp)
Definition: syz3.cc:1027
#define TIMING_START(t)
Definition: timing.h:92
#define TIMING_END_AND_PRINT(t, msg)
Definition: timing.h:94

◆ 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}
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
int * degsf
Definition: cfEzgcd.cc:59
#define DELETE_ARRAY(P)
Definition: cf_defs.h:65
#define NEW_ARRAY(T, N)
Definition: cf_defs.h:64
CanonicalForm buf1
Definition: facFqBivar.cc:73

◆ myContent() [1/2]

static CanonicalForm myContent ( const CanonicalForm F)
inlinestatic

Definition at line 58 of file facFqFactorize.cc.

59{
60 Variable x= Variable (1);
61 CanonicalForm G= swapvar (F, F.mvar(), x);
62 CFList L;
63 for (CFIterator i= G; i.hasTerms(); i++)
64 L.append (i.coeff());
65 if (L.length() == 2)
66 return swapvar (gcd (L.getFirst(), L.getLast()), F.mvar(), x);
67 if (L.length() == 1)
68 return LC (F, x);
69 return swapvar (listGCD (L), F.mvar(), x);
70}
class to iterate through CanonicalForm's
Definition: cf_iter.h:44
STATIC_VAR TreeM * G
Definition: janet.cc:31

◆ myContent() [2/2]

static CanonicalForm myContent ( const CanonicalForm F,
const Variable x 
)
inlinestatic

Definition at line 101 of file facFqFactorize.cc.

102{
103 if (degree (F, x) <= 0)
104 return 1;
105 CanonicalForm G= F;
106 bool swap= false;
107 if (x != F.mvar())
108 {
109 swap= true;
110 G= swapvar (F, x, F.mvar());
111 }
112 CFList L;
114 for (CFIterator i= G; i.hasTerms(); i++)
115 L.append (i.coeff());
116 if (L.length() == 2)
117 {
118 if (swap)
119 return swapvar (gcd (L.getFirst(), L.getLast()), F.mvar(), x);
120 else
121 return gcd (L.getFirst(), L.getLast());
122 }
123 if (L.length() == 1)
124 {
125 return LC (F, x);
126 }
127 if (swap)
128 return swapvar (listGCD (L), F.mvar(), x);
129 else
130 return listGCD (L);
131}

◆ newMainVariableSearch()

static int newMainVariableSearch ( CanonicalForm A,
CFList Aeval,
CFList evaluation,
const Variable alpha,
const int  lev,
CanonicalForm g 
)
inlinestatic

Definition at line 924 of file facFqFactorize.cc.

928{
929 Variable x= Variable (1);
930 CanonicalForm derivI, buf;
932 int swapLevel= 0;
933 CFList list;
934 bool fail= false;
935 buf= A;
936 Aeval= CFList();
938 for (int i= lev; i <= A.level(); i++)
939 {
940 derivI= deriv (buf, Variable (i));
941 if (!derivI.isZero())
942 {
943 g= gcd (buf, derivI);
944 if (degree (g) > 0)
945 return -1;
946
947 buf= swapvar (buf, x, Variable (i));
948 Aeval= CFList();
950 fail= false;
951 evaluation= evalPoints (buf, Aeval, alpha, list, GF, fail);
952 if (!fail)
953 {
954 A= buf;
955 swapLevel= i;
956 break;
957 }
958 else
959 buf= A;
960 }
961 }
962 return swapLevel;
963}

◆ 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}
int getNumVars(const CanonicalForm &f)
int getNumVars ( const CanonicalForm & f )
Definition: cf_ops.cc:314
CanonicalForm compress(const CanonicalForm &f, CFMap &m)
CanonicalForm compress ( const CanonicalForm & f, CFMap & m )
Definition: cf_map.cc:210
bool isUnivariate() const
void removeLast()
Definition: ftmpl_list.cc:317
bool found
Definition: facFactorize.cc:55
CFList evaluateAtZero(const CanonicalForm &F)
evaluate F successively n-2 at 0
CFList evaluateAtEval(const CanonicalForm &F, const CFArray &eval)
evaluate F at evaluation
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
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 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}

◆ prodEval()

static CanonicalForm prodEval ( const CFList l,
const CanonicalForm evalPoint,
const Variable v 
)
inlinestatic

Definition at line 2011 of file facFqFactorize.cc.

2013{
2015 for (CFListIterator i= l; i.hasItem(); i++)
2016 result *= i.getItem() (evalPoint, v);
2017 return result;
2018}

◆ 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)

◆ refineBiFactors()

void refineBiFactors ( const CanonicalForm A,
CFList biFactors,
CFList *const Aeval,
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]Aevallist 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}

◆ 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)

◆ testFactors()

int testFactors ( const CanonicalForm G,
const CFList uniFactors,
const Variable alpha,
CanonicalForm sqrfPartF,
CFList factors,
CFFList *&  bufSqrfFactors,
CFList evalSqrfPartF,
const CFArray evalPoint 
)

Definition at line 1384 of file facFqFactorize.cc.

1388{
1389 CanonicalForm F= G;
1390 CFFList sqrfFactorization;
1391 if (getCharacteristic() > 0)
1392 sqrfFactorization= squarefreeFactorization (F, alpha);
1393 else
1394 sqrfFactorization= sqrFree (F);
1395
1396 sqrfPartF= 1;
1397 for (CFFListIterator i= sqrfFactorization; i.hasItem(); i++)
1398 sqrfPartF *= i.getItem().factor();
1399
1400 evalSqrfPartF= evaluateAtEval (sqrfPartF, evalPoint);
1401
1402 CanonicalForm test= evalSqrfPartF.getFirst() (evalPoint[0], 2);
1403
1404 if (degree (test) != degree (sqrfPartF, 1) || test.inCoeffDomain())
1405 return 0;
1406
1407 CFFList sqrfFactors;
1408 CanonicalForm tmp;
1409 CFList tmp2;
1410 int k= 0;
1411 factors= uniFactors;
1413 for (CFListIterator i= factors; i.hasItem(); i++, k++)
1414 {
1415 tmp= 1;
1416 if (getCharacteristic() > 0)
1417 sqrfFactors= squarefreeFactorization (i.getItem(), alpha);
1418 else
1419 sqrfFactors= sqrFree (i.getItem());
1420
1421 for (iter= sqrfFactors; iter.hasItem(); iter++)
1422 {
1423 tmp2.append (iter.getItem().factor());
1424 tmp *= iter.getItem().factor();
1425 }
1426 i.getItem()= tmp/Lc(tmp);
1427 bufSqrfFactors [k]= sqrfFactors;
1428 }
1429
1430 for (int i= 0; i < factors.length() - 1; i++)
1431 {
1432 for (k= i + 1; k < factors.length(); k++)
1433 {
1434 gcdFreeBasis (bufSqrfFactors [i], bufSqrfFactors[k]);
1435 }
1436 }
1437
1438 factors= CFList();
1439 for (int i= 0; i < uniFactors.length(); i++)
1440 {
1441 if (i == 0)
1442 {
1443 for (iter= bufSqrfFactors [i]; iter.hasItem(); iter++)
1444 {
1445 if (iter.getItem().factor().inCoeffDomain())
1446 continue;
1447 iter.getItem()= CFFactor (iter.getItem().factor()/
1448 Lc (iter.getItem().factor()),
1449 iter.getItem().exp());
1450 factors.append (iter.getItem().factor());
1451 }
1452 }
1453 else
1454 {
1455 for (iter= bufSqrfFactors [i]; iter.hasItem(); iter++)
1456 {
1457 if (iter.getItem().factor().inCoeffDomain())
1458 continue;
1459 iter.getItem()= CFFactor (iter.getItem().factor()/
1460 Lc (iter.getItem().factor()),
1461 iter.getItem().exp());
1462 if (!find (factors, iter.getItem().factor()))
1463 factors.append (iter.getItem().factor());
1464 }
1465 }
1466 }
1467
1468 test= prod (factors);
1469 tmp= evalSqrfPartF.getFirst() (evalPoint[0],2);
1470 if (test/Lc (test) != tmp/Lc (tmp))
1471 return 0;
1472 else
1473 return 1;
1474}
CanonicalForm test
Definition: cfModGcd.cc:4096
void gcdFreeBasis(CFFList &factors1, CFFList &factors2)
gcd free basis of two lists of factors
CFFList squarefreeFactorization(const CanonicalForm &F, const Variable &alpha)
squarefree factorization over a finite field return a list of squarefree factors with multiplicity

◆ TIMING_DEFINE_PRINT()

TIMING_DEFINE_PRINT ( fac_fq_bi_factorizer  ) const &