1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
|
#include <cassert>
#include "gf28.h"
using namespace std;
int GF28::reduce(int v,int m){
assert(m);
while(true){
int sh=__builtin_clz(m)-__builtin_clz(v);
if(sh<0)break;
v^=m<<sh;
if(v==0)break;
}
return v;
}
uint8_t GF28::multiply(uint8_t x,uint8_t y){
if(x==0||y==0)return 0;
int res=0;
int addend=x;
while(y){
if(y&1)res^=addend;
addend<<=1;
if(addend&0x100)addend^=modulus;
y>>=1;
}
return res;
}
GF28::GF28()
:value(0){}
GF28::GF28(int v)
:value(reduce(v,modulus)){}
GF28::operator uint8_t() const {
return value;
}
GF28& GF28::operator+=(GF28 o){
value^=o.value;
return *this;
}
GF28& GF28::operator-=(GF28 o){
value^=o.value;
return *this;
}
GF28& GF28::operator<<=(int n){ //multiplication by x^n
assert(n>=0);
value<<=n;
if(value&0x100)value^=modulus;
return *this;
}
GF28 GF28::operator+(GF28 o) const {
return GF28(value^o.value);
}
GF28 GF28::operator-(GF28 o) const {
return GF28(value^o.value);
}
GF28 GF28::operator*(GF28 o) const {
if(value==0||o.value==0)return GF28(0);
GF28 res;
GF28 addend(*this);
while(o.value){
if(o.value&1)res+=addend;
addend<<=1;
o.value>>=1;
}
return res;
}
GF28 GF28::operator<<(int n) const {
return GF28(*this)<<=n;
}
bool GF28::operator==(GF28 o) const {
return value==o.value;
}
GF28 GF28::inverse() const {
if(value==0)return *this;
int x=1,y=0,x2=0,y2=1,r=modulus,r2=value;
while(r2!=0){
assert(r!=0);
int ex=__builtin_clz(r2)-__builtin_clz(r);
if(ex<0){
swap(x,x2);
swap(y,y2);
swap(r,r2);
} else {
int xn=x^(x2<<ex); x=x2; x2=xn;
int yn=y^(y2<<ex); y=y2; y2=yn;
int rn=r^(r2<<ex); r=r2; r2=rn;
}
}
assert(r==1);
return GF28(y);
}
ostream& operator<<(ostream &os,GF28 p){
if(os.flags()&ios_base::hex){
return os<<p.value;
}
if(p.value==0)return os<<'0';
bool first=true;
for(int m=1<<16,i=16;m!=0;m>>=1,i--){
if(p.value&m){
if(!first)os<<'+';
first=false;
if(i==0)os<<'1';
else os<<"x^"<<i;
}
}
return os;
}
|
