My Project
Loading...
Searching...
No Matches
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
190 {
191 amodp = mapinto( a ); bmodp = mapinto( b );
192 (void)extgcd( amodp, bmodp, smodp, tmodp );
193 }
195 s = mapinto( smodp ); t = mapinto( tmodp );
196
197 for ( j = 1; j < k; j++ ) {
198 e = ( 1 - s * a - t * b ) / modulus;
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 }
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:4078
CanonicalForm b
Definition: cfModGcd.cc:4103
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
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 }
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 {
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 FACTORY_PUBLIC 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:4097
CanonicalForm lcf
Definition: cfModGcd.cc:4097
g
Definition: cfModGcd.cc:4090
#define ASSERT(expression, message)
Definition: cf_assert.h:99
#define GaloisFieldDomain
Definition: cf_defs.h:18
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: variable.h:33
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)
template CanonicalForm tmax(const CanonicalForm &, const CanonicalForm &)
VAR char gf_name
Definition: gfops.cc:52
STATIC_VAR TreeM * G
Definition: janet.cc:31
int status int void size_t count
Definition: si_signals.h:59
void prune1(const Variable &alpha)
Definition: variable.cc:291
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
Definition: variable.cc:207
Variable rootOf(const CanonicalForm &mipo, char name)
returns a symbolic root of polynomial with name name Use it to define algebraic variables
Definition: variable.cc:162
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
fq_nmod_poly_t prod
Definition: facHensel.cc:100

◆ 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 lc(const CanonicalForm &f)
CanonicalForm FACTORY_PUBLIC icontent(const CanonicalForm &f)
CanonicalForm icontent ( const CanonicalForm & f )
Definition: cf_gcd.cc:74
Variable x
Definition: cfModGcd.cc:4082
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}