My Project  UNKNOWN_GIT_VERSION
cfGcdUtil.cc
Go to the documentation of this file.
1 #include "config.h"
2 
3 #include "canonicalform.h"
4 #include "cf_factory.h"
5 #include "cf_reval.h"
6 #include "cf_util.h"
7 #include "cf_iter.h"
8 #include "gfops.h"
9 #include "cf_map_ext.h"
11 
12 #ifdef HAVE_NTL
13 #include "NTLconvert.h"
14 #endif
15 
16 /// Coprimality Check. f and g are assumed to have the same level. If swap is
17 /// true, the main variables of f and g are swapped with Variable(1). If the
18 /// result is false, d is set to the degree of the gcd of f and g evaluated at a
19 /// random point in K^n-1. This gcd is a gcd of univariate polynomials.
20 bool
21 gcd_test_one ( const CanonicalForm & f, const CanonicalForm & g, bool swap, int & d )
22 {
23  d= 0;
24  int count = 0;
25  // assume polys have same level;
26 
27  Variable v= Variable (1);
28  bool algExtension= (hasFirstAlgVar (f, v) || hasFirstAlgVar (g, v));
30  if ( swap )
31  {
32  lcf = swapvar( LC( f ), Variable(1), f.mvar() );
33  lcg = swapvar( LC( g ), Variable(1), f.mvar() );
34  }
35  else
36  {
37  lcf = LC( f, Variable(1) );
38  lcg = LC( g, Variable(1) );
39  }
40 
41  CanonicalForm F, G;
42  if ( swap )
43  {
44  F=swapvar( f, Variable(1), f.mvar() );
45  G=swapvar( g, Variable(1), g.mvar() );
46  }
47  else
48  {
49  F = f;
50  G = g;
51  }
52 
53  #define TEST_ONE_MAX 50
54  int p= getCharacteristic();
55  bool passToGF= false;
56  int k= 1;
57  bool extOfExt= false;
58  Variable v3;
59  if (p > 0 && p < TEST_ONE_MAX && CFFactory::gettype() != GaloisFieldDomain && !algExtension)
60  {
61  if (p == 2)
62  setCharacteristic (2, 6, 'Z');
63  else if (p == 3)
64  setCharacteristic (3, 4, 'Z');
65  else if (p == 5 || p == 7)
66  setCharacteristic (p, 3, 'Z');
67  else
68  setCharacteristic (p, 2, 'Z');
69  passToGF= true;
70  }
71  else if (p > 0 && CFFactory::gettype() == GaloisFieldDomain && ipower (p , getGFDegree()) < TEST_ONE_MAX)
72  {
73  k= getGFDegree();
74  if (ipower (p, 2*k) > TEST_ONE_MAX)
76  else
78  F= GFMapUp (F, k);
79  G= GFMapUp (G, k);
80  lcf= GFMapUp (lcf, k);
81  lcg= GFMapUp (lcg, k);
82  }
83  else if (p > 0 && p < TEST_ONE_MAX && algExtension)
84  {
85 #ifdef HAVE_NTL
86  int d= degree (getMipo (v));
87  CFList source, dest;
88  Variable v2;
89  CanonicalForm primElem, imPrimElem;
90  if (p == 2 && d < 6)
91  {
92  if (fac_NTL_char != 2)
93  {
94  fac_NTL_char= 2;
95  zz_p::init (p);
96  }
97  bool primFail= false;
98  Variable vBuf;
99  primElem= primitiveElement (v, vBuf, primFail);
100  ASSERT (!primFail, "failure in integer factorizer");
101  if (d < 3)
102  {
103  zz_pX NTLIrredpoly;
104  BuildIrred (NTLIrredpoly, d*3);
105  CanonicalForm newMipo= convertNTLzzpX2CF (NTLIrredpoly, Variable (1));
106  v2= rootOf (newMipo);
107  }
108  else
109  {
110  zz_pX NTLIrredpoly;
111  BuildIrred (NTLIrredpoly, d*2);
112  CanonicalForm newMipo= convertNTLzzpX2CF (NTLIrredpoly, Variable (1));
113  v2= rootOf (newMipo);
114  }
115  imPrimElem= mapPrimElem (primElem, v, v2);
116  extOfExt= true;
117  }
118  else if ((p == 3 && d < 4) || ((p == 5 || p == 7) && d < 3))
119  {
120  if (fac_NTL_char != p)
121  {
122  fac_NTL_char= p;
123  zz_p::init (p);
124  }
125  bool primFail= false;
126  Variable vBuf;
127  primElem= primitiveElement (v, vBuf, primFail);
128  ASSERT (!primFail, "failure in integer factorizer");
129  zz_pX NTLIrredpoly;
130  BuildIrred (NTLIrredpoly, d*2);
131  CanonicalForm newMipo= convertNTLzzpX2CF (NTLIrredpoly, Variable (1));
132  v2= rootOf (newMipo);
133  imPrimElem= mapPrimElem (primElem, v, v2);
134  extOfExt= true;
135  }
136  if (extOfExt)
137  {
138  v3= v;
139  F= mapUp (F, v, v2, primElem, imPrimElem, source, dest);
140  G= mapUp (G, v, v2, primElem, imPrimElem, source, dest);
141  lcf= mapUp (lcf, v, v2, primElem, imPrimElem, source, dest);
142  lcg= mapUp (lcg, v, v2, primElem, imPrimElem, source, dest);
143  v= v2;
144  }
145 #endif
146  }
147 
148  CFRandom * sample;
149  if ((!algExtension && p > 0) || p == 0)
150  sample = CFRandomFactory::generate();
151  else
152  sample = AlgExtRandomF (v).clone();
153 
154  REvaluation e( 2, tmax( f.level(), g.level() ), *sample );
155  delete sample;
156 
157  if (passToGF)
158  {
159  lcf= lcf.mapinto();
160  lcg= lcg.mapinto();
161  }
162 
163  CanonicalForm eval1, eval2;
164  if (passToGF)
165  {
166  eval1= e (lcf);
167  eval2= e (lcg);
168  }
169  else
170  {
171  eval1= e (lcf);
172  eval2= e (lcg);
173  }
174 
175  while ( ( eval1.isZero() || eval2.isZero() ) && count < TEST_ONE_MAX )
176  {
177  e.nextpoint();
178  count++;
179  eval1= e (lcf);
180  eval2= e (lcg);
181  }
182  if ( count >= TEST_ONE_MAX )
183  {
184  if (passToGF)
186  if (k > 1)
188  if (extOfExt)
189  prune1 (v3);
190  return false;
191  }
192 
193 
194  if (passToGF)
195  {
196  F= F.mapinto();
197  G= G.mapinto();
198  eval1= e (F);
199  eval2= e (G);
200  }
201  else
202  {
203  eval1= e (F);
204  eval2= e (G);
205  }
206 
207  CanonicalForm c= gcd (eval1, eval2);
208  d= c.degree();
209  bool result= d < 1;
210  if (d < 0)
211  d= 0;
212 
213  if (passToGF)
215  if (k > 1)
217  if (extOfExt)
218  prune1 (v3);
219  return result;
220 }
221 
222 /**
223  * same as balance_p ( const CanonicalForm & f, const CanonicalForm & q )
224  * but qh= q/2 is provided, too.
225 **/
227 balance_p ( const CanonicalForm & f, const CanonicalForm & q, const CanonicalForm & qh )
228 {
229  Variable x = f.mvar();
230  CanonicalForm result = 0;
231  CanonicalForm c;
232  CFIterator i;
233  for ( i = f; i.hasTerms(); i++ )
234  {
235  c = i.coeff();
236  if ( c.inCoeffDomain())
237  {
238  if ( c > qh )
239  result += power( x, i.exp() ) * (c - q);
240  else
241  result += power( x, i.exp() ) * c;
242  }
243  else
244  result += power( x, i.exp() ) * balance_p(c,q,qh);
245  }
246  return result;
247 }
248 
249 /** static CanonicalForm balance_p ( const CanonicalForm & f, const CanonicalForm & q )
250  *
251  * balance_p() - map f from positive to symmetric representation
252  * mod q.
253  *
254  * This makes sense for polynomials over Z only.
255  * q should be an integer.
256  *
257 **/
259 balance_p ( const CanonicalForm & f, const CanonicalForm & q )
260 {
261  CanonicalForm qh = q / 2;
262  return balance_p (f, q, qh);
263 }
264 
265 
266 /*static CanonicalForm
267 balance ( const CanonicalForm & f, const CanonicalForm & q )
268 {
269  Variable x = f.mvar();
270  CanonicalForm result = 0, qh = q / 2;
271  CanonicalForm c;
272  CFIterator i;
273  for ( i = f; i.hasTerms(); i++ ) {
274  c = mod( i.coeff(), q );
275  if ( c > qh )
276  result += power( x, i.exp() ) * (c - q);
277  else
278  result += power( x, i.exp() ) * c;
279  }
280  return result;
281 }*/
fac_NTL_char
long fac_NTL_char
Definition: NTLconvert.cc:41
f
FILE * f
Definition: checklibs.c:9
k
int k
Definition: cfEzgcd.cc:92
canonicalform.h
CFIterator
class to iterate through CanonicalForm's
Definition: cf_iter.h:44
x
Variable x
Definition: cfModGcd.cc:4023
result
return result
Definition: facAbsBiFact.cc:76
cf_reval.h
CFFactory::gettype
static int gettype()
Definition: cf_factory.h:28
lcf
CanonicalForm lcf
Definition: cfModGcd.cc:4038
power
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
Definition: canonicalform.cc:1837
AlgExtRandomF
generate random elements in F_p(alpha)
Definition: cf_random.h:70
g
g
Definition: cfModGcd.cc:4031
gcd_test_one
bool gcd_test_one(const CanonicalForm &f, const CanonicalForm &g, bool swap, int &d)
Coprimality Check. f and g are assumed to have the same level. If swap is true, the main variables of...
Definition: cfGcdUtil.cc:21
rootOf
Variable rootOf(const CanonicalForm &, char name='@')
returns a symbolic root of polynomial with name name Use it to define algebraic variables
Definition: variable.cc:162
ftmpl_functions.h
gf_name
char gf_name
Definition: gfops.cc:52
primitiveElement
CanonicalForm primitiveElement(const Variable &alpha, Variable &beta, bool &fail)
determine a primitive element of , is a primitive element of a field which is isomorphic to
Definition: cf_map_ext.cc:310
getCharacteristic
int getCharacteristic()
Definition: cf_char.cc:51
CanonicalForm
factory's main class
Definition: canonicalform.h:83
GaloisFieldDomain
#define GaloisFieldDomain
Definition: cf_defs.h:22
mapUp
static CanonicalForm mapUp(const Variable &alpha, const Variable &beta)
and is a primitive element, returns the image of
Definition: cf_map_ext.cc:67
i
int i
Definition: cfEzgcd.cc:125
swapvar
CanonicalForm swapvar(const CanonicalForm &, const Variable &, const Variable &)
swapvar() - swap variables x1 and x2 in f.
Definition: cf_ops.cc:168
getMipo
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
Definition: variable.cc:207
CFRandom
virtual class for random element generation
Definition: cf_random.h:21
hasFirstAlgVar
bool hasFirstAlgVar(const CanonicalForm &f, Variable &a)
check if poly f contains an algebraic variable a
Definition: cf_ops.cc:665
ASSERT
#define ASSERT(expression, message)
Definition: cf_assert.h:99
cf_util.h
lcg
CanonicalForm lcg
Definition: cfModGcd.cc:4038
cf_iter.h
cf_map_ext.h
setCharacteristic
void setCharacteristic(int c)
Definition: cf_char.cc:23
NTLconvert.h
gfops.h
REvaluation
class to generate random evaluation points
Definition: cf_reval.h:26
ipower
int ipower(int b, int m)
int ipower ( int b, int m )
Definition: cf_util.cc:25
getGFDegree
int getGFDegree()
Definition: cf_char.cc:56
TEST_ONE_MAX
#define TEST_ONE_MAX
tmax
template CanonicalForm tmax(const CanonicalForm &, const CanonicalForm &)
CanonicalForm::inCoeffDomain
bool inCoeffDomain() const
Definition: canonicalform.cc:119
cf_factory.h
AlgExtRandomF::clone
CFRandom * clone() const
Definition: cf_random.cc:153
Variable
factory's class for variables
Definition: factory.h:118
CanonicalForm::degree
int degree() const
Returns -1 for the zero polynomial and 0 if CO is in a base domain.
Definition: canonicalform.cc:381
mapPrimElem
CanonicalForm mapPrimElem(const CanonicalForm &primElem, const Variable &alpha, const Variable &beta)
compute the image of a primitive element of in . We assume .
Definition: cf_map_ext.cc:377
LC
CanonicalForm LC(const CanonicalForm &f)
Definition: canonicalform.h:303
balance_p
CanonicalForm balance_p(const CanonicalForm &f, const CanonicalForm &q, const CanonicalForm &qh)
same as balance_p ( const CanonicalForm & f, const CanonicalForm & q ) but qh= q/2 is provided,...
Definition: cfGcdUtil.cc:227
CFRandomFactory::generate
static CFRandom * generate()
Definition: cf_random.cc:158
gcd
int gcd(int a, int b)
Definition: walkSupport.cc:836
v
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:37
REvaluation::nextpoint
void nextpoint()
Definition: cf_reval.cc:46
p
int p
Definition: cfModGcd.cc:4019
List< CanonicalForm >
swap
#define swap(_i, _j)
CanonicalForm::mapinto
CanonicalForm mapinto() const
Definition: canonicalform.cc:206
count
int status int void size_t count
Definition: si_signals.h:59
CanonicalForm::isZero
CF_NO_INLINE bool isZero() const
Definition: cf_inline.cc:372
GFMapUp
CanonicalForm GFMapUp(const CanonicalForm &F, int k)
maps a polynomial over to a polynomial over , d needs to be a multiple of k
Definition: cf_map_ext.cc:207
G
static TreeM * G
Definition: janet.cc:32
prune1
void prune1(const Variable &alpha)
Definition: variable.cc:291
degree
int degree(const CanonicalForm &f)
Definition: canonicalform.h:309
convertNTLzzpX2CF
CanonicalForm convertNTLzzpX2CF(const zz_pX &poly, const Variable &x)
Definition: NTLconvert.cc:248