Hot-keys on this page
r m x p toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
1# This file is part of the sbk project
2# https://github.com/mbarkhau/sbk
3#
4# Copyright (c) 2019 Manuel Barkhau (mbarkhau@gmail.com) - MIT License
5# SPDX-License-Identifier: MIT
7"""Main Galois Field Types and API.
9As far as type checking goes, we only reference the
10concrete GF256 and FieldGF256 types, everything else
11is too tedious. The tests do use
12int and GFP though.
13"""
15import typing as typ
16import functools
18from . import gf_lut
19from . import primes
20from . import gf_util
22Num = typ.TypeVar('Num', 'GFP', 'GF256')
23NumType = typ.Type[Num]
26class GFNum(typ.Protocol[Num]):
28 val : int
29 order: int
31 def __add__(self, other: Num) -> Num:
32 ...
34 def __radd__(self, other: int) -> Num:
35 ...
37 def __sub__(self, other: Num) -> Num:
38 ...
40 def __rsub__(self, other: int) -> Num:
41 ...
43 def __neg__(self) -> Num:
44 ...
46 def __mul__(self, other: Num) -> Num:
47 ...
49 def __rmul__(self, other: int) -> Num:
50 ...
52 def __pow__(self, other: Num) -> Num:
53 ...
55 def __truediv__(self, other: Num) -> Num:
56 ...
58 def __hash__(self) -> int:
59 # pylint: disable=invalid-hash-returned
60 ...
62 def __eq__(self, other: object) -> bool:
63 ...
65 def __lt__(self, other: object) -> bool:
66 ...
68 def __repr__(self) -> str:
69 # pylint: disable=invalid-repr-returned
70 ...
73@functools.total_ordering
74class GFP(GFNum['GFP']):
76 val : int
77 order: int
79 def __init__(self, val: int, p: int) -> None:
80 # NOTE mb: In practice p is always prime, and the operations are
81 # implemented with this assumtion. If p were not prime, then a
82 # multiplicative inverse would not exist in all cases.
83 assert primes.is_prime(p)
85 self.val = val % p
86 self.order = p
88 def _new_gf(self, val: int) -> 'GFP':
89 # Mod p is done so often as a last operation on val,
90 # so we do it here as part of the initialisation.
91 return GFP(val % self.order, p=self.order)
93 def __add__(self, other: Num) -> 'GFP':
94 return self._new_gf(self.val + other.val)
96 def __radd__(self, other: int) -> 'GFP':
97 return self._new_gf(other) + self
99 def __sub__(self, other: Num) -> 'GFP':
100 return self._new_gf(self.val - other.val)
102 def __rsub__(self, other: int) -> 'GFP':
103 return self._new_gf(other) - self
105 def __neg__(self) -> 'GFP':
106 return self._new_gf(-self.val)
108 def __mul__(self, other: Num) -> 'GFP':
109 return self._new_gf(self.val * other.val)
111 def __rmul__(self, other: int) -> 'GFP':
112 return self._new_gf(other) * self
114 def __pow__(self, other: Num) -> 'GFP':
115 return self._new_gf(self.val ** other.val)
117 def __truediv__(self, other: 'GFP') -> 'GFP':
118 return self * other._mul_inverse()
120 def _mul_inverse(self) -> 'GFP':
121 assert self.val >= 0
122 res = gf_util.xgcd(self.order, self.val)
123 inv_val = self.order + res.t
124 return self._new_gf(inv_val)
126 def _check_comparable(self, other: object) -> None:
127 if isinstance(other, int):
128 if not (0 <= other < self.order):
129 errmsg = f"GF comparison with integer faild: 0 <= {other} < {self.order}"
130 raise ValueError(errmsg)
131 return
133 if not isinstance(other, GFP):
134 errmsg = f"Cannot compare {repr(self)} with {repr(other)}"
135 raise NotImplementedError(errmsg)
137 if self.order != other.order:
138 errmsg = "Can only compare Numbers from the same finite field"
139 raise ValueError(errmsg)
141 def __hash__(self) -> int:
142 return hash(self.val) ^ hash(self.order)
144 def __eq__(self, other: object) -> bool:
145 if self is other:
146 return True
148 if isinstance(other, GFP) and self.order == other.order:
149 return self.val == other.val
151 self._check_comparable(other)
152 assert isinstance(other, int)
153 return self.val == other
155 def __lt__(self, other: object) -> bool:
156 if self is other:
157 return False
159 if isinstance(other, GFP) and self.order == other.order:
160 return self.val < other.val
162 self._check_comparable(other)
163 assert isinstance(other, int)
164 return self.val < other
166 def __repr__(self) -> str:
167 return f"GFP({self.val:>3}, p={self.order})"
170@functools.total_ordering
171class GF256(GFNum['GF256']):
173 val : int
174 order: int = 256
176 def __init__(self, val: int, order: int = 256) -> None:
177 assert order == 256
178 self.val = val
180 def __add__(self, other: Num) -> 'GF256':
181 val = self.val ^ other.val
182 assert 0 <= val < 256
183 return ALL_GF256[val]
185 def __sub__(self, other: Num) -> 'GF256':
186 val = self.val ^ other.val
187 assert 0 <= val < 256
188 return ALL_GF256[val]
190 def __mul__(self, other: Num) -> 'GF256':
191 a = self.val
192 b = other.val
193 assert 0 <= a < 256, a
194 assert 0 <= b < 256, b
196 mul_lut = gf_lut.MUL_LUT
198 if not mul_lut:
199 gf_lut.init_mul_lut()
201 val = mul_lut[a][b]
202 return ALL_GF256[val]
204 def __pow__(self, other: Num) -> 'GF256':
205 val = gf_util.pow_slow(self.val, other.val)
206 assert 0 <= val < 256
207 return ALL_GF256[val]
209 def __truediv__(self, other: Num) -> 'GF256':
210 inv = gf_lut.MUL_INVERSE_LUT[other.val]
211 return self * ALL_GF256[inv]
213 def _check_comparable(self, other: object) -> None:
214 if isinstance(other, int):
215 if not (0 <= other < 256):
216 errmsg = f"GF comparison with integer faild: 0 <= {other} < 256"
217 raise ValueError(errmsg)
218 elif not isinstance(other, GF256):
219 errmsg = f"Cannot compare {repr(self)} with {repr(other)}"
220 raise NotImplementedError(errmsg)
222 def __hash__(self) -> int:
223 return hash(self.val)
225 def __eq__(self, other: object) -> bool:
226 if self is other:
227 return True
229 if isinstance(other, GF256):
230 return self.val == other.val
232 self._check_comparable(other)
233 assert isinstance(other, int)
234 return self.val == other
236 def __lt__(self, other: object) -> bool:
237 if self is other:
238 return False
240 if isinstance(other, GF256):
241 return self.val < other.val
243 self._check_comparable(other)
244 assert isinstance(other, int)
245 return self.val < other
247 def __repr__(self) -> str:
248 return f"GF256({self.val:>3})"
251class FieldGFP:
253 order: int
255 def __init__(self, order: int) -> None:
256 # order, aka. characteristic, aka. prime
257 self.order = order
259 def __getitem__(self, val: int) -> GFP:
260 return GFP(val, self.order)
263# Cache so we don't end up with millions of objects
264# that all represent the same set of integers.
265ALL_GF256 = [GF256(n) for n in range(256)]
268class FieldGF256:
270 order: int = 256
272 def __getitem__(self, val: int) -> GF256:
273 assert 0 <= val < 256
274 return ALL_GF256[val]
277AnyField = typ.Union[FieldGFP, FieldGF256]
280def init_field(order: int) -> AnyField:
281 if order == 256:
282 return FieldGF256()
283 else:
284 return FieldGFP(order)