HElib  1.0
Implementing Homomorphic Encryption
 All Classes Files Functions Variables Friends Pages
Public Member Functions | List of all members
PAlgebra Class Reference

The structure of (Z/mZ)* /(p) More...

#include <PAlgebra.h>

Public Member Functions

 PAlgebra (unsigned mm, unsigned pp=2)
 
bool operator== (const PAlgebra &other) const
 
bool operator!= (const PAlgebra &other) const
 
void printout () const
 Prints the structure in a readable form.
 
unsigned getM () const
 Returns m.
 
unsigned getP () const
 Returns p.
 
unsigned getPhiM () const
 Returns phi(m)
 
unsigned getOrdP () const
 The order of p in (Z/mZ)^*.
 
unsigned getNSlots () const
 The number of plaintext slots = phi(m) = ord(p)
 
const ZZX & getPhimX () const
 The cyclotomix polynomial Phi_m(X)
 
unsigned numOfGens () const
 The number of generators in (Z/mZ)^* /(p)
 
unsigned ZmStarGen (unsigned i) const
 the i'th generator in (Z/mZ)^* /(p) (if any)
 
unsigned OrderOf (unsigned i) const
 The order of i'th generator (if any)
 
bool SameOrd (unsigned i) const
 Is ord(i'th generator) the same as its order in (Z/mZ)^*?
 
Translation between index, represnetatives, and exponents
unsigned ith_rep (unsigned i) const
 Returns the i'th element in T.
 
int indexOfRep (unsigned t) const
 Returns the index of t in T.
 
bool isRep (unsigned t) const
 Is t in T?
 
int indexInZmstar (unsigned t) const
 Returns the index of t in (Z/mZ)*.
 
bool inZmStar (unsigned t) const
 Is t in [0,m-1] with (t,m)=1?
 
long coordinate (long i, long k) const
 Returns ith coordinate of index k along the i'th dimension. See Section 2.4 in the design document.
 
unsigned exponentiate (const vector< unsigned > &exps, bool onlySameOrd=false) const
 Returns prod_i gi^{exps[i]} mod m. If onlySameOrd=true, use only generators that have the same order as in (Z/mZ)^*.
 
const int * dLog (unsigned t) const
 Inverse of exponentiate.
 
unsigned qGrpOrd (bool onlySameOrd=false) const
 
bool nextExpVector (vector< unsigned > &exps) const
 

Detailed Description

The structure of (Z/mZ)* /(p)

A PAlgebra object is determined by an integer m and a prime p, where p does not divide m. It holds information descrtibing the structure of (Z/mZ)^*, which is isomorphic to the Galois group over A = Z[X]/Phi_m(X)).

We represent (Z/mZ)^* as (Z/mZ)^* = (p) x (g1,g2,...) x (h1,h2,...) where the group generated by g1,g2,... consists of the elements that have the same order in (Z/mZ)^* as in (Z/mZ)^* /(p,g_1,...,g_{i-1}), and h1,h2,... generate the remaining quotient group (Z/mZ)^* /(p,g1,g2,...).

We let T subset (Z/mZ)^* be a set of representatives for the quotient group (Z/mZ)^* /(p), defined as T={ prod_i gi^{ei} * prod_j hj^{ej} } where the ei's range over 0,1,...,ord(gi)-1 and the ej's range over 0,1,...ord(hj)-1 (these last orders are in (Z/mZ)^* /(p,g1,g2,...)).

Phi_m(X) is factored as Phi_m(X)= prod_{t in T} F_t(X) mod p, where the F_t's are irreducible modulo p. An arbitrary factor is chosen as F_1, then for each t in T we associate with the index t the factor F_t(X) = GCD(F_1(X^t), Phi_m(X)).

Note that fixing a representation of the field R=(Z/pZ)[X]/F_1(X) and letting z be a root of F_1 in R (which is a primitive m-th root of unity in R), we get that F_t is the minimal polynomial of z^{1/t}.

Member Function Documentation

bool PAlgebra::nextExpVector ( vector< unsigned > &  exps) const

exps is an array of exponents (the dLog of some t in T), this function incerement exps lexicographic order, reutrn false if it cannot be incremented (because it is at its maximum value)

unsigned PAlgebra::qGrpOrd ( bool  onlySameOrd = false) const
inline

The order of the quoteint group (Z/mZ)^* /(p) (if flag=false), or the subgroup of elements with the same order as in (Z/mZ)^* (if flag=true)


The documentation for this class was generated from the following files: