My Project
Loading...
Searching...
No Matches
facBivar.cc
Go to the documentation of this file.
1/*****************************************************************************\
2 * Computer Algebra System SINGULAR
3\*****************************************************************************/
4/** @file facBivar.cc
5 *
6 * bivariate factorization over Q(a)
7 *
8 * @author Martin Lee
9 *
10 **/
11/*****************************************************************************/
12
13
14#include "config.h"
15
16
17#include "cf_assert.h"
18#include "cf_util.h"
19#include "debug.h"
20#include "timing.h"
21
22#include "cf_algorithm.h"
23#include "facFqBivar.h"
24#include "facBivar.h"
25#include "facHensel.h"
26#include "facMul.h"
27#include "cf_primes.h"
28
34
35// bound on coeffs of f (cf. Musser: Multivariate Polynomial Factorization,
36// Gelfond: Transcendental and Algebraic Numbers)
38coeffBound ( const CanonicalForm & f, int p )
39{
40 int * degs = degrees( f );
41 int M = 0, i, k = f.level();
43 for ( i = 1; i <= k; i++ )
44 {
45 M += degs[i];
46 b *= degs[i] + 1;
47 }
49 b /= power (CanonicalForm (2), k);
50 b= b.sqrt() + 1;
51 b *= 2 * maxNorm( f ) * power( CanonicalForm( 2 ), M );
53 k = 1;
54 while ( B < b ) {
55 B *= p;
56 k++;
57 }
58 return modpk( p, k );
59}
60
61void findGoodPrime(const CanonicalForm &f, int &start)
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}
95
97coeffBound ( const CanonicalForm & f, int p, const CanonicalForm& mipo )
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 }
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}
125
127{
129 for (CFFListIterator i= L; i.hasItem(); i++)
130 result.append (i.getItem().factor());
131 return result;
132}
133
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}
144
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}
186
187#if defined(HAVE_NTL) || defined(HAVE_FLINT) // henselLiftAndEarly
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
226
229
230 if (extension)
231 {
232 if (!contentAx.inCoeffDomain())
233 {
235 if (contentAxFactors.getFirst().factor().inCoeffDomain())
237 }
238 if (!contentAy.inCoeffDomain())
239 {
241 if (contentAyFactors.getFirst().factor().inCoeffDomain())
243 }
244 }
245 else
246 {
247 if (!contentAx.inCoeffDomain())
248 {
250 if (contentAxFactors.getFirst().factor().inCoeffDomain())
252 }
253 if (!contentAy.inCoeffDomain())
254 {
256 if (contentAyFactors.getFirst().factor().inCoeffDomain())
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 {
266 factors.append (A);
267
269 conv (contentAyFactors), false, false, N);
270
272 return factors;
273 }
274
275 //trivial case
277 if (A.inCoeffDomain())
278 {
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));
293 return factors;
294 }
295
296 if (irreducibilityTest (A))
297 {
299 factors.append (A);
300
302 conv (contentAyFactors), false, false, N);
303
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
318
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;
331 buf= swapvar (A,x,y);
333 for (int i= 0; i < factorNums; i++)
334 {
335 bufAeval= A;
338 TIMING_END_AND_PRINT (fac_bi_evaluation, "time for eval point over Q: ");
339
340 bufAeval2= buf;
344 "time for eval point over Q in y: ");
345
346 // univariate factorization
348 if (extension)
350 else
353 "time for univariate factorization over Q: ");
354 DEBOUTLN (cerr, "prod (bufUniFactors)== bufAeval " <<
356
357 if (bufUniFactors.getFirst().inCoeffDomain())
359
360 if (bufUniFactors.length() == 1)
361 {
362 factors.append (A);
363
366
367 if (isOn (SW_RATIONAL))
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 " <<
381
382 if (bufUniFactors2.getFirst().inCoeffDomain())
384 if (bufUniFactors2.length() == 1)
385 {
386 factors.append (A);
387
390
391 if (isOn (SW_RATIONAL))
393 return factors;
394 }
395
396 if (i == 0)
397 {
398 if (subCheck1 > 0)
399 {
401
402 if (subCheck > 1 && (subCheck1%subCheck == 0))
403 {
405 subst (bufA, bufA, subCheck, x);
410 if (isOn (SW_RATIONAL))
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);
428 if (isOn (SW_RATIONAL))
430 return factors;
431 }
432 }
433 }
434
435 // degree analysis
438
439 if (i == 0)
440 {
444 degs= bufDegs;
449 }
450 else
451 {
452 degs.intersect (bufDegs);
453 degs2.intersect (bufDegs2);
455 {
459 }
461 {
465 }
466 }
467 if (bufEvaluation > 0)
469 else
471 if (bufEvaluation > 0)
473 else
475 }
476
479 && degs.getLength() > degs2.getLength()))
480 {
481 degs= degs2;
484 Aeval= Aeval2;
485 A= buf;
486 swap2= true;
487 }
488
489 if (degs.getLength() == 1) // A is irreducible
490 {
491 factors.append (A);
494 if (isOn (SW_RATIONAL))
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 );
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);
528 mipo *= bCommonDen (mipo);
529 #ifdef HAVE_FLINT
530 // init
536 //conversion
539 // resultant, discriminant
543 // conversion
545 // clean up
547 // FLINTD is used below
550 #elif defined(HAVE_NTL)
554 ZZ NTLD= discriminant (NTLmipo);
556 #else
557 factoryError("NTL/FLINT missing: biFactorize");
558 #endif
559
560 // make factors elements of Z(a)[x] disable for modularDiophant
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
575 #elif defined(HAVE_NTL)
577 #else
578 factoryError("NTL/FLINT missing: biFactorize");
579 #endif
583
584 int p=cf_getBigPrime(i);
585 b = coeffBound( A, 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
593 if (extension)
594 dummy= ExtensionInfo (v, false);
595 bool earlySuccess= false;
602 "time for bivariate hensel lifting over Q: ");
603 DEBOUTLN (cerr, "lifted factors= " << uniFactors);
604
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
624 uniFactors.length()/2, b, den);
626 "time for bivariate factor recombination over Q: ");
627
628 On (SW_RATIONAL);
629
630 if (earlySuccess)
632 else if (!earlySuccess && degs.getLength() == 1)
634
637 if (isOn (SW_RATIONAL))
639
640 return factors;
641}
642#endif
643
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.
ZZX convertFacCF2NTLZZX(const CanonicalForm &f)
#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 lc(const CanonicalForm &f)
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 * degrees(const CanonicalForm &f, int *degs=0)
int * degrees ( const CanonicalForm & f, int * degs )
Definition cf_ops.cc:493
CF_NO_INLINE FACTORY_PUBLIC CanonicalForm mod(const CanonicalForm &, const CanonicalForm &)
int degree(const CanonicalForm &f)
CanonicalForm deriv(const CanonicalForm &f, const Variable &x)
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 )
CanonicalForm maxNorm(const CanonicalForm &f)
CanonicalForm maxNorm ( const CanonicalForm & f )
declarations of higher level algorithms.
CFFList FACTORY_PUBLIC factorize(const CanonicalForm &f, bool issqrfree=false)
factorization over or
Definition cf_factor.cc:409
CanonicalForm FACTORY_PUBLIC resultant(const CanonicalForm &f, const CanonicalForm &g, const Variable &x)
CanonicalForm resultant ( const CanonicalForm & f, const CanonicalForm & g, const Variable & x )
assertions for Factory
#define DELETE_ARRAY(P)
Definition cf_defs.h:65
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
access to prime tables
VAR void(* factoryError)(const char *s)
Definition cf_util.cc:80
int igcd(int a, int b)
Definition cf_util.cc:56
FILE * f
Definition checklibs.c:9
class to iterate through CanonicalForm's
Definition cf_iter.h:44
class CFMap
Definition cf_map.h:85
factory's main class
CF_NO_INLINE bool isOne() const
bool inCoeffDomain() const
int level() const
level() returns the level of CO.
CanonicalForm sqrt() const
CanonicalForm CanonicalForm::sqrt () const.
DegreePattern provides a functionality to create, intersect and refine degree patterns.
ExtensionInfo contains information about extension.
T getFirst() const
void removeFirst()
int length() const
void append(const T &)
factory's class for variables
Definition factory.h:127
int level() const
Definition factory.h:143
class to do operations mod p^k for int's p and k
Definition fac_util.h:23
functions to print debug output
#define DEBOUTLN(stream, objects)
Definition debug.h:49
CFFListIterator iter
return result
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
bool testPoint(const CanonicalForm &F, CanonicalForm &G, int i)
Definition facBivar.cc:134
int p
Definition facBivar.cc:39
int M
Definition facBivar.cc:41
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
b *CanonicalForm B
Definition facBivar.cc:52
int k
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
bivariate factorization over Q(a)
const Variable & v
< [in] a sqrfree bivariate poly
Definition facBivar.h:39
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 &degs, 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 &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...
This file provides functions for factorizing a bivariate polynomial over , or GF.
fq_nmod_poly_t prod
Definition facHensel.cc:100
This file defines functions for Hensel lifting.
This file defines functions for fast multiplication and division with remainder.
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
Definition variable.cc:207
template List< Variable > Union(const List< Variable > &, const List< Variable > &)
STATIC_VAR TreeM * G
Definition janet.cc:31
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_DEFINE_PRINT(t)
Definition timing.h:95
#define TIMING_START(t)
Definition timing.h:92
#define TIMING_END_AND_PRINT(t, msg)
Definition timing.h:94
int gcd(int a, int b)