My Project  UNKNOWN_GIT_VERSION
Macros | Functions | Variables
facAbsBiFact.cc File Reference
#include "config.h"
#include "timing.h"
#include "debug.h"
#include "facAbsBiFact.h"
#include "facBivar.h"
#include "facFqBivar.h"
#include "cf_reval.h"
#include "cf_primes.h"
#include "cf_algorithm.h"
#include "FLINTconvert.h"
#include <flint/fmpz_poly_factor.h>
#include "NTLconvert.h"
#include <NTL/LLL.h>

Go to the source code of this file.

Macros

#define slong   long
 

Functions

 TIMING_DEFINE_PRINT (fac_Qa_factorize) TIMING_DEFINE_PRINT(fac_evalpoint) CFAFList uniAbsFactorize(const CanonicalForm &F
 
 if (degree(F)==1)
 
 if (iter.getItem().factor().inCoeffDomain())
 
 for (;iter.hasItem();iter++)
 
result insert (CFAFactor(LcF, 1, 1))
 
int choosePoint (const CanonicalForm &F, int tdegF, CFArray &eval, bool rec, int absValue)
 
CFAFList absBiFactorizeMain (const CanonicalForm &G, bool full)
 main absolute factorization routine, expects bivariate poly which is irreducible over Q More...
 

Variables

bool full
 
CanonicalForm LcF = 1
 
Variable alpha = rootOf (F)
 
CFFList QaFactors = factorize (F, alpha)
 
CFFListIterator iter = QaFactors
 
return result
 

Detailed Description

Author
Martin Lee

Definition in file facAbsBiFact.cc.

Macro Definition Documentation

◆ slong

#define slong   long

Function Documentation

◆ absBiFactorizeMain()

CFAFList absBiFactorizeMain ( const CanonicalForm F,
bool  full = false 
)

main absolute factorization routine, expects bivariate poly which is irreducible over Q

Returns
absBiFactorizeMain returns a list whose entries contain three entities: an absolute irreducible factor, an irreducible univariate polynomial that defines the minimal field extension over which the irreducible factor is defined (note: in case the factor is already defined over Q[t]/(t), 1 is returned as defining poly), and the multiplicity of the absolute irreducible factor

Definition at line 187 of file facAbsBiFact.cc.

188 {
190  bool isRat= isOn (SW_RATIONAL);
191  Off (SW_RATIONAL);
192  F /= icontent (F);
193  On (SW_RATIONAL);
194 
195  mpz_t * M=new mpz_t [4];
196  mpz_init (M[0]);
197  mpz_init (M[1]);
198  mpz_init (M[2]);
199  mpz_init (M[3]);
200 
201  mpz_t * S=new mpz_t [2];
202  mpz_init (S[0]);
203  mpz_init (S[1]);
204 
205  F= compress (F, M, S);
206 
207  if (F.isUnivariate())
208  {
209  if (degree (F) == 1)
210  {
211  mpz_clear (M[0]);
212  mpz_clear (M[1]);
213  mpz_clear (M[2]);
214  mpz_clear (M[3]);
215  delete [] M;
216 
217  mpz_clear (S[0]);
218  mpz_clear (S[1]);
219  delete [] S;
220  if (!isRat)
221  Off (SW_RATIONAL);
222  return CFAFList (CFAFactor (G, 1, 1));
223  }
225  if (result.getFirst().factor().inCoeffDomain())
226  result.removeFirst();
228  iter.getItem()= CFAFactor (decompress (iter.getItem().factor(), M, S),
229  iter.getItem().minpoly(),iter.getItem().exp());
230  mpz_clear (M[0]);
231  mpz_clear (M[1]);
232  mpz_clear (M[2]);
233  mpz_clear (M[3]);
234  delete [] M;
235 
236  mpz_clear (S[0]);
237  mpz_clear (S[1]);
238  delete [] S;
239  if (!isRat)
240  Off (SW_RATIONAL);
241  return result;
242  }
243 
244  if (degree (F, 1) == 1 || degree (F, 2) == 1)
245  {
246  mpz_clear (M[0]);
247  mpz_clear (M[1]);
248  mpz_clear (M[2]);
249  mpz_clear (M[3]);
250  delete [] M;
251 
252  mpz_clear (S[0]);
253  mpz_clear (S[1]);
254  delete [] S;
255  if (!isRat)
256  Off (SW_RATIONAL);
257  return CFAFList (CFAFactor (G, 1, 1));
258  }
259  int minTdeg, tdegF= totaldegree (F);
260  CanonicalForm Fp, smallestFactor;
261  int p;
262  CFFList factors;
263  Variable alpha;
264  bool rec= false;
265  Variable x= Variable (1);
266  Variable y= Variable (2);
267  CanonicalForm bufF= F;
269  CFArray eval= CFArray (2);
270  int absValue= 1;
271 differentevalpoint:
272  while (1)
273  {
274  TIMING_START (fac_evalpoint);
275  p= choosePoint (F, tdegF, eval, rec, absValue);
276  TIMING_END_AND_PRINT (fac_evalpoint, "time to find eval point: ");
277 
278  //after here isOn (SW_RATIONAL)==false
280  Fp=F.mapinto();
281  factors= factorize (Fp);
282 
283  if (factors.getFirst().factor().inCoeffDomain())
284  factors.removeFirst();
285 
286  if (factors.length() == 1 && factors.getFirst().exp() == 1)
287  {
288  if (absIrredTest (Fp))
289  {
290  if (isRat)
291  On (SW_RATIONAL);
293  mpz_clear (M[0]);
294  mpz_clear (M[1]);
295  mpz_clear (M[2]);
296  mpz_clear (M[3]);
297  delete [] M;
298 
299  mpz_clear (S[0]);
300  mpz_clear (S[1]);
301  delete [] S;
302  return CFAFList (CFAFactor (G, 1, 1));
303  }
304  else
305  {
306  setCharacteristic (0);
308  {
309  if (isRat)
310  On (SW_RATIONAL);
311  mpz_clear (M[0]);
312  mpz_clear (M[1]);
313  mpz_clear (M[2]);
314  mpz_clear (M[3]);
315  delete [] M;
316 
317  mpz_clear (S[0]);
318  mpz_clear (S[1]);
319  delete [] S;
320  return CFAFList (CFAFactor (G, 1, 1));
321  }
322  rec= true;
323  continue;
324  }
325  }
326  iter= factors;
327  smallestFactor= iter.getItem().factor();
328  while (smallestFactor.isUnivariate() && iter.hasItem())
329  {
330  iter++;
331  if (!iter.hasItem())
332  break;
333  smallestFactor= iter.getItem().factor();
334  }
335 
336  minTdeg= totaldegree (smallestFactor);
337  if (iter.hasItem())
338  iter++;
339  for (; iter.hasItem(); iter++)
340  {
341  if (!iter.getItem().factor().isUnivariate() &&
342  (totaldegree (iter.getItem().factor()) < minTdeg))
343  {
344  smallestFactor= iter.getItem().factor();
345  minTdeg= totaldegree (smallestFactor);
346  }
347  }
348  if (tdegF % minTdeg == 0)
349  break;
351  rec=true;
352  }
353  CanonicalForm Gp= Fp/smallestFactor;
354  Gp= Gp /Lc (Gp);
355 
356  CanonicalForm Gpy= Gp (eval[0].mapinto(), 1);
357  CanonicalForm smallestFactorEvaly= smallestFactor (eval[0].mapinto(),1);
358  CanonicalForm Gpx= Gp (eval[1].mapinto(), 2);
359  CanonicalForm smallestFactorEvalx= smallestFactor (eval[1].mapinto(),2);
360 
361  bool xValid= !(Gpx.inCoeffDomain() || smallestFactorEvalx.inCoeffDomain() ||
362  !gcd (Gpx, smallestFactorEvalx).inCoeffDomain());
363  bool yValid= !(Gpy.inCoeffDomain() || smallestFactorEvaly.inCoeffDomain() ||
364  !gcd (Gpy, smallestFactorEvaly).inCoeffDomain());
365  if (!xValid || !yValid)
366  {
367  rec= true;
368  setCharacteristic (0);
369  goto differentevalpoint;
370  }
371 
372  setCharacteristic (0);
373 
375 
376  CFArray mipos= CFArray (2);
377  CFFList mipoFactors;
378  for (int i= 1; i < 3; i++)
379  {
380  CanonicalForm Fi= F(eval[i-1],i);
381 
382  int s= tdegF/minTdeg + 1;
383  CanonicalForm bound= power (maxNorm (Fi), 2*(s-1));
384  bound *= power (CanonicalForm (s),s-1);
385  bound *= power (CanonicalForm (2), ((s-1)*(s-1))/2); //possible int overflow
386 
387  CanonicalForm B = p;
388  long k = 1L;
389  while ( B < bound ) {
390  B *= p;
391  k++;
392  }
393 
394  //TODO take floor (log2(k))
395  k= k+1;
396 #ifdef HAVE_FLINT
397  fmpz_poly_t FLINTFi;
398  convertFacCF2Fmpz_poly_t (FLINTFi, Fi);
400  nmod_poly_t FLINTFpi, FLINTGpi;
401  if (i == 2)
402  {
403  convertFacCF2nmod_poly_t (FLINTFpi,
404  smallestFactorEvalx/lc (smallestFactorEvalx));
405  convertFacCF2nmod_poly_t (FLINTGpi, Gpx/lc (Gpx));
406  }
407  else
408  {
409  convertFacCF2nmod_poly_t (FLINTFpi,
410  smallestFactorEvaly/lc (smallestFactorEvaly));
411  convertFacCF2nmod_poly_t (FLINTGpi, Gpy/lc (Gpy));
412  }
413  nmod_poly_factor_t nmodFactors;
414  nmod_poly_factor_init (nmodFactors);
415  nmod_poly_factor_insert (nmodFactors, FLINTFpi, 1L);
416  nmod_poly_factor_insert (nmodFactors, FLINTGpi, 1L);
417 
418  // the following fix is due to interface changes from FLINT 2.3 -> FLINT 2.4
419 # ifndef slong
420 # define slong long
421 # endif
422 
423  slong * link= new slong [2];
424  fmpz_poly_t *v= new fmpz_poly_t[2];
425  fmpz_poly_t *w= new fmpz_poly_t[2];
426  fmpz_poly_init(v[0]);
427  fmpz_poly_init(v[1]);
428  fmpz_poly_init(w[0]);
429  fmpz_poly_init(w[1]);
430 
431  fmpz_poly_factor_t liftedFactors;
432  fmpz_poly_factor_init (liftedFactors);
433  _fmpz_poly_hensel_start_lift (liftedFactors, link, v, w, FLINTFi,
434  nmodFactors, k);
435 
436  nmod_poly_factor_clear (nmodFactors);
437  nmod_poly_clear (FLINTFpi);
438  nmod_poly_clear (FLINTGpi);
439 
441  CanonicalForm liftedSmallestFactor=
442  convertFmpz_poly_t2FacCF ((fmpz_poly_t &)liftedFactors->p[0],x);
443 
444  CanonicalForm otherFactor=
445  convertFmpz_poly_t2FacCF ((fmpz_poly_t &)liftedFactors->p[1],x);
446  modpk pk= modpk (p, k);
447 #else
448  modpk pk= modpk (p, k);
449  ZZX NTLFi=convertFacCF2NTLZZX (pk (Fi*pk.inverse (lc(Fi))));
451 
452  if (fac_NTL_char != p)
453  {
454  fac_NTL_char= p;
455  zz_p::init (p);
456  }
457  zz_pX NTLFpi, NTLGpi;
458  if (i == 2)
459  {
460  NTLFpi=convertFacCF2NTLzzpX (smallestFactorEvalx/lc(smallestFactorEvalx));
461  NTLGpi=convertFacCF2NTLzzpX (Gpx/lc (Gpx));
462  }
463  else
464  {
465  NTLFpi=convertFacCF2NTLzzpX (smallestFactorEvaly/lc(smallestFactorEvaly));
466  NTLGpi=convertFacCF2NTLzzpX (Gpy/lc (Gpy));
467  }
468  vec_zz_pX modFactors;
469  modFactors.SetLength(2);
470  modFactors[0]= NTLFpi;
471  modFactors[1]= NTLGpi;
472  vec_ZZX liftedFactors;
473  MultiLift (liftedFactors, modFactors, NTLFi, (long) k);
475  CanonicalForm liftedSmallestFactor=
476  convertNTLZZX2CF (liftedFactors[0], x);
477 
478  CanonicalForm otherFactor=
479  convertNTLZZX2CF (liftedFactors[1], x);
480 #endif
481 
483  liftedSmallestFactor= pk (liftedSmallestFactor);
484  if (i == 2)
485  liftedSmallestFactor= liftedSmallestFactor (eval[0],1);
486  else
487  liftedSmallestFactor= liftedSmallestFactor (eval[1],1);
488 
490  CFMatrix *M= new CFMatrix (s, s);
491  (*M)(s,s)= power (CanonicalForm (p), k);
492  for (int j= 1; j < s; j++)
493  {
494  (*M) (j,j)= 1;
495  (*M) (j+1,j)= -liftedSmallestFactor;
496  }
497 
498  mat_ZZ * NTLM= convertFacCFMatrix2NTLmat_ZZ (*M);
499 
500  ZZ det;
501 
502  transpose (*NTLM, *NTLM);
503  (void) LLL (det, *NTLM, 1L, 1L); //use floating point LLL ?
504  transpose (*NTLM, *NTLM);
505  delete M;
507  delete NTLM;
508 
509  mipo= 0;
510  for (int j= 1; j <= s; j++)
511  mipo += (*M) (j,1)*power (x,s-j);
512 
513  delete M;
514  mipoFactors= factorize (mipo);
515  if (mipoFactors.getFirst().factor().inCoeffDomain())
516  mipoFactors.removeFirst();
517 
518 #ifdef HAVE_FLINT
519  fmpz_poly_clear (v[0]);
520  fmpz_poly_clear (v[1]);
521  fmpz_poly_clear (w[0]);
522  fmpz_poly_clear (w[1]);
523  delete [] v;
524  delete [] w;
525  delete [] link;
526  fmpz_poly_factor_clear (liftedFactors);
527 #endif
528 
529  if (mipoFactors.length() > 1 ||
530  (mipoFactors.length() == 1 && mipoFactors.getFirst().exp() > 1) ||
532  {
533  rec=true;
534  goto differentevalpoint;
535  }
536  else
537  mipos[i-1]= mipo;
538  }
539 
540  if (degree (mipos[0]) != degree (mipos[1]))
541  {
542  rec=true;
543  goto differentevalpoint;
544  }
545 
546  On (SW_RATIONAL);
547  if (maxNorm (mipos[0]) < maxNorm (mipos[1]))
548  alpha= rootOf (mipos[0]);
549  else
550  alpha= rootOf (mipos[1]);
551 
552  int wrongMipo= 0;
553 
554  Variable beta;
555  if (maxNorm (mipos[0]) < maxNorm (mipos[1]))
556  {
557  mipoFactors= factorize (mipos[1], alpha);
558  if (mipoFactors.getFirst().factor().inCoeffDomain())
559  mipoFactors.removeFirst();
560  for (iter= mipoFactors; iter.hasItem(); iter++)
561  {
562  if (degree (iter.getItem().factor()) > 1)
563  wrongMipo++;
564  }
565  if (wrongMipo == mipoFactors.length())
566  {
567  rec=true;
568  goto differentevalpoint;
569  }
570  wrongMipo= 0;
571  beta= rootOf (mipos[1]);
572  mipoFactors= factorize (mipos[0], beta);
573  if (mipoFactors.getFirst().factor().inCoeffDomain())
574  mipoFactors.removeFirst();
575  for (iter= mipoFactors; iter.hasItem(); iter++)
576  {
577  if (degree (iter.getItem().factor()) > 1)
578  wrongMipo++;
579  }
580  if (wrongMipo == mipoFactors.length())
581  {
582  rec=true;
583  goto differentevalpoint;
584  }
585  }
586  else
587  {
588  mipoFactors= factorize (mipos[0], alpha);
589  if (mipoFactors.getFirst().factor().inCoeffDomain())
590  mipoFactors.removeFirst();
591  for (iter= mipoFactors; iter.hasItem(); iter++)
592  {
593  if (degree (iter.getItem().factor()) > 1)
594  wrongMipo++;
595  }
596  if (wrongMipo == mipoFactors.length())
597  {
598  rec=true;
599  goto differentevalpoint;
600  }
601  wrongMipo= 0;
602  beta= rootOf (mipos[0]);
603  mipoFactors= factorize (mipos[1], beta);
604  if (mipoFactors.getFirst().factor().inCoeffDomain())
605  mipoFactors.removeFirst();
606  for (iter= mipoFactors; iter.hasItem(); iter++)
607  {
608  if (degree (iter.getItem().factor()) > 1)
609  wrongMipo++;
610  }
611  if (wrongMipo == mipoFactors.length())
612  {
613  rec=true;
614  goto differentevalpoint;
615  }
616  }
617 
618 
619  CanonicalForm F1;
620  if (degree (F,1) > minTdeg)
621  F1= F (eval[1], 2);
622  else
623  F1= F (eval[0], 1);
624 
625  CFFList QaF1Factors;
626  bool swap= false;
627  if (F1.level() == 2)
628  {
629  swap= true;
630  F1=swapvar (F1, x, y);
631  F= swapvar (F, x, y);
632  }
633 
634  wrongMipo= 0;
635  QaF1Factors= factorize (F1, alpha);
636  if (QaF1Factors.getFirst().factor().inCoeffDomain())
637  QaF1Factors.removeFirst();
638  for (iter= QaF1Factors; iter.hasItem(); iter++)
639  {
640  if (degree (iter.getItem().factor()) > minTdeg)
641  wrongMipo++;
642  }
643 
644  if (wrongMipo == QaF1Factors.length())
645  {
646  rec= true;
647  F= bufF;
648  goto differentevalpoint;
649  }
650 
652  if (swap)
653  evaluation= eval[0];
654  else
655  evaluation= eval[1];
656 
657  F *= bCommonDen (F);
658  F= F (y + evaluation, y);
659 
660  int liftBound= degree (F,y) + 1;
661 
662  modpk b= modpk();
663 
664  CanonicalForm den= 1;
665 
666  mipo= getMipo (alpha);
667 
668  CFList uniFactors;
669  for (iter=QaF1Factors; iter.hasItem(); iter++)
670  uniFactors.append (iter.getItem().factor());
671 
672  F /= Lc (F1);
673  ZZX NTLmipo= convertFacCF2NTLZZX (mipo);
674  ZZX NTLLcf= convertFacCF2NTLZZX (Lc (F*bCommonDen (F)));
675  ZZ NTLf= resultant (NTLmipo, NTLLcf);
676  ZZ NTLD= discriminant (NTLmipo);
677  den= abs (convertZZ2CF (NTLD*NTLf));
678 
679  // make factors elements of Z(a)[x] disable for modularDiophant
680  CanonicalForm multiplier= 1;
681  for (CFListIterator i= uniFactors; i.hasItem(); i++)
682  {
683  multiplier *= bCommonDen (i.getItem());
684  i.getItem()= i.getItem()*bCommonDen(i.getItem());
685  }
686  F *= multiplier;
687  F *= bCommonDen (F);
688 
689  Off (SW_RATIONAL);
690  int ii= 0;
691  CanonicalForm discMipo= convertZZ2CF (NTLD);
692  findGoodPrime (bufF*discMipo,ii);
693  findGoodPrime (F1*discMipo,ii);
694  findGoodPrime (F*discMipo,ii);
695 
696  int pp=cf_getBigPrime(ii);
697  b = coeffBound( F, pp, mipo );
698  modpk bb= coeffBound (F1, pp, mipo);
699  if (bb.getk() > b.getk() ) b=bb;
700  bb= coeffBound (F, pp, mipo);
701  if (bb.getk() > b.getk() ) b=bb;
702 
703  ExtensionInfo dummy= ExtensionInfo (alpha, false);
704  DegreePattern degs= DegreePattern (uniFactors);
705 
706  bool earlySuccess= false;
707  CFList earlyFactors;
708  uniFactors= henselLiftAndEarly
709  (F, earlySuccess, earlyFactors, degs, liftBound,
710  uniFactors, dummy, evaluation, b, den);
711 
712  DEBOUTLN (cerr, "lifted factors= " << uniFactors);
713 
714  CanonicalForm MODl= power (y, liftBound);
715 
716  On (SW_RATIONAL);
717  F *= bCommonDen (F);
718  Off (SW_RATIONAL);
719 
720  CFList biFactors;
721 
722  biFactors= factorRecombination (uniFactors, F, MODl, degs, evaluation, 1,
723  uniFactors.length()/2, b, den);
724 
725  On (SW_RATIONAL);
726 
727  if (earlySuccess)
728  biFactors= Union (earlyFactors, biFactors);
729  else if (!earlySuccess && degs.getLength() == 1)
730  biFactors= earlyFactors;
731 
732  bool swap2= false;
733  appendSwapDecompress (biFactors, CFList(), CFList(), swap, swap2, CFMap());
734  if (isOn (SW_RATIONAL))
735  normalize (biFactors);
736 
738  bool found= false;
739 
740  for (CFListIterator i= biFactors; i.hasItem(); i++)
741  {
742  if (full)
743  result.append (CFAFactor (decompress (i.getItem(), M, S),
744  getMipo (alpha), 1));
745 
746  if (totaldegree (i.getItem()) == minTdeg)
747  {
748  if (!full)
749  result= CFAFList (CFAFactor (decompress (i.getItem(), M, S),
750  getMipo (alpha), 1));
751  found= true;
752 
753  if (!full)
754  break;
755  }
756  }
757 
758  if (!found)
759  {
760  rec= true;
761  F= bufF;
762  goto differentevalpoint;
763  }
764 
765  if (isRat)
766  On (SW_RATIONAL);
767  else
768  Off (SW_RATIONAL);
769 
770  mpz_clear (M[0]);
771  mpz_clear (M[1]);
772  mpz_clear (M[2]);
773  mpz_clear (M[3]);
774  delete [] M;
775 
776  mpz_clear (S[0]);
777  mpz_clear (S[1]);
778  delete [] S;
779 
780  return result;
781 }

◆ choosePoint()

int choosePoint ( const CanonicalForm F,
int  tdegF,
CFArray eval,
bool  rec,
int  absValue 
)

Definition at line 81 of file facAbsBiFact.cc.

83 {
84  REvaluation E1 (1, 1, IntRandom (absValue));
85  REvaluation E2 (2, 2, IntRandom (absValue));
86  if (rec)
87  {
88  E1.nextpoint();
89  E2.nextpoint();
90  }
91 
92  CanonicalForm f, f1, f2, Fp;
93  int i, p;
94  CFFList f1Factors, f2Factors;
96  int count= 0;
97  while (1)
98  {
99  count++;
100  f1= E1 (F);
101  if (!f1.isZero() && degree (f1) == degree (F,2))
102  {
103  f1Factors= factorize (f1);
104  if (f1Factors.getFirst().factor().inCoeffDomain())
105  f1Factors.removeFirst();
106  if (f1Factors.length() == 1 && f1Factors.getFirst().exp() == 1)
107  {
108  f= E2(f1);
109  f2= E2 (F);
110  f2Factors= factorize (f2);
111  Off (SW_RATIONAL);
112  if (f2Factors.getFirst().factor().inCoeffDomain())
113  f2Factors.removeFirst();
114  if (f2Factors.length() == 1 && f2Factors.getFirst().exp() == 1)
115  {
116  ZZX NTLf1= convertFacCF2NTLZZX (f1);
117  ZZX NTLf2= convertFacCF2NTLZZX (f2);
118  ZZ NTLD1= discriminant (NTLf1);
119  ZZ NTLD2= discriminant (NTLf2);
120  CanonicalForm D1= convertZZ2CF (NTLD1);
121  CanonicalForm D2= convertZZ2CF (NTLD2);
122  if ((!f.isZero()) &&
124  {
125  for (i= cf_getNumPrimes()-1; i >= 0; i--)
126  {
127  if (f % CanonicalForm (cf_getPrime (i)) == 0)
128  {
129  p= cf_getPrime(i);
130  Fp= mod (F,p);
131  if (totaldegree (Fp) == tdegF &&
132  degree (mod (f2,p), 1) == degree (F,1) &&
133  degree (mod (f1, p),2) == degree (F,2))
134  {
135  if (mod (D1, p) != 0 && mod (D2, p) != 0)
136  {
137  eval[0]= E1[1];
138  eval[1]= E2[2];
139  return p;
140  }
141  }
142  }
143  }
144  }
145  else if (!f.isZero())
146  {
147  for (i= cf_getNumSmallPrimes()-1; i >= 0; i--)
148  {
149  if (f % CanonicalForm (cf_getSmallPrime (i)) == 0)
150  {
151  p= cf_getSmallPrime (i);
152  Fp= mod (F,p);
153  if (totaldegree (Fp) == tdegF &&
154  degree (mod (f2, p),1) == degree (F,1) &&
155  degree (mod (f1,p),2) == degree (F,2))
156  {
157  if (mod (D1, p) != 0 && mod (D2, p) != 0)
158  {
159  eval[0]= E1[1];
160  eval[1]= E2[2];
161  return p;
162  }
163  }
164  }
165  }
166  }
167  }
168  E2.nextpoint();
169  On (SW_RATIONAL);
170  }
171  }
172  E1.nextpoint();
173  if (count == 2)
174  {
175  count= 0;
176  absValue++;
177  E1=REvaluation (1, 1, IntRandom (absValue));
178  E2=REvaluation (2, 2, IntRandom (absValue));
179  E1.nextpoint();
180  E2.nextpoint();
181  }
182  }
183  return 0;
184 }

◆ for()

for ( ;iter.hasItem();iter++  )

Definition at line 63 of file facAbsBiFact.cc.

64  {
65  if (full)
66  result.append (CFAFactor (iter.getItem().factor(), getMipo (alpha),
67  iter.getItem().exp()));
68  if (!full && degree (iter.getItem().factor()) == 1)
69  {
70  result.append (CFAFactor (iter.getItem().factor(), getMipo (alpha),
71  iter.getItem().exp()));
72  break;
73  }
74  }

◆ if() [1/2]

if ( degree(F)  = = 1)

Definition at line 41 of file facAbsBiFact.cc.

42  {
43  bool isRat= isOn (SW_RATIONAL);
44  On (SW_RATIONAL);
45  result= CFAFList (CFAFactor (F/Lc(F), 1, 1));
46  result.insert (CFAFactor (Lc (F), 1, 1));
47  if (!isRat)
48  Off (SW_RATIONAL);
49  return result;
50  }

◆ if() [2/2]

if ( iter.  getItem).factor().inCoeffDomain()

Definition at line 58 of file facAbsBiFact.cc.

59  {
60  LcF = iter.getItem().factor();
61  iter++;
62  }

◆ insert()

result insert ( CFAFactor(LcF, 1, 1)  )

◆ TIMING_DEFINE_PRINT()

TIMING_DEFINE_PRINT ( fac_Qa_factorize  ) const &

Variable Documentation

◆ alpha

alpha = rootOf (F)

Definition at line 52 of file facAbsBiFact.cc.

◆ full

bool full
Initial value:

Definition at line 39 of file facAbsBiFact.cc.

◆ iter

iter = QaFactors

Definition at line 54 of file facAbsBiFact.cc.

◆ LcF

CanonicalForm LcF = 1

Definition at line 51 of file facAbsBiFact.cc.

◆ QaFactors

QaFactors = factorize (F, alpha)

Definition at line 53 of file facAbsBiFact.cc.

◆ result

return result

Definition at line 76 of file facAbsBiFact.cc.

Matrix
Definition: ftmpl_matrix.h:20
fac_NTL_char
long fac_NTL_char
Definition: NTLconvert.cc:41
convertZZ2CF
CanonicalForm convertZZ2CF(const ZZ &a)
NAME: convertZZ2CF.
Definition: NTLconvert.cc:489
SW_RATIONAL
static const int SW_RATIONAL
set to 1 for computations over Q
Definition: cf_defs.h:28
slong
#define slong
convertFacCF2NTLzzpX
zz_pX convertFacCF2NTLzzpX(const CanonicalForm &f)
Definition: NTLconvert.cc:100
CFAFList
List< CFAFactor > CFAFList
Definition: canonicalform.h:383
isOn
bool isOn(int sw)
switches
Definition: canonicalform.cc:1912
j
int j
Definition: facHensel.cc:105
f
FILE * f
Definition: checklibs.c:9
k
int k
Definition: cfEzgcd.cc:92
icontent
CanonicalForm icontent(const CanonicalForm &f)
CanonicalForm icontent ( const CanonicalForm & f )
Definition: cf_gcd.cc:71
x
Variable x
Definition: cfModGcd.cc:4023
DEBOUTLN
#define DEBOUTLN(stream, objects)
Definition: debug.h:49
y
const CanonicalForm int const CFList const Variable & y
Definition: facAbsFact.cc:57
uniAbsFactorize
CFAFList uniAbsFactorize(const CanonicalForm &F, bool full=false)
univariate absolute factorization over Q
result
return result
Definition: facAbsBiFact.cc:76
CFArray
Array< CanonicalForm > CFArray
Definition: canonicalform.h:390
nmod_poly_clear
nmod_poly_clear(FLINTmipo)
DegreePattern
Definition: DegreePattern.h:31
CFMap
class CFMap
Definition: cf_map.h:84
power
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
Definition: canonicalform.cc:1837
mod
CF_NO_INLINE CanonicalForm mod(const CanonicalForm &, const CanonicalForm &)
Definition: cf_inline.cc:564
rootOf
Variable rootOf(const CanonicalForm &, char name='@')
returns a symbolic root of polynomial with name name Use it to define algebraic variables
Definition: variable.cc:162
CFMatrix
Matrix< CanonicalForm > CFMatrix
Definition: canonicalform.h:391
iter
CFFListIterator iter
Definition: facAbsBiFact.cc:54
cf_getBigPrime
int cf_getBigPrime(int i)
Definition: cf_primes.cc:39
w
const CanonicalForm & w
Definition: facAbsFact.cc:55
b
CanonicalForm b
Definition: cfModGcd.cc:4044
CanonicalForm
factory's main class
Definition: canonicalform.h:77
found
bool found
Definition: facFactorize.cc:56
maxNorm
CanonicalForm maxNorm(const CanonicalForm &f)
CanonicalForm maxNorm ( const CanonicalForm & f )
Definition: cf_algorithm.cc:534
evaluation
const CanonicalForm int const CFList & evaluation
Definition: facAbsFact.cc:56
i
int i
Definition: cfEzgcd.cc:125
Lc
CanonicalForm Lc(const CanonicalForm &f)
Definition: canonicalform.h:300
swapvar
CanonicalForm swapvar(const CanonicalForm &, const Variable &, const Variable &)
swapvar() - swap variables x1 and x2 in f.
Definition: cf_ops.cc:168
Array
Definition: ftmpl_array.h:17
convertFacCF2nmod_poly_t
convertFacCF2nmod_poly_t(FLINTmipo, M)
getMipo
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
Definition: variable.cc:207
abs
Rational abs(const Rational &a)
Definition: GMPrat.cc:439
M
#define M
Definition: sirandom.c:24
appendSwapDecompress
void appendSwapDecompress(CFList &factors1, const CFList &factors2, const CFList &factors3, const bool swap1, const bool swap2, const CFMap &N)
first swap Variables in factors1 if necessary, then append factors2 and factors3 on factors1 and fina...
Definition: facFqBivarUtil.cc:70
TIMING_START
TIMING_START(fac_alg_resultant)
lc
CanonicalForm lc(const CanonicalForm &f)
Definition: canonicalform.h:297
IntRandom
generate random integers
Definition: cf_random.h:55
choosePoint
int choosePoint(const CanonicalForm &F, int tdegF, CFArray &eval, bool rec, int absValue)
Definition: facAbsBiFact.cc:81
alpha
Variable alpha
Definition: facAbsBiFact.cc:52
absIrredTest
bool absIrredTest(const CanonicalForm &F)
absolute irreducibility test as described in "Modular Las Vegas Algorithms for Polynomial Absolute Fa...
Definition: cfNewtonPolygon.cc:1163
factorRecombination
CFList factorRecombination(CFList &factors, CanonicalForm &F, const CanonicalForm &N, DegreePattern &degs, const CanonicalForm &eval, int s, int thres, const modpk &b, const CanonicalForm &den)
naive factor recombination as decribed in "Factoring multivariate polynomials over a finite field" by...
Definition: facFqBivar.cc:561
setCharacteristic
void setCharacteristic(int c)
Definition: cf_char.cc:23
compress
CanonicalForm compress(const CanonicalForm &f, CFMap &m)
CanonicalForm compress ( const CanonicalForm & f, CFMap & m )
Definition: cf_map.cc:210
LcF
CanonicalForm LcF
Definition: facAbsBiFact.cc:51
AFactor
Definition: ftmpl_afactor.h:17
convertFacCFMatrix2NTLmat_ZZ
mat_ZZ * convertFacCFMatrix2NTLmat_ZZ(const CFMatrix &m)
Definition: NTLconvert.cc:1137
full
bool full
Definition: facAbsBiFact.cc:39
REvaluation
class to generate random evaluation points
Definition: cf_reval.h:25
CFAFactor
AFactor< CanonicalForm > CFAFactor
Definition: canonicalform.h:382
pp
CanonicalForm pp(const CanonicalForm &)
CanonicalForm pp ( const CanonicalForm & f )
Definition: cf_gcd.cc:248
factorize
CFFList factorize(const CanonicalForm &f, bool issqrfree=false)
factorization over or
Definition: cf_factor.cc:390
cf_getPrime
int cf_getPrime(int i)
Definition: cf_primes.cc:14
eval
CFList & eval
Definition: facFactorize.cc:48
den
CanonicalForm den(const CanonicalForm &f)
Definition: canonicalform.h:333
convertFacCF2NTLZZX
ZZX convertFacCF2NTLZZX(const CanonicalForm &f)
Definition: NTLconvert.cc:685
ListIterator::hasItem
int hasItem()
Definition: ftmpl_list.cc:439
decompress
CanonicalForm decompress(const CanonicalForm &F, const mpz_t *inverseM, const mpz_t *A)
decompress a bivariate poly
Definition: cfNewtonPolygon.cc:853
beta
Variable beta
Definition: facAbsFact.cc:99
Off
void Off(int sw)
switches
Definition: canonicalform.cc:1905
List::removeFirst
void removeFirst()
Definition: ftmpl_list.cc:287
modpk
class to do operations mod p^k for int's p and k
Definition: fac_util.h:22
List::getFirst
T getFirst() const
Definition: ftmpl_list.cc:279
convertFmpz_poly_t2FacCF
CanonicalForm convertFmpz_poly_t2FacCF(const fmpz_poly_t poly, const Variable &x)
conversion of a FLINT poly over Z to CanonicalForm
Definition: FLINTconvert.cc:101
DegreePattern::getLength
int getLength() const
getter
Definition: DegreePattern.h:86
bCommonDen
CanonicalForm bCommonDen(const CanonicalForm &f)
CanonicalForm bCommonDen ( const CanonicalForm & f )
Definition: cf_algorithm.cc:293
CanonicalForm::inCoeffDomain
bool inCoeffDomain() const
Definition: canonicalform.cc:119
List::length
int length() const
Definition: ftmpl_list.cc:273
convertNTLmat_ZZ2FacCFMatrix
CFMatrix * convertNTLmat_ZZ2FacCFMatrix(const mat_ZZ &m)
Definition: NTLconvert.cc:1152
cf_getNumPrimes
int cf_getNumPrimes()
Definition: cf_primes.cc:23
TIMING_END_AND_PRINT
TIMING_END_AND_PRINT(fac_alg_resultant, "time to compute resultant0: ")
normalize
static poly normalize(poly next_p, ideal add_generators, syStrategy syzstr, int *g_l, int *p_l, int crit_comp)
Definition: syz3.cc:1027
modpk::getk
int getk() const
Definition: fac_util.h:36
Variable
factory's class for variables
Definition: factory.h:117
ListIterator::getItem
T & getItem() const
Definition: ftmpl_list.cc:431
bound
static CanonicalForm bound(const CFMatrix &M)
Definition: cf_linsys.cc:460
cf_getSmallPrime
int cf_getSmallPrime(int i)
Definition: cf_primes.cc:28
B
b *CanonicalForm B
Definition: facBivar.cc:52
coeffBound
modpk coeffBound(const CanonicalForm &f, int p, const CanonicalForm &mipo)
compute p^k larger than the bound on the coefficients of a factor of f over Q (mipo)
Definition: facBivar.cc:97
ExtensionInfo
Definition: ExtensionInfo.h:50
mapinto
CanonicalForm mapinto(const CanonicalForm &f)
Definition: canonicalform.h:348
resultant
CanonicalForm resultant(const CanonicalForm &f, const CanonicalForm &g, const Variable &x)
CanonicalForm resultant ( const CanonicalForm & f, const CanonicalForm & g, const Variable & x )
Definition: cf_resultant.cc:173
modpk::inverse
CanonicalForm inverse(const CanonicalForm &f, bool symmetric=true) const
Definition: fac_util.cc:58
SW_SYMMETRIC_FF
static const int SW_SYMMETRIC_FF
set to 1 for symmetric representation over F_q
Definition: cf_defs.h:30
CanonicalForm::isUnivariate
bool isUnivariate() const
Definition: canonicalform.cc:152
Union
template List< Variable > Union(const List< Variable > &, const List< Variable > &)
gcd
int gcd(int a, int b)
Definition: walkSupport.cc:836
convertNTLZZX2CF
CanonicalForm convertNTLZZX2CF(const ZZX &polynom, const Variable &x)
Definition: NTLconvert.cc:278
absValue
number absValue(poly p)
Definition: linearAlgebra.cc:725
v
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:37
p
int p
Definition: cfModGcd.cc:4019
mipo
CanonicalForm mipo
Definition: facAlgExt.cc:57
List
Definition: ftmpl_list.h:20
swap
#define swap(_i, _j)
CanonicalForm::mapinto
CanonicalForm mapinto() const
Definition: canonicalform.cc:206
s
const CanonicalForm int s
Definition: facAbsFact.cc:55
CFList
List< CanonicalForm > CFList
Definition: canonicalform.h:388
count
int status int void size_t count
Definition: si_signals.h:59
findGoodPrime
void findGoodPrime(const CanonicalForm &f, int &start)
find a big prime p from our tables such that no term of f vanishes mod p
Definition: facBivar.cc:61
CanonicalForm::isZero
CF_NO_INLINE bool isZero() const
Definition: cf_inline.cc:372
cf_getNumSmallPrimes
int cf_getNumSmallPrimes()
Definition: cf_primes.cc:34
henselLiftAndEarly
CFList henselLiftAndEarly(CanonicalForm &A, bool &earlySuccess, CFList &earlyFactors, DegreePattern &degs, int &liftBound, const CFList &uniFactors, const ExtensionInfo &info, const CanonicalForm &eval, modpk &b, CanonicalForm &den)
hensel Lifting and early factor detection
Definition: facFqBivar.cc:1115
convertFacCF2Fmpz_poly_t
void convertFacCF2Fmpz_poly_t(fmpz_poly_t result, const CanonicalForm &f)
conversion of a factory univariate polynomial over Z to a fmpz_poly_t
Definition: FLINTconvert.cc:74
modularIrredTestWithShift
bool modularIrredTestWithShift(const CanonicalForm &F)
modular absolute irreducibility test with shift as described in "Modular Las Vegas Algorithms for Pol...
Definition: cfNewtonPolygon.cc:1292
G
static TreeM * G
Definition: janet.cc:32
CanonicalForm::level
int level() const
level() returns the level of CO.
Definition: canonicalform.cc:543
List::append
void append(const T &)
Definition: ftmpl_list.cc:256
modpk
return modpk(p, k)
degree
int degree(const CanonicalForm &f)
Definition: canonicalform.h:309
On
void On(int sw)
switches
Definition: canonicalform.cc:1898
totaldegree
int totaldegree(const CanonicalForm &f)
int totaldegree ( const CanonicalForm & f )
Definition: cf_ops.cc:523
ListIterator
Definition: ftmpl_list.h:17