29 #include <NTL/vec_ZZ.h>
30 #include <NTL/xdouble.h>
31 #include <NTL/mat_lzz_pE.h>
32 #include <NTL/mat_GF2E.h>
33 #include <NTL/lzz_pXFactoring.h>
34 #include <NTL/GF2XFactoring.h>
35 #include <tr1/unordered_map>
41 typedef tr1::unordered_map<string, const char *> argmap_t;
49 bool parseArgs(
int argc,
char *argv[], argmap_t& argmap);
52 long multOrd(
long p,
long m);
63 void ppsolve(vec_zz_pE& x,
const mat_zz_pE& A,
const vec_zz_pE& b,
67 void ppsolve(vec_GF2E& x,
const mat_GF2E& A,
const vec_GF2E& b,
77 void buildLinPolyCoeffs(vec_zz_pE& C,
const vec_zz_pE& L,
long p,
long r);
80 void buildLinPolyCoeffs(vec_GF2E& C,
const vec_GF2E& L,
long p,
long r);
86 void applyLinPoly(zz_pE& beta,
const vec_zz_pE& C,
const zz_pE& alpha,
long p);
89 void applyLinPoly(GF2E& beta,
const vec_GF2E& C,
const GF2E& alpha,
long p);
92 inline double log2(
const xdouble& x){
return log(x) * 1.442695040889; }
93 inline double log2(
const double x){
return log(x) * 1.442695040889; }
97 void factorize(vector<long> &factors,
long N);
98 void factorize(vector<ZZ> &factors,
const ZZ& N);
101 void phiN(
long &phiN, vector<long> &facts,
long N);
102 void phiN(ZZ &phiN, vector<ZZ> &facts,
const ZZ &N);
108 void FindPrimitiveRoot(zz_p &r,
unsigned e);
109 void FindPrimitiveRoot(ZZ_p &r,
unsigned e);
115 ZZX Cyclotomic(
int N);
118 int primroot(
int N,
int phiN);
121 int ord(
int N,
int p);
125 ZZX RandPoly(
int n,
const ZZ& p);
134 void PolyRed(ZZX& out,
const ZZX& in,
int q,
bool abs=
false);
135 void PolyRed(ZZX& out,
const ZZX& in,
const ZZ& q,
bool abs=
false);
136 inline void PolyRed(ZZX& F,
int q,
bool abs=
false) { PolyRed(F,F,q,abs); }
137 inline void PolyRed(ZZX& F,
const ZZ& q,
bool abs=
false)
138 { PolyRed(F,F,q,abs); }
142 void MulMod(ZZX& out,
const ZZX& f,
long a,
long q,
bool abs=
true);
143 inline ZZX MulMod(
const ZZX& f,
long a,
long q,
bool abs=
true) {
145 MulMod(res, f, a, q, abs);
151 inline void convert(
long& x1,
const GF2X& x2)
153 x1 = rep(ConstTerm(x2));
155 inline void convert(
long& x1,
const zz_pX& x2)
157 x1 = rep(ConstTerm(x2));
159 void convert(vec_zz_pE& X,
const vector<ZZX>& A);
160 void convert(mat_zz_pE& X,
const vector< vector<ZZX> >& A);
161 void convert(vector<ZZX>& X,
const vec_zz_pE& A);
162 void convert(vector< vector<ZZX> >& X,
const mat_zz_pE& A);
166 template<
class T1,
class T2>
167 void convert(T1& x1,
const T2& x2)
173 template<
class T1,
class T2>
174 void convert(vector<T1>& v1,
const vector<T2>& v2)
178 for (
long i = 0; i < n; i++)
179 convert(v1[i], v2[i]);
183 void mul(vector<ZZX>& x,
const vector<ZZX>& a,
long b);
184 void div(vector<ZZX>& x,
const vector<ZZX>& a,
long b);
185 void add(vector<ZZX>& x,
const vector<ZZX>& a,
const vector<ZZX>& b);
190 int is_in(
int x,
int* X,
int sz);
206 template <
class zzvec>
207 bool intVecCRT(vec_ZZ& vp,
const ZZ& p,
const zzvec& vq,
long q);
219 template <
class T,
bool maxFlag>
222 if (v.size()<1)
return -1;
225 for (
unsigned i=1; i<v.size(); i++)
226 if (maxFlag) {
if (v[i] > target) { target = v[i]; idx = i;} }
227 else {
if (v[i] < target) { target = v[i]; idx = i;} }
231 template <
class T>
long argmax(vector<T>& v)
232 {
return argminmax<T,true>(v); }
234 template <
class T>
long argmin(vector<T>& v)
235 {
return argminmax<T,false>(v); }
246 void sampleSmall(ZZX &poly,
long n=0);
252 void sampleHWt(ZZX &poly,
long Hwt,
long n=0);
255 void sampleGaussian(ZZX &poly,
long n=0,
double stdev=1.0);
284 RandomBits(state, 512);
306 void seekPastChar(istream& str,
int cc);
312 template <
typename T>
313 inline long lsize(
const vector<T>& v) {
314 return (
long) v.size();
319 template <
typename T1,
typename T2>
321 return dynamic_cast<const void*
>(p1) == dynamic_cast<const void*>(p2);
325 void ModComp(ZZX& res,
const ZZX& g,
const ZZX& h,
const ZZX& f);
329 ZZ sumOfCoeffs(
const ZZX& f);
330 ZZ largestCoeff(
const ZZX& f);
331 xdouble coeffsL2Norm(
const ZZX& f);