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

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

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

Go to the source code of this file.

Macros

#define CHAR_THRESHOLD   8
 

Functions

 TIMING_DEFINE_PRINT (fac_fq_bi_factorizer) TIMING_DEFINE_PRINT(fac_fq_hensel_lift) TIMING_DEFINE_PRINT(fac_fq_factor_recombination) TIMING_DEFINE_PRINT(fac_fq_shift_to_zero) TIMING_DEFINE_PRINT(fac_fq_precompute_leadcoeff) TIMING_DEFINE_PRINT(fac_fq_evaluation) TIMING_DEFINE_PRINT(fac_fq_recover_factors) TIMING_DEFINE_PRINT(fac_fq_preprocess_and_content) TIMING_DEFINE_PRINT(fac_fq_bifactor_total) TIMING_DEFINE_PRINT(fac_fq_luckswang) TIMING_DEFINE_PRINT(fac_fq_lcheuristic) TIMING_DEFINE_PRINT(fac_fq_content) TIMING_DEFINE_PRINT(fac_fq_check_mainvar) TIMING_DEFINE_PRINT(fac_fq_compress) static inline CanonicalForm listGCD(const CFList &L)
 
static CanonicalForm myContent (const CanonicalForm &F)
 
static CanonicalForm listGCD (const CFList &L)
 
static CanonicalForm myContent (const CanonicalForm &F, const Variable &x)
 
CanonicalForm myCompress (const CanonicalForm &F, CFMap &N)
 compress a polynomial s.t. $ deg_{x_{i}} (F) >= deg_{x_{i+1}} (F) $ and no gaps between the variables occur
 
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 748 of file facFqFactorize.cc.

Function Documentation

◆ buildUniFactors()

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

plug in evalPoint for y in a list of polys

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

Definition at line 2320 of file facFqFactorize.cc.

2322{
2323 CFList result;
2325 for (CFListIterator i= biFactors; i.hasItem(); i++)
2326 {
2327 tmp= mod (i.getItem(), y - evalPoint);
2328 tmp /= Lc (tmp);
2329 result.append (tmp);
2330 }
2331 return result;
2332}
CF_NO_INLINE FACTORY_PUBLIC CanonicalForm mod(const CanonicalForm &, const CanonicalForm &)
CanonicalForm Lc(const CanonicalForm &f)
int i
Definition cfEzgcd.cc:132
static void evalPoint(const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &FEval, CanonicalForm &GEval, CFGenerator &evalPoint)
factory's main class
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
[in,out]Aa multivariate poly
[in,out]biFactorsbivariate factors
[in,out]evaluationevaluation point
[in,out]oldAevalold bivariate factors wrt. different second vars
[in]lengthAeval2length of oldAeval
[in]uniFactorsunivariate factors
[in]wsome variable

Definition at line 2543 of file facFqFactorize.cc.

2546{
2547 Variable y= Variable (2);
2548 A= swapvar (A, y, w);
2549 int i= A.level();
2551 for (CFListIterator iter= evaluation; iter.hasItem(); iter++, i--)
2552 {
2553 if (i == w.level())
2554 {
2555 evalPoint= iter.getItem();
2556 iter.getItem()= evaluation.getLast();
2557 evaluation.removeLast();
2558 evaluation.append (evalPoint);
2559 break;
2560 }
2561 }
2562 for (i= 0; i < lengthAeval2; i++)
2563 {
2564 if (oldAeval[i].isEmpty())
2565 continue;
2566 if (oldAeval[i].getFirst().level() == w.level())
2567 {
2570 for (CFListIterator iter= oldAeval[i]; iter.hasItem(); iter++)
2571 iter.getItem()= swapvar (iter.getItem(), w, y);
2572 for (int ii= 0; ii < tmp.size(); ii++)
2573 tmp[ii]= swapvar (tmp[ii], w, y);
2574 CFArray tmp2= CFArray (tmp.size());
2576 for (int ii= 0; ii < tmp.size(); ii++)
2577 {
2578 buf= tmp[ii] (evaluation.getLast(),y);
2579 buf /= Lc (buf);
2581 }
2582 biFactors= CFList();
2583 for (int j= 0; j < tmp2.size(); j++)
2585 }
2586 }
2587}
Array< CanonicalForm > CFArray
CanonicalForm FACTORY_PUBLIC swapvar(const CanonicalForm &, const Variable &, const Variable &)
swapvar() - swap variables x1 and x2 in f.
Definition cf_ops.cc:168
int level(const CanonicalForm &f)
List< CanonicalForm > CFList
int findItem(const CFList &list, const CanonicalForm &item)
helper function
Definition cf_map_ext.cc:42
int level() const
level() returns the level of CO.
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:74
int j
Definition facHensel.cc:110
int status int void * buf
Definition si_signals.h:59
#define A
Definition sirandom.c:24

◆ checkHelper()

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

Definition at line 2021 of file facFqFactorize.cc.

2023{
2024 CanonicalForm g1= f1, g2;
2026 for (; iter1.hasItem(); iter1++, iter2++)
2027 {
2028 g2= gcd (g1, iter1.getItem());
2029 if (!g2.inCoeffDomain())
2030 {
2031 l1.append (iter1.getItem());
2032 l2.append (iter2.getItem());
2033 g1 /= g2;
2034 }
2035 }
2038}
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 2045 of file facFqFactorize.cc.

2047{
2053 int pos;
2054
2055 for (iter= factors1; iter.hasItem(); iter++)
2056 {
2057 tmp= iter.getItem() (evalPoint, x);
2058 tmp /= Lc (tmp);
2059 if ((pos= findItem (factors2, tmp)))
2060 {
2061 result2.append (getItem (factors3, pos));
2062 result.append (iter.getItem());
2064 }
2065 else
2067 }
2068
2069 CFList bad2, bad3;
2072 CFList tmp2, tmp3;
2073 CanonicalForm g1, g2, g3, g4;
2074
2075 while (!uniFactorsOfFactors1.isEmpty())
2076 {
2079 g1= prod (tmp2);
2080 g2= prod (tmp3);
2081 tmp2= CFList();
2082 tmp3= CFList();
2084 g3= prod (tmp2);
2085 g4= prod (tmp3);
2086 tmp2= CFList();
2087 tmp3= CFList();
2088 do
2089 {
2091 g1 *= prod (tmp2);
2092 g2 *= prod (tmp3);
2093 tmp2= CFList();
2094 tmp3= CFList();
2096 g3 *= prod (tmp2);
2097 g4 *= prod (tmp3);
2098 tmp2= CFList();
2099 tmp3= CFList();
2100 } while (!bad2.isEmpty() && !bad3.isEmpty());
2101 result.append (g4);
2102 result2.append (g2);
2103 }
2104
2105 if (factors3.length() != result2.length())
2107 return result;
2108}
Variable x
Definition cfModGcd.cc:4082
CanonicalForm getItem(const CFList &list, const int &pos)
helper function
Definition cf_map_ext.cc: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 2223 of file facFqFactorize.cc.

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

◆ distributeContent()

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

distribute content

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

Definition at line 1294 of file facFqFactorize.cc.

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

◆ distributeLCmultiplier()

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

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

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

Definition at line 2590 of file facFqFactorize.cc.

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

◆ earlyFactorDetect()

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

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

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

Definition at line 611 of file facFqFactorize.cc.

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

◆ evalPoints()

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

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

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

Definition at line 750 of file facFqFactorize.cc.

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

Definition at line 1965 of file facFqFactorize.cc.

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

◆ extEarlyFactorDetect()

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

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

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

Definition at line 664 of file facFqFactorize.cc.

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

◆ extFactorize()

CFList extFactorize ( const CanonicalForm F,
const ExtensionInfo info 
)

multivariate factorization over an extension of the initial field

Factorization over an extension of initial field.

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

Definition at line 3660 of file facFqFactorize.cc.

3661{
3662 CanonicalForm A= F;
3663
3664 Variable alpha= info.getAlpha();
3665 Variable beta= info.getBeta();
3666 int k= info.getGFDegree();
3667 char cGFName= info.getGFName();
3668 CanonicalForm delta= info.getDelta();
3670 Variable w= Variable (1);
3671
3673 if (!GF && alpha == w) // we are in F_p
3674 {
3676 bool extension= true;
3677 int p= getCharacteristic();
3678 if (p < 7)
3679 {
3680 if (p == 2)
3682 else if (p == 3)
3684 else if (p == 5)
3687 A= A.mapinto();
3689
3693 for (CFListIterator j= factors; j.hasItem(); j++)
3694 j.getItem()= GF2FalphaRep (j.getItem(), vBuf);
3695 prune (vBuf);
3696 }
3697 else if (p >= 7 && p*p < (1<<16)) // pass to GF if possible
3698 {
3701 A= A.mapinto();
3703
3707 for (CFListIterator j= factors; j.hasItem(); j++)
3708 j.getItem()= GF2FalphaRep (j.getItem(), vBuf);
3709 prune (vBuf);
3710 }
3711 else // not able to pass to GF, pass to F_p(\alpha)
3712 {
3714 Variable v= rootOf (mipo);
3717 prune (v);
3718 }
3719 return factors;
3720 }
3721 else if (!GF && (alpha != w)) // we are in F_p(\alpha)
3722 {
3723 if (k == 1) // need factorization over F_p
3724 {
3725 int extDeg= degree (getMipo (alpha));
3726 extDeg++;
3728 Variable v= rootOf (mipo);
3731 prune (v);
3732 }
3733 else
3734 {
3735 if (beta == w)
3736 {
3739 bool primFail= false;
3740 Variable vBuf;
3742 ASSERT (!primFail, "failure in integer factorizer");
3743 if (primFail)
3744 ; //ERROR
3745 else
3747
3748 CFList source, dest;
3750 source, dest);
3753 prune (v);
3754 }
3755 else
3756 {
3759 bool primFail= false;
3760 Variable vBuf;
3761 ASSERT (!primFail, "failure in integer factorizer");
3762 if (primFail)
3763 ; //ERROR
3764 else
3765 imPrimElem= mapPrimElem (delta, beta, v);
3766
3767 CFList source, dest;
3769 source= CFList();
3770 dest= CFList();
3771 bufA= mapUp (bufA, beta, v, delta, imPrimElem, source, dest);
3774 prune (v);
3775 }
3776 }
3777 return factors;
3778 }
3779 else // we are in GF (p^k)
3780 {
3781 int p= getCharacteristic();
3783 bool extension= true;
3784 if (k == 1) // need factorization over F_p
3785 {
3786 extensionDeg++;
3787 if (pow ((double) p, (double) extensionDeg) < (1<<16))
3788 // pass to GF(p^k+1)
3789 {
3793 A= GF2FalphaRep (A, vBuf);
3796 factors= multiFactorize (A.mapinto(), info);
3797 prune (vBuf);
3798 }
3799 else // not able to pass to another GF, pass to F_p(\alpha)
3800 {
3804 A= GF2FalphaRep (A, vBuf);
3808 prune (vBuf);
3809 }
3810 }
3811 else // need factorization over GF (p^k)
3812 {
3813 if (pow ((double) p, (double) 2*extensionDeg) < (1<<16))
3814 // pass to GF(p^2k)
3815 {
3820 }
3821 else // not able to pass to GF (p^2k), pass to F_p (\alpha)
3822 {
3826 A= GF2FalphaRep (A, v1);
3829 bool primFail= false;
3830 Variable vBuf;
3832 if (primFail)
3833 ; //ERROR
3834 else
3836 CFList source, dest;
3838 source, dest);
3842 for (CFListIterator i= factors; i.hasItem(); i++)
3843 i.getItem()= Falpha2GFRep (i.getItem());
3844 prune (v1);
3845 }
3846 }
3847 return factors;
3848 }
3849}
void FACTORY_PUBLIC setCharacteristic(int c)
Definition cf_char.cc:28
static Variable chooseExtension(const Variable &alpha)
Definition cfModGcd.cc:420
#define ASSERT(expression, message)
Definition cf_assert.h:99
#define GaloisFieldDomain
Definition cf_defs.h:18
CanonicalForm randomIrredpoly(int i, const Variable &x)
computes a random monic irreducible univariate polynomial in x over Fp of degree i via NTL/FLINT
Definition cf_irred.cc:26
CanonicalForm mapPrimElem(const CanonicalForm &primElem, const Variable &alpha, const Variable &beta)
compute the image of a primitive element of in . We assume .
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
CanonicalForm mapinto() const
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 215 of file facFqFactorize.cc.

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

◆ extLiftBoundAdaption()

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

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

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

Definition at line 513 of file facFqFactorize.cc.

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

◆ extNonMonicFactorRecombination()

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

Definition at line 2420 of file facFqFactorize.cc.

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

◆ factorizationWRTDifferentSecondVars()

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

Definition at line 2183 of file facFqFactorize.cc.

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

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

◆ gcdFreeBasis()

void gcdFreeBasis ( CFFList factors1,
CFFList factors2 
)

gcd free basis of two lists of factors

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

Definition at line 1268 of file facFqFactorize.cc.

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

◆ getLeadingCoeffs()

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

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

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

Definition at line 2232 of file facFqFactorize.cc.

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

◆ henselLiftAndEarly()

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

hensel Lifting and early factor detection

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

Definition at line 984 of file facFqFactorize.cc.

988{
989 bool extension= info.isInExtension();
992
994
996 CFArray Pi;
997 int smallFactorDeg= 11; //tunable parameter
999 int adaptedLiftBound= 0;
1000 int liftBound= liftBounds[1];
1001
1002 earlySuccess= false;
1005 j++;
1006 CanonicalForm buf= j.getItem();
1008 MOD= CFList (power (Variable (2), liftBounds[0]));
1010 {
1012 }
1013 else if (smallFactorDeg >= degree (buf) + 1)
1014 {
1015 liftBounds[1]= degree (buf) + 1;
1017 if (Aeval.length() == 2)
1018 {
1019 if (!extension)
1022 degree (buf) + 1, MOD, liftBound);
1023 else
1027 (buf) + 1, MOD, liftBound);
1028 }
1029 else
1030 {
1031 if (!extension)
1033 degree (buf) + 1, MOD, liftBound);
1034 else
1036 evaluation, degree (buf) + 1,
1037 MOD, liftBound);
1038 }
1039 if (!earlySuccess)
1040 {
1041 result.insert (LC (buf, 1));
1045 Pi, diophant, Mat, MOD);
1046 }
1047 else
1049 }
1050 else if (smallFactorDeg < degree (buf) + 1)
1051 {
1054 if (Aeval.length() == 2)
1055 {
1056 if (!extension)
1059 liftBound);
1060 else
1064 }
1065 else
1066 {
1067 if (!extension)
1070 else
1073 liftBound);
1074 }
1075
1076 if (!earlySuccess)
1077 {
1078 result.insert (LC (buf, 1));
1080 Pi, diophant, Mat, MOD);
1081 if (Aeval.length() == 2)
1082 {
1083 if (!extension)
1085 earlySuccess, degree (buf) + 1,
1086 MOD, liftBound);
1087 else
1090 degree (buf) + 1, MOD,
1091 liftBound);
1092 }
1093 else
1094 {
1095 if (!extension)
1097 degree (buf) + 1, MOD,liftBound);
1098 else
1101 degree (buf) + 1, MOD,
1102 liftBound);
1103 }
1104 if (!earlySuccess)
1105 {
1106 result.insert (LC (buf, 1));
1110 Pi, diophant, Mat, MOD);
1111 }
1112 else
1114 }
1115 else
1117 }
1118
1119 MOD.append (power (Variable (3), liftBounds[1]));
1120
1121 if (Aeval.length() > 2)
1122 {
1124 j++;
1126 bufEval.append (j.getItem());
1127 j++;
1128 int liftBoundsLength= Aeval.getLast().level() - 1;
1129 for (int i= 2; i <= liftBoundsLength && j.hasItem(); i++, j++)
1130 {
1131 earlySuccess= false;
1132 result.insert (LC (bufEval.getFirst(), 1));
1133 bufEval.append (j.getItem());
1135 Mat= CFMatrix (liftBounds[i], result.length() - 1);
1136
1137 buf= j.getItem();
1140 liftBounds[i - 1], liftBounds[i]);
1141 else if (smallFactorDeg >= degree (buf) + 1)
1142 {
1144 liftBounds[i - 1], degree (buf) + 1);
1145
1146 if (Aeval.length() == i + 1)
1147 {
1148 if (!extension)
1151 degree (buf) + 1, MOD, liftBound);
1152 else
1156 }
1157 else
1158 {
1159 if (!extension)
1162 + 1, MOD, liftBound);
1163 else
1166 degree (buf) + 1, MOD, liftBound);
1167 }
1168
1169 if (!earlySuccess)
1170 {
1171 result.insert (LC (buf, 1));
1175 Pi, diophant, Mat, MOD);
1176 }
1177 else
1178 {
1180 }
1181 }
1182 else if (smallFactorDeg < degree (buf) + 1)
1183 {
1186
1187 if (Aeval.length() == i + 1)
1188 {
1189 if (!extension)
1193 else
1197 }
1198 else
1199 {
1200 if (!extension)
1204 else
1208 }
1209
1210 if (!earlySuccess)
1211 {
1212 result.insert (LC (buf, 1));
1214 degree (buf) + 1, Pi, diophant, Mat, MOD);
1215 if (Aeval.length() == i + 1)
1216 {
1217 if (!extension)
1220 degree (buf) + 1, MOD, liftBound);
1221 else
1224 info, evaluation, degree (buf) + 1, MOD,
1225 liftBound);
1226 }
1227 else
1228 {
1229 if (!extension)
1232 (buf) + 1, MOD, liftBound);
1233 else
1236 degree (buf) + 1, MOD, liftBound);
1237 }
1238
1239 if (!earlySuccess)
1240 {
1241 result.insert (LC (buf, 1));
1245 Pi, diophant, Mat, MOD);
1246 }
1247 else
1249 }
1250 else
1252 }
1253 MOD.append (power (Variable (i + 2), liftBounds[i]));
1255 }
1257 }
1258 else
1260
1261 if (earlySuccess)
1262 A= buf;
1263 return result;
1264}
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
[in,out]Aa poly
[in,out]LCmultiplierdivisor of LC (A,1)
[in,out]biFactorsbivariate factors
[in,out]leadingCoeffsleading coeffs
[in]oldAevalbivariate factors wrt. different second vars
[in]lengthAevallength of oldAeval
[in]evaluationevaluation point
[in]oldBiFactorsbivariate factors without LCmultiplier distributed on them

Definition at line 2614 of file facFqFactorize.cc.

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

Definition at line 2778 of file facFqFactorize.cc.

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

◆ LCHeuristic3()

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

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

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

Definition at line 2808 of file facFqFactorize.cc.

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

◆ LCHeuristic4()

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

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

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

Definition at line 2856 of file facFqFactorize.cc.

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

◆ LCHeuristicCheck()

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

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

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

Definition at line 2762 of file facFqFactorize.cc.

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

◆ lcmContent()

CanonicalForm lcmContent ( const CanonicalForm A,
CFList contentAi 
)

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

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

Definition at line 965 of file facFqFactorize.cc.

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

◆ liftBoundAdaption()

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

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

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

Definition at line 447 of file facFqFactorize.cc.

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

◆ listGCD()

static CanonicalForm listGCD ( const CFList L)
inlinestatic

Definition at line 74 of file facFqFactorize.cc.

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

◆ multiFactorize()

CFList multiFactorize ( const CanonicalForm F,
const ExtensionInfo info 
)

Definition at line 2928 of file facFqFactorize.cc.

2929{
2930 if (F.inCoeffDomain())
2931 return CFList (F);
2932
2934 // compress and find main Variable
2935 CFMap N;
2938 TIMING_END_AND_PRINT (fac_fq_compress, "time to compress poly over Fq: ")
2939
2940 A /= Lc (A); // make monic
2941
2942 Variable alpha= info.getAlpha();
2943 Variable beta= info.getBeta();
2944 CanonicalForm gamma= info.getGamma();
2945 CanonicalForm delta= info.getDelta();
2947 bool GF= (CFFactory::gettype() == GaloisFieldDomain);
2948 //univariate case
2949 if (F.isUnivariate())
2950 {
2951 if (extension == false)
2952 return uniFactorizer (F, alpha, GF);
2953 else
2954 {
2955 CFList source, dest;
2956 A= mapDown (F, info, source, dest);
2957 return uniFactorizer (A, beta, GF);
2958 }
2959 }
2960
2961 //bivariate case
2962 if (A.level() == 2)
2963 {
2965 if (buf.getFirst().inCoeffDomain())
2966 buf.removeFirst();
2967 return buf;
2968 }
2969
2970 Variable x= Variable (1);
2971 Variable y= Variable (2);
2972
2973 // remove content
2977 A /= lcmCont;
2978 TIMING_END_AND_PRINT (fac_fq_content, "time to extract content over Fq: ");
2979
2980 // trivial after content removal
2982 if (A.inCoeffDomain())
2983 {
2984 for (CFListIterator i= contentAi; i.hasItem(); i++)
2985 {
2986 if (i.getItem().inCoeffDomain())
2987 continue;
2988 else
2989 {
2990 lcmCont /= i.getItem();
2993 multiFactorize (i.getItem(), info));
2994 break;
2995 }
2996 }
2998 if (!extension)
3000 return contentAFactors;
3001 }
3002
3003 // factorize content
3006 TIMING_END_AND_PRINT (fac_fq_content, "time to factor content over Fq: ");
3007
3008 // univariate after content removal
3010 if (A.isUnivariate ())
3011 {
3014 decompress (factors, N);
3015 return factors;
3016 }
3017
3018 // check main variable
3020 int swapLevel= 0;
3024 Variable z;
3025 for (int i= 1; i <= A.level(); i++)
3026 {
3027 z= Variable (i);
3028 derivZ= deriv (bufA, z);
3029 if (derivZ.isZero())
3030 {
3031 if (i == 1)
3032 swapLevel= 1;
3033 else
3034 continue;
3035 }
3036 else
3037 {
3039 if (degree (gcdDerivZ) > 0 && !derivZ.isZero())
3040 {
3046 if (!extension)
3048 return factorsG;
3049 }
3050 else
3051 {
3052 if (swapLevel == 1)
3053 {
3054 swapLevel= i;
3055 bufA= swapvar (A, x, z);
3056 }
3057 A= bufA;
3058 break;
3059 }
3060 }
3061 }
3063 "time to check main var over Fq: ");
3065 "time to preprocess poly and extract content over Fq: ");
3066
3068 bool fail= false;
3069 int swapLevel2= 0;
3070 //int level;
3071 int factorNums= 3;
3074 int lift, bufLift, lengthAeval2= A.level()-2;
3075 double logarithm= (double) ilog2 (totaldegree (A));
3076 logarithm /= log2exp;
3078 if (factorNums < (int) logarithm)
3082 int counter;
3083 int differentSecondVar= 0;
3084 // several bivariate factorizations
3086 for (int i= 0; i < factorNums; i++)
3087 {
3088 counter= 0;
3089 bufA= A;
3090 bufAeval= CFList();
3094 "time to find evaluation point over Fq: ");
3095 evalPoly= 0;
3096
3097 if (fail && (i == 0))
3098 {
3099 /*if (!swapLevel) //uncomment to reenable search for new main variable
3100 level= 2;
3101 else
3102 level= swapLevel + 1;*/
3103
3104 //CanonicalForm g;
3105 //swapLevel2= newMainVariableSearch (A, Aeval, evaluation, alpha, level, g);
3106
3107 /*if (!swapLevel2) // need to pass to an extension
3108 {*/
3112 delete [] bufAeval2;
3113 delete [] Aeval2;
3114 return factors;
3115 /*}
3116 else
3117 {
3118 if (swapLevel2 == -1)
3119 {
3120 CFList factorsG=
3121 Union (multiFactorize (g, info),
3122 multiFactorize (A/g, info));
3123 appendSwapDecompress (factorsG, contentAFactors, N, swapLevel, x);
3124 if (!extension)
3125 normalize (factorsG);
3126 delete [] bufAeval2;
3127 delete [] Aeval2;
3128 return factorsG;
3129 }
3130 fail= false;
3131 bufAeval= Aeval;
3132 bufA= A;
3133 bufEvaluation= evaluation;
3134 }*/ //end uncomment
3135 }
3136 else if (fail && (i > 0))
3137 break;
3138
3142 "time for evaluation wrt diff second vars over Fq: ");
3143
3144 for (int j= 0; j < lengthAeval2; j++)
3145 {
3146 if (!bufAeval2[j].isEmpty())
3147 counter++;
3148 }
3149
3150 bufLift= degree (A, y) + 1 + degree (LC(A, x), y);
3151
3153 if (!GF && alpha.level() == 1)
3155 else if (GF)
3157 else
3160 "time for bivariate factorization: ");
3162
3163 if (bufBiFactors.length() == 1)
3164 {
3165 if (extension)
3166 {
3167 CFList source, dest;
3168 A= mapDown (A, info, source, dest);
3169 }
3170 factors.append (A);
3172 swapLevel2, x);
3173 if (!extension)
3175 delete [] bufAeval2;
3176 delete [] Aeval2;
3177 return factors;
3178 }
3179
3180 if (i == 0)
3181 {
3182 Aeval= bufAeval;
3185 lift= bufLift;
3186 for (int j= 0; j < lengthAeval2; j++)
3187 Aeval2 [j]= bufAeval2 [j];
3188 differentSecondVar= counter;
3189 }
3190 else
3191 {
3192 if (bufBiFactors.length() < biFactors.length() ||
3193 ((bufLift < lift) && (bufBiFactors.length() == biFactors.length())) ||
3194 counter > differentSecondVar)
3195 {
3196 Aeval= bufAeval;
3199 lift= bufLift;
3200 for (int j= 0; j < lengthAeval2; j++)
3201 Aeval2 [j]= bufAeval2 [j];
3202 differentSecondVar= counter;
3203 }
3204 }
3205 int k= 0;
3206 for (CFListIterator j= bufEvaluation; j.hasItem(); j++, k++)
3207 evalPoly += j.getItem()*power (x, k);
3208 list.append (evalPoly);
3209 }
3210
3211 delete [] bufAeval2;
3212
3213 sortList (biFactors, x);
3214
3215 int minFactorsLength;
3216 bool irred= false;
3220 "time for bivariate factorization wrt diff second vars over Fq: ");
3221
3223 "total time for eval and bivar factors over Fq: ");
3224 if (irred)
3225 {
3226 if (extension)
3227 {
3228 CFList source, dest;
3229 A= mapDown (A, info, source, dest);
3230 }
3231 factors.append (A);
3233 swapLevel2, x);
3234 if (!extension)
3236 delete [] Aeval2;
3237 return factors;
3238 }
3239
3240 if (minFactorsLength == 0)
3242 else if (biFactors.length() > minFactorsLength)
3245
3247
3249
3251
3252 if (minFactorsLength == 1)
3253 {
3254 if (extension)
3255 {
3256 CFList source, dest;
3257 A= mapDown (A, info, source, dest);
3258 }
3259 factors.append (A);
3261 swapLevel2, x);
3262 if (!extension)
3264 delete [] Aeval2;
3265 return factors;
3266 }
3267
3269 {
3270 bool zeroOccured= false;
3271 for (CFListIterator iter= evaluation; iter.hasItem(); iter++)
3272 {
3273 if (iter.getItem().isZero())
3274 {
3275 zeroOccured= true;
3276 break;
3277 }
3278 }
3279 if (!zeroOccured)
3280 {
3283 if (factors.length() == biFactors.length())
3284 {
3285 if (extension)
3287
3289 swapLevel2, x);
3290 if (!extension)
3292 delete [] Aeval2;
3293 return factors;
3294 }
3295 else
3296 factors= CFList();
3297 //TODO case where factors.length() > 0
3298 }
3299 }
3300
3301 CFList * oldAeval= new CFList [lengthAeval2]; //TODO use bufAeval2 for this
3302 for (int i= 0; i < lengthAeval2; i++)
3303 oldAeval[i]= Aeval2[i];
3304
3306
3308 for (CFListIterator i= biFactors; i.hasItem(); i++)
3309 biFactorsLCs.append (LC (i.getItem(), 1));
3310
3311 Variable v;
3315
3316 if (v.level() != 1)
3318 uniFactors, v);
3319
3322
3324 bool LCmultiplierIsConst= LCmultiplier.inCoeffDomain();
3326
3329
3330 //prepare leading coefficients
3334
3338 bufA= A;
3341 {
3342 testVars= Variable (2);
3343 for (int i= 0; i < lengthAeval2; i++)
3344 {
3345 if (!oldAeval[i].isEmpty())
3346 testVars *= oldAeval[i].getFirst().mvar();
3347 }
3348 }
3350 "time to precompute LC over Fq: ");
3351
3354 bool LCheuristic= false;
3356 factors))
3357 {
3358 int check= biFactors.length();
3359 int * index= new int [factors.length()];
3362
3363 if (check == factors.length())
3364 {
3365 if (extension)
3367
3368 if (v.level() != 1)
3369 {
3370 for (iter= factors; iter.hasItem(); iter++)
3371 iter.getItem()= swapvar (iter.getItem(), v, y);
3372 }
3373
3375 swapLevel2, x);
3376 if (!extension)
3378 delete [] index;
3379 delete [] Aeval2;
3381 "time for successful LucksWang over Fq: ");
3382 return factors;
3383 }
3384 else if (factors.length() > 0)
3385 {
3386 int oneCount= 0;
3387 CFList l;
3388 for (int i= 0; i < check; i++)
3389 {
3390 if (index[i] == 1)
3391 {
3393 for (int j=1; j <= i-oneCount; j++)
3394 iter++;
3395 iter.remove (1);
3396 for (int j= 0; j < lengthAeval2; j++)
3397 {
3398 l= leadingCoeffs2[j];
3399 iter= l;
3400 for (int k=1; k <= i-oneCount; k++)
3401 iter++;
3402 iter.remove (1);
3404 }
3405 oneCount++;
3406 }
3407 }
3409 factors= CFList();
3410 }
3411 else if (!LCmultiplierIsConst && factors.length() == 0)
3412 {
3413 LCheuristic= true;
3416 bool foundTrueMultiplier= false;
3420 {
3421 A= oldA;
3423 for (int i= lengthAeval2-1; i > -1; i--)
3427 }
3428 else
3429 {
3430 bool foundMultiplier= false;
3433
3434 // coming from above: divide out more LCmultiplier if possible
3435 if (foundMultiplier)
3436 {
3437 foundMultiplier= false;
3441 }
3442 else
3443 {
3447 {
3450 }
3451 }
3452
3453 // patch everything together again
3455 for (int i= lengthAeval2-1; i > -1; i--)
3459 }
3460 factors= CFList();
3462 {
3463 LCheuristic= false;
3464 A= bufA;
3468 }
3469 }
3470 else
3471 factors= CFList();
3472 delete [] index;
3473 }
3474 TIMING_END_AND_PRINT (fac_fq_luckswang, "time for LucksWang over Fq: ");
3475
3479 {
3480 LCheuristic= true;
3483
3485 for (int i= lengthAeval2-1; i > -1; i--)
3489
3491 {
3492 LCheuristic= false;
3493 A= bufA;
3497 }
3498 }
3499 TIMING_END_AND_PRINT (fac_fq_lcheuristic, "time for Lc heuristic over Fq: ");
3500
3504
3505 for (iter= biFactors; iter.hasItem(); iter++)
3506 iter.getItem()= iter.getItem () (y + evaluation.getLast(), y);
3507
3508 for (int i= 0; i < lengthAeval2-1; i++)
3510 for (iter= leadingCoeffs2[lengthAeval2-1]; iter.hasItem(); iter++)
3511 {
3512 iter.getItem()= shift2Zero (iter.getItem(), list, evaluation);
3513 for (int i= A.level() - 4; i > -1; i--)
3514 {
3515 if (i + 1 == lengthAeval2-1)
3516 leadingCoeffs2[i].append (iter.getItem() (0, i + 4));
3517 else
3518 leadingCoeffs2[i].append (leadingCoeffs2[i+1].getLast() (0, i + 4));
3519 }
3520 }
3522 "time to shift evaluation point to zero: ");
3523
3524 CFArray Pi;
3526 int* liftBounds= new int [A.level() - 1];
3527 int liftBoundsLength= A.level() - 1;
3528 for (int i= 0; i < liftBoundsLength; i++)
3529 liftBounds [i]= degree (A, i + 2) + 1;
3530
3532 bool noOneToOne= false;
3537 "time for non monic hensel lifting over Fq: ");
3538
3539 if (!noOneToOne)
3540 {
3541 int check= factors.length();
3542 A= oldA;
3546 "time to recover factors over Fq: ");
3547 if (check != factors.length())
3548 noOneToOne= true;
3549 else
3551
3552 if (extension && !noOneToOne)
3554 }
3555 if (noOneToOne)
3556 {
3558 {
3559 A= bufA;
3562 delete [] liftBounds;
3563 LCheuristic= false;
3564 goto tryAgainWithoutHeu;
3565 //something probably went wrong in the heuristic
3566 }
3567
3570 for (iter= biFactors; iter.hasItem(); iter++)
3571 iter.getItem()= iter.getItem () (y + evaluation.getLast(), y);
3575 lift= degree (i.getItem(), 2) + degree (LC (i.getItem(), 1)) + 1;
3576 i++;
3577
3578 for (; i.hasItem(); i++)
3579 lift= tmax (lift,
3580 degree (i.getItem(), 2) + degree (LC (i.getItem(), 1)) + 1);
3581
3582 lift= tmax (degree (Aeval.getFirst() , 2) + 1, lift);
3583
3584 i= biFactors;
3585 yToLift= power (y, lift);
3587 for (; i.hasItem(); i++)
3588 {
3589 LCA= LC (i.getItem(), 1);
3590 extgcd (LCA, yToLift, LCA, dummy);
3591 i.getItem()= mod (i.getItem()*LCA, yToLift);
3592 }
3593
3594 liftBoundsLength= F.level() - 1;
3596
3597 CFList MOD;
3598 bool earlySuccess;
3605 "time for hensel lifting over Fq: ");
3606
3607 if (!extension)
3608 {
3612 "time for factor recombination: ");
3613 }
3614 else
3615 {
3619 "time for factor recombination: ");
3620 }
3621
3622 if (earlySuccess)
3624 if (!extension)
3625 {
3626 for (CFListIterator i= factors; i.hasItem(); i++)
3627 {
3628 int kk= Aeval.getLast().level();
3629 for (CFListIterator j= evaluation; j.hasItem(); j++, kk--)
3630 {
3631 if (i.getItem().level() < kk)
3632 continue;
3633 i.getItem()= i.getItem() (Variable (kk) - j.getItem(), kk);
3634 }
3635 }
3636 }
3637 }
3638
3639 if (v.level() != 1)
3640 {
3641 for (CFListIterator iter= factors; iter.hasItem(); iter++)
3642 iter.getItem()= swapvar (iter.getItem(), v, y);
3643 }
3644
3647 decompress (factors, N);
3648 if (!extension)
3650
3651 delete[] liftBounds;
3652
3653 return factors;
3654}
#define swap(_i, _j)
int ilog2(const CanonicalForm &a)
int totaldegree(const CanonicalForm &f)
int totaldegree ( const CanonicalForm & f )
Definition cf_ops.cc:523
const CanonicalForm CFMap CFMap & N
Definition cfEzgcd.cc:56
static const double log2exp
Definition cfEzgcd.cc:45
CanonicalForm decompress(const CanonicalForm &F, const mpz_t *inverseM, const mpz_t *A)
decompress a bivariate poly
CanonicalForm extgcd(const CanonicalForm &f, const CanonicalForm &g, CanonicalForm &a, CanonicalForm &b)
CanonicalForm extgcd ( const CanonicalForm & f, const CanonicalForm & g, CanonicalForm & a,...
class CFMap
Definition cf_map.h:85
CFFList append(const CFFList &Inputlist, const CFFactor &TheFactor)
void appendSwapDecompress(CFList &factors1, const CFList &factors2, const CFList &factors3, const bool swap1, const bool swap2, const CFMap &N)
first swap Variables in factors1 if necessary, then append factors2 and factors3 on factors1 and fina...
else L getLast()(0
CFList uniFactorizer(const CanonicalForm &A, const Variable &alpha, const bool &GF)
Univariate factorization of squarefree monic polys over finite fields via NTL. If the characteristic ...
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)(void) system(sys)
template List< Variable > Union(const List< Variable > &, const List< Variable > &)
VAR int check
Definition libparse.cc:1106
ideal lift(const ideal J, const ring r, const ideal inI, const ring s)
Definition lift.cc:26
const signed long ceil(const ampf< Precision > &x)
Definition amp.h:788
static poly normalize(poly next_p, ideal add_generators, syStrategy syzstr, int *g_l, int *p_l, int crit_comp)
Definition syz3.cc:1027
#define TIMING_START(t)
Definition timing.h:92
#define TIMING_END_AND_PRINT(t, msg)
Definition timing.h:94

◆ myCompress()

CanonicalForm myCompress ( const CanonicalForm F,
CFMap N 
)

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

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

Definition at line 133 of file facFqFactorize.cc.

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

◆ myContent() [1/2]

static CanonicalForm myContent ( const CanonicalForm F)
inlinestatic

Definition at line 58 of file facFqFactorize.cc.

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

◆ myContent() [2/2]

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

Definition at line 101 of file facFqFactorize.cc.

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

◆ newMainVariableSearch()

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

Definition at line 924 of file facFqFactorize.cc.

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

◆ precomputeLeadingCoeff()

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

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

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

Definition at line 1478 of file facFqFactorize.cc.

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

◆ prepareLeadingCoeffs()

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

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

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

Definition at line 2381 of file facFqFactorize.cc.

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

◆ prodEval()

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

Definition at line 2011 of file facFqFactorize.cc.

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

◆ recombination()

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

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

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

Definition at line 2113 of file facFqFactorize.cc.

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

◆ refineBiFactors()

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

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

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

Definition at line 2334 of file facFqFactorize.cc.

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

◆ sortByUniFactors()

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

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

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

Definition at line 2250 of file facFqFactorize.cc.

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

◆ testFactors()

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

Definition at line 1384 of file facFqFactorize.cc.

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

◆ TIMING_DEFINE_PRINT()

TIMING_DEFINE_PRINT ( fac_fq_bi_factorizer  ) const &