[3895ab] | 1 | #ifndef CF_GCD_SMALL_H |
---|
| 2 | #define CF_GCD_SMALL_H |
---|
[10af64] | 3 | // -*- c++ -*- |
---|
| 4 | //***************************************************************************** |
---|
| 5 | /** @file cf_gcd_smallp.h |
---|
| 6 | * |
---|
[806c18] | 7 | * @author Martin Lee |
---|
[10af64] | 8 | * @date 22.10.2009 |
---|
| 9 | * |
---|
[806c18] | 10 | * This file defines the functions GCD_Fp_extension which computes the GCD of |
---|
| 11 | * two polynomials over \f$ F_{p}(\alpha ) \f$ , GCD_small_p which computes the |
---|
| 12 | * GCD of two polynomials over \f$ F_{p} \f$ , and GCD_GF which computes the |
---|
| 13 | * GCD of two polynomials over GF. Algorithms are based on "On the Genericity of |
---|
[10af64] | 14 | * the Modular Polynomial GCD Algorithm" by E. Kaltofen & M. Monagan |
---|
| 15 | * |
---|
| 16 | * @par Copyright: |
---|
| 17 | * (c) by The SINGULAR Team, see LICENSE file |
---|
| 18 | * |
---|
[806c18] | 19 | * @internal |
---|
[10af64] | 20 | * @version \$Id$ |
---|
| 21 | * |
---|
| 22 | **/ |
---|
| 23 | //***************************************************************************** |
---|
| 24 | |
---|
[e4fe2b] | 25 | // #include "config.h" |
---|
[650f2d8] | 26 | #include "cf_assert.h" |
---|
[b1070f] | 27 | |
---|
[f71453] | 28 | #include "cf_factory.h" |
---|
| 29 | |
---|
[b1070f] | 30 | CanonicalForm GCD_Fp_extension (const CanonicalForm& F, const CanonicalForm& G, |
---|
| 31 | Variable & alpha, CFList& l, bool& top_level); |
---|
[10af64] | 32 | |
---|
[806c18] | 33 | /// GCD of A and B over \f$ F_{p}(\alpha ) \f$ |
---|
| 34 | static inline CanonicalForm GCD_Fp_extension (const CanonicalForm& A, const CanonicalForm& B, |
---|
| 35 | Variable & alpha) |
---|
[10af64] | 36 | { |
---|
| 37 | CFList list; |
---|
| 38 | bool top_level= true; |
---|
| 39 | return GCD_Fp_extension (A, B, alpha, list, top_level); |
---|
| 40 | } |
---|
| 41 | |
---|
[b1070f] | 42 | |
---|
| 43 | CanonicalForm GCD_small_p (const CanonicalForm& F, const CanonicalForm& G, |
---|
| 44 | bool& top_level, CFList& l); |
---|
| 45 | |
---|
[597783] | 46 | CanonicalForm GCD_small_p (const CanonicalForm& F, const CanonicalForm& G, CanonicalForm& coF, CanonicalForm& coG, |
---|
| 47 | bool& topLevel, CFList& l); |
---|
| 48 | |
---|
[10af64] | 49 | ///GCD of A and B over \f$ F_{p} \f$ |
---|
[b1070f] | 50 | static inline CanonicalForm GCD_small_p (const CanonicalForm& A, const CanonicalForm& B) |
---|
[10af64] | 51 | { |
---|
| 52 | CFList list; |
---|
| 53 | bool top_level= true; |
---|
| 54 | return GCD_small_p (A, B, top_level, list); |
---|
| 55 | } |
---|
| 56 | |
---|
[597783] | 57 | static inline CanonicalForm GCD_small_p (const CanonicalForm& A, const CanonicalForm& B, CanonicalForm& coA, CanonicalForm& coB) |
---|
| 58 | { |
---|
| 59 | CFList list; |
---|
| 60 | bool top_level= true; |
---|
| 61 | return GCD_small_p (A, B, coA, coB, top_level, list); |
---|
| 62 | } |
---|
| 63 | |
---|
[b1070f] | 64 | CanonicalForm GCD_GF (const CanonicalForm& F, const CanonicalForm& G, CFList& l, |
---|
| 65 | bool& top_level); |
---|
| 66 | |
---|
[10af64] | 67 | /// GCD of A and B over GF |
---|
[806c18] | 68 | static inline CanonicalForm GCD_GF (const CanonicalForm& A, const CanonicalForm& B) |
---|
[10af64] | 69 | { |
---|
[806c18] | 70 | ASSERT (CFFactory::gettype() == GaloisFieldDomain, |
---|
[10af64] | 71 | "GF as base field expected"); |
---|
| 72 | CFList list; |
---|
| 73 | bool top_level= true; |
---|
| 74 | return GCD_GF (A, B, list, top_level); |
---|
| 75 | } |
---|
[fecc08] | 76 | |
---|
[08daea] | 77 | CanonicalForm sparseGCDFp (const CanonicalForm& F, const CanonicalForm& G, |
---|
| 78 | bool& topLevel, CFList& l); |
---|
| 79 | |
---|
| 80 | /// Zippel's sparse GCD over Fp |
---|
| 81 | static inline |
---|
| 82 | CanonicalForm sparseGCDFp (const CanonicalForm& A, const CanonicalForm& B) |
---|
| 83 | { |
---|
| 84 | ASSERT (CFFactory::gettype() == GaloisFieldDomain, |
---|
| 85 | "GF as base field expected"); |
---|
| 86 | CFList list; |
---|
| 87 | bool topLevel= true; |
---|
| 88 | return sparseGCDFp (A, B, topLevel, list); |
---|
| 89 | } |
---|
| 90 | |
---|
| 91 | /// Zippel's sparse GCD over Fq |
---|
| 92 | CanonicalForm |
---|
| 93 | sparseGCDFq (const CanonicalForm& F, const CanonicalForm& G, |
---|
| 94 | const Variable& alpha, CFList& l, bool& topLevel); |
---|
| 95 | |
---|
| 96 | static inline |
---|
| 97 | CanonicalForm sparseGCDFq (const CanonicalForm& A, const CanonicalForm& B, |
---|
| 98 | const Variable& alpha) |
---|
| 99 | { |
---|
| 100 | CFList list; |
---|
| 101 | bool topLevel= true; |
---|
| 102 | return sparseGCDFq (A, B, alpha, list, topLevel); |
---|
| 103 | } |
---|
| 104 | |
---|
| 105 | /// extended Zassenhaus GCD |
---|
| 106 | CanonicalForm |
---|
| 107 | EZGCD_P (const CanonicalForm& A, const CanonicalForm& B); |
---|
| 108 | |
---|
[806c18] | 109 | CanonicalForm |
---|
[c4f4fd] | 110 | randomIrredpoly (int i, const Variable & x) ; |
---|
[6deedd] | 111 | |
---|
| 112 | CFArray |
---|
| 113 | getMonoms (const CanonicalForm& F); |
---|
[1e4b53] | 114 | |
---|
| 115 | bool |
---|
| 116 | terminationTest (const CanonicalForm& F, const CanonicalForm& G, |
---|
| 117 | const CanonicalForm& coF, const CanonicalForm& coG, |
---|
| 118 | const CanonicalForm& cand); |
---|
[3895ab] | 119 | #endif |
---|