source:git/factory/cf_gcd_smallp.h@0d5627

jengelh-datetimespielwiese
Last change on this file since 0d5627 was 597783, checked in by Martin Lee <martinlee84@…>, 11 years ago
chg: compute cofactors of gcd and use them to test divisibility chg: do not use bounds in gcd over Fq
• Property mode set to 100644
File size: 3.4 KB
Line
1#ifndef CF_GCD_SMALL_H
2#define CF_GCD_SMALL_H
3// -*- c++ -*-
4//*****************************************************************************
5/** @file cf_gcd_smallp.h
6 *
7 * @author Martin Lee
8 * @date   22.10.2009
9 *
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
14 * the Modular Polynomial GCD Algorithm" by E. Kaltofen & M. Monagan
15 *
17 *   (c) by The SINGULAR Team, see LICENSE file
18 *
19 * @internal
20 * @version \$Id$
21 *
22**/
23//*****************************************************************************
24
25// #include "config.h"
26#include "cf_assert.h"
27
28#include "cf_factory.h"
29
30CanonicalForm GCD_Fp_extension (const CanonicalForm& F, const CanonicalForm& G,
31                  Variable & alpha, CFList& l, bool& top_level);
32
33/// GCD of A and B over \f$F_{p}(\alpha ) \f$
34static inline CanonicalForm GCD_Fp_extension (const CanonicalForm& A, const CanonicalForm& B,
35                                Variable & alpha)
36{
37  CFList list;
38  bool top_level= true;
39  return GCD_Fp_extension (A, B, alpha, list, top_level);
40}
41
42
43CanonicalForm GCD_small_p (const CanonicalForm& F, const CanonicalForm&  G,
44                           bool& top_level, CFList& l);
45
46CanonicalForm GCD_small_p (const CanonicalForm& F, const CanonicalForm&  G, CanonicalForm& coF, CanonicalForm& coG,
47                           bool& topLevel, CFList& l);
48
49///GCD of A and B over \f$F_{p} \f$
50static inline CanonicalForm GCD_small_p (const CanonicalForm& A, const CanonicalForm& B)
51{
52  CFList list;
53  bool top_level= true;
54  return GCD_small_p (A, B, top_level, list);
55}
56
57static 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
64CanonicalForm GCD_GF (const CanonicalForm& F, const CanonicalForm& G, CFList& l,
65        bool& top_level);
66
67/// GCD of A and B over GF
68static inline CanonicalForm GCD_GF (const CanonicalForm& A, const CanonicalForm& B)
69{
70  ASSERT (CFFactory::gettype() == GaloisFieldDomain,
71          "GF as base field expected");
72  CFList list;
73  bool top_level= true;
74  return GCD_GF (A, B, list, top_level);
75}
76
77CanonicalForm sparseGCDFp (const CanonicalForm& F, const CanonicalForm& G,
78                           bool& topLevel, CFList& l);
79
80/// Zippel's sparse GCD over Fp
81static inline
82CanonicalForm 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
92CanonicalForm
93sparseGCDFq (const CanonicalForm& F, const CanonicalForm& G,
94             const Variable& alpha, CFList& l, bool& topLevel);
95
96static inline
97CanonicalForm 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
106CanonicalForm
107EZGCD_P (const CanonicalForm& A, const CanonicalForm& B);
108
109CanonicalForm
110randomIrredpoly (int i, const Variable & x) ;
111
112CFArray
113getMonoms (const CanonicalForm& F);
114#endif
Note: See TracBrowser for help on using the repository browser.