1 #ifndef CF_MOD_GCD_H
2 #define CF_MOD_GCD_H
3 // -*- c++ -*-
4 //*****************************************************************************
5 /** @file cfModGcd.h
6 *
7 * modular and sparse modular GCD algorithms over finite fields and Z.
8 *
9 * @author Martin Lee
10 * @date 22.10.2009
11 *
12 * @par Copyright:
13 * (c) by The SINGULAR Team, see LICENSE file
14 *
15 **/
16 //*****************************************************************************
17
18 // #include "config.h"
19 #include "cf_assert.h"
20
21 #include "cf_factory.h"
22
23 CanonicalForm modGCDFq (const CanonicalForm& F, const CanonicalForm& G,
24 Variable & alpha, CFList& l, bool& top_level);
25
26 /// GCD of A and B over \f$ F_{p}(\alpha ) \f$
27 static inline
modGCDFq(const CanonicalForm & A,const CanonicalForm & B,Variable & alpha)28 CanonicalForm modGCDFq (const CanonicalForm& A, ///<[in] poly over F_q
29 const CanonicalForm& B, ///<[in] poly over F_q
30 Variable & alpha ///<[in] algebraic variable
31 )
32 {
33 CFList list;
34 bool top_level= true;
35 return modGCDFq (A, B, alpha, list, top_level);
36 }
37
38
39 CanonicalForm
40 modGCDFp (const CanonicalForm& F, const CanonicalForm& G, bool& top_level,
41 CFList& l);
42
43 CanonicalForm
44 modGCDFp (const CanonicalForm& F, const CanonicalForm& G,
45 CanonicalForm& coF, CanonicalForm& coG,
46 bool& topLevel, CFList& l);
47
48 ///GCD of A and B over \f$ F_{p} \f$
49 static inline
modGCDFp(const CanonicalForm & A,const CanonicalForm & B)50 CanonicalForm modGCDFp (const CanonicalForm& A, ///<[in] poly over F_p
51 const CanonicalForm& B ///<[in] poly over F_p
52 )
53 {
54 CFList list;
55 bool top_level= true;
56 return modGCDFp (A, B, top_level, list);
57 }
58
59 static inline
modGCDFp(const CanonicalForm & A,const CanonicalForm & B,CanonicalForm & coA,CanonicalForm & coB)60 CanonicalForm modGCDFp (const CanonicalForm& A, const CanonicalForm& B,
61 CanonicalForm& coA, CanonicalForm& coB)
62 {
63 CFList list;
64 bool top_level= true;
65 return modGCDFp (A, B, coA, coB, top_level, list);
66 }
67
68 CanonicalForm
69 modGCDGF (const CanonicalForm& F, const CanonicalForm& G, CFList& l,
70 bool& top_level);
71
72 /// GCD of A and B over GF
73 static inline
modGCDGF(const CanonicalForm & A,const CanonicalForm & B)74 CanonicalForm modGCDGF (const CanonicalForm& A, ///<[in] poly over GF
75 const CanonicalForm& B ///<[in] poly over GF
76 )
77 {
78 ASSERT (CFFactory::gettype() == GaloisFieldDomain,
79 "GF as base field expected");
80 CFList list;
81 bool top_level= true;
82 return modGCDGF (A, B, list, top_level);
83 }
84
85 CanonicalForm sparseGCDFp (const CanonicalForm& F, const CanonicalForm& G,
86 bool& topLevel, CFList& l);
87
88 /// Zippel's sparse GCD over Fp
89 static inline
sparseGCDFp(const CanonicalForm & A,const CanonicalForm & B)90 CanonicalForm sparseGCDFp (const CanonicalForm& A, ///<[in] poly over F_p
91 const CanonicalForm& B ///<[in] poly over F_p
92 )
93 {
94 ASSERT (CFFactory::gettype() == FiniteFieldDomain,
95 "Fp as base field expected");
96 CFList list;
97 bool topLevel= true;
98 return sparseGCDFp (A, B, topLevel, list);
99 }
100
101
102 CanonicalForm
103 sparseGCDFq (const CanonicalForm& F, const CanonicalForm& G,
104 const Variable& alpha, CFList& l, bool& topLevel);
105
106 /// Zippel's sparse GCD over Fq
107 static inline
sparseGCDFq(const CanonicalForm & A,const CanonicalForm & B,const Variable & alpha)108 CanonicalForm sparseGCDFq (const CanonicalForm& A, ///<[in] poly over F_q
109 const CanonicalForm& B, ///<[in] poly over F_q
110 const Variable& alpha ///<[in] algebraic variable
111 )
112 {
113 CFList list;
114 bool topLevel= true;
115 return sparseGCDFq (A, B, alpha, list, topLevel);
116 }
117
118 /// extract monomials of F, parts in algebraic variable are considered
119 /// coefficients
120 CFArray
121 getMonoms (const CanonicalForm& F ///<[in] some poly
122 );
123
124 bool
125 terminationTest (const CanonicalForm& F, const CanonicalForm& G,
126 const CanonicalForm& coF, const CanonicalForm& coG,
127 const CanonicalForm& cand);
128
129 /// modular GCD over Z
130 CanonicalForm modGCDZ (const CanonicalForm & FF, ///<[in] poly over Z
131 const CanonicalForm & GG ///<[in] poly over Z
132 );
133 #endif
134