My Project  debian-1:4.1.1-p2+ds-4build2
Functions
cfGcdUtil.h File Reference

Go to the source code of this file.

Functions

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 f and g are swapped with Variable(1). If the result is false, d is set to the degree of the gcd of f and g evaluated at a random point in K^n-1. This gcd is a gcd of univariate polynomials. More...
 
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, too. More...
 
CanonicalForm balance_p (const CanonicalForm &f, const CanonicalForm &q)
 static CanonicalForm balance_p ( const CanonicalForm & f, const CanonicalForm & q ) More...
 

Detailed Description

coprimality check and change of representation mod n

Definition in file cfGcdUtil.h.

Function Documentation

◆ balance_p() [1/2]

CanonicalForm balance_p ( const CanonicalForm f,
const CanonicalForm q 
)

static CanonicalForm balance_p ( const CanonicalForm & f, const CanonicalForm & q )

balance_p() - map f from positive to symmetric representation mod q.

This makes sense for polynomials over Z only. q should be an integer.

Definition at line 259 of file cfGcdUtil.cc.

260 {
261  CanonicalForm qh = q / 2;
262  return balance_p (f, q, qh);
263 }

◆ balance_p() [2/2]

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, too.

Definition at line 227 of file cfGcdUtil.cc.

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 }

◆ 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 f and g are swapped with Variable(1). If the result is false, d is set to the degree of the gcd of f and g evaluated at a random point in K^n-1. This gcd is a gcd of univariate polynomials.

Definition at line 21 of file cfGcdUtil.cc.

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 }
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
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
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
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
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:77
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
lcg
CanonicalForm lcg
Definition: cfModGcd.cc:4038
setCharacteristic
void setCharacteristic(int c)
Definition: cf_char.cc:23
REvaluation
class to generate random evaluation points
Definition: cf_reval.h:25
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
AlgExtRandomF::clone
CFRandom * clone() const
Definition: cf_random.cc:153
Variable
factory's class for variables
Definition: factory.h:117
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
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:289
degree
int degree(const CanonicalForm &f)
Definition: canonicalform.h:309
convertNTLzzpX2CF
CanonicalForm convertNTLzzpX2CF(const zz_pX &poly, const Variable &x)
Definition: NTLconvert.cc:248