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) |
Miscellaneous utility functions.
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.
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.
maxFlag | A 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.
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:
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.