HElib  1.0
Implementing Homomorphic Encryption
 All Classes Files Functions Variables Friends Pages
Classes | Typedefs | Functions
NumbTh.h File Reference

Miscellaneous utility functions. More...

#include <vector>
#include <cmath>
#include <istream>
#include <NTL/ZZ.h>
#include <NTL/ZZ_p.h>
#include <NTL/ZZX.h>
#include <NTL/GF2X.h>
#include <NTL/vec_ZZ.h>
#include <NTL/xdouble.h>
#include <NTL/mat_lzz_pE.h>
#include <NTL/mat_GF2E.h>
#include <NTL/lzz_pXFactoring.h>
#include <NTL/GF2XFactoring.h>
#include <tr1/unordered_map>
#include <string>

Go to the source code of this file.

Classes

class  RandomState
 Facility for "restoring" the NTL PRG state. More...
 

Typedefs

typedef tr1::unordered_map
< string, const char * > 
argmap_t
 

Functions

bool parseArgs (int argc, char *argv[], argmap_t &argmap)
 Code for parsing command line arguments. More...
 
long multOrd (long p, long m)
 Return multiplicative order of p modulo m, or 0 if GCD(p, m) != 1.
 
void ppsolve (vec_zz_pE &x, const mat_zz_pE &A, const vec_zz_pE &b, long p, long r)
 Prime power solver. More...
 
void ppsolve (vec_GF2E &x, const mat_GF2E &A, const vec_GF2E &b, long p, long r)
 A version for GF2: must have p == 2 and r == 1.
 
void buildLinPolyCoeffs (vec_zz_pE &C, const vec_zz_pE &L, long p, long r)
 Combination of buildLinPolyMatrix and ppsolve. More...
 
void buildLinPolyCoeffs (vec_GF2E &C, const vec_GF2E &L, long p, long r)
 A version for GF2: must be called with p == 2 and r == 1.
 
void applyLinPoly (zz_pE &beta, const vec_zz_pE &C, const zz_pE &alpha, long p)
 Apply a linearized polynomial with coefficient vector C. More...
 
void applyLinPoly (GF2E &beta, const vec_GF2E &C, const GF2E &alpha, long p)
 A version for GF2: must be called with p == 2 and r == 1.
 
double log2 (const xdouble &x)
 Base-2 logarithm.
 
double log2 (const double x)
 
void factorize (vector< long > &factors, long N)
 Factoring by trial division, only works for N<2^{60}, only the primes are recorded, not their multiplicity.
 
void factorize (vector< ZZ > &factors, const ZZ &N)
 
void phiN (long &phiN, vector< long > &facts, long N)
 Compute Phi(N) and also factorize N.
 
void phiN (ZZ &phiN, vector< ZZ > &facts, const ZZ &N)
 
int phi_N (int N)
 Compute Phi(N).
 
void FindPrimitiveRoot (zz_p &r, unsigned e)
 Find e-th root of unity modulo the current modulus.
 
void FindPrimitiveRoot (ZZ_p &r, unsigned e)
 
int mobius (int n)
 Compute mobius function (naive method as n is small).
 
ZZX Cyclotomic (int N)
 Compute cyclotomic polynomial.
 
int primroot (int N, int phiN)
 Find a primitive root modulo N.
 
int ord (int N, int p)
 Compute the highest power of p that divides N.
 
ZZX RandPoly (int n, const ZZ &p)
 
void MulMod (ZZX &out, const ZZX &f, long a, long q, bool abs=true)
 Multiply the polynomial f by the integer a modulo q.
 
ZZX MulMod (const ZZX &f, long a, long q, bool abs=true)
 
template<class T1 , class T2 >
void convert (T1 &x1, const T2 &x2)
 A generic template that resolves to NTL's conv routine.
 
template<class T1 , class T2 >
void convert (vector< T1 > &v1, const vector< T2 > &v2)
 A generic vector conversion routine.
 
void mul (vector< ZZX > &x, const vector< ZZX > &a, long b)
 
void div (vector< ZZX > &x, const vector< ZZX > &a, long b)
 
void add (vector< ZZX > &x, const vector< ZZX > &a, const vector< ZZX > &b)
 
int is_in (int x, int *X, int sz)
 Finds whether x is an element of the set X of size sz, Returns -1 it not and the location if true.
 
template<class zzvec >
bool intVecCRT (vec_ZZ &vp, const ZZ &p, const zzvec &vq, long q)
 Incremental integer CRT for vectors. More...
 
template<class T , bool maxFlag>
long argminmax (vector< T > &v)
 Find the index of the (first) largest/smallest element. More...
 
template<class T >
long argmax (vector< T > &v)
 
template<class T >
long argmin (vector< T > &v)
 
void sampleSmall (ZZX &poly, long n=0)
 Sample polynomials with entries {-1,0,1}. Each coefficient is 0 with probability 1/2 and +-1 with probability 1/4.
 
void sampleHWt (ZZX &poly, long Hwt, long n=0)
 Sample polynomials with entries {-1,0,1} with a given HAming weight. More...
 
void sampleGaussian (ZZX &poly, long n=0, double stdev=1.0)
 Sample polynomials with Gaussian coefficients.
 
void seekPastChar (istream &str, int cc)
 Advance the input stream beyond white spaces and a single instance of the char cc.
 
template<typename T >
long lsize (const vector< T > &v)
 Size of STL vector as a long (rather than unsigned long)
 
template<typename T1 , typename T2 >
bool sameObject (const T1 *p1, const T2 *p2)
 Testing if two vectors point to the same object.
 
void ModComp (ZZX &res, const ZZX &g, const ZZX &h, const ZZX &f)
 Modular composition of polynomials: res = g(h) mod f.
 
void PolyRed (ZZX &out, const ZZX &in, int q, bool abs=false)
 Reduce all the coefficients of a polynomial modulo q. More...
 
void PolyRed (ZZX &out, const ZZX &in, const ZZ &q, bool abs=false)
 
void PolyRed (ZZX &F, int q, bool abs=false)
 
void PolyRed (ZZX &F, const ZZ &q, bool abs=false)
 
Some enhanced conversion routines
void convert (long &x1, const GF2X &x2)
 
void convert (long &x1, const zz_pX &x2)
 
void convert (vec_zz_pE &X, const vector< ZZX > &A)
 
void convert (mat_zz_pE &X, const vector< vector< ZZX > > &A)
 
void convert (vector< ZZX > &X, const vec_zz_pE &A)
 
void convert (vector< vector< ZZX > > &X, const mat_zz_pE &A)
 
The size of the coefficient vector of a polynomial.
ZZ sumOfCoeffs (const ZZX &f)
 
ZZ largestCoeff (const ZZX &f)
 
xdouble coeffsL2Norm (const ZZX &f)
 

Detailed Description

Miscellaneous utility functions.

Function Documentation

void applyLinPoly ( zz_pE &  beta,
const vec_zz_pE &  C,
const zz_pE &  alpha,
long  p 
)

Apply a linearized polynomial with coefficient vector C.

NTL's current smallint modulus, zz_p::modulus(), is assumed to be p^r, for p prime, r >= 1 integer.

template<class T , bool maxFlag>
long argminmax ( vector< T > &  v)

Find the index of the (first) largest/smallest element.

These procedures are roughly just simpler variants of std::max_element and std::min_element. argmin/argmax are implemented as a template, so the code must be placed in the header file for the comiler to find it. The class T must have an implementation of operator> and operator< for this template to work.

Template Parameters
maxFlagA boolean value: true - argmax, false - argmin
void buildLinPolyCoeffs ( vec_zz_pE &  C,
const vec_zz_pE &  L,
long  p,
long  r 
)

Combination of buildLinPolyMatrix and ppsolve.

Obtain the linearized polynomial coefficients from a vector L representing the action of a linear map on the standard basis for zz_pE over zz_p.

NTL's current smallint modulus, zz_p::modulus(), is assumed to be p^r, for p prime, r >= 1 integer.

template<class zzvec >
bool intVecCRT ( vec_ZZ &  vp,
const ZZ &  p,
const zzvec &  vq,
long  q 
)

Incremental integer CRT for vectors.

Expects co-primes p,q with q odd, and such that all the entries in v1 are in [-p/2,p/2). Returns in v1 the CRT of vp mod p and vq mod q, as integers in [-pq/2, pq/2). Uses the formula:

\[ CRT(vp,p,vq,q) = vp + [(vq-vp) * p^{-1}]_q * p, \]

where [...]_q means reduction to the interval [-q/2,q/2). Notice that if q is odd then this is the same as reducing to [-(q-1)/2,(q-1)/2], which means that [...]_q * p is in [-p(q-1)/2, p(q-1)/2], and since vp is in [-p/2,p/2) then the sum is indeed in [-pq/2,pq/2).

Return true is both vectors are of the same length, false otherwise

bool parseArgs ( int  argc,
char *  argv[],
argmap_t &  argmap 
)

Code for parsing command line arguments.

Tries to parse each argument as arg=val, and returns a correspinding map. It returns false if errors were detected, and true otherwise.

void PolyRed ( ZZX &  out,
const ZZX &  in,
int  q,
bool  abs = false 
)

Reduce all the coefficients of a polynomial modulo q.

When abs=false reduce to interval (-q/2,...,q/2), when abs=true reduce to [0,q). When abs=false and q=2, maintains the same sign as the input.

void ppsolve ( vec_zz_pE &  x,
const mat_zz_pE &  A,
const vec_zz_pE &  b,
long  p,
long  r 
)

Prime power solver.

A is an n x n matrix, b is a length n (row) vector, this function finds a solution for the matrix-vector equation x A = b. An error is raised if A is not inverible mod p.

NTL's current smallint modulus, zz_p::modulus(), is assumed to be p^r, for p prime, r >= 1 integer.

void sampleHWt ( ZZX &  poly,
long  Hwt,
long  n = 0 
)

Sample polynomials with entries {-1,0,1} with a given HAming weight.

Choose min(Hwt,n) coefficients at random in {-1,+1} and the others are set to zero. If n=0 then n=poly.deg()+1 is used.