helib::PAlgebra Class Reference

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

#include <PAlgebra.h>

Public Member Functions
	PAlgebra (long mm, long pp=2, const std::vector< long > &_gens=std::vector< long >(), const std::vector< long > &_ords=std::vector< long >())
bool	operator== (const PAlgebra &other) const
bool	operator!= (const PAlgebra &other) const
void	printout (std::ostream &out=std::cout) const
	Prints the structure in a readable form. More...
void	printAll (std::ostream &out=std::cout) const
long	getM () const
	Returns m. More...
long	getP () const
	Returns p. More...
long	getPhiM () const
	Returns phi(m) More...
long	getOrdP () const
	The order of p in (Z/mZ)^*. More...
long	getNFactors () const
	The number of distinct prime factors of m. More...
long	getRadM () const
	getRadM() = prod of distinct prime factors of m More...
double	getNormBnd () const
	max-norm-on-pwfl-basis <= normBnd * max-norm-canon-embed More...
double	getPolyNormBnd () const
	max-norm-on-pwfl-basis <= polyNormBnd * max-norm-canon-embed More...
long	getNSlots () const
	The number of plaintext slots = phi(m)/ord(p) More...
long	getPow2 () const
	if m = 2^k, then pow2 == k; otherwise, pow2 == 0 More...
const NTL::ZZX &	getPhimX () const
	The cyclotomix polynomial Phi_m(X) More...
void	set_cM (double c)
	The "ring constant" cM. More...
double	get_cM () const
long	numOfGens () const
	The prime-power factorization of m. More...
long	ZmStarGen (long i) const
	the i'th generator in (Z/mZ)^* /(p) (if any) More...
long	genToPow (long i, long j) const
	the i'th generator to the power j mod m More...
long	frobeniusPow (long j) const
long	OrderOf (long i) const
	The order of i'th generator (if any) More...
long	ProdOrdsFrom (long i) const
	The product prod_{j=i}^{n-1} OrderOf(i) More...
bool	SameOrd (long i) const
	Is ord(i'th generator) the same as its order in (Z/mZ)^*? More...
long	FrobPerturb (long i) const
Translation between index, representatives, and exponents
long	ith_rep (long i) const
	Returns the i'th element in T. More...
long	indexOfRep (long t) const
	Returns the index of t in T. More...
bool	isRep (long t) const
	Is t in T? More...
long	indexInZmstar (long t) const
	Returns the index of t in (Z/mZ)*. More...
long	indexInZmstar_unchecked (long t) const
	Returns the index of t in (Z/mZ)* – no range checking. More...
long	repInZmstar_unchecked (long idx) const
	Returns rep whose index is i. More...
bool	inZmStar (long t) const
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 as in (Z/mZ)^*. More...
long	coordinate (long i, long k) const
	Returns coordinate of index k along the i'th dimension. More...
std::pair< long, long >	breakIndexByDim (long idx, long dim) const
long	assembleIndexByDim (std::pair< long, long > idx, long dim) const
	The inverse of breakIndexByDim. More...
long	addCoord (long i, long k, long offset) const
	adds offset to index k in the i'th dimension More...
bool	nextExpVector (std::vector< long > &exps) const
long	fftSizeNeeded () const
	The largest FFT we need to handle degree-m polynomials. More...
const PGFFT &	getFFTInfo () const
const half_FFT &	getHalfFFTInfo () const
const quarter_FFT &	getQuarterFFTInfo () 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 describing 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}.

Constructor & Destructor Documentation

PAlgebra()

helib::PAlgebra::PAlgebra	(	long	mm,
		long	pp = 2,
		const std::vector< long > &	_gens = std::vector<long>(),
		const std::vector< long > &	_ords = std::vector<long>()
	)

Member Function Documentation

addCoord()

long helib::PAlgebra::addCoord ( long  i, long  k, long  offset  ) const

inline

adds offset to index k in the i'th dimension

assembleIndexByDim()

long helib::PAlgebra::assembleIndexByDim ( std::pair< long, long >  idx, long  dim  ) const

inline

The inverse of breakIndexByDim.

breakIndexByDim()

std::pair<long, long> helib::PAlgebra::breakIndexByDim ( long  idx, long  dim  ) const

inline

Break an index into the hypercube to index of the dimension-dim subcube and index inside that subcube.

coordinate()

long helib::PAlgebra::coordinate ( long  i, long  k  ) const

inline

Returns coordinate of index k along the i'th dimension.

exponentiate()

long helib::PAlgebra::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 as in (Z/mZ)^*.

fftSizeNeeded()

long helib::PAlgebra::fftSizeNeeded ( ) const

inline

The largest FFT we need to handle degree-m polynomials.

frobeniusPow()

long helib::PAlgebra::frobeniusPow

(

long

j

)

const

FrobPerturb()

long helib::PAlgebra::FrobPerturb ( long  i ) const

inline

genToPow()

long helib::PAlgebra::genToPow	(	long	i,
		long	j
	)		const

the i'th generator to the power j mod m

get_cM()

double helib::PAlgebra::get_cM ( ) const

inline

getFFTInfo()

const PGFFT& helib::PAlgebra::getFFTInfo ( ) const

inline

getHalfFFTInfo()

const half_FFT& helib::PAlgebra::getHalfFFTInfo ( ) const

inline

getM()

long helib::PAlgebra::getM ( ) const

inline

Returns m.

getNFactors()

long helib::PAlgebra::getNFactors ( ) const

inline

The number of distinct prime factors of m.

getNormBnd()

double helib::PAlgebra::getNormBnd ( ) const

inline

max-norm-on-pwfl-basis <= normBnd * max-norm-canon-embed

getNSlots()

long helib::PAlgebra::getNSlots ( ) const

inline

The number of plaintext slots = phi(m)/ord(p)

getOrdP()

long helib::PAlgebra::getOrdP ( ) const

inline

The order of p in (Z/mZ)^*.

getP()

long helib::PAlgebra::getP ( ) const

inline

Returns p.

getPhiM()

long helib::PAlgebra::getPhiM ( ) const

inline

Returns phi(m)

getPhimX()

const NTL::ZZX& helib::PAlgebra::getPhimX ( ) const

inline

The cyclotomix polynomial Phi_m(X)

getPolyNormBnd()

double helib::PAlgebra::getPolyNormBnd ( ) const

inline

max-norm-on-pwfl-basis <= polyNormBnd * max-norm-canon-embed

getPow2()

long helib::PAlgebra::getPow2 ( ) const

inline

if m = 2^k, then pow2 == k; otherwise, pow2 == 0

getQuarterFFTInfo()

const quarter_FFT& helib::PAlgebra::getQuarterFFTInfo ( ) const

inline

getRadM()

long helib::PAlgebra::getRadM ( ) const

inline

getRadM() = prod of distinct prime factors of m

indexInZmstar()

long helib::PAlgebra::indexInZmstar ( long  t ) const

inline

Returns the index of t in (Z/mZ)*.

indexInZmstar_unchecked()

long helib::PAlgebra::indexInZmstar_unchecked ( long  t ) const

inline

Returns the index of t in (Z/mZ)* – no range checking.

indexOfRep()

long helib::PAlgebra::indexOfRep ( long  t ) const

inline

Returns the index of t in T.

inZmStar()

bool helib::PAlgebra::inZmStar ( long  t ) const

inline

isRep()

bool helib::PAlgebra::isRep ( long  t ) const

inline

Is t in T?

ith_rep()

long helib::PAlgebra::ith_rep ( long  i ) const

inline

Returns the i'th element in T.

nextExpVector()

bool helib::PAlgebra::nextExpVector ( std::vector< long > &  exps ) const

inline

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

numOfGens()

long helib::PAlgebra::numOfGens ( ) const

inline

The prime-power factorization of m.

The number of generators in (Z/mZ)^* /(p)

operator!=()

bool helib::PAlgebra::operator!= ( const PAlgebra &  other ) const

inline

operator==()

bool helib::PAlgebra::operator==

(

const PAlgebra &

other

)

const

OrderOf()

long helib::PAlgebra::OrderOf ( long  i ) const

inline

The order of i'th generator (if any)

printAll()

void helib::PAlgebra::printAll

(

std::ostream &

out = std::cout

)

const

printout()

void helib::PAlgebra::printout

(

std::ostream &

out = std::cout

)

const

Prints the structure in a readable form.

ProdOrdsFrom()

long helib::PAlgebra::ProdOrdsFrom ( long  i ) const

inline

The product prod_{j=i}^{n-1} OrderOf(i)

repInZmstar_unchecked()

long helib::PAlgebra::repInZmstar_unchecked ( long  idx ) const

inline

Returns rep whose index is i.

SameOrd()

bool helib::PAlgebra::SameOrd ( long  i ) const

inline

Is ord(i'th generator) the same as its order in (Z/mZ)^*?

set_cM()

void helib::PAlgebra::set_cM ( double  c )

inline

The "ring constant" cM.

ZmStarGen()

long helib::PAlgebra::ZmStarGen ( long  i ) const

inline

the i'th generator in (Z/mZ)^* /(p) (if any)