My Project
Loading...
Searching...
No Matches
facFqFactorize.cc File Reference

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

#include "config.h"
#include <math.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
 
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.
 
CFList factorRecombination (const CanonicalForm &F, const CFList &factors, const CFList &M)
 Naive factor recombination for multivariate factorization. No precomputed is used to exclude combinations.
 
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.
 
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.
 
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.
 
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.
 
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.
 
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.
 
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 gcdFreeBasis (CFFList &factors1, CFFList &factors2)
 gcd free basis of two lists of factors
 
CFList distributeContent (const CFList &L, const CFList *differentSecondVarFactors, int length)
 distribute content
 
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.
 
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
 
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.
 
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
 
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
 
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
 
CFList buildUniFactors (const CFList &biFactors, const CanonicalForm &evalPoint, const Variable &y)
 plug in evalPoint for y in a list of polys
 
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 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
 
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
 
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
 
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
 
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
 
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
 
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.
 
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.
 
CFList extFactorize (const CanonicalForm &F, const ExtensionInfo &info)
 multivariate factorization over an extension of the initial field
 
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 749 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 2321 of file facFqFactorize.cc.

2323{
2324 CFList result;
2325 CanonicalForm tmp;
2326 for (CFListIterator i= biFactors; i.hasItem(); i++)
2327 {
2328 tmp= mod (i.getItem(), y - evalPoint);
2329 tmp /= Lc (tmp);
2330 result.append (tmp);
2331 }
2332 return result;
2333}
CF_NO_INLINE FACTORY_PUBLIC CanonicalForm mod(const CanonicalForm &, const CanonicalForm &)
ListIterator< CanonicalForm > CFListIterator
CanonicalForm Lc(const CanonicalForm &f)
List< CanonicalForm > CFList
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
return result
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
A[in,out] a multivariate poly
biFactors[in,out] bivariate factors
evaluation[in,out] evaluation point
oldAeval[in,out] old bivariate factors wrt. different second vars
[in]lengthAeval2length of oldAeval
[in]uniFactorsunivariate factors
[in]wsome variable

Definition at line 2544 of file facFqFactorize.cc.

2547{
2548 Variable y= Variable (2);
2549 A= swapvar (A, y, w);
2550 int i= A.level();
2552 for (CFListIterator iter= evaluation; iter.hasItem(); iter++, i--)
2553 {
2554 if (i == w.level())
2555 {
2556 evalPoint= iter.getItem();
2557 iter.getItem()= evaluation.getLast();
2558 evaluation.removeLast();
2559 evaluation.append (evalPoint);
2560 break;
2561 }
2562 }
2563 for (i= 0; i < lengthAeval2; i++)
2564 {
2565 if (oldAeval[i].isEmpty())
2566 continue;
2567 if (oldAeval[i].getFirst().level() == w.level())
2568 {
2569 CFArray tmp= copy (oldAeval[i]);
2570 oldAeval[i]= biFactors;
2571 for (CFListIterator iter= oldAeval[i]; iter.hasItem(); iter++)
2572 iter.getItem()= swapvar (iter.getItem(), w, y);
2573 for (int ii= 0; ii < tmp.size(); ii++)
2574 tmp[ii]= swapvar (tmp[ii], w, y);
2575 CFArray tmp2= CFArray (tmp.size());
2577 for (int ii= 0; ii < tmp.size(); ii++)
2578 {
2579 buf= tmp[ii] (evaluation.getLast(),y);
2580 buf /= Lc (buf);
2581 tmp2[findItem (uniFactors, buf)-1]=tmp[ii];
2582 }
2583 biFactors= CFList();
2584 for (int j= 0; j < tmp2.size(); j++)
2585 biFactors.append (tmp2[j]);
2586 }
2587 }
2588}
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)
int findItem(const CFList &list, const CanonicalForm &item)
helper function
Definition cf_map_ext.cc:42
int size() const
void append(const T &)
factory's class for variables
Definition factory.h:127
CFFListIterator iter
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:75
int j
Definition facHensel.cc:110
int status int void * buf
Definition si_signals.h:69
#define A
Definition sirandom.c:24

◆ checkHelper()

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

Definition at line 2022 of file facFqFactorize.cc.

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

◆ 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 2046 of file facFqFactorize.cc.

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

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

◆ 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 1295 of file facFqFactorize.cc.

1298{
1299 CFList l= L;
1300 CanonicalForm content= l.getFirst();
1301
1302 if (content.inCoeffDomain())
1303 return l;
1304
1305 if (l.length() == 1)
1306 {
1307 CFList result;
1308 for (int i= 0; i < length; i++)
1309 {
1310 if (differentSecondVarFactors[i].isEmpty())
1311 continue;
1312 if (result.isEmpty())
1313 {
1314 result= differentSecondVarFactors[i];
1315 for (CFListIterator iter= result; iter.hasItem(); iter++)
1316 content /= iter.getItem();
1317 }
1318 else
1319 {
1320 CFListIterator iter1= result;
1321 for (CFListIterator iter2= differentSecondVarFactors[i];iter2.hasItem();
1322 iter2++, iter1++)
1323 {
1324 iter1.getItem() *= iter2.getItem();
1325 content /= iter2.getItem();
1326 }
1327 }
1328 }
1329 result.insert (content);
1330 return result;
1331 }
1332
1333 Variable v;
1334 CFListIterator iter1, iter2;
1335 CanonicalForm tmp, g;
1336 CFList multiplier;
1337 for (int i= 0; i < length; i++)
1338 {
1339 if (differentSecondVarFactors[i].isEmpty())
1340 continue;
1341 iter1= l;
1342 iter1++;
1343
1344 tmp= 1;
1345 for (iter2= differentSecondVarFactors[i]; iter2.hasItem();
1346 iter2++, iter1++)
1347 {
1348 if (iter2.getItem().inCoeffDomain())
1349 {
1350 multiplier.append (1);
1351 continue;
1352 }
1353 v= iter2.getItem().mvar();
1354 if (degree (iter2.getItem()) == degree (iter1.getItem(),v))
1355 {
1356 multiplier.append (1);
1357 continue;
1358 }
1359 g= gcd (iter2.getItem(), content);
1360 if (!g.inCoeffDomain())
1361 {
1362 tmp *= g;
1363 multiplier.append (g);
1364 }
1365 else
1366 multiplier.append (1);
1367 }
1368 if (!tmp.isOne() && fdivides (tmp, content))
1369 {
1370 iter1= l;
1371 iter1++;
1372 content /= tmp;
1373 for (iter2= multiplier; iter2.hasItem(); iter1++, iter2++)
1374 iter1.getItem() *= iter2.getItem();
1375 }
1376 multiplier= CFList();
1377 }
1378
1379 l.removeFirst();
1380 l.insert (content);
1381 return l;
1382}
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:4098
bool fdivides(const CanonicalForm &f, const CanonicalForm &g)
bool fdivides ( const CanonicalForm & f, const CanonicalForm & g )
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
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
A[in,out] some poly
leadingCoeffs[in,out] leading coefficients
biFactors[in,out] bivariate factors
[in]evaluationeval. point
[in]LCmultiplermultiplier

Definition at line 2591 of file facFqFactorize.cc.

2594{
2595 CanonicalForm tmp= power (LCmultipler, biFactors.length() - 1);
2596 A *= tmp;
2597 tmp= LCmultipler;
2598 CFListIterator iter= leadingCoeffs;
2599 for (;iter.hasItem(); iter++)
2600 iter.getItem() *= LCmultipler;
2602 for (int i= A.level(); i > 2; i--, iter++)
2603 tmp= tmp (iter.getItem(), i);
2604 if (!tmp.inCoeffDomain())
2605 {
2606 for (CFListIterator i= biFactors; i.hasItem(); i++)
2607 {
2608 i.getItem() *= tmp/LC (i.getItem(), 1);
2609 i.getItem() /= Lc (i.getItem());
2610 }
2611 }
2612}
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
F[in,out] poly to be factored, returns poly divided by detected factors in case of success
factors[in,out] list of factors lifted up to deg, returns a list of factors without detected factors
adaptedLiftBound[in,out] adapted lift bound
success[in,out] indicating success
[in]degstage of Hensel lifting
[in]MODa list of powers of Variables
[in]boundinitial lift bound

Definition at line 612 of file facFqFactorize.cc.

615{
617 CFList T= factors;
619 Variable y= F.mvar();
620 Variable x= Variable (1);
621 CanonicalForm LCBuf= LC (buf, x);
622 CanonicalForm g, quot;
623 CFList M= MOD;
624 M.append (power (y, deg));
625 adaptedLiftBound= 0;
626 int d= bound;
627 int e= 0;
628 int nBuf;
629 for (CFListIterator i= factors; i.hasItem(); i++)
630 {
631 g= mulMod (i.getItem(), LCBuf, M);
632 g /= myContent (g);
633 if (fdivides (g, buf, quot))
634 {
635 result.append (g);
636 nBuf= degree (g, y) + degree (LC (g, x), y);
637 d -= nBuf;
638 e= tmax (e, nBuf);
639 buf= quot;
640 LCBuf= LC (buf, x);
641 T= Difference (T, CFList (i.getItem()));
642 }
643 }
644 adaptedLiftBound= d;
645
646 if (adaptedLiftBound < deg)
647 {
648 if (adaptedLiftBound < degree (F) + 1)
649 {
650 if (d == 1)
651 adaptedLiftBound= tmin (e + 1, deg);
652 else
653 adaptedLiftBound= deg;
654 }
655 factors= T;
656 F= buf;
657 success= true;
658 }
659 return result;
660}
static CanonicalForm bound(const CFMatrix &M)
Definition cf_linsys.cc:460
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:3086
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
eval[in,out] an empty list, returns F successive evaluated
[in]alphaalgebraic variable
list[in,out] a list of points already considered, a point is encoded as a poly of degree F.level()-1 in Variable(1)
[in]GFGF?
fail[in,out] indicates failure

Definition at line 751 of file facFqFactorize.cc.

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

◆ 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
Aeval[in,out] an 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 1966 of file facFqFactorize.cc.

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

◆ 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
F[in,out] poly to be factored, returns poly divided by detected factors in case of success
factors[in,out] list of factors lifted up to deg, returns a list of factors without detected factors
adaptedLiftBound[in,out] adapted lift bound
success[in,out] indicating 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 665 of file facFqFactorize.cc.

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

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

◆ 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 216 of file facFqFactorize.cc.

219{
220 Variable alpha= info.getAlpha();
221 Variable beta= info.getBeta();
222 CanonicalForm gamma= info.getGamma();
223 CanonicalForm delta= info.getDelta();
224 int k= info.getGFDegree();
225 CFList source, dest;
226 if (factors.length() == 1)
227 {
229 return CFList (mapDown (buf, info, source, dest));
230 }
231 if (factors.length() < 1)
232 return CFList();
233
234 int degMipoBeta= 1;
235 if (!k && beta.level() != 1)
236 degMipoBeta= degree (getMipo (beta));
237
238 CFList T, S;
239 T= factors;
240
241 int s= 1;
244
245 buf= F;
246
247 Variable x= Variable (1);
248 CanonicalForm g, LCBuf= LC (buf, x);
249 CanonicalForm buf2, quot;
250 int * v= new int [T.length()];
251 for (int i= 0; i < T.length(); i++)
252 v[i]= 0;
253 bool noSubset= false;
254 CFArray TT;
255 TT= copy (factors);
256 bool recombination= false;
257 bool trueFactor= false;
258 while (T.length() >= 2*s)
259 {
260 while (noSubset == false)
261 {
262 if (T.length() == s)
263 {
264 delete [] v;
265 if (recombination)
266 {
267 T.insert (LCBuf);
268 g= prodMod (T, M);
269 T.removeFirst();
270 result.append (g/myContent (g));
272 g /= Lc (g);
273 appendTestMapDown (result, g, info, source, dest);
274 return result;
275 }
276 else
277 {
279 return CFList (buf);
280 }
281 }
282
283 S= subset (v, s, TT, noSubset);
284 if (noSubset) break;
285
286 S.insert (LCBuf);
287 g= prodMod (S, M);
288 S.removeFirst();
289 g /= myContent (g);
290 if (fdivides (g, buf, quot))
291 {
293 buf2 /= Lc (buf2);
294 if (!k && beta == x)
295 {
296 if (degree (buf2, alpha) < degMipoBeta)
297 {
298 appendTestMapDown (result, buf2, info, source, dest);
299 buf= quot;
300 LCBuf= LC (buf, x);
301 recombination= true;
302 trueFactor= true;
303 }
304 }
305 else
306 {
307 if (!isInExtension (buf2, gamma, k, delta, source, dest))
308 {
309 appendTestMapDown (result, buf2, info, source, dest);
310 buf /= g;
311 LCBuf= LC (buf, x);
312 recombination= true;
313 trueFactor= true;
314 }
315 }
316
317 if (trueFactor)
318 {
319 T= Difference (T, S);
320
321 if (T.length() < 2*s || T.length() == s)
322 {
324 buf /= Lc (buf);
325 appendTestMapDown (result, buf, info, source, dest);
326 delete [] v;
327 return result;
328 }
329 trueFactor= false;
330 TT= copy (T);
331 indexUpdate (v, s, T.length(), noSubset);
332 if (noSubset) break;
333 }
334 }
335 }
336 s++;
337 if (T.length() < 2*s || T.length() == s)
338 {
340 appendTestMapDown (result, buf, info, source, dest);
341 delete [] v;
342 return result;
343 }
344 for (int i= 0; i < T.length(); i++)
345 v[i]= 0;
346 noSubset= false;
347 }
348 if (T.length() < 2*s)
349 {
351 appendMapDown (result, buf, info, source, dest);
352 }
353
354 delete [] v;
355 return result;
356}
void removeFirst()
void insert(const T &)
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:76
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:3186

◆ 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
success[in,out] indicates 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 514 of file facFqFactorize.cc.

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

◆ extNonMonicFactorRecombination()

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

Definition at line 2421 of file facFqFactorize.cc.

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

◆ factorizationWRTDifferentSecondVars()

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

Definition at line 2184 of file facFqFactorize.cc.

2187{
2188 Variable x= Variable (1);
2190 irred= false;
2191 CFList factors;
2192 Variable v;
2193 for (int j= 0; j < A.level() - 2; j++)
2194 {
2195 if (!Aeval[j].isEmpty())
2196 {
2197 v= Variable (Aeval[j].getFirst().level());
2199 factors= GFBiSqrfFactorize (Aeval[j].getFirst());
2200 else if (info.getAlpha().level() == 1)
2201 factors= FpBiSqrfFactorize (Aeval[j].getFirst());
2202 else
2203 factors= FqBiSqrfFactorize (Aeval[j].getFirst(), info.getAlpha());
2204
2205 factors.removeFirst();
2206 if (minFactorsLength == 0)
2207 minFactorsLength= factors.length();
2208 else
2210
2211 if (factors.length() == 1)
2212 {
2213 irred= true;
2214 return;
2215 }
2216 sortList (factors, x);
2217 Aeval [j]= factors;
2218 }
2219 }
2220}
CFList int & minFactorsLength
[in,out] minimal length of bivariate factors
CFList int bool & irred
[in,out] Is A irreducible?
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 361 of file facFqFactorize.cc.

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

◆ gcdFreeBasis()

void gcdFreeBasis ( CFFList & factors1,
CFFList & factors2 )

gcd free basis of two lists of factors

Parameters
factors1[in,out] list of factors, returns gcd free factors
factors2[in,out] list of factors, returns gcd free factors

Definition at line 1269 of file facFqFactorize.cc.

1270{
1272 int k= factors1.length();
1273 int l= factors2.length();
1274 int n= 0;
1275 int m;
1277 for (CFFListIterator i= factors1; (n < k && i.hasItem()); i++, n++)
1278 {
1279 m= 0;
1280 for (j= factors2; (m < l && j.hasItem()); j++, m++)
1281 {
1282 g= gcd (i.getItem().factor(), j.getItem().factor());
1283 if (degree (g,1) > 0)
1284 {
1285 j.getItem()= CFFactor (j.getItem().factor()/g, j.getItem().exp());
1286 i.getItem()= CFFactor (i.getItem().factor()/g, i.getItem().exp());
1287 factors1.append (CFFactor (g, i.getItem().exp()));
1288 factors2.append (CFFactor (g, j.getItem().exp()));
1289 }
1290 }
1291 }
1292}
ListIterator< CFFactor > CFFListIterator
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
Aeval[in,out] array of bivariate factors, returns the leading coefficients of these factors

Definition at line 2233 of file facFqFactorize.cc.

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

◆ 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
A[in,out] poly to be factored, returns poly divided by detected factors, in case of success
MOD[in,out] a list of powers of Variables
liftBounds[in,out] initial lift bounds, returns adapted lift bounds
earlySuccess[in,out] indicating success
earlyFactors[in,out] early factors
[in]AevalA successively evaluated at elements of evaluation
[in]biFactorsbivariate factors
[in]evaluationevaluation point
[in]infoinfo about extension

Definition at line 985 of file facFqFactorize.cc.

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

◆ 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
A[in,out] a poly
LCmultiplier[in,out] divisor of LC (A,1)
biFactors[in,out] bivariate factors
leadingCoeffs[in,out] leading 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 2615 of file facFqFactorize.cc.

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

◆ 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
leadingCoeffs[in,out] leading coeffs
contents[in,out] content of factors
LCs[in,out] LC of factors divided by content of factors
foundTrueMultiplier[in,out] success?

Definition at line 2779 of file facFqFactorize.cc.

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

◆ 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
A[in,out] poly
leadingCoeffs[in,out] leading coeffs
[in]lengthAevallength of oldAeval
foundMultiplier[in,out] success?

Definition at line 2809 of file facFqFactorize.cc.

2813{
2814 int index= 1;
2815 CFListIterator iter, iter2= factors;
2816 for (iter= contents; iter.hasItem(); iter++, iter2++, index++)
2817 {
2818 if (fdivides (iter.getItem(), LCmultiplier))
2819 {
2820 if ((LCmultiplier/iter.getItem()).inCoeffDomain() &&
2821 !isOnlyLeadingCoeff(iter2.getItem())) //content divides LCmultiplier completely and factor consists of more terms than just the leading coeff
2822 {
2823 Variable xx= Variable (2);
2824 CanonicalForm vars;
2825 vars= power (xx, degree (LC (getItem(oldBiFactors, index),1),
2826 xx));
2827 for (int i= 0; i < lengthAeval; i++)
2828 {
2829 if (oldAeval[i].isEmpty())
2830 continue;
2831 xx= oldAeval[i].getFirst().mvar();
2832 vars *= power (xx, degree (LC (getItem(oldAeval[i], index),1),
2833 xx));
2834 }
2835 if (vars.level() <= 2)
2836 {
2837 int index2= 1;
2838 for (CFListIterator iter3= leadingCoeffs[lengthAeval-1];
2839 iter3.hasItem(); iter3++, index2++)
2840 {
2841 if (index2 == index)
2842 {
2843 iter3.getItem() /= LCmultiplier;
2844 break;
2845 }
2846 }
2847 A /= LCmultiplier;
2848 foundMultiplier= true;
2849 iter.getItem()= 1;
2850 }
2851 }
2852 }
2853 }
2854}
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
leadingCoeffs[in,out] leading coeffs
A[in,out] poly
LCmultiplier[in,out] divisor of LC (A,1)
[in]foundMultipliersuccess?

Definition at line 2857 of file facFqFactorize.cc.

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

◆ 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
A[in,out] oldA*LCmultiplier^m
[in]oldAsome poly
leadingCoeffs[in,out] leading coefficients
foundTrueMultiplier[in,out] success?

Definition at line 2763 of file facFqFactorize.cc.

2766{
2767 CanonicalForm pLCs= prod (LCs);
2768 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
2769 {
2770 A= oldA;
2771 CFListIterator iter2= leadingCoeffs;
2772 for (CFListIterator iter= contents; iter.hasItem(); iter++, iter2++)
2773 iter2.getItem() /= iter.getItem();
2774 foundTrueMultiplier= true;
2775 }
2776}

◆ 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
contentAi[in,out] an empty list, returns a list of the contents of A wrt to each variable occuring in A starting from A.mvar().

Definition at line 966 of file facFqFactorize.cc.

967{
968 int i= A.level();
970 contentAi.append (content (buf, i));
971 buf /= contentAi.getLast();
972 contentAi.append (content (buf, i - 1));
973 CanonicalForm result= lcm (contentAi.getFirst(), contentAi.getLast());
974 for (i= i - 2; i > 0; i--)
975 {
976 contentAi.append (content (buf, i));
977 buf /= contentAi.getLast();
978 result= lcm (result, contentAi.getLast());
979 }
980 return result;
981}
T getLast() const
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)
success[in,out] indicates 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 448 of file facFqFactorize.cc.

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

◆ listGCD()

static CanonicalForm listGCD ( const CFList & L)
inlinestatic

Definition at line 75 of file facFqFactorize.cc.

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

◆ multiFactorize()

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

Definition at line 2929 of file facFqFactorize.cc.

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

Definition at line 134 of file facFqFactorize.cc.

135{
136 int n= F.level();
137 int * degsf= NEW_ARRAY(int,n + 1);
138 int ** swap= new int* [n + 1];
139 for (int i= 0; i <= n; i++)
140 {
141 degsf[i]= 0;
142 swap [i]= new int [3];
143 swap [i] [0]= 0;
144 swap [i] [1]= 0;
145 swap [i] [2]= 0;
146 }
147 int i= 1;
148 n= 1;
149 degsf= degrees (F, degsf);
150
152 while ( i <= F.level() )
153 {
154 while( degsf[i] == 0 ) i++;
155 swap[n][0]= i;
156 swap[n][1]= size (LC (F,i));
157 swap[n][2]= degsf [i];
158 if (i != n)
160 n++; i++;
161 }
162
163 int buf1, buf2, buf3;
164 n--;
165
166 for (i= 1; i < n; i++)
167 {
168 for (int j= 1; j < n - i + 1; j++)
169 {
170 if (swap[j][1] > swap[j + 1][1])
171 {
172 buf1= swap [j + 1] [0];
173 buf2= swap [j + 1] [1];
174 buf3= swap [j + 1] [2];
175 swap[j + 1] [0]= swap[j] [0];
176 swap[j + 1] [1]= swap[j] [1];
177 swap[j + 1] [2]= swap[j] [2];
178 swap[j][0]= buf1;
179 swap[j][1]= buf2;
180 swap[j][2]= buf3;
181 result= swapvar (result, Variable (j + 1), Variable (j));
182 }
183 else if (swap[j][1] == swap[j + 1][1] && swap[j][2] < swap[j + 1][2])
184 {
185 buf1= swap [j + 1] [0];
186 buf2= swap [j + 1] [1];
187 buf3= swap [j + 1] [2];
188 swap[j + 1] [0]= swap[j] [0];
189 swap[j + 1] [1]= swap[j] [1];
190 swap[j + 1] [2]= swap[j] [2];
191 swap[j][0]= buf1;
192 swap[j][1]= buf2;
193 swap[j][2]= buf3;
194 result= swapvar (result, Variable (j + 1), Variable (j));
195 }
196 }
197 }
198
199 for (i= n; i > 0; i--)
200 {
201 if (i != swap[i] [0])
202 N.newpair (Variable (i), Variable (swap[i] [0]));
203 }
204
205 for (i= F.level(); i >=0 ; i--)
206 delete [] swap[i];
207 delete [] swap;
208
210
211 return result;
212}
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:76

◆ myContent() [1/2]

static CanonicalForm myContent ( const CanonicalForm & F)
inlinestatic

Definition at line 59 of file facFqFactorize.cc.

60{
61 Variable x= Variable (1);
62 CanonicalForm G= swapvar (F, F.mvar(), x);
63 CFList L;
64 for (CFIterator i= G; i.hasTerms(); i++)
65 L.append (i.coeff());
66 if (L.length() == 2)
67 return swapvar (gcd (L.getFirst(), L.getLast()), F.mvar(), x);
68 if (L.length() == 1)
69 return LC (F, x);
70 return swapvar (listGCD (L), F.mvar(), x);
71}
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 102 of file facFqFactorize.cc.

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

◆ newMainVariableSearch()

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

Definition at line 925 of file facFqFactorize.cc.

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

◆ 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
y[in,out] if y.level() is not 1 on output the second variable has been changed to y

Definition at line 1479 of file facFqFactorize.cc.

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

◆ 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
LCs[in,out]
A[in,out]
Aeval[in,out]
[in]nlevel of poly to be factored
[in]leadingCoeffsprecomputed leading coeffs
[in]biFactorsbivariate factors
[in]evaluationevaluation point

Definition at line 2382 of file facFqFactorize.cc.

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

◆ prodEval()

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

Definition at line 2012 of file facFqFactorize.cc.

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

◆ 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 2114 of file facFqFactorize.cc.

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

2338{
2339 CFListIterator iter, iter2;
2341 int i;
2342 Variable v;
2343 Variable y= Variable (2);
2344 CFList list;
2345 bool leaveLoop= false;
2346 for (int j= 0; j < A.level() - 2; j++)
2347 {
2348 if (Aeval[j].length() == minFactorsLength)
2349 {
2350 i= A.level();
2351
2352 for (iter= evaluation; iter.hasItem(); iter++, i--)
2353 {
2354 for (iter2= Aeval[j]; iter2.hasItem(); iter2++)
2355 {
2356 if (i == iter2.getItem().level())
2357 {
2358 evalPoint= iter.getItem();
2359 leaveLoop= true;
2360 break;
2361 }
2362 }
2363 if (leaveLoop)
2364 {
2365 leaveLoop= false;
2366 break;
2367 }
2368 }
2369
2370 v= Variable (i);
2371 list= buildUniFactors (Aeval[j], evalPoint, v);
2372
2373 biFactors= recombination (biFactors, list, 1,
2374 biFactors.length() - list.length() + 1,
2375 evaluation.getLast(), y);
2376 return;
2377 }
2378 }
2379}

◆ 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
Aeval[in,out] array of bivariate factors
[in]AevalLengthlength of Aeval
uniFactors[in,out] univariate factors
biFactors[in,out] bivariate factors
[in]evaluationevaluation point

Definition at line 2251 of file facFqFactorize.cc.

2255{
2257 int i;
2258 CFListIterator iter, iter2;
2259 Variable v;
2260 CFList LCs, buf;
2261 CFArray l;
2262 int pos, index, checklength;
2263 bool leaveLoop=false;
2264recurse:
2265 for (int j= 0; j < AevalLength; j++)
2266 {
2267 if (!Aeval[j].isEmpty())
2268 {
2269 i= evaluation.length() + 1;
2270 for (iter= evaluation; iter.hasItem(); iter++, i--)
2271 {
2272 for (iter2= Aeval[j]; iter2.hasItem(); iter2++)
2273 {
2274 if (i == iter2.getItem().level())
2275 {
2276 evalPoint= iter.getItem();
2277 leaveLoop= true;
2278 break;
2279 }
2280 }
2281 if (leaveLoop)
2282 {
2283 leaveLoop= false;
2284 break;
2285 }
2286 }
2287
2288 v= Variable (i);
2289 if (Aeval[j].length() > uniFactors.length())
2290 Aeval[j]= recombination (Aeval[j], uniFactors, 1,
2291 Aeval[j].length() - uniFactors.length() + 1,
2292 evalPoint, v);
2293
2294 checklength= biFactors.length();
2295 Aeval[j]= checkOneToOne (Aeval[j], uniFactors, biFactors, evalPoint, v);
2296 if (checklength > biFactors.length())
2297 {
2298 uniFactors= buildUniFactors (biFactors, evaluation.getLast(),
2299 Variable (2));
2300 goto recurse;
2301 }
2302
2304 l= CFArray (uniFactors.length());
2305 index= 1;
2306 for (iter= buf; iter.hasItem(); iter++, index++)
2307 {
2308 pos= findItem (uniFactors, iter.getItem());
2309 if (pos)
2310 l[pos-1]= getItem (Aeval[j], index);
2311 }
2312 buf= conv (l);
2313 Aeval [j]= buf;
2314
2316 }
2317 }
2318}
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 1385 of file facFqFactorize.cc.

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