My Project
Functions
cfGcdUtil.h File Reference

coprimality check and change of representation mod n More...

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 290 of file cfGcdUtil.cc.

291 {
292  CanonicalForm qh = q / 2;
293  return balance_p (f, q, qh);
294 }
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:258
FILE * f
Definition: checklibs.c:9
factory's main class
Definition: canonicalform.h:86

◆ 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 258 of file cfGcdUtil.cc.

259 {
260  Variable x = f.mvar();
261  CanonicalForm result = 0;
262  CanonicalForm c;
263  CFIterator i;
264  for ( i = f; i.hasTerms(); i++ )
265  {
266  c = i.coeff();
267  if ( c.inCoeffDomain())
268  {
269  if ( c > qh )
270  result += power( x, i.exp() ) * (c - q);
271  else
272  result += power( x, i.exp() ) * c;
273  }
274  else
275  result += power( x, i.exp() ) * balance_p(c,q,qh);
276  }
277  return result;
278 }
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
int i
Definition: cfEzgcd.cc:132
Variable x
Definition: cfModGcd.cc:4084
class to iterate through CanonicalForm's
Definition: cf_iter.h:44
bool inCoeffDomain() const
factory's class for variables
Definition: factory.h:134
return result
Definition: facAbsBiFact.cc:75

◆ 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 25 of file cfGcdUtil.cc.

26 {
27  d= 0;
28  int count = 0;
29  // assume polys have same level;
30 
31  Variable v= Variable (1);
32  bool algExtension= (hasFirstAlgVar (f, v) || hasFirstAlgVar (g, v));
34  if ( swap )
35  {
36  lcf = swapvar( LC( f ), Variable(1), f.mvar() );
37  lcg = swapvar( LC( g ), Variable(1), f.mvar() );
38  }
39  else
40  {
41  lcf = LC( f, Variable(1) );
42  lcg = LC( g, Variable(1) );
43  }
44 
45  CanonicalForm F, G;
46  if ( swap )
47  {
48  F=swapvar( f, Variable(1), f.mvar() );
49  G=swapvar( g, Variable(1), g.mvar() );
50  }
51  else
52  {
53  F = f;
54  G = g;
55  }
56 
57  #define TEST_ONE_MAX 50
58  int p= getCharacteristic();
59  bool passToGF= false;
60  int k= 1;
61  bool extOfExt= false;
62  Variable v3;
63  if (p > 0 && p < TEST_ONE_MAX && CFFactory::gettype() != GaloisFieldDomain && !algExtension)
64  {
65  if (p == 2)
66  setCharacteristic (2, 6, 'Z');
67  else if (p == 3)
68  setCharacteristic (3, 4, 'Z');
69  else if (p == 5 || p == 7)
70  setCharacteristic (p, 3, 'Z');
71  else
72  setCharacteristic (p, 2, 'Z');
73  passToGF= true;
74  }
75  else if (p > 0 && CFFactory::gettype() == GaloisFieldDomain && ipower (p , getGFDegree()) < TEST_ONE_MAX)
76  {
77  k= getGFDegree();
78  if (ipower (p, 2*k) > TEST_ONE_MAX)
80  else
82  F= GFMapUp (F, k);
83  G= GFMapUp (G, k);
84  lcf= GFMapUp (lcf, k);
85  lcg= GFMapUp (lcg, k);
86  }
87  else if (p > 0 && p < TEST_ONE_MAX && algExtension)
88  {
89 #if defined(HAVE_NTL) || defined(HAVE_FLINT)
90  int d= degree (getMipo (v));
91  CFList source, dest;
92  Variable v2;
93  CanonicalForm primElem, imPrimElem;
94  #if defined(HAVE_NTL) && !defined(HAVE_FLINT)
95  if (fac_NTL_char != p)
96  {
97  fac_NTL_char= p;
98  zz_p::init (p);
99  }
100  #endif
101  if (p == 2 && d < 6)
102  {
103  bool primFail= false;
104  Variable vBuf;
105  primElem= primitiveElement (v, vBuf, primFail);
106  ASSERT (!primFail, "failure in integer factorizer");
107  if (d < 3)
108  {
109  #ifdef HAVE_FLINT
110  nmod_poly_t Irredpoly;
111  nmod_poly_init(Irredpoly,p);
112  nmod_poly_randtest_monic_irreducible(Irredpoly, FLINTrandom, 3*d+1);
113  CanonicalForm newMipo=convertnmod_poly_t2FacCF(Irredpoly,Variable(1));
114  nmod_poly_clear(Irredpoly);
115  #elif defined(HAVE_NTL)
116  zz_pX NTLIrredpoly;
117  BuildIrred (NTLIrredpoly, d*3);
118  CanonicalForm newMipo= convertNTLzzpX2CF (NTLIrredpoly, Variable (1));
119  #else
120  factoryError("NTL/FLINT missing:gcd_test_one");
121  #endif
122  v2= rootOf (newMipo);
123  }
124  else
125  {
126  #ifdef HAVE_FLINT
127  nmod_poly_t Irredpoly;
128  nmod_poly_init(Irredpoly,p);
129  nmod_poly_randtest_monic_irreducible(Irredpoly, FLINTrandom, 3*d+1);
130  CanonicalForm newMipo=convertnmod_poly_t2FacCF(Irredpoly,Variable(1));
131  nmod_poly_clear(Irredpoly);
132  #elif defined(HAVE_NTL)
133  zz_pX NTLIrredpoly;
134  BuildIrred (NTLIrredpoly, d*2);
135  CanonicalForm newMipo= convertNTLzzpX2CF (NTLIrredpoly, Variable (1));
136  #else
137  factoryError("NTL/FLINT missing:gcd_test_one");
138  #endif
139  v2= rootOf (newMipo);
140  }
141  imPrimElem= mapPrimElem (primElem, v, v2);
142  extOfExt= true;
143  }
144  else if ((p == 3 && d < 4) || ((p == 5 || p == 7) && d < 3))
145  {
146  bool primFail= false;
147  Variable vBuf;
148  primElem= primitiveElement (v, vBuf, primFail);
149  ASSERT (!primFail, "failure in integer factorizer");
150  #ifdef HAVE_FLINT
151  nmod_poly_t Irredpoly;
152  nmod_poly_init(Irredpoly,p);
153  nmod_poly_randtest_monic_irreducible(Irredpoly, FLINTrandom, 2*d+1);
154  CanonicalForm newMipo=convertnmod_poly_t2FacCF(Irredpoly,Variable(1));
155  nmod_poly_clear(Irredpoly);
156  #elif defined(HAVE_NTL)
157  zz_pX NTLIrredpoly;
158  BuildIrred (NTLIrredpoly, d*2);
159  CanonicalForm newMipo= convertNTLzzpX2CF (NTLIrredpoly, Variable (1));
160  #else
161  factoryError("NTL/FLINT missing:gcd_test_one");
162  #endif
163  v2= rootOf (newMipo);
164  imPrimElem= mapPrimElem (primElem, v, v2);
165  extOfExt= true;
166  }
167  if (extOfExt)
168  {
169  v3= v;
170  F= mapUp (F, v, v2, primElem, imPrimElem, source, dest);
171  G= mapUp (G, v, v2, primElem, imPrimElem, source, dest);
172  lcf= mapUp (lcf, v, v2, primElem, imPrimElem, source, dest);
173  lcg= mapUp (lcg, v, v2, primElem, imPrimElem, source, dest);
174  v= v2;
175  }
176 #endif
177  }
178 
179  CFRandom * sample;
180  if ((!algExtension && p > 0) || p == 0)
181  sample = CFRandomFactory::generate();
182  else
183  sample = AlgExtRandomF (v).clone();
184 
185  REvaluation e( 2, tmax( f.level(), g.level() ), *sample );
186  delete sample;
187 
188  if (passToGF)
189  {
190  lcf= lcf.mapinto();
191  lcg= lcg.mapinto();
192  }
193 
194  CanonicalForm eval1, eval2;
195  if (passToGF)
196  {
197  eval1= e (lcf);
198  eval2= e (lcg);
199  }
200  else
201  {
202  eval1= e (lcf);
203  eval2= e (lcg);
204  }
205 
206  while ( ( eval1.isZero() || eval2.isZero() ) && count < TEST_ONE_MAX )
207  {
208  e.nextpoint();
209  count++;
210  eval1= e (lcf);
211  eval2= e (lcg);
212  }
213  if ( count >= TEST_ONE_MAX )
214  {
215  if (passToGF)
217  if (k > 1)
219  if (extOfExt)
220  prune1 (v3);
221  return false;
222  }
223 
224 
225  if (passToGF)
226  {
227  F= F.mapinto();
228  G= G.mapinto();
229  eval1= e (F);
230  eval2= e (G);
231  }
232  else
233  {
234  eval1= e (F);
235  eval2= e (G);
236  }
237 
238  CanonicalForm c= gcd (eval1, eval2);
239  d= c.degree();
240  bool result= d < 1;
241  if (d < 0)
242  d= 0;
243 
244  if (passToGF)
246  if (k > 1)
248  if (extOfExt)
249  prune1 (v3);
250  return result;
251 }
CanonicalForm convertnmod_poly_t2FacCF(const nmod_poly_t poly, const Variable &x)
conversion of a FLINT poly over Z/p to CanonicalForm
CanonicalForm convertNTLzzpX2CF(const zz_pX &poly, const Variable &x)
Definition: NTLconvert.cc:255
VAR long fac_NTL_char
Definition: NTLconvert.cc:46
#define swap(_i, _j)
int degree(const CanonicalForm &f)
int getGFDegree()
Definition: cf_char.cc:75
void FACTORY_PUBLIC setCharacteristic(int c)
Definition: cf_char.cc:28
bool hasFirstAlgVar(const CanonicalForm &f, Variable &a)
check if poly f contains an algebraic variable a
Definition: cf_ops.cc:679
CanonicalForm swapvar(const CanonicalForm &, const Variable &, const Variable &)
swapvar() - swap variables x1 and x2 in f.
Definition: cf_ops.cc:168
CanonicalForm LC(const CanonicalForm &f)
int FACTORY_PUBLIC getCharacteristic()
Definition: cf_char.cc:70
int k
Definition: cfEzgcd.cc:99
#define TEST_ONE_MAX
CanonicalForm lcg
Definition: cfModGcd.cc:4099
int p
Definition: cfModGcd.cc:4080
CanonicalForm lcf
Definition: cfModGcd.cc:4099
g
Definition: cfModGcd.cc:4092
#define ASSERT(expression, message)
Definition: cf_assert.h:99
#define GaloisFieldDomain
Definition: cf_defs.h:24
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:450
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:342
static CanonicalForm mapUp(const Variable &alpha, const Variable &beta)
and is a primitive element, returns the image of
Definition: cf_map_ext.cc:70
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:240
GLOBAL_VAR flint_rand_t FLINTrandom
Definition: cf_random.cc:25
VAR void(* factoryError)(const char *s)
Definition: cf_util.cc:80
int ipower(int b, int m)
int ipower ( int b, int m )
Definition: cf_util.cc:27
generate random elements in F_p(alpha)
Definition: cf_random.h:70
CFRandom * clone() const
Definition: cf_random.cc:165
static int gettype()
Definition: cf_factory.h:28
static CFRandom * generate()
Definition: cf_random.cc:170
virtual class for random element generation
Definition: cf_random.h:21
CF_NO_INLINE bool isZero() const
int degree() const
Returns -1 for the zero polynomial and 0 if CO is in a base domain.
CanonicalForm mapinto() const
class to generate random evaluation points
Definition: cf_reval.h:26
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:39
nmod_poly_init(FLINTmipo, getCharacteristic())
nmod_poly_clear(FLINTmipo)
Variable FACTORY_PUBLIC rootOf(const CanonicalForm &, char name='@')
returns a symbolic root of polynomial with name name Use it to define algebraic variables
Definition: variable.cc:162
void prune1(const Variable &alpha)
Definition: variable.cc:291
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
Definition: variable.cc:207
template CanonicalForm tmax(const CanonicalForm &, const CanonicalForm &)
VAR char gf_name
Definition: gfops.cc:52
STATIC_VAR TreeM * G
Definition: janet.cc:31
void init()
Definition: lintree.cc:864
int status int void size_t count
Definition: si_signals.h:59
int gcd(int a, int b)
Definition: walkSupport.cc:836