#include <stdio.h>
#include <string.h>
class GaloisField {
public:
unsigned char v[32];
int n;
GaloisField() {
n = 8;
memset(v, 0, sizeof(v));
}
GaloisField(int val) {
n = 8;
memset(v, 0, sizeof(v));
for (int i = 0; i < 8; i++)
v[i] = (val>>i)&1;
}
GaloisField(const int a[], int an) {
memset(v, 0, sizeof(v));
n = 8;
for (int i = 0; i <= an; i++)
v[i] = a[i];
}
GaloisField operator+(const GaloisField &a) const {
GaloisField r;
for (int i = 0; i <= r.n; i++)
r.v[i] = v[i] xor a.v[i];
r.normal();
return r;
}
GaloisField operator-(const GaloisField &a) const {
return (*this) + a;
}
GaloisField operator*(const GaloisField &a) const {
GaloisField r;
for (int i = 0; i <= n; i++)
for (int j = 0; j <= a.n; j++)
r.v[i+j] = r.v[i+j] xor (v[i] and a.v[j]);
r.normal();
return r;
}
GaloisField shift(int sn) const {
GaloisField r;
for (int i = 0; i < n; i++)
r.v[i + sn] = v[i];
return r;
}
bool operator<(const GaloisField &a) const {
for (int i = 16; i >= 0; i--) {
if (v[i] == 1 && a.v[i] == 1)
return true;
if (v[i] == 1 && a.v[i] == 0)
return false;
if (v[i] == 0 && a.v[i] == 1)
return false;
}
return false;
}
GaloisField operator/(const GaloisField &a) const {
for (int i = 16; i >= 0; i--) {
if (a.v[i] == 1 && v[i] == 0)
return GaloisField();
if (a.v[i] == 0 && v[i] == 1)
break;
}
GaloisField r, b = (*this), c;
for (int i = n; i >= 0; i--) {
c = a.shift(i);
if (c < b) {
r.v[i] = 1;
for (int j = 16; j >= 0; j--)
b.v[j] = b.v[j] xor c.v[j];
}
}
r.normal();
return r;
}
GaloisField operator%(const GaloisField &a) const {
GaloisField ret = (*this) - (*this) / a * a;
return ret;
}
bool isZero() const {
for (int i = 16; i >= 0; i--)
if (v[i]) return 0;
return 1;
}
GaloisField inverse() {
const int m[] = {1, 1, 0, 1, 1, 0, 0, 0, 1}, mn = 8;
GaloisField y(m, mn);
GaloisField g, a, b;
exgcd((*this), y, g, a, b);
return a;
}
void exgcd(GaloisField x, GaloisField y, GaloisField &g, GaloisField &a, GaloisField &b) {
if (y.isZero()) {
g = x, a = GaloisField(1), b = GaloisField(0);
} else {
exgcd(y, x%y, g, b, a), b = b - (x / y) * a;
}
}
void normal() {
const int m[] = {1, 1, 0, 1, 1, 0, 0, 0, 1}, mn = 8;
for (int i = 16; i - mn >= 0; i--) {
if (v[i] == 1) {
for (int j = mn, k = i; j >= 0; j--, k--)
v[k] = v[k] xor (m[j]);
}
}
}
void print() const {
for (int i = 7; i >= 0; i--) {
printf("%d", v[i]);
if (i%4 == 0) printf(" ");
}
puts("");
}
int getHbits() const {
return v[7]<<3 | v[6]<<2 | v[5]<<1 | v[4];
}
int getLbits() const {
return v[3]<<3 | v[2]<<2 | v[1]<<1 | v[0];
}
};
void testGF() {
int va[] = {1, 1, 1, 0, 1, 1, 0, 0};
int vb[] = {0, 1, 0, 0, 0, 0, 1, 0};
for (int i = 0; i < 256; i++) {
GaloisField a(i);
GaloisField b = a.inverse();
printf("%X%X ", b.getHbits(), b.getLbits());
if (i%16 == 15) puts("");
}
}
class GF_Polynominal {
public:
GaloisField v[32];
int n;
GF_Polynominal() {
n = 4;
for (int i = 0; i < 16; i++)
v[i] = GaloisField();
}
GF_Polynominal(const GaloisField a[], int an) {
n = 4;
for (int i = 0; i <= an; i++)
v[i] = a[i];
}
GF_Polynominal operator+(const GF_Polynominal &a) const {
GF_Polynominal r;
for (int i = 0; i <= r.n; i++)
r.v[i] = v[i] + a.v[i];
r.normal();
return r;
}
GF_Polynominal operator-(const GF_Polynominal &a) const {
return (*this) + a;
}
GF_Polynominal operator*(const GF_Polynominal &a) const {
GF_Polynominal r;
for (int i = 0; i <= n; i++)
for (int j = 0; j <= a.n; j++)
r.v[i+j] = r.v[i+j] + (v[i] * a.v[j]);
r.normal();
return r;
}
GF_Polynominal shift(int sn) const {
GF_Polynominal r;
for (int i = 0; i < n; i++)
r.v[i + sn] = v[i];
return r;
}
bool operator<(const GF_Polynominal &a) const {
for (int i = 8; i >= 0; i--) {
if (!v[i].isZero() && !a.v[i].isZero())
return true;
if (v[i].isZero() != a.v[i].isZero())
return false;
}
return false;
}
GF_Polynominal operator/(const GF_Polynominal &a) const {
for (int i = 8; i >= 0; i--) {
if (!a.v[i].isZero() && v[i].isZero())
return GF_Polynominal();
if (a.v[i].isZero() && !v[i].isZero())
break;
}
GF_Polynominal r, b = (*this), c;
for (int i = n; i >= 0; i--) {
c = a.shift(i);
if (c < b) {
GaloisField t, x, y;
for (int j = 16; j >= 0; j--) {
if (!c.v[j].isZero()) {
y = c.v[j], x = b.v[j];
break;
}
}
t = y.inverse() * x;
r.v[i] = t;
for (int j = 8; j >= 0; j--)
b.v[j] = b.v[j] - c.v[j] * t;
}
}
r.normal();
return r;
}
GF_Polynominal operator%(const GF_Polynominal &a) const {
GF_Polynominal ret = (*this) - (*this) / a * a;
return ret;
}
bool isZero() {
for (int i = 8; i >= 0; i--)
if (!v[i].isZero()) return 0;
return 1;
}
GF_Polynominal inverse() {
const GaloisField m[] = {GaloisField(1), GaloisField(0), GaloisField(0), GaloisField(0), GaloisField(1)};
const int mn = 4;
GF_Polynominal y(m, mn);
GF_Polynominal g, a, b;
exgcd((*this), y, g, a, b);
return a / g;
}
void exgcd(GF_Polynominal x, GF_Polynominal y, GF_Polynominal &g, GF_Polynominal &a, GF_Polynominal &b) {
if (y.isZero()) {
const GaloisField m1[] = {GaloisField(1)};
const GaloisField m0[] = {GaloisField(0)};
g = x, a = GF_Polynominal(m1, 1), b = GF_Polynominal(m0, 1);
} else {
exgcd(y, x%y, g, b, a), b = b - (x / y) * a;
}
}
void normal() {
const GaloisField m[] = {GaloisField(1), GaloisField(0), GaloisField(0), GaloisField(0), GaloisField(1)};
const int mn = 4;
for (int i = 16; i - mn >= 0; i--) {
if (!v[i].isZero()) {
GaloisField t = v[i];
for (int j = mn, k = i; j >= 0; j--, k--)
v[k] = v[k] - (m[j] * t);
}
}
}
void print() const {
for (int i = 3; i >= 0; i--) {
printf("%X%X ", v[i].getHbits(), v[i].getLbits());
printf("x^%d", i);
if (i) printf(" + ");
}
puts("");
}
};
void testPoly() {
const GaloisField m[] = {GaloisField(2), GaloisField(1), GaloisField(1), GaloisField(3)};
const GaloisField m2[] = {GaloisField(14), GaloisField(9), GaloisField(13), GaloisField(11)};
const int mn = 3, mn2 = 3;
GF_Polynominal a(m, mn), b(m2, mn2);
a.print();
b.print();
GF_Polynominal c = a * b;
c.print();
GF_Polynominal d = a.inverse();
d.print();
}
int main() {
testGF();
testPoly();
return 0;
}
