My Project
Loading...
Searching...
No Matches
Functions | Variables
facBivar.cc File Reference

bivariate factorization over Q(a) More...

#include "config.h"
#include "cf_assert.h"
#include "cf_util.h"
#include "debug.h"
#include "timing.h"
#include "cf_algorithm.h"
#include "facFqBivar.h"
#include "facBivar.h"
#include "facHensel.h"
#include "facMul.h"
#include "cf_primes.h"

Go to the source code of this file.

Functions

 TIMING_DEFINE_PRINT (fac_uni_factorizer) TIMING_DEFINE_PRINT(fac_bi_hensel_lift) TIMING_DEFINE_PRINT(fac_bi_factor_recombination) TIMING_DEFINE_PRINT(fac_bi_evaluation) TIMING_DEFINE_PRINT(fac_bi_shift_to_zero) modpk coeffBound(const CanonicalForm &f
 
 for (i=1;i<=k;i++)
 
 DELETE_ARRAY (degs)
 
 while (B< b)
 
return modpk (p, k)
 
void findGoodPrime (const CanonicalForm &f, int &start)
 find a big prime p from our tables such that no term of f vanishes mod p More...
 
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) More...
 
CFList conv (const CFFList &L)
 convert a CFFList to a CFList by dropping the multiplicity More...
 
bool testPoint (const CanonicalForm &F, CanonicalForm &G, int i)
 
CanonicalForm evalPoint (const CanonicalForm &F, int &i)
 
CFList biFactorize (const CanonicalForm &F, const Variable &v)
 

Variables

int p
 
int M = 0
 
int i
 
int k = f.level()
 
CanonicalForm b = 1
 
b *CanonicalForm B = p
 

Detailed Description

bivariate factorization over Q(a)

Author
Martin Lee

Definition in file facBivar.cc.

Function Documentation

◆ biFactorize()

CFList biFactorize ( const CanonicalForm F,
const Variable v 
)

Definition at line 188 of file facBivar.cc.

189{
190 if (F.inCoeffDomain())
191 return CFList(F);
192
193 bool extension= (v.level() != 1);
195 if (isOn (SW_RATIONAL))
196 A= F*bCommonDen (F);
197 else
198 A= F;
199
201 if (extension)
202 mipo= getMipo (v);
203
204 if (A.isUnivariate())
205 {
206 CFFList buf;
207 if (extension)
208 buf= factorize (A, v);
209 else
210 buf= factorize (A, true);
212 if (result.getFirst().inCoeffDomain())
213 result.removeFirst();
214 return result;
215 }
216
217 CFMap N;
218 A= compress (A, N);
219 Variable y= A.mvar();
220
221 if (y.level() > 2) return CFList (F);
222 Variable x= Variable (1);
223
224 CanonicalForm contentAx= content (A, x);
225 CanonicalForm contentAy= content (A);
226
227 A= A/(contentAx*contentAy);
228 CFFList contentAxFactors, contentAyFactors;
229
230 if (extension)
231 {
232 if (!contentAx.inCoeffDomain())
233 {
234 contentAxFactors= factorize (contentAx, v);
235 if (contentAxFactors.getFirst().factor().inCoeffDomain())
236 contentAxFactors.removeFirst();
237 }
238 if (!contentAy.inCoeffDomain())
239 {
240 contentAyFactors= factorize (contentAy, v);
241 if (contentAyFactors.getFirst().factor().inCoeffDomain())
242 contentAyFactors.removeFirst();
243 }
244 }
245 else
246 {
247 if (!contentAx.inCoeffDomain())
248 {
249 contentAxFactors= factorize (contentAx, true);
250 if (contentAxFactors.getFirst().factor().inCoeffDomain())
251 contentAxFactors.removeFirst();
252 }
253 if (!contentAy.inCoeffDomain())
254 {
255 contentAyFactors= factorize (contentAy, true);
256 if (contentAyFactors.getFirst().factor().inCoeffDomain())
257 contentAyFactors.removeFirst();
258 }
259 }
260
261 //check trivial case
262 if (degree (A) == 1 || degree (A, 1) == 1 ||
263 (size (A) == 2 && igcd (degree (A), degree (A,1)) == 1))
264 {
265 CFList factors;
266 factors.append (A);
267
268 appendSwapDecompress (factors, conv (contentAxFactors),
269 conv (contentAyFactors), false, false, N);
270
271 normalize (factors);
272 return factors;
273 }
274
275 //trivial case
276 CFList factors;
277 if (A.inCoeffDomain())
278 {
279 append (factors, conv (contentAxFactors));
280 append (factors, conv (contentAyFactors));
281 decompress (factors, N);
282 return factors;
283 }
284 else if (A.isUnivariate())
285 {
286 if (extension)
287 factors= conv (factorize (A, v));
288 else
289 factors= conv (factorize (A, true));
290 append (factors, conv (contentAxFactors));
291 append (factors, conv (contentAyFactors));
292 decompress (factors, N);
293 return factors;
294 }
295
296 if (irreducibilityTest (A))
297 {
298 CFList factors;
299 factors.append (A);
300
301 appendSwapDecompress (factors, conv (contentAxFactors),
302 conv (contentAyFactors), false, false, N);
303
304 normalize (factors);
305 return factors;
306 }
307 bool swap= false;
308 if (degree (A) > degree (A, x))
309 {
310 A= swapvar (A, y, x);
311 swap= true;
312 }
313
314 CanonicalForm Aeval, bufAeval, buf;
315 CFList uniFactors, list, bufUniFactors;
316 DegreePattern degs;
317 DegreePattern bufDegs;
318
319 CanonicalForm Aeval2, bufAeval2;
320 CFList bufUniFactors2, list2, uniFactors2;
321 DegreePattern degs2;
322 DegreePattern bufDegs2;
323 bool swap2= false;
324
325 // several univariate factorizations to obtain more information about the
326 // degree pattern therefore usually less combinations have to be tried during
327 // the recombination process
328 int factorNums= 2;
329 int subCheck1= substituteCheck (A, x);
330 int subCheck2= substituteCheck (A, y);
331 buf= swapvar (A,x,y);
332 int evaluation, evaluation2=0, bufEvaluation= 0, bufEvaluation2= 0;
333 for (int i= 0; i < factorNums; i++)
334 {
335 bufAeval= A;
336 TIMING_START (fac_bi_evaluation);
337 bufAeval= evalPoint (A, bufEvaluation);
338 TIMING_END_AND_PRINT (fac_bi_evaluation, "time for eval point over Q: ");
339
340 bufAeval2= buf;
341 TIMING_START (fac_bi_evaluation);
342 bufAeval2= evalPoint (buf, bufEvaluation2);
343 TIMING_END_AND_PRINT (fac_bi_evaluation,
344 "time for eval point over Q in y: ");
345
346 // univariate factorization
347 TIMING_START (fac_uni_factorizer);
348 if (extension)
349 bufUniFactors= conv (factorize (bufAeval, v));
350 else
351 bufUniFactors= conv (factorize (bufAeval, true));
352 TIMING_END_AND_PRINT (fac_uni_factorizer,
353 "time for univariate factorization over Q: ");
354 DEBOUTLN (cerr, "prod (bufUniFactors)== bufAeval " <<
355 (prod (bufUniFactors) == bufAeval));
356
357 if (bufUniFactors.getFirst().inCoeffDomain())
358 bufUniFactors.removeFirst();
359
360 if (bufUniFactors.length() == 1)
361 {
362 factors.append (A);
363
364 appendSwapDecompress (factors, conv (contentAxFactors),
365 conv (contentAyFactors), swap, swap2, N);
366
367 if (isOn (SW_RATIONAL))
368 normalize (factors);
369 return factors;
370 }
371
372 TIMING_START (fac_uni_factorizer);
373 if (extension)
374 bufUniFactors2= conv (factorize (bufAeval2, v));
375 else
376 bufUniFactors2= conv (factorize (bufAeval2, true));
377 TIMING_END_AND_PRINT (fac_uni_factorizer,
378 "time for univariate factorization in y over Q: ");
379 DEBOUTLN (cerr, "prod (bufuniFactors2)== bufAeval2 " <<
380 (prod (bufUniFactors2) == bufAeval2));
381
382 if (bufUniFactors2.getFirst().inCoeffDomain())
383 bufUniFactors2.removeFirst();
384 if (bufUniFactors2.length() == 1)
385 {
386 factors.append (A);
387
388 appendSwapDecompress (factors, conv (contentAxFactors),
389 conv (contentAyFactors), swap, swap2, N);
390
391 if (isOn (SW_RATIONAL))
392 normalize (factors);
393 return factors;
394 }
395
396 if (i == 0)
397 {
398 if (subCheck1 > 0)
399 {
400 int subCheck= substituteCheck (bufUniFactors);
401
402 if (subCheck > 1 && (subCheck1%subCheck == 0))
403 {
404 CanonicalForm bufA= A;
405 subst (bufA, bufA, subCheck, x);
406 factors= biFactorize (bufA, v);
407 reverseSubst (factors, subCheck, x);
408 appendSwapDecompress (factors, conv (contentAxFactors),
409 conv (contentAyFactors), swap, swap2, N);
410 if (isOn (SW_RATIONAL))
411 normalize (factors);
412 return factors;
413 }
414 }
415
416 if (subCheck2 > 0)
417 {
418 int subCheck= substituteCheck (bufUniFactors2);
419
420 if (subCheck > 1 && (subCheck2%subCheck == 0))
421 {
422 CanonicalForm bufA= A;
423 subst (bufA, bufA, subCheck, y);
424 factors= biFactorize (bufA, v);
425 reverseSubst (factors, subCheck, y);
426 appendSwapDecompress (factors, conv (contentAxFactors),
427 conv (contentAyFactors), swap, swap2, N);
428 if (isOn (SW_RATIONAL))
429 normalize (factors);
430 return factors;
431 }
432 }
433 }
434
435 // degree analysis
436 bufDegs = DegreePattern (bufUniFactors);
437 bufDegs2= DegreePattern (bufUniFactors2);
438
439 if (i == 0)
440 {
441 Aeval= bufAeval;
442 evaluation= bufEvaluation;
443 uniFactors= bufUniFactors;
444 degs= bufDegs;
445 Aeval2= bufAeval2;
446 evaluation2= bufEvaluation2;
447 uniFactors2= bufUniFactors2;
448 degs2= bufDegs2;
449 }
450 else
451 {
452 degs.intersect (bufDegs);
453 degs2.intersect (bufDegs2);
454 if (bufUniFactors2.length() < uniFactors2.length())
455 {
456 uniFactors2= bufUniFactors2;
457 Aeval2= bufAeval2;
458 evaluation2= bufEvaluation2;
459 }
460 if (bufUniFactors.length() < uniFactors.length())
461 {
462 uniFactors= bufUniFactors;
463 Aeval= bufAeval;
464 evaluation= bufEvaluation;
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
477 if (uniFactors.length() > uniFactors2.length() ||
478 (uniFactors.length() == uniFactors2.length()
479 && degs.getLength() > degs2.getLength()))
480 {
481 degs= degs2;
482 uniFactors= uniFactors2;
483 evaluation= evaluation2;
484 Aeval= Aeval2;
485 A= buf;
486 swap2= true;
487 }
488
489 if (degs.getLength() == 1) // A is irreducible
490 {
491 factors.append (A);
492 appendSwapDecompress (factors, conv (contentAxFactors),
493 conv (contentAyFactors), swap, swap2, N);
494 if (isOn (SW_RATIONAL))
495 normalize (factors);
496 return factors;
497 }
498
499 A *= bCommonDen (A);
500 A= A (y + evaluation, y);
501
502 int liftBound= degree (A, y) + 1;
503
504 modpk b= modpk();
505 bool mipoHasDen= false;
507 if (!extension)
508 {
510 int i= 0;
511 findGoodPrime(F,i);
514 if (i >= cf_getNumBigPrimes())
515 printf ("out of primes\n"); //TODO exit
516
517 int p=cf_getBigPrime(i);
518 b = coeffBound( A, p );
519 modpk bb= coeffBound (Aeval, p);
520 if (bb.getk() > b.getk() ) b=bb;
521 bb= coeffBound (F, p);
522 if (bb.getk() > b.getk() ) b=bb;
523 }
524 else
525 {
526 A /= Lc (Aeval);
527 mipoHasDen= !bCommonDen(mipo).isOne();
528 mipo *= bCommonDen (mipo);
529 #ifdef HAVE_FLINT
530 // init
531 fmpz_t FLINTf,FLINTD;
532 fmpz_init(FLINTf);
533 fmpz_init(FLINTD);
534 fmpz_poly_t FLINTmipo;
535 fmpz_poly_t FLINTLcf;
536 //conversion
539 // resultant, discriminant
540 fmpz_poly_resultant(FLINTf,FLINTmipo,FLINTLcf);
541 fmpz_poly_discriminant(FLINTD,FLINTmipo);
542 fmpz_mul(FLINTf,FLINTD,FLINTf);
543 // conversion
544 den= abs (convertFmpz2CF(FLINTf));
545 // clean up
546 fmpz_clear(FLINTf);
547 // FLINTD is used below
548 fmpz_poly_clear(FLINTLcf);
549 fmpz_poly_clear(FLINTmipo);
550 #elif defined(HAVE_NTL)
551 ZZX NTLmipo= convertFacCF2NTLZZX (mipo);
552 ZZX NTLLcf= convertFacCF2NTLZZX (Lc (A*bCommonDen (A)));
553 ZZ NTLf= resultant (NTLmipo, NTLLcf);
554 ZZ NTLD= discriminant (NTLmipo);
555 den= abs (convertZZ2CF (NTLD*NTLf));
556 #else
557 factoryError("NTL/FLINT missing: biFactorize");
558 #endif
559
560 // make factors elements of Z(a)[x] disable for modularDiophant
561 CanonicalForm multiplier= 1;
562 for (CFListIterator i= uniFactors; i.hasItem(); i++)
563 {
564 multiplier *= bCommonDen (i.getItem());
565 i.getItem()= i.getItem()*bCommonDen(i.getItem());
566 }
567 A *= multiplier;
568 A *= bCommonDen (A);
569
571 int i= 0;
572 #ifdef HAVE_FLINT
573 CanonicalForm discMipo= convertFmpz2CF(FLINTD);
574 fmpz_clear(FLINTD);
575 #elif defined(HAVE_NTL)
576 CanonicalForm discMipo= convertZZ2CF (NTLD);
577 #else
578 factoryError("NTL/FLINT missing: biFactorize");
579 #endif
580 findGoodPrime (F*discMipo,i);
581 findGoodPrime (Aeval*discMipo,i);
582 findGoodPrime (A*discMipo,i);
583
584 int p=cf_getBigPrime(i);
585 b = coeffBound( A, p, mipo );
586 modpk bb= coeffBound (Aeval, p, mipo);
587 if (bb.getk() > b.getk() ) b=bb;
588 bb= coeffBound (F, p, mipo);
589 if (bb.getk() > b.getk() ) b=bb;
590 }
591
592 ExtensionInfo dummy= ExtensionInfo (false);
593 if (extension)
594 dummy= ExtensionInfo (v, false);
595 bool earlySuccess= false;
596 CFList earlyFactors;
597 TIMING_START (fac_bi_hensel_lift);
598 uniFactors= henselLiftAndEarly
599 (A, earlySuccess, earlyFactors, degs, liftBound,
600 uniFactors, dummy, evaluation, b, den);
601 TIMING_END_AND_PRINT (fac_bi_hensel_lift,
602 "time for bivariate hensel lifting over Q: ");
603 DEBOUTLN (cerr, "lifted factors= " << uniFactors);
604
605 CanonicalForm MODl= power (y, liftBound);
606
607 if (mipoHasDen)
608 {
609 Variable vv;
610 for (CFListIterator iter= uniFactors; iter.hasItem(); iter++)
611 if (hasFirstAlgVar (iter.getItem(), vv))
612 break;
613 for (CFListIterator iter= uniFactors; iter.hasItem(); iter++)
614 iter.getItem()= replacevar (iter.getItem(), vv, v);
615 //prune (vv);
616 }
617
618 On (SW_RATIONAL);
619 A *= bCommonDen (A);
621
622 TIMING_START (fac_bi_factor_recombination);
623 factors= factorRecombination (uniFactors, A, MODl, degs, evaluation, 1,
624 uniFactors.length()/2, b, den);
625 TIMING_END_AND_PRINT (fac_bi_factor_recombination,
626 "time for bivariate factor recombination over Q: ");
627
628 On (SW_RATIONAL);
629
630 if (earlySuccess)
631 factors= Union (earlyFactors, factors);
632 else if (!earlySuccess && degs.getLength() == 1)
633 factors= earlyFactors;
634
635 appendSwapDecompress (factors, conv (contentAxFactors),
636 conv (contentAyFactors), swap, swap2, N);
637 if (isOn (SW_RATIONAL))
638 normalize (factors);
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)
Definition: GMPrat.cc:436
CanonicalForm convertZZ2CF(const ZZ &a)
NAME: convertZZ2CF.
Definition: NTLconvert.cc:495
ZZX convertFacCF2NTLZZX(const CanonicalForm &f)
Definition: NTLconvert.cc:691
#define swap(_i, _j)
bool isOn(int sw)
switches
void On(int sw)
switches
void Off(int sw)
switches
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
CanonicalForm FACTORY_PUBLIC content(const CanonicalForm &)
CanonicalForm content ( const CanonicalForm & f )
Definition: cf_gcd.cc:603
int size(const CanonicalForm &f, const Variable &v)
int size ( const CanonicalForm & f, const Variable & v )
Definition: cf_ops.cc:600
CanonicalForm FACTORY_PUBLIC replacevar(const CanonicalForm &, const Variable &, const Variable &)
CanonicalForm replacevar ( const CanonicalForm & f, const Variable & x1, const Variable & x2 )
Definition: cf_ops.cc:271
int degree(const CanonicalForm &f)
bool hasFirstAlgVar(const CanonicalForm &f, Variable &a)
check if poly f contains an algebraic variable a
Definition: cf_ops.cc:679
CanonicalForm FACTORY_PUBLIC swapvar(const CanonicalForm &, const Variable &, const Variable &)
swapvar() - swap variables x1 and x2 in f.
Definition: cf_ops.cc:168
CanonicalForm den(const CanonicalForm &f)
CanonicalForm Lc(const CanonicalForm &f)
List< CanonicalForm > CFList
const CanonicalForm CFMap CFMap & N
Definition: cfEzgcd.cc:56
Variable x
Definition: cfModGcd.cc:4082
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
Definition: cf_factor.cc:405
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
Definition: cf_defs.h:31
CanonicalForm compress(const CanonicalForm &f, CFMap &m)
CanonicalForm compress ( const CanonicalForm & f, CFMap & m )
Definition: cf_map.cc:210
int cf_getBigPrime(int i)
Definition: cf_primes.cc:39
int cf_getNumBigPrimes()
Definition: cf_primes.cc:45
VAR void(* factoryError)(const char *s)
Definition: cf_util.cc:80
int igcd(int a, int b)
Definition: cf_util.cc:56
class CFMap
Definition: cf_map.h:85
factory's main class
Definition: canonicalform.h:86
CF_NO_INLINE bool isOne() const
bool inCoeffDomain() const
int level() const
level() returns the level of CO.
DegreePattern provides a functionality to create, intersect and refine degree patterns.
Definition: DegreePattern.h:32
void intersect(const DegreePattern &degPat)
intersect two degree patterns
int getLength() const
getter
Definition: DegreePattern.h:86
ExtensionInfo contains information about extension.
Definition: ExtensionInfo.h:51
T & getItem() const
Definition: ftmpl_list.cc:431
T getFirst() const
Definition: ftmpl_list.cc:279
void removeFirst()
Definition: ftmpl_list.cc:287
int length() const
Definition: ftmpl_list.cc:273
void append(const T &)
Definition: ftmpl_list.cc:256
factory's class for variables
Definition: variable.h:33
int level() const
Definition: variable.h:49
class to do operations mod p^k for int's p and k
Definition: fac_util.h:23
int getk() const
Definition: fac_util.h:36
#define DEBOUTLN(stream, objects)
Definition: debug.h:49
CFFListIterator iter
Definition: facAbsBiFact.cc:53
return result
Definition: facAbsBiFact.cc:75
const CanonicalForm int const CFList & evaluation
Definition: facAbsFact.cc:52
const CanonicalForm int const CFList const Variable & y
Definition: facAbsFact.cc:53
CanonicalForm mipo
Definition: facAlgExt.cc:57
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)
Definition: facBivar.cc:97
CanonicalForm b
Definition: facBivar.cc:42
CanonicalForm evalPoint(const CanonicalForm &F, int &i)
Definition: facBivar.cc:145
int p
Definition: facBivar.cc:39
CFList conv(const CFFList &L)
convert a CFFList to a CFList by dropping the multiplicity
Definition: facBivar.cc:126
CFList biFactorize(const CanonicalForm &F, const Variable &v)
Definition: facBivar.cc:188
int i
Definition: facBivar.cc:41
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
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:39
CFList *& Aeval
<[in] poly
Definition: facFactorize.h:31
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 &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:1152
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:586
fq_nmod_poly_t prod
Definition: facHensel.cc:100
template List< Variable > Union(const List< Variable > &, const List< Variable > &)
int status int void * buf
Definition: si_signals.h:59
#define A
Definition: sirandom.c:24
static poly normalize(poly next_p, ideal add_generators, syStrategy syzstr, int *g_l, int *p_l, int crit_comp)
Definition: syz3.cc:1027
#define TIMING_START(t)
Definition: timing.h:92
#define TIMING_END_AND_PRINT(t, msg)
Definition: timing.h:94
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
Definition: variable.cc:207

◆ 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)

Parameters
[in]fpoly over Z[a]
[in]psome positive integer
[in]mipominimal polynomial with denominator 1

Definition at line 97 of file facBivar.cc.

98{
99 int * degs = degrees( f );
100 int M = 0, i, k = f.level();
101 CanonicalForm K= 1;
102 for ( i = 1; i <= k; i++ )
103 {
104 M += degs[i];
105 K *= degs[i] + 1;
106 }
107 DELETE_ARRAY(degs);
108 K /= power (CanonicalForm (2), k/2);
109 K *= power (CanonicalForm (2), M);
110 int N= degree (mipo);
112 b= 2*power (maxNorm (f), N)*power (maxNorm (mipo), 4*N)*K*
113 power (CanonicalForm (2), N)*
114 power (CanonicalForm (N+1), 4*N);
115 b /= power (abs (lc (mipo)), N);
116
117 CanonicalForm B = p;
118 k = 1;
119 while ( B < b ) {
120 B *= p;
121 k++;
122 }
123 return modpk( p, k );
124}
CanonicalForm lc(const CanonicalForm &f)
int * degrees(const CanonicalForm &f, int *degs=0)
int * degrees ( const CanonicalForm & f, int * degs )
Definition: cf_ops.cc:493
CanonicalForm maxNorm(const CanonicalForm &f)
CanonicalForm maxNorm ( const CanonicalForm & f )
#define DELETE_ARRAY(P)
Definition: cf_defs.h:65
FILE * f
Definition: checklibs.c:9
int M
Definition: facBivar.cc:41
b *CanonicalForm B
Definition: facBivar.cc:52
int k
Definition: facBivar.cc:41

◆ conv()

CFList conv ( const CFFList L)

convert a CFFList to a CFList by dropping the multiplicity

Parameters
[in]La CFFList

Definition at line 126 of file facBivar.cc.

127{
129 for (CFFListIterator i= L; i.hasItem(); i++)
130 result.append (i.getItem().factor());
131 return result;
132}

◆ DELETE_ARRAY()

DELETE_ARRAY ( degs  )

◆ evalPoint()

CanonicalForm evalPoint ( const CanonicalForm F,
int &  i 
)

Definition at line 145 of file facBivar.cc.

146{
147 Variable x= Variable (1);
148 Variable y= Variable (2);
150
151 int k;
152
153 if (i == 0)
154 {
155 if (testPoint (F, result, i))
156 return result;
157 }
158 do
159 {
160 if (i > 0)
161 k= 1;
162 else
163 k= 2;
164 while (k < 3)
165 {
166 if (k == 1)
167 {
168 if (testPoint (F, result, i))
169 return result;
170 }
171 else
172 {
173 if (testPoint (F, result, -i))
174 {
175 i= -i;
176 return result;
177 }
178 else if (i < 0)
179 i= -i;
180 }
181 k++;
182 }
183 i++;
184 } while (1);
185}
bool testPoint(const CanonicalForm &F, CanonicalForm &G, int i)
Definition: facBivar.cc:134

◆ 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

Parameters
[in]fpoly over Z or Z[a]
[in,out]startindex of big prime in cf_primetab.h

Definition at line 61 of file facBivar.cc.

62{
63 if (! f.inBaseDomain() )
64 {
65 CFIterator i = f;
66 for(;;)
67 {
68 if ( i.hasTerms() )
69 {
70 findGoodPrime(i.coeff(),start);
71 if (0==cf_getBigPrime(start)) return;
72 if((i.exp()!=0) && ((i.exp() % cf_getBigPrime(start))==0))
73 {
74 start++;
75 i=f;
76 }
77 else i++;
78 }
79 else break;
80 }
81 }
82 else
83 {
84 if (f.inZ())
85 {
86 if (0==cf_getBigPrime(start)) return;
87 while((!f.isZero()) && (mod(f,cf_getBigPrime(start))==0))
88 {
89 start++;
90 if (0==cf_getBigPrime(start)) return;
91 }
92 }
93 }
94}
CF_NO_INLINE FACTORY_PUBLIC CanonicalForm mod(const CanonicalForm &, const CanonicalForm &)
class to iterate through CanonicalForm's
Definition: cf_iter.h:44

◆ for()

for ( i  = 1; i <= ki++)

Definition at line 43 of file facBivar.cc.

44 {
45 M += degs[i];
46 b *= degs[i] + 1;
47 }

◆ modpk()

return modpk ( p  ,
k   
)

◆ testPoint()

bool testPoint ( const CanonicalForm F,
CanonicalForm G,
int  i 
)

Definition at line 134 of file facBivar.cc.

135{
136 G= F (i, 2);
137 if (G.inCoeffDomain() || degree (F, 1) > degree (G, 1))
138 return false;
139
140 if (degree (gcd (deriv (G, G.mvar()), G)) > 0)
141 return false;
142 return true;
143}
CanonicalForm deriv(const CanonicalForm &f, const Variable &x)
STATIC_VAR TreeM * G
Definition: janet.cc:31
int gcd(int a, int b)
Definition: walkSupport.cc:836

◆ TIMING_DEFINE_PRINT()

TIMING_DEFINE_PRINT ( fac_uni_factorizer  ) const &

◆ while()

while ( )

Definition at line 54 of file facBivar.cc.

54 {
55 B *= p;
56 k++;
57 }

Variable Documentation

◆ b

b = 1

Definition at line 42 of file facBivar.cc.

◆ B

Definition at line 52 of file facBivar.cc.

◆ i

int i

Definition at line 41 of file facBivar.cc.

◆ k

k = f.level()

Definition at line 41 of file facBivar.cc.

◆ M

int M = 0

Definition at line 41 of file facBivar.cc.

◆ p

int p
Initial value:
{
int * degs = degrees( f )

Definition at line 38 of file facBivar.cc.