PAlgebra.h
1 /* Copyright (C) 2012-2020 IBM Corp.
2  * This program is Licensed under the Apache License, Version 2.0
3  * (the "License"); you may not use this file except in compliance
4  * with the License. You may obtain a copy of the License at
5  * http://www.apache.org/licenses/LICENSE-2.0
6  * Unless required by applicable law or agreed to in writing, software
7  * distributed under the License is distributed on an "AS IS" BASIS,
8  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
9  * See the License for the specific language governing permissions and
10  * limitations under the License. See accompanying LICENSE file.
11  */
12 #ifndef HELIB_PALGEBRA_H
13 #define HELIB_PALGEBRA_H
14 
18 #include <exception>
19 #include <utility>
20 #include <vector>
21 #include <complex>
22 
23 #include <helib/NumbTh.h>
24 #include <helib/zzX.h>
25 #include <helib/hypercube.h>
26 #include <helib/PGFFT.h>
27 #include <helib/clonedPtr.h>
28 #include <helib/apiAttributes.h>
29 
30 namespace helib {
31 
32 struct half_FFT
33 {
35  std::vector<std::complex<double>> pow;
36 
37  half_FFT(long m);
38 };
39 
41 {
43  std::vector<std::complex<double>> pow1, pow2;
44 
45  quarter_FFT(long m);
46 };
47 
76 class PAlgebra
77 {
78  long m; // the integer m defines (Z/mZ)^*, Phi_m(X), etc.
79  long p; // the prime base of the plaintext space
80 
81  long phiM; // phi(m)
82  long ordP; // the order of p in (Z/mZ)^*
83  long nfactors; // number of distinct prime factors of m
84  long radm; // rad(m) = prod of distinct primes dividing m
85  double normBnd; // max-norm-on-pwfl-basis <= normBnd * max-norm-canon-embed
86  double polyNormBnd; // max-norm-on-poly-basis <= polyNormBnd *
87  // max-norm-canon-embed
88 
89  long pow2; // if m = 2^k, then pow2 == k; otherwise, pow2 == 0
90 
91  std::vector<long> gens; // Our generators for (Z/mZ)^* (other than p)
92 
93  // native[i] is true iff gens[i] has the same order in the quotient
94  // group as its order in Zm*.
95  NTL::Vec<bool> native;
96 
97  // frob_perturb[i] = j if gens[i] raised to its order equals p^j,
98  // otherwise -1
99  NTL::Vec<long> frob_perturb;
100 
101  CubeSignature cube; // the hypercube structure of Zm* /(p)
102 
103  NTL::ZZX PhimX; // Holds the integer polynomial Phi_m(X)
104 
105  double cM; // the "ring constant" c_m for Z[X]/Phi_m(X)
106  // NOTE: cM is related to the ratio between the l_infinity norm of
107  // a "random" ring element in different bases. For example, think of
108  // choosing the power-basis coefficients of x uniformly at random in
109  // [+-a/2] (for some parameter a), then the powerful basis norm of x
110  // should be bounded whp by cM*a.
111  //
112  // More precisely, for an element x whose coefficients are chosen
113  // uniformly in [+-a/2] (in either the powerful or the power basis)
114  // we have a high-probability bound |x|_canonical < A*a for some
115  // A = O(sqrt(phi(m)). Also for "random enough" x we have some bound
116  // |x|_powerful < |x|_canonical * B
117  // where we "hope" that B = O(1/sqrt(phi(m)). The cM value is
118  // supposed to be cM=A*B.
119  //
120  // The value cM is only used for bootstrapping, see more comments
121  // for the method RecryptData::setAE in recryption.cpp. Also see
122  // Appendix A of https://ia.cr/2014/873 (updated version from 2019)
123 
124  std::vector<long> T; // The representatives for the quotient group Zm* /(p)
125  std::vector<long> Tidx; // i=Tidx[t] is the index i s.t. T[i]=t.
126  // Tidx[t]==-1 if t notin T
127 
128  std::vector<long> zmsIdx; // if t is the i'th element in Zm* then zmsIdx[t]=i
129  // zmsIdx[t]==-1 if t notin Zm*
130 
131  std::vector<long> zmsRep; // inverse of zmsIdx
132 
133  std::shared_ptr<PGFFT> fftInfo; // info for computing m-point complex FFT's
134  // shard_ptr allows delayed initialization
135  // and lightweight copying
136 
137  std::shared_ptr<half_FFT> half_fftInfo;
138  // an optimization for FFT's with even m
139 
140  std::shared_ptr<quarter_FFT> quarter_fftInfo;
141  // an optimization for FFT's with m = 0 (mod 4)
142 
143 public:
144  PAlgebra(long mm,
145  long pp = 2,
146  const std::vector<long>& _gens = std::vector<long>(),
147  const std::vector<long>& _ords = std::vector<long>()); // constructor
148 
149  bool operator==(const PAlgebra& other) const;
150  bool operator!=(const PAlgebra& other) const { return !(*this == other); }
151  // comparison
152 
153  /* I/O methods */
154 
156  void printout(std::ostream& out = std::cout) const;
157  void printAll(std::ostream& out = std::cout) const; // print even more
158 
159  /* Access methods */
160 
162  long getM() const { return m; }
163 
165  long getP() const { return p; }
166 
168  long getPhiM() const { return phiM; }
169 
171  long getOrdP() const { return ordP; }
172 
174  long getNFactors() const { return nfactors; }
175 
177  long getRadM() const { return radm; }
178 
180  double getNormBnd() const { return normBnd; }
181 
183  double getPolyNormBnd() const { return polyNormBnd; }
184 
186  long getNSlots() const { return cube.getSize(); }
187 
189  long getPow2() const { return pow2; }
190 
192  const NTL::ZZX& getPhimX() const { return PhimX; }
193 
195  void set_cM(double c) { cM = c; }
196  double get_cM() const { return cM; }
197 
199  // const std::vector<long> getMfactors() const { return mFactors; }
200 
202  long numOfGens() const { return gens.size(); }
203 
205  long ZmStarGen(long i) const { return (i < long(gens.size())) ? gens[i] : 0; }
206 
208  // VJS: I'm moving away from all of this unsigned stuff...
209  // Also, note that j really may be negative
210  // NOTE: i == -1 means Frobenius
211  long genToPow(long i, long j) const;
212 
213  // p to the power j mod m
214  long frobeniusPow(long j) const;
215 
217  long OrderOf(long i) const { return cube.getDim(i); }
218 
220  long ProdOrdsFrom(long i) const { return cube.getProd(i); }
221 
223  bool SameOrd(long i) const { return native[i]; }
224 
225  // FrobPerturb[i] = j if gens[i] raised to its order equals p^j,
226  // where j in [0..ordP), otherwise -1
227  long FrobPerturb(long i) const { return frob_perturb[i]; }
228 
230 
232  long ith_rep(long i) const { return (i < getNSlots()) ? T[i] : 0; }
233 
235  long indexOfRep(long t) const { return (t > 0 && t < m) ? Tidx[t] : -1; }
236 
238  bool isRep(long t) const { return (t > 0 && t < m && Tidx[t] > -1); }
239 
241  long indexInZmstar(long t) const { return (t > 0 && t < m) ? zmsIdx[t] : -1; }
242 
244  long indexInZmstar_unchecked(long t) const { return zmsIdx[t]; }
245 
247  long repInZmstar_unchecked(long idx) const { return zmsRep[idx]; }
248 
249  bool inZmStar(long t) const { return (t > 0 && t < m && zmsIdx[t] > -1); }
250 
253  long exponentiate(const std::vector<long>& exps,
254  bool onlySameOrd = false) const;
255 
257  long coordinate(long i, long k) const { return cube.getCoord(k, i); }
258 
261  std::pair<long, long> breakIndexByDim(long idx, long dim) const
262  {
263  return cube.breakIndexByDim(idx, dim);
264  }
266  long assembleIndexByDim(std::pair<long, long> idx, long dim) const
267  {
268  return cube.assembleIndexByDim(idx, dim);
269  }
270 
272  long addCoord(long i, long k, long offset) const
273  {
274  return cube.addCoord(k, i, offset);
275  }
276 
277  /* Miscellaneous */
278 
282  bool nextExpVector(std::vector<long>& exps) const
283  {
284  return cube.incrementCoords(exps);
285  }
286 
288  long fftSizeNeeded() const { return NTL::NextPowerOfTwo(getM()) + 1; }
289  // TODO: should have a special case when m is power of two
290 
291  const PGFFT& getFFTInfo() const { return *fftInfo; }
292  const half_FFT& getHalfFFTInfo() const { return *half_fftInfo; }
293  const quarter_FFT& getQuarterFFTInfo() const { return *quarter_fftInfo; }
294 };
295 
296 enum PA_tag
297 {
300  PA_cx_tag
301 };
302 
330 class DummyBak
332 {
333  // placeholder class used in GF2X impl
334 
335 public:
336  void save() {}
337  void restore() const {}
338 };
339 
340 class DummyContext
341 {
342  // placeholder class used in GF2X impl
343 
344 public:
345  void save() {}
346  void restore() const {}
347  DummyContext() {}
348  DummyContext(long) {}
349 };
350 
351 // some stuff to help with template code
352 template <typename R>
353 struct GenericModulus
354 {};
355 
356 template <>
357 struct GenericModulus<NTL::zz_p>
358 {
359  static void init(long p) { NTL::zz_p::init(p); }
360 };
361 
362 template <>
363 struct GenericModulus<NTL::GF2>
364 {
365  static void init(long p)
366  {
367  assertEq<InvalidArgument>(p, 2l, "Cannot init NTL::GF2 with p not 2");
368  }
369 };
370 
371 class PA_GF2
372 {
373  // typedefs for algebraic structures built up from GF2
374 
375 public:
376  static const PA_tag tag = PA_GF2_tag;
377  typedef NTL::GF2 R;
378  typedef NTL::GF2X RX;
379  typedef NTL::vec_GF2X vec_RX;
380  typedef NTL::GF2XModulus RXModulus;
381  typedef DummyBak RBak;
382  typedef DummyContext RContext;
383  typedef NTL::GF2E RE;
384  typedef NTL::vec_GF2E vec_RE;
385  typedef NTL::mat_GF2E mat_RE;
386  typedef NTL::GF2EX REX;
387  typedef NTL::GF2EBak REBak;
388  typedef NTL::vec_GF2EX vec_REX;
389  typedef NTL::GF2EContext REContext;
390  typedef NTL::mat_GF2 mat_R;
391  typedef NTL::vec_GF2 vec_R;
392 };
393 
394 class PA_zz_p
395 {
396  // typedefs for algebraic structures built up from zz_p
397 
398 public:
399  static const PA_tag tag = PA_zz_p_tag;
400  typedef NTL::zz_p R;
401  typedef NTL::zz_pX RX;
402  typedef NTL::vec_zz_pX vec_RX;
403  typedef NTL::zz_pXModulus RXModulus;
404  typedef NTL::zz_pBak RBak;
405  typedef NTL::zz_pContext RContext;
406  typedef NTL::zz_pE RE;
407  typedef NTL::vec_zz_pE vec_RE;
408  typedef NTL::mat_zz_pE mat_RE;
409  typedef NTL::zz_pEX REX;
410  typedef NTL::zz_pEBak REBak;
411  typedef NTL::vec_zz_pEX vec_REX;
412  typedef NTL::zz_pEContext REContext;
413  typedef NTL::mat_zz_p mat_R;
414  typedef NTL::vec_zz_p vec_R;
415 };
417 
420 {
421 
422 public:
423  virtual ~PAlgebraModBase() {}
424  virtual PAlgebraModBase* clone() const = 0;
425 
427  virtual PA_tag getTag() const = 0;
428 
430  virtual const PAlgebra& getZMStar() const = 0;
431 
433  virtual const std::vector<NTL::ZZX>& getFactorsOverZZ() const = 0;
434 
436  virtual long getR() const = 0;
437 
439  virtual long getPPowR() const = 0;
440 
442  virtual void restoreContext() const = 0;
443 
444  virtual zzX getMask_zzX(long i, long j) const = 0;
445 };
446 
447 #ifndef DOXYGEN_IGNORE
448 #define PA_INJECT(typ) \
449  static const PA_tag tag = typ::tag; \
450  typedef typename typ::R R; \
451  typedef typename typ::RX RX; \
452  typedef typename typ::vec_RX vec_RX; \
453  typedef typename typ::RXModulus RXModulus; \
454  typedef typename typ::RBak RBak; \
455  typedef typename typ::RContext RContext; \
456  typedef typename typ::RE RE; \
457  typedef typename typ::vec_RE vec_RE; \
458  typedef typename typ::mat_RE mat_RE; \
459  typedef typename typ::REX REX; \
460  typedef typename typ::REBak REBak; \
461  typedef typename typ::vec_REX vec_REX; \
462  typedef typename typ::REContext REContext; \
463  typedef typename typ::mat_R mat_R; \
464  typedef typename typ::vec_R vec_R;
465 
466 #endif
467 
468 template <typename type>
469 class PAlgebraModDerived;
470 // forward declaration
471 
473 template <typename type>
475 {
476 
477 public:
478  PA_INJECT(type)
479 
480  friend class PAlgebraModDerived<type>;
481 
482 private:
483  RX G; // the polynomial defining the field extension
484  long degG; // the degree of the polynomial
485 
486  REContext contextForG;
487 
488  /* the remaining fields are visible only to PAlgebraModDerived */
489 
490  std::vector<RX> maps;
491  std::vector<mat_R> matrix_maps;
492  std::vector<REX> rmaps;
493 
494 public:
495  const RX& getG() const { return G; }
496  long getDegG() const { return degG; }
497  void restoreContextForG() const { contextForG.restore(); }
498 
499  // copy and assignment
500 };
501 
503 template <typename T>
504 class TNode
505 {
506 public:
507  std::shared_ptr<TNode<T>> left, right;
508  T data;
509 
510  TNode(std::shared_ptr<TNode<T>> _left,
511  std::shared_ptr<TNode<T>> _right,
512  const T& _data) :
513  left(_left), right(_right), data(_data)
514  {}
515 };
516 
517 template <typename T>
518 std::shared_ptr<TNode<T>> buildTNode(std::shared_ptr<TNode<T>> left,
519  std::shared_ptr<TNode<T>> right,
520  const T& data)
521 {
522  return std::shared_ptr<TNode<T>>(new TNode<T>(left, right, data));
523 }
524 
525 template <typename T>
526 std::shared_ptr<TNode<T>> nullTNode()
527 {
528  return std::shared_ptr<TNode<T>>();
529 }
531 
533 template <typename type>
535 {
536 public:
537  PA_INJECT(type)
538 
539 private:
540  const PAlgebra& zMStar;
541  long r;
542  long pPowR;
543  RContext pPowRContext;
544 
545  RXModulus PhimXMod;
546 
547  vec_RX factors;
548  std::vector<NTL::ZZX> factorsOverZZ;
549  vec_RX crtCoeffs;
550  std::vector<std::vector<RX>> maskTable;
551  std::vector<RX> crtTable;
552  std::shared_ptr<TNode<RX>> crtTree;
553 
554  void genMaskTable();
555  void genCrtTable();
556 
557 public:
558  PAlgebraModDerived(const PAlgebra& zMStar, long r);
559 
560  PAlgebraModDerived(const PAlgebraModDerived& other) // copy constructor
561  :
562  zMStar(other.zMStar),
563  r(other.r),
564  pPowR(other.pPowR),
565  pPowRContext(other.pPowRContext)
566  {
567  RBak bak;
568  bak.save();
569  restoreContext();
570  PhimXMod = other.PhimXMod;
571  factors = other.factors;
572  maskTable = other.maskTable;
573  crtTable = other.crtTable;
574  crtTree = other.crtTree;
575  }
576 
577  PAlgebraModDerived& operator=(const PAlgebraModDerived& other) // assignment
578  {
579  if (this == &other)
580  return *this;
581 
582  assertEq(&zMStar,
583  &other.zMStar,
584  "Cannot assign PAlgebras with different zMStar values");
585  r = other.r;
586  pPowR = other.pPowR;
587  pPowRContext = other.pPowRContext;
588 
589  RBak bak;
590  bak.save();
591  restoreContext();
592  PhimXMod = other.PhimXMod;
593  factors = other.factors;
594  maskTable = other.maskTable;
595  crtTable = other.crtTable;
596  crtTree = other.crtTree;
597 
598  return *this;
599  }
600 
602  virtual PAlgebraModBase* clone() const override
603  {
604  return new PAlgebraModDerived(*this);
605  }
606 
608  virtual PA_tag getTag() const override { return tag; }
609 
611  virtual const PAlgebra& getZMStar() const override { return zMStar; }
612 
614  virtual const std::vector<NTL::ZZX>& getFactorsOverZZ() const override
615  {
616  return factorsOverZZ;
617  }
618 
620  virtual long getR() const override { return r; }
621 
623  virtual long getPPowR() const override { return pPowR; }
624 
626  virtual void restoreContext() const override { pPowRContext.restore(); }
627 
628  /* In all of the following functions, it is expected that the caller
629  has already restored the relevant modulus (p^r), which
630  can be done by invoking the method restoreContext()
631  */
632 
634  const RXModulus& getPhimXMod() const { return PhimXMod; }
635 
637  const vec_RX& getFactors() const { return factors; }
638 
642  const vec_RX& getCrtCoeffs() const { return crtCoeffs; }
643 
656  // logically, but not really, const
657  const std::vector<std::vector<RX>>& getMaskTable() const { return maskTable; }
658 
659  zzX getMask_zzX(long i, long j) const override
660  {
661  RBak bak;
662  bak.save();
663  restoreContext();
664  return balanced_zzX(maskTable.at(i).at(j));
665  }
666 
673 
676  void CRT_decompose(std::vector<RX>& crt, const RX& H) const;
677 
680  void CRT_reconstruct(RX& H, std::vector<RX>& crt) const;
681 
685  void mapToSlots(MappingData<type>& mappingData, const RX& G) const;
686 
693  void embedInAllSlots(RX& H,
694  const RX& alpha,
695  const MappingData<type>& mappingData) const;
696 
703  void embedInSlots(RX& H,
704  const std::vector<RX>& alphas,
705  const MappingData<type>& mappingData) const;
706 
711  void decodePlaintext(std::vector<RX>& alphas,
712  const RX& ptxt,
713  const MappingData<type>& mappingData) const;
714 
723  void buildLinPolyCoeffs(std::vector<RX>& C,
724  const std::vector<RX>& L,
725  const MappingData<type>& mappingData) const;
727 private:
728  /* internal functions, not for public consumption */
729 
730  static void SetModulus(long p)
731  {
732  RContext context(p);
733  context.restore();
734  }
735 
737  void mapToF1(RX& w, const RX& G) const { mapToFt(w, G, 1); }
738 
741  void mapToFt(RX& w, const RX& G, long t, const RX* rF1 = nullptr) const;
742 
743  void buildTree(std::shared_ptr<TNode<RX>>& res,
744  long offset,
745  long extent) const;
746 
747  void evalTree(RX& res,
748  std::shared_ptr<TNode<RX>> tree,
749  const std::vector<RX>& crt1,
750  long offset,
751  long extent) const;
752 };
753 
758 {
759  const PAlgebra& zMStar;
760  long r; // counts bits of precision
761 
762 public:
763  PAlgebraModCx(const PAlgebra& palg, long _r) : zMStar(palg), r(_r)
764  {
765  assertInRange<InvalidArgument>(r,
766  1l,
767  (long)NTL_SP_NBITS,
768  "Invalid bit precision r");
769  }
770 
771  PAlgebraModBase* clone() const override { return new PAlgebraModCx(*this); }
772  PA_tag getTag() const override { return PA_cx_tag; }
773 
774  const PAlgebra& getZMStar() const override { return zMStar; }
775  long getR() const override { return r; }
776  long getPPowR() const override { return 1L << r; }
777  void restoreContext() const override {}
778 
779  // These function make no sense for PAlgebraModCx
780  const std::vector<NTL::ZZX>& getFactorsOverZZ() const override
781  {
782  throw LogicError("PAlgebraModCx::getFactorsOverZZ undefined");
783  }
784  zzX getMask_zzX(UNUSED long i, UNUSED long j) const override
785  {
786  throw LogicError("PAlgebraModCx::getMask_zzX undefined");
787  }
788 };
789 
791 PAlgebraModBase* buildPAlgebraMod(const PAlgebra& zMStar, long r);
792 
793 // A simple wrapper for a pointer to an object of type PAlgebraModBase.
794 //
795 // Direct access to the virtual methods of PAlgebraModBase is provided,
796 // along with a "downcast" operator to get a reference to the object
797 // as a derived type, and == and != operators.
799 {
800 
801 private:
802  cloned_ptr<PAlgebraModBase> rep;
803 
804 public:
805  // copy constructor: default
806  // assignment: default
807  // destructor: default
808  // NOTE: the use of cloned_ptr ensures that the default copy constructor,
809  // assignment operator, and destructor will work correctly.
810 
811  explicit PAlgebraMod(const PAlgebra& zMStar, long r) :
812  rep(buildPAlgebraMod(zMStar, r))
813  {}
814  // constructor
815 
819  template <typename type>
821  {
822  return dynamic_cast<const PAlgebraModDerived<type>&>(*rep);
823  }
824  const PAlgebraModCx& getCx() const
825  {
826  return dynamic_cast<const PAlgebraModCx&>(*rep);
827  }
828 
829  bool operator==(const PAlgebraMod& other) const
830  {
831  return getZMStar() == other.getZMStar() && getR() == other.getR();
832  }
833  // comparison
834 
835  bool operator!=(const PAlgebraMod& other) const { return !(*this == other); }
836  // comparison
837 
838  /* direct access to the PAlgebraModBase methods */
839 
841  PA_tag getTag() const { return rep->getTag(); }
843  const PAlgebra& getZMStar() const { return rep->getZMStar(); }
845  const std::vector<NTL::ZZX>& getFactorsOverZZ() const
846  {
847  return rep->getFactorsOverZZ();
848  }
850  long getR() const { return rep->getR(); }
852  long getPPowR() const { return rep->getPPowR(); }
854  void restoreContext() const { rep->restoreContext(); }
855 
856  zzX getMask_zzX(long i, long j) const { return rep->getMask_zzX(i, j); }
857 };
858 
860 bool comparePAlgebra(const PAlgebra& palg,
861  unsigned long m,
862  unsigned long p,
863  unsigned long r,
864  const std::vector<long>& gens,
865  const std::vector<long>& ords);
866 
867 // for internal consumption only
868 double calcPolyNormBnd(long m);
869 
870 } // namespace helib
871 
872 #endif // #ifndef HELIB_PALGEBRA_H
virtual long getPPowR() const =0
The value p^r.
long OrderOf(long i) const
The order of i'th generator (if any)
Definition: PAlgebra.h:217
long getM() const
Returns m.
Definition: PAlgebra.h:162
bool isRep(long t) const
Is t in T?
Definition: PAlgebra.h:238
long getCoord(long i, long d) const
get coordinate in dimension d of index i
Definition: hypercube.h:104
long getNSlots() const
The number of plaintext slots = phi(m)/ord(p)
Definition: PAlgebra.h:186
long indexInZmstar_unchecked(long t) const
Returns the index of t in (Z/mZ)* – no range checking.
Definition: PAlgebra.h:244
zzX balanced_zzX(const NTL::zz_pX &f)
Definition: zzX.cpp:122
const vec_RX & getCrtCoeffs() const
Returns the CRT coefficients: element i contains (prod_{j!=i} F_j)^{-1} mod F_i, where F_0 F_1 ....
Definition: PAlgebra.h:642
void embedInAllSlots(RX &H, const RX &alpha, const MappingData< type > &mappingData) const
Returns H in R[X]/Phi_m(X) s.t. for every t in T, the element Ht = (H mod Ft) in R[X]/Ft(X) represent...
Definition: PAlgebra.cpp:887
void decodePlaintext(std::vector< RX > &alphas, const RX &ptxt, const MappingData< type > &mappingData) const
Return an array such that alphas[i] in R[X]/G(X) represent the same element as rt = (H mod Ft) in R[X...
Definition: PAlgebra.cpp:1228
virtual const PAlgebra & getZMStar() const override
Returns reference to underlying PAlgebra object.
Definition: PAlgebra.h:611
NTL::Vec< long > zzX
Definition: zzX.h:24
long genToPow(long i, long j) const
the i'th generator to the power j mod m
Definition: PAlgebra.cpp:606
PGFFT fft
Definition: PAlgebra.h:34
long getPPowR() const
The value p^r.
Definition: PAlgebra.h:852
long addCoord(long i, long k, long offset) const
adds offset to index k in the i'th dimension
Definition: PAlgebra.h:272
const std::vector< NTL::ZZX > & getFactorsOverZZ() const
Returns reference to the factorization of Phi_m(X) mod p^r, but as ZZX's.
Definition: PAlgebra.h:845
quarter_FFT(long m)
Definition: PAlgebra.cpp:183
virtual long getR() const override
The value r.
Definition: PAlgebra.h:620
@ PA_GF2_tag
Definition: PAlgebra.h:298
const quarter_FFT & getQuarterFFTInfo() const
Definition: PAlgebra.h:293
long assembleIndexByDim(std::pair< long, long > idx, long dim) const
The inverse of breakIndexByDim.
Definition: PAlgebra.h:266
zzX getMask_zzX(UNUSED long i, UNUSED long j) const override
Definition: PAlgebra.h:784
long indexInZmstar(long t) const
Returns the index of t in (Z/mZ)*.
Definition: PAlgebra.h:241
long fftSizeNeeded() const
The largest FFT we need to handle degree-m polynomials.
Definition: PAlgebra.h:288
long getOrdP() const
The order of p in (Z/mZ)^*.
Definition: PAlgebra.h:171
Definition: PAlgebra.h:33
virtual PAlgebraModBase * clone() const =0
Inherits from Exception and std::logic_error.
Definition: exceptions.h:68
PAlgebraModBase * clone() const override
Definition: PAlgebra.h:771
virtual void restoreContext() const =0
Restores the NTL context for p^r.
long frobeniusPow(long j) const
Definition: PAlgebra.cpp:600
Auxiliary structure to support encoding/decoding slots.
Definition: PAlgebra.h:475
const PAlgebraModCx & getCx() const
Definition: PAlgebra.h:824
virtual void restoreContext() const override
Restores the NTL context for p^r.
Definition: PAlgebra.h:626
const std::vector< NTL::ZZX > & getFactorsOverZZ() const override
Returns reference to the factorization of Phi_m(X) mod p^r, but as ZZX's.
Definition: PAlgebra.h:780
const PAlgebra & getZMStar() const
Returns reference to underlying PAlgebra object.
Definition: PAlgebra.h:843
long ZmStarGen(long i) const
the i'th generator in (Z/mZ)^* /(p) (if any)
Definition: PAlgebra.h:205
bool inZmStar(long t) const
Definition: PAlgebra.h:249
virtual const PAlgebra & getZMStar() const =0
Returns reference to underlying PAlgebra object.
virtual long getR() const =0
The value r.
void restoreContext() const
Restores the NTL context for p^r.
Definition: PAlgebra.h:854
void assertEq(const T &a, const T &b, const std::string &message)
Definition: assertions.h:108
long getDegG() const
Definition: PAlgebra.h:496
std::vector< std::complex< double > > pow2
Definition: PAlgebra.h:43
long addCoord(long i, long d, long offset) const
add offset to coordinate in dimension d of index i
Definition: hypercube.h:115
long getP() const
Returns p.
Definition: PAlgebra.h:165
bool incrementCoords(VecType &v) const
Definition: hypercube.h:138
Definition: PGFFT.h:30
void restoreContextForG() const
Definition: PAlgebra.h:497
const PGFFT & getFFTInfo() const
Definition: PAlgebra.h:291
double get_cM() const
Definition: PAlgebra.h:196
virtual PAlgebraModBase * clone() const override
Returns a pointer to a "clone".
Definition: PAlgebra.h:602
std::vector< std::complex< double > > pow1
Definition: PAlgebra.h:43
bool operator!=(const PAlgebra &other) const
Definition: PAlgebra.h:150
std::pair< long, long > breakIndexByDim(long idx, long dim) const
Definition: PAlgebra.h:261
The structure of (Z/mZ)* /(p)
Definition: PAlgebra.h:77
PAlgebra(long mm, long pp=2, const std::vector< long > &_gens=std::vector< long >(), const std::vector< long > &_ords=std::vector< long >())
Definition: PAlgebra.cpp:431
virtual const std::vector< NTL::ZZX > & getFactorsOverZZ() const override
Returns reference to the factorization of Phi_m(X) mod p^r, but as ZZX's.
Definition: PAlgebra.h:614
const half_FFT & getHalfFFTInfo() const
Definition: PAlgebra.h:292
long getDim(long d) const
size of dimension d
Definition: hypercube.h:92
long assembleIndexByDim(std::pair< long, long > idx, long dim) const
The inverse of breakIndexByDim.
Definition: hypercube.cpp:29
void printout(std::ostream &out=std::cout) const
Prints the structure in a readable form.
Definition: PAlgebra.cpp:107
PA_tag getTag() const override
Returns the type tag: PA_GF2_tag or PA_zz_p_tag.
Definition: PAlgebra.h:772
const NTL::ZZX & getPhimX() const
The cyclotomix polynomial Phi_m(X)
Definition: PAlgebra.h:192
long getPow2() const
if m = 2^k, then pow2 == k; otherwise, pow2 == 0
Definition: PAlgebra.h:189
void CRT_decompose(std::vector< RX > &crt, const RX &H) const
Returns a std::vector crt[] such that crt[i] = H mod Ft (with t = T[i])
Definition: PAlgebra.cpp:872
long getProd(long d) const
product of sizes of dimensions d, d+1, ...
Definition: hypercube.h:95
bool operator!=(const PAlgebraMod &other) const
Definition: PAlgebra.h:835
bool operator==(const PAlgebraMod &other) const
Definition: PAlgebra.h:829
Definition: PAlgebra.h:41
const PAlgebra & getZMStar() const override
Returns reference to underlying PAlgebra object.
Definition: PAlgebra.h:774
PA_tag
Definition: PAlgebra.h:297
long FrobPerturb(long i) const
Definition: PAlgebra.h:227
long getPPowR() const override
The value p^r.
Definition: PAlgebra.h:776
bool SameOrd(long i) const
Is ord(i'th generator) the same as its order in (Z/mZ)^*?
Definition: PAlgebra.h:223
PAlgebraModBase * buildPAlgebraMod(const PAlgebra &zMStar, long r)
Builds a table, of type PA_GF2 if p == 2 and r == 1, and PA_zz_p otherwise.
Definition: PAlgebra.cpp:632
double getNormBnd() const
max-norm-on-pwfl-basis <= normBnd * max-norm-canon-embed
Definition: PAlgebra.h:180
virtual PA_tag getTag() const override
Returns the type tag: PA_GF2_tag or PA_zz_p_tag.
Definition: PAlgebra.h:608
void embedInSlots(RX &H, const std::vector< RX > &alphas, const MappingData< type > &mappingData) const
Returns H in R[X]/Phi_m(X) s.t. for every t in T, the element Ht = (H mod Ft) in R[X]/Ft(X) represent...
Definition: PAlgebra.cpp:925
bool comparePAlgebra(const PAlgebra &palg, unsigned long m, unsigned long p, unsigned long r, const std::vector< long > &gens, const std::vector< long > &ords)
returns true if the palg parameters match the rest, false otherwise
double getPolyNormBnd() const
max-norm-on-pwfl-basis <= polyNormBnd * max-norm-canon-embed
Definition: PAlgebra.h:183
const RXModulus & getPhimXMod() const
Returns reference to an RXModulus representing Phi_m(X) (mod p^r)
Definition: PAlgebra.h:634
void mapToSlots(MappingData< type > &mappingData, const RX &G) const
Compute the maps for all the slots. In the current implementation, we if r > 1, then we must have eit...
Definition: PAlgebra.cpp:1101
long getNFactors() const
The number of distinct prime factors of m.
Definition: PAlgebra.h:174
Definition: apiAttributes.h:21
PAlgebraModCx(const PAlgebra &palg, long _r)
Definition: PAlgebra.h:763
long getR() const
The value r.
Definition: PAlgebra.h:850
long repInZmstar_unchecked(long idx) const
Returns rep whose index is i.
Definition: PAlgebra.h:247
bool nextExpVector(std::vector< long > &exps) const
Definition: PAlgebra.h:282
const PAlgebraModDerived< type > & getDerived(type) const
Definition: PAlgebra.h:820
const std::vector< std::vector< RX > > & getMaskTable() const
Returns ref to maskTable, which is used to implement rotations (in the EncryptedArray module).
Definition: PAlgebra.h:657
Holds a vector of dimensions for a hypercube and some additional data.
Definition: hypercube.h:28
half_FFT(long m)
Definition: PAlgebra.cpp:170
virtual zzX getMask_zzX(long i, long j) const =0
virtual long getPPowR() const override
The value p^r.
Definition: PAlgebra.h:623
PAlgebraModDerived(const PAlgebra &zMStar, long r)
Definition: PAlgebra.cpp:668
long indexOfRep(long t) const
Returns the index of t in T.
Definition: PAlgebra.h:235
void printAll(std::ostream &out=std::cout) const
Definition: PAlgebra.cpp:149
long getPhiM() const
Returns phi(m)
Definition: PAlgebra.h:168
@ PA_cx_tag
Definition: PAlgebra.h:300
long getSize() const
total size of cube
Definition: hypercube.h:89
void CRT_reconstruct(RX &H, std::vector< RX > &crt) const
Returns H in R[X]/Phi_m(X) s.t. for every i<nSlots and t=T[i], we have H == crt[i] (mod Ft)
Definition: PAlgebra.cpp:994
long coordinate(long i, long k) const
Returns coordinate of index k along the i'th dimension.
Definition: PAlgebra.h:257
long getRadM() const
getRadM() = prod of distinct prime factors of m
Definition: PAlgebra.h:177
Virtual base class for PAlgebraMod.
Definition: PAlgebra.h:420
std::vector< std::complex< double > > pow
Definition: PAlgebra.h:35
The structure of Z[X]/(Phi_m(X), p)
Definition: PAlgebra.h:799
long exponentiate(const std::vector< long > &exps, bool onlySameOrd=false) const
Returns prod_i gi^{exps[i]} mod m. If onlySameOrd=true, use only generators that have the same order ...
Definition: PAlgebra.cpp:91
@ PA_zz_p_tag
Definition: PAlgebra.h:299
virtual PA_tag getTag() const =0
Returns the type tag: PA_GF2_tag or PA_zz_p_tag.
const vec_RX & getFactors() const
Returns reference to the factors of Phim_m(X) modulo p^r.
Definition: PAlgebra.h:637
PGFFT fft
Definition: PAlgebra.h:42
long numOfGens() const
The prime-power factorization of m.
Definition: PAlgebra.h:202
virtual const std::vector< NTL::ZZX > & getFactorsOverZZ() const =0
Returns reference to the factorization of Phi_m(X) mod p^r, but as ZZX's.
std::pair< long, long > breakIndexByDim(long idx, long dim) const
Definition: hypercube.cpp:20
long ith_rep(long i) const
Returns the i'th element in T.
Definition: PAlgebra.h:232
zzX getMask_zzX(long i, long j) const
Definition: PAlgebra.h:856
void set_cM(double c)
The "ring constant" cM.
Definition: PAlgebra.h:195
Definition: PAlgebra.h:758
void restoreContext() const override
Restores the NTL context for p^r.
Definition: PAlgebra.h:777
zzX getMask_zzX(long i, long j) const override
Definition: PAlgebra.h:659
PA_tag getTag() const
Returns the type tag: PA_GF2_tag or PA_zz_p_tag.
Definition: PAlgebra.h:841
const RX & getG() const
Definition: PAlgebra.h:495
double calcPolyNormBnd(long m)
Definition: PAlgebra.cpp:213
void buildLinPolyCoeffs(std::vector< RX > &C, const std::vector< RX > &L, const MappingData< type > &mappingData) const
Returns a coefficient std::vector C for the linearized polynomial representing M.
Definition: PAlgebra.cpp:1266
PAlgebraMod(const PAlgebra &zMStar, long r)
Definition: PAlgebra.h:811
PAlgebraModDerived(const PAlgebraModDerived &other)
Definition: PAlgebra.h:560
A concrete instantiation of the virtual class.
Definition: PAlgebra.h:535
virtual ~PAlgebraModBase()
Definition: PAlgebra.h:423
PAlgebraModDerived & operator=(const PAlgebraModDerived &other)
Definition: PAlgebra.h:577
bool operator==(const PAlgebra &other) const
Definition: PAlgebra.cpp:81
long ProdOrdsFrom(long i) const
The product prod_{j=i}^{n-1} OrderOf(i)
Definition: PAlgebra.h:220
long getR() const override
The value r.
Definition: PAlgebra.h:775