189{
192
193 bool extension= (
v.
level() != 1);
197 else
199
201 if (extension)
203
204 if (
A.isUnivariate())
205 {
207 if (extension)
209 else
212 if (
result.getFirst().inCoeffDomain())
215 }
216
220
223
226
227 A=
A/(contentAx*contentAy);
228 CFFList contentAxFactors, contentAyFactors;
229
230 if (extension)
231 {
233 {
235 if (contentAxFactors.
getFirst().factor().inCoeffDomain())
237 }
239 {
241 if (contentAyFactors.
getFirst().factor().inCoeffDomain())
243 }
244 }
245 else
246 {
248 {
249 contentAxFactors=
factorize (contentAx,
true);
250 if (contentAxFactors.
getFirst().factor().inCoeffDomain())
252 }
254 {
255 contentAyFactors=
factorize (contentAy,
true);
256 if (contentAyFactors.
getFirst().factor().inCoeffDomain())
258 }
259 }
260
261
264 {
267
269 conv (contentAyFactors),
false,
false,
N);
270
272 return factors;
273 }
274
275
277 if (
A.inCoeffDomain())
278 {
282 return factors;
283 }
284 else if (
A.isUnivariate())
285 {
286 if (extension)
288 else
293 return factors;
294 }
295
297 {
300
302 conv (contentAyFactors),
false,
false,
N);
303
305 return factors;
306 }
309 {
312 }
313
315 CFList uniFactors, list, bufUniFactors;
318
320 CFList bufUniFactors2, list2, uniFactors2;
323 bool swap2= false;
324
325
326
327
328 int factorNums= 2;
332 int evaluation, evaluation2=0, bufEvaluation= 0, bufEvaluation2= 0;
333 for (
int i= 0;
i < factorNums;
i++)
334 {
339
344 "time for eval point over Q in y: ");
345
346
348 if (extension)
350 else
353 "time for univariate factorization over Q: ");
354 DEBOUTLN (cerr,
"prod (bufUniFactors)== bufAeval " <<
355 (
prod (bufUniFactors) == bufAeval));
356
359
360 if (bufUniFactors.
length() == 1)
361 {
363
365 conv (contentAyFactors),
swap, swap2,
N);
366
369 return factors;
370 }
371
373 if (extension)
375 else
378 "time for univariate factorization in y over Q: ");
379 DEBOUTLN (cerr,
"prod (bufuniFactors2)== bufAeval2 " <<
380 (
prod (bufUniFactors2) == bufAeval2));
381
384 if (bufUniFactors2.
length() == 1)
385 {
387
389 conv (contentAyFactors),
swap, swap2,
N);
390
393 return factors;
394 }
395
397 {
398 if (subCheck1 > 0)
399 {
401
402 if (subCheck > 1 && (subCheck1%subCheck == 0))
403 {
405 subst (bufA, bufA, subCheck,
x);
409 conv (contentAyFactors),
swap, swap2,
N);
412 return factors;
413 }
414 }
415
416 if (subCheck2 > 0)
417 {
419
420 if (subCheck > 1 && (subCheck2%subCheck == 0))
421 {
423 subst (bufA, bufA, subCheck,
y);
427 conv (contentAyFactors),
swap, swap2,
N);
430 return factors;
431 }
432 }
433 }
434
435
438
440 {
443 uniFactors= bufUniFactors;
444 degs= bufDegs;
445 Aeval2= bufAeval2;
446 evaluation2= bufEvaluation2;
447 uniFactors2= bufUniFactors2;
448 degs2= bufDegs2;
449 }
450 else
451 {
455 {
456 uniFactors2= bufUniFactors2;
457 Aeval2= bufAeval2;
458 evaluation2= bufEvaluation2;
459 }
461 {
462 uniFactors= bufUniFactors;
465 }
466 }
467 if (bufEvaluation > 0)
468 bufEvaluation++;
469 else
470 bufEvaluation= -bufEvaluation + 1;
471 if (bufEvaluation > 0)
472 bufEvaluation2++;
473 else
474 bufEvaluation2= -bufEvaluation2 + 1;
475 }
476
480 {
481 degs= degs2;
482 uniFactors= uniFactors2;
486 swap2= true;
487 }
488
490 {
493 conv (contentAyFactors),
swap, swap2,
N);
496 return factors;
497 }
498
501
503
505 bool mipoHasDen= false;
507 if (!extension)
508 {
515 printf ("out of primes\n");
516
520 if (bb.
getk() >
b.getk() )
b=bb;
522 if (bb.
getk() >
b.getk() )
b=bb;
523 }
524 else
525 {
529 #ifdef HAVE_FLINT
530
531 fmpz_t FLINTf,FLINTD;
532 fmpz_init(FLINTf);
533 fmpz_init(FLINTD);
534 fmpz_poly_t FLINTmipo;
535 fmpz_poly_t FLINTLcf;
536
539
540 fmpz_poly_resultant(FLINTf,FLINTmipo,FLINTLcf);
541 fmpz_poly_discriminant(FLINTD,FLINTmipo);
542 fmpz_mul(FLINTf,FLINTD,FLINTf);
543
545
546 fmpz_clear(FLINTf);
547
548 fmpz_poly_clear(FLINTLcf);
549 fmpz_poly_clear(FLINTmipo);
550 #elif defined(HAVE_NTL)
554 ZZ NTLD= discriminant (NTLmipo);
556 #else
558 #endif
559
560
563 {
566 }
569
572 #ifdef HAVE_FLINT
574 fmpz_clear(FLINTD);
575 #elif defined(HAVE_NTL)
577 #else
579 #endif
583
587 if (bb.
getk() >
b.getk() )
b=bb;
589 if (bb.
getk() >
b.getk() )
b=bb;
590 }
591
593 if (extension)
595 bool earlySuccess= false;
599 (
A, earlySuccess, earlyFactors, degs, liftBound,
602 "time for bivariate hensel lifting over Q: ");
603 DEBOUTLN (cerr,
"lifted factors= " << uniFactors);
604
606
607 if (mipoHasDen)
608 {
612 break;
615
616 }
617
621
626 "time for bivariate factor recombination over Q: ");
627
629
630 if (earlySuccess)
631 factors=
Union (earlyFactors, factors);
632 else if (!earlySuccess && degs.
getLength() == 1)
633 factors= earlyFactors;
634
636 conv (contentAyFactors),
swap, swap2,
N);
639
640 return factors;
641}
CanonicalForm convertFmpz2CF(const fmpz_t coefficient)
conversion of a FLINT integer to CanonicalForm
void convertFacCF2Fmpz_poly_t(fmpz_poly_t result, const CanonicalForm &f)
conversion of a factory univariate polynomial over Z to a fmpz_poly_t
Rational abs(const Rational &a)
CanonicalForm convertZZ2CF(const ZZ &a)
NAME: convertZZ2CF.
ZZX convertFacCF2NTLZZX(const CanonicalForm &f)
const CanonicalForm CFMap CFMap & N
bool irreducibilityTest(const CanonicalForm &F)
computes the Newton polygon of F and checks if it satisfies the irreducibility criterion from S....
CanonicalForm decompress(const CanonicalForm &F, const mpz_t *inverseM, const mpz_t *A)
decompress a bivariate poly
CanonicalForm bCommonDen(const CanonicalForm &f)
CanonicalForm bCommonDen ( const CanonicalForm & f )
CFFList FACTORY_PUBLIC factorize(const CanonicalForm &f, bool issqrfree=false)
factorization over or
CanonicalForm FACTORY_PUBLIC resultant(const CanonicalForm &f, const CanonicalForm &g, const Variable &x)
CanonicalForm resultant ( const CanonicalForm & f, const CanonicalForm & g, const Variable & x )
static const int SW_RATIONAL
set to 1 for computations over Q
CanonicalForm compress(const CanonicalForm &f, CFMap &m)
CanonicalForm compress ( const CanonicalForm & f, CFMap & m )
int cf_getBigPrime(int i)
VAR void(* factoryError)(const char *s)
DegreePattern provides a functionality to create, intersect and refine degree patterns.
void intersect(const DegreePattern °Pat)
intersect two degree patterns
int getLength() const
getter
ExtensionInfo contains information about extension.
factory's class for variables
class to do operations mod p^k for int's p and k
#define DEBOUTLN(stream, objects)
const CanonicalForm int const CFList & evaluation
const CanonicalForm int const CFList const Variable & y
CFFList append(const CFFList &Inputlist, const CFFactor &TheFactor)
CanonicalForm subst(const CanonicalForm &f, const CFList &a, const CFList &b, const CanonicalForm &Rstar, bool isFunctionField)
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)
CanonicalForm evalPoint(const CanonicalForm &F, int &i)
CFList conv(const CFFList &L)
convert a CFFList to a CFList by dropping the multiplicity
CFList biFactorize(const CanonicalForm &F, const Variable &v)
void findGoodPrime(const CanonicalForm &f, int &start)
find a big prime p from our tables such that no term of f vanishes mod p
const Variable & v
< [in] a sqrfree bivariate poly
CFList *& Aeval
<[in] poly
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...
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
CFList henselLiftAndEarly(CanonicalForm &A, bool &earlySuccess, CFList &earlyFactors, DegreePattern °s, int &liftBound, const CFList &uniFactors, const ExtensionInfo &info, const CanonicalForm &eval, modpk &b, CanonicalForm &den)
hensel Lifting and early factor detection
CFList factorRecombination(CFList &factors, CanonicalForm &F, const CanonicalForm &N, DegreePattern °s, 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...
template List< Variable > Union(const List< Variable > &, const List< Variable > &)
int status int void * buf
static poly normalize(poly next_p, ideal add_generators, syStrategy syzstr, int *g_l, int *p_l, int crit_comp)
#define TIMING_END_AND_PRINT(t, msg)
CanonicalForm getMipo(const Variable &alpha, const Variable &x)