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