IT++ Logo
galois.h
Go to the documentation of this file.
1
29#ifndef GALOIS_H
30#define GALOIS_H
31
32#include <itpp/base/vec.h>
33#include <itpp/base/array.h>
34#include <itpp/base/binary.h>
36#include <itpp/itexports.h>
38
39namespace itpp
40{
41
74class ITPP_EXPORT GF
75{
76public:
78 GF() { m = 0; }
80 GF(int qvalue) {
81 m = 0;
82 if (qvalue == 0) // qvalue==0 gives the zeroth element
83 value = -1;
84 else set_size(qvalue);
85 }
87 GF(int qvalue, int inexp) { m = 0; set(qvalue, inexp); }
89 GF(const GF &ingf) { m = ingf.m; value = ingf.value; }
90
92 void set(int qvalue, int inexp) {
93 set_size(qvalue);
94 it_assert_debug(inexp >= -1 && inexp < qvalue - 1, "GF::set, out of range");
95 value = inexp;
96 }
102 void set(int qvalue, const bvec &vectorspace);
104 void set_size(int qvalue);
106 int get_size() const { return ((m != 0) ? q[m] : 0); }
112 bvec get_vectorspace() const;
114 int get_value() const;
116 int operator==(const GF &ingf) const;
118 int operator!=(const GF &ingf) const;
119
121 void operator=(const GF &ingf);
123 void operator=(const int inexp);
125 void operator+=(const GF &ingf);
127 GF operator+(const GF &ingf) const;
129 void operator-=(const GF &ingf);
131 GF operator-(const GF &ingf) const;
133 void operator*=(const GF &ingf);
135 GF operator*(const GF &ingf) const;
137 void operator/=(const GF &ingf);
139 GF operator/(const GF &ingf) const;
141 ITPP_EXPORT friend std::ostream &operator<<(std::ostream &os, const GF &ingf);
143 ITPP_EXPORT friend std::istream &operator>>(std::istream &is, GF &ingf);
144protected:
145private:
146 char m;
147 int value;
148 static Array<Array<int> > alphapow;
149 static Array<Array<int> > logalpha;
150 static ivec q;
151};
152
154
155#if (defined(_MSC_VER) && defined (ITPP_SHARED_LIB))
156//MSVC explicitely instantiate required template while building the shared library
157template class ITPP_EXPORT Array<GF>;
158#endif
159
161
162class GFX;
163
165ITPP_EXPORT GFX operator*(const GF &ingf, const GFX &ingfx);
167ITPP_EXPORT GFX operator*(const GFX &ingfx, const GF &ingf);
169ITPP_EXPORT GFX operator/(const GFX &ingfx, const GF &ingf);
171ITPP_EXPORT std::ostream &operator<<(std::ostream &os, const GFX &ingfx);
175class ITPP_EXPORT GFX
176{
177public:
179 GFX();
181 GFX(int qvalue);
183 GFX(int qvalue, int indegree);
185 GFX(int qvalue, const ivec &invalues);
187 GFX(int qvalue, char *invalues);
189 GFX(int qvalue, std::string invalues);
191 GFX(const GFX &ingfx);
193 int get_size() const;
195 int get_degree() const;
199 void set_degree(int indegree, bool copy = false);
201 int get_true_degree() const;
203 void set(int qvalue, const char *invalues);
205 void set(int qvalue, const std::string invalues);
207 void set(int qvalue, const ivec &invalues);
209 void clear();
211 GF operator[](int index) const {
212 it_assert_debug(index<=degree, "GFX::op[], out of range");
213 return coeffs(index);
214 }
216 GF &operator[](int index) {
217 it_assert_debug(index<=degree, "GFX::op[], out of range");
218 return coeffs(index);
219 }
221 void operator=(const GFX &ingfx);
223 void operator+=(const GFX &ingfx);
225 GFX operator+(const GFX &ingfx) const;
227 void operator-=(const GFX &ingfx);
229 GFX operator-(const GFX &ingfx) const;
231 void operator*=(const GFX &ingfx);
233 GFX operator*(const GFX &ingfx) const;
235 GF operator()(const GF &ingf);
237 ITPP_EXPORT friend GFX operator*(const GF &ingf, const GFX &ingfx);
239 ITPP_EXPORT friend GFX operator*(const GFX &ingfx, const GF &ingf);
241 ITPP_EXPORT friend GFX operator/(const GFX &ingfx, const GF &ingf);
243 ITPP_EXPORT friend std::ostream &operator<<(std::ostream &os, const GFX &ingfx);
244protected:
245private:
246 int degree, q;
247 Array<GF> coeffs;
248};
249
250//-------------- Help Functions ------------------
257ITPP_EXPORT GFX divgfx(const GFX &c, const GFX &g);
258
263ITPP_EXPORT GFX modgfx(const GFX &a, const GFX &b);
264
265
266// --------------- Inlines ------------------------
267// --------------- class GF -----------------------
268
269inline void GF::set(int qvalue, const bvec &vectorspace)
270{
271 set_size(qvalue);
272 it_assert_debug(vectorspace.length() == m, "GF::set, out of range");
273 value = logalpha(m)(bin2dec(vectorspace));
274}
275
276inline bvec GF::get_vectorspace() const
277{
278 bvec temp(m);
279 if (value == -1)
280 temp = dec2bin(m, 0);
281 else
282 temp = dec2bin(m, alphapow(m)(value));
283 return temp;
284}
285
286inline int GF::get_value() const
287{
288 return value;
289}
290
291inline int GF::operator==(const GF &ingf) const
292{
293 if (value == -1 && ingf.value == -1)
294 return true;
295 if (m == ingf.m && value == ingf.value)
296 return true;
297 else
298 return false;
299}
300
301inline int GF::operator!=(const GF &ingf) const
302{
303 GF tmp(*this);
304 return !(tmp == ingf);
305}
306
307inline void GF::operator=(const GF &ingf)
308{
309 m = ingf.m;
310 value = ingf.value;
311}
312
313inline void GF::operator=(const int inexp)
314{
315 it_assert_debug(m > 0 && inexp >= -1 && inexp < (q[m] - 1), "GF::op=, out of range");
316 value = inexp;
317}
318
319inline void GF::operator+=(const GF &ingf)
320{
321 if (value == -1) {
322 value = ingf.value;
323 m = ingf.m;
324 }
325 else if (ingf.value != -1) {
326 it_assert_debug(ingf.m == m, "GF::op+=, not same field");
327 value = logalpha(m)(alphapow(m)(value) ^ alphapow(m)(ingf.value));
328 }
329}
330
331inline GF GF::operator+(const GF &ingf) const
332{
333 GF tmp(*this);
334 tmp += ingf;
335 return tmp;
336}
337
338inline void GF::operator-=(const GF &ingf)
339{
340 (*this) += ingf;
341}
342
343inline GF GF::operator-(const GF &ingf) const
344{
345 GF tmp(*this);
346 tmp -= ingf;
347 return tmp;
348}
349
350inline void GF::operator*=(const GF &ingf)
351{
352 if (value == -1 || ingf.value == -1)
353 value = -1;
354 else {
355 it_assert_debug(ingf.m == m, "GF::op+=, not same field");
356 value = (value + ingf.value) % (q[m] - 1);
357 }
358}
359
360inline GF GF::operator*(const GF &ingf) const
361{
362 GF tmp(*this);
363 tmp *= ingf;
364 return tmp;
365}
366
367inline void GF::operator/=(const GF &ingf)
368{
369 it_assert(ingf.value != -1, "GF::operator/: division by zero element"); // no division by the zeroth element
370 if (value == -1)
371 value = -1;
372 else {
373 it_assert_debug(ingf.m == m, "GF::op+=, not same field");
374 value = (value - ingf.value + q[m] - 1) % (q[m] - 1);
375 }
376}
377
378inline GF GF::operator/(const GF &ingf) const
379{
380 GF tmp(*this);
381 tmp /= ingf;
382 return tmp;
383}
384
385// ------------------ class GFX --------------------
386inline GFX::GFX()
387{
388 degree = -1;
389 q = 0;
390}
391
392inline GFX::GFX(int qvalue)
393{
394 it_assert_debug(qvalue >= 0, "GFX::GFX, out of range");
395 q = qvalue;
396}
397
398inline void GFX::set(int qvalue, const ivec &invalues)
399{
400 it_assert_debug(qvalue > 0, "GFX::set, out of range");
401 degree = invalues.size() - 1;
402 coeffs.set_size(degree + 1, false);
403 for (int i = 0;i < degree + 1;i++)
404 coeffs(i).set(qvalue, invalues(i));
405 q = qvalue;
406}
407
408inline void GFX::set(int qvalue, const char *invalues)
409{
410 set(qvalue, ivec(invalues));
411}
412
413inline void GFX::set(int qvalue, const std::string invalues)
414{
415 set(qvalue, invalues.c_str());
416}
417
418inline GFX::GFX(int qvalue, int indegree)
419{
420 it_assert_debug(qvalue > 0 && indegree >= 0, "GFX::GFX, out of range");
421 q = qvalue;
422 coeffs.set_size(indegree + 1, false);
423 degree = indegree;
424 for (int i = 0;i < degree + 1;i++)
425 coeffs(i).set(q, -1);
426}
427inline GFX::GFX(int qvalue, const ivec &invalues)
428{
429 set(qvalue, invalues);
430}
431
432inline GFX::GFX(int qvalue, char *invalues)
433{
434 set(qvalue, invalues);
435}
436
437inline GFX::GFX(int qvalue, std::string invalues)
438{
439 set(qvalue, invalues.c_str());
440}
441
442inline GFX::GFX(const GFX &ingfx)
443{
444 degree = ingfx.degree;
445 coeffs = ingfx.coeffs;
446 q = ingfx.q;
447}
448
449inline int GFX::get_size() const
450{
451 return q;
452}
453
454inline int GFX::get_degree() const
455{
456 return degree;
457}
458
459inline void GFX::set_degree(int indegree, bool copy)
460{
461 it_assert_debug(indegree >= -1, "GFX::set_degree, out of range");
462 coeffs.set_size(indegree + 1, copy);
463 degree = indegree;
464}
465
466inline int GFX::get_true_degree() const
467{
468 int i = degree;
469 while (coeffs(i).get_value() == -1) {
470 i--;
471 if (i == -1)
472 break;
473 }
474 return i;
475}
476
477inline void GFX::clear()
478{
479 it_assert_debug(degree >= 0 && q > 0, "GFX::clear, not set");
480 for (int i = 0;i < degree + 1;i++)
481 coeffs(i).set(q, -1);
482}
483
484inline void GFX::operator=(const GFX &ingfx)
485{
486 degree = ingfx.degree;
487 coeffs = ingfx.coeffs;
488 q = ingfx.q;
489}
490
491inline void GFX::operator+=(const GFX &ingfx)
492{
493 it_assert_debug(q == ingfx.q, "GFX::op+=, not same field");
494 if (ingfx.degree > degree) {
495 coeffs.set_size(ingfx.degree + 1, true);
496 // set new coefficients to the zeroth element
497 for (int j = degree + 1; j < coeffs.size(); j++) { coeffs(j).set(q, -1); }
498 degree = ingfx.degree;
499 }
500 for (int i = 0;i < ingfx.degree + 1;i++) { coeffs(i) += ingfx.coeffs(i); }
501}
502
503inline GFX GFX::operator+(const GFX &ingfx) const
504{
505 GFX tmp(*this);
506 tmp += ingfx;
507 return tmp;
508}
509
510inline void GFX::operator-=(const GFX &ingfx)
511{
512 (*this) += ingfx;
513}
514
515inline GFX GFX::operator-(const GFX &ingfx) const
516{
517 GFX tmp(*this);
518 tmp -= ingfx;
519 return tmp;
520}
521
522inline void GFX::operator*=(const GFX &ingfx)
523{
524 it_assert_debug(q == ingfx.q, "GFX::op*=, Not same field");
525 int i, j;
526 Array<GF> tempcoeffs = coeffs;
527 coeffs.set_size(degree + ingfx.degree + 1, false);
528 for (j = 0; j < coeffs.size(); j++)
529 coeffs(j).set(q, -1); // set coefficients to the zeroth element (log(0)=-Inf=-1)
530 for (i = 0;i < degree + 1;i++)
531 for (j = 0;j < ingfx.degree + 1;j++)
532 coeffs(i + j) += tempcoeffs(i) * ingfx.coeffs(j);
533 degree = coeffs.size() - 1;
534}
535
536inline GFX GFX::operator*(const GFX &ingfx) const
537{
538 GFX tmp(*this);
539 tmp *= ingfx;
540 return tmp;
541}
542
543inline GFX operator*(const GF &ingf, const GFX &ingfx)
544{
545 it_assert_debug(ingf.get_size() == ingfx.q, "GFX::op*, Not same field");
546 GFX temp(ingfx);
547 for (int i = 0;i < ingfx.degree + 1;i++)
548 temp.coeffs(i) *= ingf;
549 return temp;
550}
551
552inline GFX operator*(const GFX &ingfx, const GF &ingf)
553{
554 return ingf*ingfx;
555}
556
557inline GFX operator/(const GFX &ingfx, const GF &ingf)
558{
559 it_assert_debug(ingf.get_size() == ingfx.q, "GFX::op/, Not same field");
560 GFX temp(ingfx);
561 for (int i = 0;i < ingfx.degree + 1;i++)
562 temp.coeffs(i) /= ingf;
563 return temp;
564}
565
566inline GF GFX::operator()(const GF &ingf)
567{
568 it_assert_debug(q == ingf.get_size(), "GFX::op(), Not same field");
569 GF temp(coeffs(0)), ingfpower(ingf);
570 for (int i = 1; i < degree + 1; i++) {
571 temp += coeffs(i) * ingfpower;
572 ingfpower *= ingf;
573 }
574 return temp;
575}
576
577} // namespace itpp
578
579#endif // #ifndef GALOIS_H
Definition of Array class (container)
Import/Export definitions for some templates defined in base folder.
Binary class definition.
General array class.
Definition: array.h:105
Polynomials over GF(q)[x], where q=2^m, m=1,...,16.
Definition: galois.h:176
GFX operator+(const GFX &ingfx) const
sum of two GF(q)[x]
Definition: galois.h:503
GF & operator[](int index)
Acces to individual element in the GF(q)[x] polynomial.
Definition: galois.h:216
int get_true_degree() const
Return true degree of GF(q)[x].
Definition: galois.h:466
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
void operator+=(const GFX &ingfx)
sum of two GF(q)[x]
Definition: galois.h:491
void operator=(const GFX &ingfx)
Copy.
Definition: galois.h:484
GFX()
Constructor.
Definition: galois.h:386
void operator-=(const GFX &ingfx)
Difference of two GF(q), same as sum for q=2^m.
Definition: galois.h:510
int get_degree() const
Return degree of GF(q)[x].
Definition: galois.h:454
ITPP_EXPORT friend GFX operator*(const GF &ingf, const GFX &ingfx)
Multiply a GF element with a GF(q)[x].
Definition: galois.h:543
void set(int qvalue, const char *invalues)
Set the GF(q)[x] polynomial.
Definition: galois.h:408
GF operator[](int index) const
Acces to individual element in the GF(q)[x] polynomial.
Definition: galois.h:211
void operator*=(const GFX &ingfx)
product of two GF(q)[x]
Definition: galois.h:522
int get_size() const
Return q.
Definition: galois.h:449
GF operator()(const GF &ingf)
Evaluate polynom at alpha^inexp.
Definition: galois.h:566
void clear()
Set all coefficients to zero.
Definition: galois.h:477
GFX operator-(const GFX &ingfx) const
Difference of two GF(q), same as sum for q=2^m.
Definition: galois.h:515
Galois Field GF(q).
Definition: galois.h:75
GF(int qvalue, int inexp)
Constructor.
Definition: galois.h:87
GF()
Constructor.
Definition: galois.h:78
int operator==(const GF &ingf) const
Equality check.
Definition: galois.h:291
GF operator*(const GF &ingf) const
product of two GF(q)
Definition: galois.h:360
GF operator-(const GF &ingf) const
Difference of two GF(q), same as sum for q=2^m.
Definition: galois.h:343
void operator=(const GF &ingf)
GF(q) equals ingf.
Definition: galois.h:307
void operator-=(const GF &ingf)
Difference of two GF(q), same as sum for q=2^m.
Definition: galois.h:338
int get_value() const
Returns the alpha exponent.
Definition: galois.h:286
void set_size(int qvalue)
set q=2^mvalue
Definition: galois.cpp:44
void operator*=(const GF &ingf)
product of two GF(q)
Definition: galois.h:350
int get_size() const
Return q.
Definition: galois.h:106
void set(int qvalue, int inexp)
GF(q) equals alpha ^ inexp.
Definition: galois.h:92
bvec get_vectorspace() const
Returns the vector space representation of GF(q).
Definition: galois.h:276
GF operator+(const GF &ingf) const
sum of two GF(q)
Definition: galois.h:331
GF(int qvalue)
Constructor.
Definition: galois.h:80
int operator!=(const GF &ingf) const
Not-equality check.
Definition: galois.h:301
void operator/=(const GF &ingf)
division of two GF(q)
Definition: galois.h:367
GF(const GF &ingf)
Copy constructor.
Definition: galois.h:89
void operator+=(const GF &ingf)
sum of two GF(q)
Definition: galois.h:319
GF operator/(const GF &ingf) const
product of two GF(q)
Definition: galois.h:378
Definitions of converters between different vector and matrix types.
#define it_assert_debug(t, s)
Abort if t is not true and NDEBUG is not defined.
Definition: itassert.h:107
#define it_assert(t, s)
Abort if t is not true.
Definition: itassert.h:94
itpp namespace
Definition: itmex.h:37
std::ostream & operator<<(std::ostream &output, const bin &inbin)
Output stream of bin.
Definition: binary.cpp:36
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.
Mat< Num_T > operator-(const Mat< Num_T > &m1, const Mat< Num_T > &m2)
Subtraction of two matrices.
Definition: mat.h:1382
GF2mat operator*(const GF2mat &X, const GF2mat &Y)
GF(2) matrix multiplication.
Definition: gf2mat.cpp:847
ITPP_EXPORT bvec dec2bin(int length, int index)
Convert a decimal int index to bvec using length bits in the representation.
Mat< Num_T > operator/(const Mat< Num_T > &m, Num_T t)
Element-wise division by a scalar.
Definition: mat.h:1670
GFX divgfx(const GFX &c, const GFX &g)
Division of two GFX (local help function)
Definition: galois.cpp:157
std::istream & operator>>(std::istream &input, bin &outbin)
Input stream of bin.
Definition: binary.cpp:42
GF2mat operator+(const GF2mat &X, const GF2mat &Y)
GF(2) matrix addition.
Definition: gf2mat.cpp:948
GFX modgfx(const GFX &a, const GFX &b)
Modulo function of two GFX (local help function)
Definition: galois.cpp:183
Templated Vector Class Definitions.
SourceForge Logo

Generated on Tue Jan 24 2023 00:00:00 for IT++ by Doxygen 1.9.6