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

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

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

Go to the source code of this file.

Functions

 TIMING_DEFINE_PRINT (fac_fq_squarefree) TIMING_DEFINE_PRINT(fac_fq_factor_squarefree) CFList multiFactorize(const CanonicalForm &F
 Factorization over a finite field.
 
CFList FpSqrfFactorize (const CanonicalForm &F)
 factorize a squarefree multivariate polynomial over $ F_{p} $
 
CFList FqSqrfFactorize (const CanonicalForm &F, const Variable &alpha)
 factorize a squarefree multivariate polynomial over $ F_{p} (\alpha ) $
 
CFList GFSqrfFactorize (const CanonicalForm &F)
 factorize a squarefree multivariate polynomial over GF
 
CFFList FpFactorize (const CanonicalForm &G, bool substCheck=true)
 factorize a multivariate polynomial over $ F_{p} $
 
CFFList FqFactorize (const CanonicalForm &G, const Variable &alpha, bool substCheck=true)
 factorize a multivariate polynomial over $ F_{p} (\alpha ) $
 
CFFList GFFactorize (const CanonicalForm &G, bool substCheck=true)
 factorize a multivariate polynomial over GF
 
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.
 
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
 
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.
 
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
 
CFList extFactorize (const CanonicalForm &F, const ExtensionInfo &info)
 Factorization over an extension of initial field.
 
CanonicalForm lcmContent (const CanonicalForm &A, CFList &contentAi)
 compute the LCM of the contents of A wrt to each variable occuring in A.
 
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
 
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
 
void refineBiFactors (const CanonicalForm &A, CFList &biFactors, CFList *const &factors, const CFList &evaluation, int minFactorsLength)
 refine a bivariate factorization of A with l factors to one with minFactorsLength if possible
 
CFList buildUniFactors (const CFList &biFactors, const CanonicalForm &evalPoint, const Variable &y)
 plug in evalPoint for y in a list of polys
 
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
 
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 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 leadingCoeffReconstruction (const CanonicalForm &F, const CFList &factors, const CFList &M)
 obtain factors of F by reconstructing their leading coeffs
 
CFList distributeContent (const CFList &L, const CFList *differentSecondVarFactors, int length)
 distribute content
 
void gcdFreeBasis (CFFList &factors1, CFFList &factors2)
 gcd free basis of two lists of factors
 
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 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.
 

Variables

const ExtensionInfoinfo
 < [in] sqrfree poly
 

Detailed Description

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

Author
Martin Lee

Definition in file facFqFactorize.h.

Function Documentation

◆ buildUniFactors()

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

plug in evalPoint for y in a list of polys

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

Definition at line 2321 of file facFqFactorize.cc.

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

◆ changeSecondVariable()

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

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

Parameters
A[in,out] a multivariate poly
biFactors[in,out] bivariate factors
evaluation[in,out] evaluation point
oldAeval[in,out] old bivariate factors wrt. different second vars
[in]lengthAeval2length of oldAeval
[in]uniFactorsunivariate factors
[in]wsome variable

Definition at line 2544 of file facFqFactorize.cc.

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

◆ distributeContent()

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

distribute content

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

Definition at line 1295 of file facFqFactorize.cc.

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

◆ distributeLCmultiplier()

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

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

Parameters
A[in,out] some poly
leadingCoeffs[in,out] leading coefficients
biFactors[in,out] bivariate factors
[in]evaluationeval. point
[in]LCmultiplermultiplier

Definition at line 2591 of file facFqFactorize.cc.

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

◆ earlyFactorDetect()

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

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

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

Definition at line 612 of file facFqFactorize.cc.

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

◆ evalPoints()

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

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

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

Definition at line 751 of file facFqFactorize.cc.

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

◆ evaluationWRTDifferentSecondVars()

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

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

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

Definition at line 1966 of file facFqFactorize.cc.

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

◆ extEarlyFactorDetect()

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

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

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

Definition at line 665 of file facFqFactorize.cc.

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

◆ extFactorize()

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

Factorization over an extension of initial field.

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

Factorization over an extension of initial field.

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

Definition at line 3661 of file facFqFactorize.cc.

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

◆ extFactorRecombination()

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

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

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

Definition at line 216 of file facFqFactorize.cc.

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

◆ extLiftBoundAdaption()

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

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

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

Definition at line 514 of file facFqFactorize.cc.

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

◆ factorRecombination()

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

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

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

Definition at line 361 of file facFqFactorize.cc.

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

◆ FpFactorize()

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

factorize a multivariate polynomial over $ F_{p} $

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

Definition at line 101 of file facFqFactorize.h.

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

◆ FpSqrfFactorize()

CFList FpSqrfFactorize ( const CanonicalForm & F)
inline

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

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

Definition at line 47 of file facFqFactorize.h.

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

◆ FqFactorize()

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

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

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

Definition at line 184 of file facFqFactorize.h.

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

◆ FqSqrfFactorize()

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

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

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

Definition at line 64 of file facFqFactorize.h.

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

◆ gcdFreeBasis()

void gcdFreeBasis ( CFFList & factors1,
CFFList & factors2 )

gcd free basis of two lists of factors

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

Definition at line 1269 of file facFqFactorize.cc.

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

◆ getLeadingCoeffs()

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

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

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

Definition at line 2233 of file facFqFactorize.cc.

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

◆ GFFactorize()

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

factorize a multivariate polynomial over GF

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

Definition at line 267 of file facFqFactorize.h.

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

◆ GFSqrfFactorize()

CFList GFSqrfFactorize ( const CanonicalForm & F)
inline

factorize a squarefree multivariate polynomial over GF

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

Definition at line 82 of file facFqFactorize.h.

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

◆ henselLiftAndEarly()

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

hensel Lifting and early factor detection

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

Definition at line 985 of file facFqFactorize.cc.

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

◆ LCHeuristic()

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

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

Parameters
A[in,out] a poly
LCmultiplier[in,out] divisor of LC (A,1)
biFactors[in,out] bivariate factors
leadingCoeffs[in,out] leading coeffs
[in]oldAevalbivariate factors wrt. different second vars
[in]lengthAevallength of oldAeval
[in]evaluationevaluation point
[in]oldBiFactorsbivariate factors without LCmultiplier distributed on them

Definition at line 2615 of file facFqFactorize.cc.

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

◆ LCHeuristic2()

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

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

Parameters
[in]LCmultiplierdivisor of LC (A,1)
[in]factorsresult of LucksWangSparseHeuristic
leadingCoeffs[in,out] leading coeffs
contents[in,out] content of factors
LCs[in,out] LC of factors divided by content of factors
foundTrueMultiplier[in,out] success?

Definition at line 2779 of file facFqFactorize.cc.

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

◆ LCHeuristic3()

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

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

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

Definition at line 2809 of file facFqFactorize.cc.

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

◆ LCHeuristic4()

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

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

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

Definition at line 2857 of file facFqFactorize.cc.

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

◆ LCHeuristicCheck()

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

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

Parameters
[in]LCsleading coeffs computed
[in]contentscontent of factors
A[in,out] oldA*LCmultiplier^m
[in]oldAsome poly
leadingCoeffs[in,out] leading coefficients
foundTrueMultiplier[in,out] success?

Definition at line 2763 of file facFqFactorize.cc.

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

◆ lcmContent()

CanonicalForm lcmContent ( const CanonicalForm & A,
CFList & contentAi )

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

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

Definition at line 966 of file facFqFactorize.cc.

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

◆ leadingCoeffReconstruction()

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

obtain factors of F by reconstructing their leading coeffs

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

◆ liftBoundAdaption()

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

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

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

Definition at line 448 of file facFqFactorize.cc.

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

◆ myCompress()

CanonicalForm myCompress ( const CanonicalForm & F,
CFMap & N )

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

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

Definition at line 134 of file facFqFactorize.cc.

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

◆ precomputeLeadingCoeff()

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

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

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

Definition at line 1479 of file facFqFactorize.cc.

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

◆ prepareLeadingCoeffs()

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

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

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

Definition at line 2382 of file facFqFactorize.cc.

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

◆ recombination()

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

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

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

Definition at line 2114 of file facFqFactorize.cc.

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

◆ refineBiFactors()

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

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

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

Definition at line 2335 of file facFqFactorize.cc.

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

◆ sortByUniFactors()

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

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

Parameters
Aeval[in,out] array of bivariate factors
[in]AevalLengthlength of Aeval
uniFactors[in,out] univariate factors
biFactors[in,out] bivariate factors
[in]evaluationevaluation point

Definition at line 2251 of file facFqFactorize.cc.

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

◆ TIMING_DEFINE_PRINT()

TIMING_DEFINE_PRINT ( fac_fq_squarefree ) const &

Factorization over a finite field.

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

Variable Documentation

◆ info

< [in] sqrfree poly

< [in] info about extension

Definition at line 37 of file facFqFactorize.h.