galois.h
Go to the documentation of this file.
#ifndef GALOIS_H
#define GALOIS_H
#include <itpp/base/vec.h>
#include <itpp/base/array.h>
#include <itpp/base/binary.h>
#include <itpp/base/converters.h>
#include <itpp/itexports.h>
#include <itpp/base/base_exports.h>
namespace itpp
{
class ITPP_EXPORT GF
{
public:
GF() { m = 0; }
GF(int qvalue) {
m = 0;
if (qvalue == 0) // qvalue==0 gives the zeroth element
value = -1;
else set_size(qvalue);
}
GF(int qvalue, int inexp) { m = 0; set(qvalue, inexp); }
GF(const GF &ingf) { m = ingf.m; value = ingf.value; }
void set(int qvalue, int inexp) {
set_size(qvalue);
it_assert_debug(inexp >= -1 && inexp < qvalue - 1, "GF::set, out of range");
value = inexp;
}
void set(int qvalue, const bvec &vectorspace);
void set_size(int qvalue);
int get_size() const { return ((m != 0) ? q[m] : 0); }
bvec get_vectorspace() const;
int get_value() const;
int operator==(const GF &ingf) const;
int operator!=(const GF &ingf) const;
void operator=(const GF &ingf);
void operator=(const int inexp);
void operator+=(const GF &ingf);
GF operator+(const GF &ingf) const;
void operator-=(const GF &ingf);
GF operator-(const GF &ingf) const;
void operator*=(const GF &ingf);
GF operator*(const GF &ingf) const;
void operator/=(const GF &ingf);
GF operator/(const GF &ingf) const;
ITPP_EXPORT friend std::ostream &operator<<(std::ostream &os, const GF &ingf);
ITPP_EXPORT friend std::istream &operator>>(std::istream &is, GF &ingf);
protected:
private:
char m;
int value;
static Array<Array<int> > alphapow;
static Array<Array<int> > logalpha;
static ivec q;
};
#if (defined(_MSC_VER) && defined (ITPP_SHARED_LIB))
//MSVC explicitely instantiate required template while building the shared library
template class ITPP_EXPORT Array<GF>;
#endif
class GFX;
ITPP_EXPORT GFX operator*(const GF &ingf, const GFX &ingfx);
ITPP_EXPORT GFX operator*(const GFX &ingfx, const GF &ingf);
ITPP_EXPORT GFX operator/(const GFX &ingfx, const GF &ingf);
ITPP_EXPORT std::ostream &operator<<(std::ostream &os, const GFX &ingfx);
class ITPP_EXPORT GFX
{
public:
GFX();
GFX(int qvalue);
GFX(int qvalue, int indegree);
GFX(int qvalue, const ivec &invalues);
GFX(int qvalue, char *invalues);
GFX(int qvalue, std::string invalues);
GFX(const GFX &ingfx);
int get_size() const;
int get_degree() const;
void set_degree(int indegree, bool copy = false);
int get_true_degree() const;
void set(int qvalue, const char *invalues);
void set(int qvalue, const std::string invalues);
void set(int qvalue, const ivec &invalues);
void clear();
GF operator[](int index) const {
it_assert_debug(index<=degree, "GFX::op[], out of range");
return coeffs(index);
}
GF &operator[](int index) {
it_assert_debug(index<=degree, "GFX::op[], out of range");
return coeffs(index);
}
void operator=(const GFX &ingfx);
void operator+=(const GFX &ingfx);
GFX operator+(const GFX &ingfx) const;
void operator-=(const GFX &ingfx);
GFX operator-(const GFX &ingfx) const;
void operator*=(const GFX &ingfx);
GFX operator*(const GFX &ingfx) const;
GF operator()(const GF &ingf);
ITPP_EXPORT friend GFX operator*(const GF &ingf, const GFX &ingfx);
ITPP_EXPORT friend GFX operator*(const GFX &ingfx, const GF &ingf);
ITPP_EXPORT friend GFX operator/(const GFX &ingfx, const GF &ingf);
ITPP_EXPORT friend std::ostream &operator<<(std::ostream &os, const GFX &ingfx);
protected:
private:
int degree, q;
Array<GF> coeffs;
};
//-------------- Help Functions ------------------
ITPP_EXPORT GFX divgfx(const GFX &c, const GFX &g);
ITPP_EXPORT GFX modgfx(const GFX &a, const GFX &b);
// --------------- Inlines ------------------------
// --------------- class GF -----------------------
inline void GF::set(int qvalue, const bvec &vectorspace)
{
set_size(qvalue);
it_assert_debug(vectorspace.length() == m, "GF::set, out of range");
value = logalpha(m)(bin2dec(vectorspace));
}
inline bvec GF::get_vectorspace() const
{
bvec temp(m);
if (value == -1)
temp = dec2bin(m, 0);
else
temp = dec2bin(m, alphapow(m)(value));
return temp;
}
inline int GF::get_value() const
{
return value;
}
inline int GF::operator==(const GF &ingf) const
{
if (value == -1 && ingf.value == -1)
return true;
if (m == ingf.m && value == ingf.value)
return true;
else
return false;
}
inline int GF::operator!=(const GF &ingf) const
{
GF tmp(*this);
return !(tmp == ingf);
}
inline void GF::operator=(const GF &ingf)
{
m = ingf.m;
value = ingf.value;
}
inline void GF::operator=(const int inexp)
{
it_assert_debug(m > 0 && inexp >= -1 && inexp < (q[m] - 1), "GF::op=, out of range");
value = inexp;
}
inline void GF::operator+=(const GF &ingf)
{
if (value == -1) {
value = ingf.value;
m = ingf.m;
}
else if (ingf.value != -1) {
it_assert_debug(ingf.m == m, "GF::op+=, not same field");
value = logalpha(m)(alphapow(m)(value) ^ alphapow(m)(ingf.value));
}
}
inline GF GF::operator+(const GF &ingf) const
{
GF tmp(*this);
tmp += ingf;
return tmp;
}
inline void GF::operator-=(const GF &ingf)
{
(*this) += ingf;
}
inline GF GF::operator-(const GF &ingf) const
{
GF tmp(*this);
tmp -= ingf;
return tmp;
}
inline void GF::operator*=(const GF &ingf)
{
if (value == -1 || ingf.value == -1)
value = -1;
else {
it_assert_debug(ingf.m == m, "GF::op+=, not same field");
value = (value + ingf.value) % (q[m] - 1);
}
}
inline GF GF::operator*(const GF &ingf) const
{
GF tmp(*this);
tmp *= ingf;
return tmp;
}
inline void GF::operator/=(const GF &ingf)
{
it_assert(ingf.value != -1, "GF::operator/: division by zero element"); // no division by the zeroth element
if (value == -1)
value = -1;
else {
it_assert_debug(ingf.m == m, "GF::op+=, not same field");
value = (value - ingf.value + q[m] - 1) % (q[m] - 1);
}
}
inline GF GF::operator/(const GF &ingf) const
{
GF tmp(*this);
tmp /= ingf;
return tmp;
}
// ------------------ class GFX --------------------
inline GFX::GFX()
{
degree = -1;
q = 0;
}
inline GFX::GFX(int qvalue)
{
it_assert_debug(qvalue >= 0, "GFX::GFX, out of range");
q = qvalue;
}
inline void GFX::set(int qvalue, const ivec &invalues)
{
it_assert_debug(qvalue > 0, "GFX::set, out of range");
degree = invalues.size() - 1;
coeffs.set_size(degree + 1, false);
for (int i = 0;i < degree + 1;i++)
coeffs(i).set(qvalue, invalues(i));
q = qvalue;
}
inline void GFX::set(int qvalue, const char *invalues)
{
set(qvalue, ivec(invalues));
}
inline void GFX::set(int qvalue, const std::string invalues)
{
set(qvalue, invalues.c_str());
}
inline GFX::GFX(int qvalue, int indegree)
{
it_assert_debug(qvalue > 0 && indegree >= 0, "GFX::GFX, out of range");
q = qvalue;
coeffs.set_size(indegree + 1, false);
degree = indegree;
for (int i = 0;i < degree + 1;i++)
coeffs(i).set(q, -1);
}
inline GFX::GFX(int qvalue, const ivec &invalues)
{
set(qvalue, invalues);
}
inline GFX::GFX(int qvalue, char *invalues)
{
set(qvalue, invalues);
}
inline GFX::GFX(int qvalue, std::string invalues)
{
set(qvalue, invalues.c_str());
}
inline GFX::GFX(const GFX &ingfx)
{
degree = ingfx.degree;
coeffs = ingfx.coeffs;
q = ingfx.q;
}
inline int GFX::get_size() const
{
return q;
}
inline int GFX::get_degree() const
{
return degree;
}
inline void GFX::set_degree(int indegree, bool copy)
{
it_assert_debug(indegree >= -1, "GFX::set_degree, out of range");
coeffs.set_size(indegree + 1, copy);
degree = indegree;
}
inline int GFX::get_true_degree() const
{
int i = degree;
while (coeffs(i).get_value() == -1) {
i--;
if (i == -1)
break;
}
return i;
}
inline void GFX::clear()
{
it_assert_debug(degree >= 0 && q > 0, "GFX::clear, not set");
for (int i = 0;i < degree + 1;i++)
coeffs(i).set(q, -1);
}
inline void GFX::operator=(const GFX &ingfx)
{
degree = ingfx.degree;
coeffs = ingfx.coeffs;
q = ingfx.q;
}
inline void GFX::operator+=(const GFX &ingfx)
{
it_assert_debug(q == ingfx.q, "GFX::op+=, not same field");
if (ingfx.degree > degree) {
coeffs.set_size(ingfx.degree + 1, true);
// set new coefficients to the zeroth element
for (int j = degree + 1; j < coeffs.size(); j++) { coeffs(j).set(q, -1); }
degree = ingfx.degree;
}
for (int i = 0;i < ingfx.degree + 1;i++) { coeffs(i) += ingfx.coeffs(i); }
}
inline GFX GFX::operator+(const GFX &ingfx) const
{
GFX tmp(*this);
tmp += ingfx;
return tmp;
}
inline void GFX::operator-=(const GFX &ingfx)
{
(*this) += ingfx;
}
inline GFX GFX::operator-(const GFX &ingfx) const
{
GFX tmp(*this);
tmp -= ingfx;
return tmp;
}
inline void GFX::operator*=(const GFX &ingfx)
{
it_assert_debug(q == ingfx.q, "GFX::op*=, Not same field");
int i, j;
Array<GF> tempcoeffs = coeffs;
coeffs.set_size(degree + ingfx.degree + 1, false);
for (j = 0; j < coeffs.size(); j++)
coeffs(j).set(q, -1); // set coefficients to the zeroth element (log(0)=-Inf=-1)
for (i = 0;i < degree + 1;i++)
for (j = 0;j < ingfx.degree + 1;j++)
coeffs(i + j) += tempcoeffs(i) * ingfx.coeffs(j);
degree = coeffs.size() - 1;
}
inline GFX GFX::operator*(const GFX &ingfx) const
{
GFX tmp(*this);
tmp *= ingfx;
return tmp;
}
inline GFX operator*(const GF &ingf, const GFX &ingfx)
{
it_assert_debug(ingf.get_size() == ingfx.q, "GFX::op*, Not same field");
GFX temp(ingfx);
for (int i = 0;i < ingfx.degree + 1;i++)
temp.coeffs(i) *= ingf;
return temp;
}
inline GFX operator*(const GFX &ingfx, const GF &ingf)
{
return ingf*ingfx;
}
inline GFX operator/(const GFX &ingfx, const GF &ingf)
{
it_assert_debug(ingf.get_size() == ingfx.q, "GFX::op/, Not same field");
GFX temp(ingfx);
for (int i = 0;i < ingfx.degree + 1;i++)
temp.coeffs(i) /= ingf;
return temp;
}
inline GF GFX::operator()(const GF &ingf)
{
it_assert_debug(q == ingf.get_size(), "GFX::op(), Not same field");
GF temp(coeffs(0)), ingfpower(ingf);
for (int i = 1; i < degree + 1; i++) {
temp += coeffs(i) * ingfpower;
ingfpower *= ingf;
}
return temp;
}
} // namespace itpp
#endif // #ifndef GALOIS_H
itpp::GF::operator-
GF operator-(const GF &ingf) const
Difference of two GF(q), same as sum for q=2^m.
Definition: galois.h:343
itpp::operator/
Mat< Num_T > operator/(const Mat< Num_T > &m, Num_T t)
Element-wise division by a scalar.
Definition: mat.h:1670
itpp::GF::operator+=
void operator+=(const GF &ingf)
sum of two GF(q)
Definition: galois.h:319
itpp::Array
General array class.
Definition: array.h:42
itpp::GF::set_size
void set_size(int qvalue)
set q=2^mvalue
Definition: galois.cpp:44
itpp::GF::operator=
void operator=(const GF &ingf)
GF(q) equals ingf.
Definition: galois.h:307
itpp::GF::operator/
GF operator/(const GF &ingf) const
product of two GF(q)
Definition: galois.h:378
itpp::GFX::clear
void clear()
Set all coefficients to zero.
Definition: galois.h:477
itpp::GFX::operator=
void operator=(const GFX &ingfx)
Copy.
Definition: galois.h:484
itpp::GF::GF
GF()
Constructor.
Definition: galois.h:78
itpp::GFX::operator+=
void operator+=(const GFX &ingfx)
sum of two GF(q)[x]
Definition: galois.h:491
binary.h
Binary class definition.
itpp::operator<<
std::ostream & operator<<(std::ostream &output, const bin &inbin)
Output stream of bin.
Definition: binary.cpp:36
itpp::GF::GF
GF(int qvalue)
Constructor.
Definition: galois.h:80
itpp::GFX::get_degree
int get_degree() const
Return degree of GF(q)[x].
Definition: galois.h:454
it_assert
#define it_assert(t, s)
Abort if t is not true.
Definition: itassert.h:94
it_assert_debug
#define it_assert_debug(t, s)
Abort if t is not true and NDEBUG is not defined.
Definition: itassert.h:107
array.h
Definition of Array class (container)
converters.h
Definitions of converters between different vector and matrix types.
itpp::GF::operator+
GF operator+(const GF &ingf) const
sum of two GF(q)
Definition: galois.h:331
itpp::operator-
Mat< Num_T > operator-(const Mat< Num_T > &m1, const Mat< Num_T > &m2)
Subtraction of two matrices.
Definition: mat.h:1382
itpp::GF::operator*=
void operator*=(const GF &ingf)
product of two GF(q)
Definition: galois.h:350
base_exports.h
Import/Export definitions for some templates defined in base folder.
itpp::GFX::operator-=
void operator-=(const GFX &ingfx)
Difference of two GF(q), same as sum for q=2^m.
Definition: galois.h:510
itpp::operator+
GF2mat operator+(const GF2mat &X, const GF2mat &Y)
GF(2) matrix addition.
Definition: gf2mat.cpp:948
itpp::GF::operator-=
void operator-=(const GF &ingf)
Difference of two GF(q), same as sum for q=2^m.
Definition: galois.h:338
itpp::GF::operator*
GF operator*(const GF &ingf) const
product of two GF(q)
Definition: galois.h:360
itpp::GF::get_size
int get_size() const
Return q.
Definition: galois.h:106
itpp::GFX::GFX
GFX()
Constructor.
Definition: galois.h:386
itpp::GFX::operator-
GFX operator-(const GFX &ingfx) const
Difference of two GF(q), same as sum for q=2^m.
Definition: galois.h:515
itpp::operator*
GF2mat operator*(const GF2mat &X, const GF2mat &Y)
GF(2) matrix multiplication.
Definition: gf2mat.cpp:847
itpp::GF::set
void set(int qvalue, int inexp)
GF(q) equals alpha ^ inexp.
Definition: galois.h:92
itpp::dec2bin
ITPP_EXPORT bvec dec2bin(int length, int index)
Convert a decimal int index to bvec using length bits in the representation.
itpp::GFX::operator[]
GF & operator[](int index)
Acces to individual element in the GF(q)[x] polynomial.
Definition: galois.h:216
itpp::GFX::get_true_degree
int get_true_degree() const
Return true degree of GF(q)[x].
Definition: galois.h:466
itpp::GF::GF
GF(int qvalue, int inexp)
Constructor.
Definition: galois.h:87
itpp::GF
Galois Field GF(q).
Definition: galois.h:74
itpp::modgfx
GFX modgfx(const GFX &a, const GFX &b)
Modulo function of two GFX (local help function)
Definition: galois.cpp:183
itpp::GF::GF
GF(const GF &ingf)
Copy constructor.
Definition: galois.h:89
itpp::GFX::operator+
GFX operator+(const GFX &ingfx) const
sum of two GF(q)[x]
Definition: galois.h:503
itpp::GFX
Polynomials over GF(q)[x], where q=2^m, m=1,...,16.
Definition: galois.h:175
itpp::divgfx
GFX divgfx(const GFX &c, const GFX &g)
Division of two GFX (local help function)
Definition: galois.cpp:157
itpp::GFX::get_size
int get_size() const
Return q.
Definition: galois.h:449
itpp::GFX::operator[]
GF operator[](int index) const
Acces to individual element in the GF(q)[x] polynomial.
Definition: galois.h:211
itpp::GFX::operator()
GF operator()(const GF &ingf)
Evaluate polynom at alpha^inexp.
Definition: galois.h:566
itpp::GF::operator==
int operator==(const GF &ingf) const
Equality check.
Definition: galois.h:291
itpp::operator>>
std::istream & operator>>(std::istream &input, bin &outbin)
Input stream of bin.
Definition: binary.cpp:42
itpp::GF::operator/=
void operator/=(const GF &ingf)
division of two GF(q)
Definition: galois.h:367
itpp::GFX::set_degree
void set_degree(int indegree, bool copy=false)
Resize the polynomial to the given indegree. If copy is set to true, the old polynomial's coefficient...
Definition: galois.h:459
itpp::bin2dec
ITPP_EXPORT int bin2dec(const bvec &inbvec, bool msb_first=true)
Convert a bvec to decimal int with the first bit as MSB if msb_first == true.
itpp::GFX::set
void set(int qvalue, const char *invalues)
Set the GF(q)[x] polynomial.
Definition: galois.h:408
itpp::GFX::operator*
GFX operator*(const GFX &ingfx) const
product of two GF(q)[x]
Definition: galois.h:536
itpp::GF::get_value
int get_value() const
Returns the alpha exponent.
Definition: galois.h:286
itpp::GF::operator!=
int operator!=(const GF &ingf) const
Not-equality check.
Definition: galois.h:301
itpp::GF::get_vectorspace
bvec get_vectorspace() const
Returns the vector space representation of GF(q).
Definition: galois.h:276
vec.h
Templated Vector Class Definitions.
itpp::GFX::operator*=
void operator*=(const GFX &ingfx)
product of two GF(q)[x]
Definition: galois.h:522

Generated on Thu Mar 20 2014 12:26:42 for IT++ by Doxygen 1.8.6