HElib  1.0
Implementing Homomorphic Encryption
 All Classes Files Functions Variables Friends Pages
NumbTh.h
Go to the documentation of this file.
1 /* Copyright (C) 2012,2013 IBM Corp.
2  * This program is free software; you can redistribute it and/or modify
3  * it under the terms of the GNU General Public License as published by
4  * the Free Software Foundation; either version 2 of the License, or
5  * (at your option) any later version.
6  *
7  * This program is distributed in the hope that it will be useful,
8  * but WITHOUT ANY WARRANTY; without even the implied warranty of
9  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
10  * See the GNU General Public License for more details.
11  *
12  * You should have received a copy of the GNU General Public License along
13  * with this program; if not, write to the Free Software Foundation, Inc.,
14  * 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
15  */
16 #ifndef _NumbTh
17 #define _NumbTh
18 
22 #include <vector>
23 #include <cmath>
24 #include <istream>
25 #include <NTL/ZZ.h>
26 #include <NTL/ZZ_p.h>
27 #include <NTL/ZZX.h>
28 #include <NTL/GF2X.h>
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>
36 #include <string>
37 NTL_CLIENT
38 
39 
41 typedef tr1::unordered_map<string, const char *> argmap_t;
42 
43 
45 
49 bool parseArgs(int argc, char *argv[], argmap_t& argmap);
50 
52 long multOrd(long p, long m);
53 
54 
63 void ppsolve(vec_zz_pE& x, const mat_zz_pE& A, const vec_zz_pE& b,
64  long p, long r);
65 
67 void ppsolve(vec_GF2E& x, const mat_GF2E& A, const vec_GF2E& b,
68  long p, long r);
69 
77 void buildLinPolyCoeffs(vec_zz_pE& C, const vec_zz_pE& L, long p, long r);
78 
80 void buildLinPolyCoeffs(vec_GF2E& C, const vec_GF2E& L, long p, long r);
81 
86 void applyLinPoly(zz_pE& beta, const vec_zz_pE& C, const zz_pE& alpha, long p);
87 
89 void applyLinPoly(GF2E& beta, const vec_GF2E& C, const GF2E& alpha, long p);
90 
92 inline double log2(const xdouble& x){ return log(x) * 1.442695040889; }
93 inline double log2(const double x){ return log(x) * 1.442695040889; }
94 
97 void factorize(vector<long> &factors, long N);
98 void factorize(vector<ZZ> &factors, const ZZ& N);
99 
101 void phiN(long &phiN, vector<long> &facts, long N);
102 void phiN(ZZ &phiN, vector<ZZ> &facts, const ZZ &N);
103 
105 int phi_N(int N);
106 
108 void FindPrimitiveRoot(zz_p &r, unsigned e);
109 void FindPrimitiveRoot(ZZ_p &r, unsigned e);
110 
112 int mobius(int n);
113 
115 ZZX Cyclotomic(int N);
116 
118 int primroot(int N,int phiN);
119 
121 int ord(int N,int p);
122 
123 
124 // Rand mod p poly of degree < n
125 ZZX RandPoly(int n,const ZZ& p);
126 
128 
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); }
140 
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) {
144  ZZX res;
145  MulMod(res, f, a, q, abs);
146  return res;
147 }
148 
151 inline void convert(long& x1, const GF2X& x2)
152 {
153  x1 = rep(ConstTerm(x2));
154 }
155 inline void convert(long& x1, const zz_pX& x2)
156 {
157  x1 = rep(ConstTerm(x2));
158 }
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);
164 
166 template<class T1, class T2>
167 void convert(T1& x1, const T2& x2)
168 {
169  conv(x1, x2);
170 }
171 
173 template<class T1, class T2>
174 void convert(vector<T1>& v1, const vector<T2>& v2)
175 {
176  long n = v2.size();
177  v1.resize(n);
178  for (long i = 0; i < n; i++)
179  convert(v1[i], v2[i]);
180 }
181 
182 // some useful operations
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);
186 
187 
190 int is_in(int x,int* X,int sz);
191 
206 template <class zzvec> // zzvec can be vec_ZZ or vec_long
207 bool intVecCRT(vec_ZZ& vp, const ZZ& p, const zzvec& vq, long q);
208 
219 template <class T, bool maxFlag>
220 long argminmax(vector<T>& v)
221 {
222  if (v.size()<1) return -1; // error: this is an empty array
223  unsigned idx = 0;
224  T target = v[0];
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;} }
228  return (long) idx;
229 }
230 
231 template <class T> long argmax(vector<T>& v)
232 { return argminmax<T,true>(v); }
233 
234 template <class T> long argmin(vector<T>& v)
235 { return argminmax<T,false>(v); }
236 
237 
238 // Sample polynomials with entries {-1,0,1}. These functions are similar to
239 // the SampleSmall class from v1, but without a class around it.
240 
241 // In sampleSmall,
242 // sampleHWt, min(Hwt,n) random coefficients are chosen at random in {-1,+1}
243 // and the others are set to zero. If n=0 then n=poly.deg()+1 is used.
244 
246 void sampleSmall(ZZX &poly, long n=0);
247 
252  void sampleHWt(ZZX &poly, long Hwt, long n=0);
253 
255 void sampleGaussian(ZZX &poly, long n=0, double stdev=1.0);
256 
257 
277 class RandomState {
278 private:
279  ZZ state;
280  bool restored;
281 
282 public:
283  RandomState() {
284  RandomBits(state, 512);
285  restored = false;
286  }
287 
289  void restore() {
290  if (!restored) {
291  SetSeed(state);
292  restored = true;
293  }
294  }
295 
296  ~RandomState() {
297  restore();
298  }
299 
300 private:
301  RandomState(const RandomState&); // disable copy constructor
302  RandomState& operator=(const RandomState&); // disable assignment
303 };
304 
306 void seekPastChar(istream& str, int cc);
307 
308 
309 // An experimental facility...it is annoying that vector::size() is an
310 // unsigned quantity...this leads to all kinds of annoying warning messages...
312 template <typename T>
313 inline long lsize(const vector<T>& v) {
314  return (long) v.size();
315 }
316 
318 // Believe it or not, this is really the way to do it...
319 template <typename T1, typename T2>
320 bool sameObject(const T1* p1, const T2* p2) {
321  return dynamic_cast<const void*>(p1) == dynamic_cast<const void*>(p2);
322 }
323 
325 void ModComp(ZZX& res, const ZZX& g, const ZZX& h, const ZZX& f);
326 
329 ZZ sumOfCoeffs(const ZZX& f); // = f(1)
330 ZZ largestCoeff(const ZZX& f); // l_infty norm
331 xdouble coeffsL2Norm(const ZZX& f); // l_2 norm
333 #endif