1 | /* emacs edit mode for this file is -*- C++ -*- */ |
---|
2 | /* $Id: cf_factor.cc,v 1.8 1997-12-08 18:24:23 schmidt Exp $ */ |
---|
3 | |
---|
4 | //{{{ docu |
---|
5 | // |
---|
6 | // cf_factor.cc - factorization and square free algorithms. |
---|
7 | // |
---|
8 | // Used by: fac_multivar.cc, fac_univar.cc, cf_irred.cc |
---|
9 | // |
---|
10 | // Header file: cf_algorithm.h |
---|
11 | // |
---|
12 | //}}} |
---|
13 | |
---|
14 | #include <config.h> |
---|
15 | |
---|
16 | #include "cf_gmp.h" |
---|
17 | |
---|
18 | #include "assert.h" |
---|
19 | |
---|
20 | #include "cf_defs.h" |
---|
21 | #include "canonicalform.h" |
---|
22 | #include "cf_iter.h" |
---|
23 | #include "fac_berlekamp.h" |
---|
24 | #include "fac_cantzass.h" |
---|
25 | #include "fac_univar.h" |
---|
26 | #include "fac_multivar.h" |
---|
27 | #include "fac_sqrfree.h" |
---|
28 | |
---|
29 | static bool isUnivariateBaseDomain( const CanonicalForm & f ) |
---|
30 | { |
---|
31 | CFIterator i = f; |
---|
32 | bool ok = i.coeff().inBaseDomain(); |
---|
33 | i++; |
---|
34 | while ( i.hasTerms() && ( ok = ok && i.coeff().inBaseDomain() ) ) i++; |
---|
35 | return ok; |
---|
36 | } |
---|
37 | |
---|
38 | CFFList factorize ( const CanonicalForm & f, bool issqrfree ) |
---|
39 | { |
---|
40 | if ( f.inCoeffDomain() ) |
---|
41 | return CFFList( f ); |
---|
42 | if ( getCharacteristic() > 0 ) { |
---|
43 | ASSERT( f.isUnivariate(), "multivariate factorization not implemented" ); |
---|
44 | if ( isOn( SW_BERLEKAMP ) ) |
---|
45 | return FpFactorizeUnivariateB( f, issqrfree ); |
---|
46 | else |
---|
47 | return FpFactorizeUnivariateCZ( f, issqrfree, 0, Variable(), Variable() ); |
---|
48 | } |
---|
49 | else { |
---|
50 | if ( f.isUnivariate() ) |
---|
51 | return ZFactorizeUnivariate( f, issqrfree ); |
---|
52 | else |
---|
53 | return ZFactorizeMultivariate( f, issqrfree ); |
---|
54 | } |
---|
55 | } |
---|
56 | |
---|
57 | CFFList factorize ( const CanonicalForm & f, const Variable & alpha ) |
---|
58 | { |
---|
59 | ASSERT( alpha.level() < 0, "not an algebraic extension" ); |
---|
60 | ASSERT( f.isUnivariate(), "multivariate factorization not implemented" ); |
---|
61 | ASSERT( getCharacteristic() > 0, "char 0 factorization not implemented" ); |
---|
62 | return FpFactorizeUnivariateCZ( f, false, 1, alpha, Variable() ); |
---|
63 | } |
---|
64 | |
---|
65 | CFFList sqrFree ( const CanonicalForm & f, bool sort ) |
---|
66 | { |
---|
67 | // ASSERT( f.isUnivariate(), "multivariate factorization not implemented" ); |
---|
68 | CFFList result; |
---|
69 | |
---|
70 | if ( getCharacteristic() == 0 ) |
---|
71 | result = sqrFreeZ( f ); |
---|
72 | else |
---|
73 | result = sqrFreeFp( f ); |
---|
74 | |
---|
75 | return ( sort ? sortCFFList( result ) : result ); |
---|
76 | } |
---|
77 | |
---|
78 | bool isSqrFree ( const CanonicalForm & f ) |
---|
79 | { |
---|
80 | // ASSERT( f.isUnivariate(), "multivariate factorization not implemented" ); |
---|
81 | if ( getCharacteristic() == 0 ) |
---|
82 | return isSqrFreeZ( f ); |
---|
83 | else |
---|
84 | return isSqrFreeFp( f ); |
---|
85 | } |
---|