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 |
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}.
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)
|
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)