My Project
Data Structures | Functions
fac_util.h File Reference

operations mod p^k and some other useful functions for factorization More...

#include "canonicalform.h"
#include "cf_eval.h"

Go to the source code of this file.

Data Structures

class  modpk
 class to do operations mod p^k for int's p and k More...
 

Functions

CanonicalForm replaceLc (const CanonicalForm &f, const CanonicalForm &c)
 
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...
 
void extgcd (const CanonicalForm &a, const CanonicalForm &b, CanonicalForm &S, CanonicalForm &T, const modpk &pk)
 
CanonicalForm remainder (const CanonicalForm &f, const CanonicalForm &g, const modpk &pk)
 
CanonicalForm prod (const CFArray &a, int f, int l)
 
CanonicalForm prod (const CFArray &a)
 

Detailed Description

operations mod p^k and some other useful functions for factorization

Definition in file fac_util.h.

Function Documentation

◆ extgcd()

void extgcd ( const CanonicalForm a,
const CanonicalForm b,
CanonicalForm S,
CanonicalForm T,
const modpk pk 
)

Definition at line 183 of file fac_util.cc.

184 {
185  int p = pk.getp(), k = pk.getk(), j;
186  CanonicalForm amodp, bmodp, smodp, tmodp, s, t, sigma, tau, e;
187  CanonicalForm modulus = p, sigmat, taut, q;
188 
189  setCharacteristic( p );
190  {
191  amodp = mapinto( a ); bmodp = mapinto( b );
192  (void)extgcd( amodp, bmodp, smodp, tmodp );
193  }
194  setCharacteristic( 0 );
195  s = mapinto( smodp ); t = mapinto( tmodp );
196 
197  for ( j = 1; j < k; j++ ) {
198  e = ( 1 - s * a - t * b ) / modulus;
199  setCharacteristic( p );
200  {
201  e = mapinto( e );
202  sigmat = smodp * e;
203  taut = tmodp * e;
204  divrem( sigmat, bmodp, q, sigma );
205  tau = taut + q * amodp;
206  }
207  setCharacteristic( 0 );
208  s += mapinto( sigma ) * modulus;
209  t += mapinto( tau ) * modulus;
210  modulus *= p;
211  }
212  S = s; T = t;
213 }
void divrem(const CanonicalForm &f, const CanonicalForm &g, CanonicalForm &q, CanonicalForm &r)
CanonicalForm mapinto(const CanonicalForm &f)
void FACTORY_PUBLIC setCharacteristic(int c)
Definition: cf_char.cc:28
int k
Definition: cfEzgcd.cc:99
int p
Definition: cfModGcd.cc:4080
CanonicalForm b
Definition: cfModGcd.cc:4105
void tau(int **points, int sizePoints, int k)
factory's main class
Definition: canonicalform.h:86
int getk() const
Definition: fac_util.h:36
int getp() const
Definition: fac_util.h:35
const CanonicalForm int s
Definition: facAbsFact.cc:51
int j
Definition: facHensel.cc:110
void extgcd(const CanonicalForm &a, const CanonicalForm &b, CanonicalForm &S, CanonicalForm &T, const modpk &pk)
Definition: fac_util.cc:183
STATIC_VAR jList * T
Definition: janet.cc:30

◆ 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
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
#define TEST_ONE_MAX
CanonicalForm lcg
Definition: cfModGcd.cc:4099
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
FILE * f
Definition: checklibs.c:9
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
factory's class for variables
Definition: factory.h:134
return result
Definition: facAbsBiFact.cc:75
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

◆ prod() [1/2]

CanonicalForm prod ( const CFArray a)

Definition at line 177 of file fac_util.cc.

178 {
179  return prod( a, a.min(), a.max() );
180 }
int max() const
Definition: ftmpl_array.cc:104
int min() const
Definition: ftmpl_array.cc:98
CanonicalForm prod(const CFArray &a, int f, int l)
Definition: fac_util.cc:166

◆ prod() [2/2]

CanonicalForm prod ( const CFArray a,
int  f,
int  l 
)

Definition at line 166 of file fac_util.cc.

167 {
168  if ( f < a.min() ) f = a.min();
169  if ( l > a.max() ) l = a.max();
170  CanonicalForm p = 1;
171  for ( int i = f; i <= l; i++ )
172  p *= a[i];
173  return p;
174 }
int l
Definition: cfEzgcd.cc:100
int i
Definition: cfEzgcd.cc:132

◆ remainder()

CanonicalForm remainder ( const CanonicalForm f,
const CanonicalForm g,
const modpk pk 
)

Definition at line 115 of file fac_util.cc.

116 {
117  ASSERT( (f.inCoeffDomain() || f.isUnivariate()) && (g.inCoeffDomain() || g.isUnivariate()) && (f.inCoeffDomain() || g.inCoeffDomain() || f.mvar() == g.mvar()), "can not build remainder" );
118  if ( f.inCoeffDomain() )
119  if ( g.inCoeffDomain() )
120  return pk( f % g );
121  else
122  return pk( f );
123  else {
124  Variable x = f.mvar();
126  int degg = g.degree();
127  CanonicalForm invlcg = pk.inverse( g.lc() );
128  CanonicalForm gg = pk( g*invlcg );
129  if((gg.lc().isOne()))
130  {
131  while ( result.degree() >= degg )
132  {
133  result -= pk(lc( result ) * gg) * power( x, result.degree() - degg );
134  result=pk(result);
135  }
136  }
137  else
138  // no inverse found
139  {
141  if (!ic.isOne())
142  {
143  gg=g/ic;
144  return remainder(f,gg,pk);
145  }
146  while ( result.degree() >= degg )
147  {
148  if (gg.lc().isZero()) return result;
149  CanonicalForm lcgf = result.lc() / gg.lc();
150  if (lcgf.inZ())
151  gg = pk( g*lcgf );
152  else
153  {
154  //printf("!\n\n");
155  return result;
156  }
157  result -= gg * power( x, result.degree() - degg );
158  result=pk(result);
159  }
160  }
161  return result;
162  }
163 }
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
CanonicalForm icontent(const CanonicalForm &f)
CanonicalForm icontent ( const CanonicalForm & f )
Definition: cf_gcd.cc:74
CanonicalForm lc(const CanonicalForm &f)
Variable x
Definition: cfModGcd.cc:4084
CF_NO_INLINE bool isOne() const
bool inZ() const
predicates
CanonicalForm lc() const
CanonicalForm CanonicalForm::lc (), Lc (), LC (), LC ( v ) const.
CanonicalForm inverse(const CanonicalForm &f, bool symmetric=true) const
Definition: fac_util.cc:59
int degg
Definition: facAlgExt.cc:64
CanonicalForm remainder(const CanonicalForm &f, const CanonicalForm &g, const modpk &pk)
Definition: fac_util.cc:115

◆ replaceLc()

CanonicalForm replaceLc ( const CanonicalForm f,
const CanonicalForm c 
)

Definition at line 90 of file fac_util.cc.

91 {
92  if ( f.inCoeffDomain() )
93  return c;
94  else
95  return f + ( c - LC( f ) ) * power( f.mvar(), degree( f ) );
96 }