Hide keyboard shortcuts

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 

6 

7"""Main Galois Field Types and API. 

8 

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""" 

14 

15import typing as typ 

16import functools 

17 

18from . import gf_lut 

19from . import primes 

20from . import gf_util 

21 

22Num = typ.TypeVar('Num', 'GFP', 'GF256') 

23NumType = typ.Type[Num] 

24 

25 

26class GFNum(typ.Protocol[Num]): 

27 

28 val : int 

29 order: int 

30 

31 def __add__(self, other: Num) -> Num: 

32 ... 

33 

34 def __radd__(self, other: int) -> Num: 

35 ... 

36 

37 def __sub__(self, other: Num) -> Num: 

38 ... 

39 

40 def __rsub__(self, other: int) -> Num: 

41 ... 

42 

43 def __neg__(self) -> Num: 

44 ... 

45 

46 def __mul__(self, other: Num) -> Num: 

47 ... 

48 

49 def __rmul__(self, other: int) -> Num: 

50 ... 

51 

52 def __pow__(self, other: Num) -> Num: 

53 ... 

54 

55 def __truediv__(self, other: Num) -> Num: 

56 ... 

57 

58 def __hash__(self) -> int: 

59 # pylint: disable=invalid-hash-returned 

60 ... 

61 

62 def __eq__(self, other: object) -> bool: 

63 ... 

64 

65 def __lt__(self, other: object) -> bool: 

66 ... 

67 

68 def __repr__(self) -> str: 

69 # pylint: disable=invalid-repr-returned 

70 ... 

71 

72 

73@functools.total_ordering 

74class GFP(GFNum['GFP']): 

75 

76 val : int 

77 order: int 

78 

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) 

84 

85 self.val = val % p 

86 self.order = p 

87 

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) 

92 

93 def __add__(self, other: Num) -> 'GFP': 

94 return self._new_gf(self.val + other.val) 

95 

96 def __radd__(self, other: int) -> 'GFP': 

97 return self._new_gf(other) + self 

98 

99 def __sub__(self, other: Num) -> 'GFP': 

100 return self._new_gf(self.val - other.val) 

101 

102 def __rsub__(self, other: int) -> 'GFP': 

103 return self._new_gf(other) - self 

104 

105 def __neg__(self) -> 'GFP': 

106 return self._new_gf(-self.val) 

107 

108 def __mul__(self, other: Num) -> 'GFP': 

109 return self._new_gf(self.val * other.val) 

110 

111 def __rmul__(self, other: int) -> 'GFP': 

112 return self._new_gf(other) * self 

113 

114 def __pow__(self, other: Num) -> 'GFP': 

115 return self._new_gf(self.val ** other.val) 

116 

117 def __truediv__(self, other: 'GFP') -> 'GFP': 

118 return self * other._mul_inverse() 

119 

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) 

125 

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 

132 

133 if not isinstance(other, GFP): 

134 errmsg = f"Cannot compare {repr(self)} with {repr(other)}" 

135 raise NotImplementedError(errmsg) 

136 

137 if self.order != other.order: 

138 errmsg = "Can only compare Numbers from the same finite field" 

139 raise ValueError(errmsg) 

140 

141 def __hash__(self) -> int: 

142 return hash(self.val) ^ hash(self.order) 

143 

144 def __eq__(self, other: object) -> bool: 

145 if self is other: 

146 return True 

147 

148 if isinstance(other, GFP) and self.order == other.order: 

149 return self.val == other.val 

150 

151 self._check_comparable(other) 

152 assert isinstance(other, int) 

153 return self.val == other 

154 

155 def __lt__(self, other: object) -> bool: 

156 if self is other: 

157 return False 

158 

159 if isinstance(other, GFP) and self.order == other.order: 

160 return self.val < other.val 

161 

162 self._check_comparable(other) 

163 assert isinstance(other, int) 

164 return self.val < other 

165 

166 def __repr__(self) -> str: 

167 return f"GFP({self.val:>3}, p={self.order})" 

168 

169 

170@functools.total_ordering 

171class GF256(GFNum['GF256']): 

172 

173 val : int 

174 order: int = 256 

175 

176 def __init__(self, val: int, order: int = 256) -> None: 

177 assert order == 256 

178 self.val = val 

179 

180 def __add__(self, other: Num) -> 'GF256': 

181 val = self.val ^ other.val 

182 assert 0 <= val < 256 

183 return ALL_GF256[val] 

184 

185 def __sub__(self, other: Num) -> 'GF256': 

186 val = self.val ^ other.val 

187 assert 0 <= val < 256 

188 return ALL_GF256[val] 

189 

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 

195 

196 mul_lut = gf_lut.MUL_LUT 

197 

198 if not mul_lut: 

199 gf_lut.init_mul_lut() 

200 

201 val = mul_lut[a][b] 

202 return ALL_GF256[val] 

203 

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] 

208 

209 def __truediv__(self, other: Num) -> 'GF256': 

210 inv = gf_lut.MUL_INVERSE_LUT[other.val] 

211 return self * ALL_GF256[inv] 

212 

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) 

221 

222 def __hash__(self) -> int: 

223 return hash(self.val) 

224 

225 def __eq__(self, other: object) -> bool: 

226 if self is other: 

227 return True 

228 

229 if isinstance(other, GF256): 

230 return self.val == other.val 

231 

232 self._check_comparable(other) 

233 assert isinstance(other, int) 

234 return self.val == other 

235 

236 def __lt__(self, other: object) -> bool: 

237 if self is other: 

238 return False 

239 

240 if isinstance(other, GF256): 

241 return self.val < other.val 

242 

243 self._check_comparable(other) 

244 assert isinstance(other, int) 

245 return self.val < other 

246 

247 def __repr__(self) -> str: 

248 return f"GF256({self.val:>3})" 

249 

250 

251class FieldGFP: 

252 

253 order: int 

254 

255 def __init__(self, order: int) -> None: 

256 # order, aka. characteristic, aka. prime 

257 self.order = order 

258 

259 def __getitem__(self, val: int) -> GFP: 

260 return GFP(val, self.order) 

261 

262 

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)] 

266 

267 

268class FieldGF256: 

269 

270 order: int = 256 

271 

272 def __getitem__(self, val: int) -> GF256: 

273 assert 0 <= val < 256 

274 return ALL_GF256[val] 

275 

276 

277AnyField = typ.Union[FieldGFP, FieldGF256] 

278 

279 

280def init_field(order: int) -> AnyField: 

281 if order == 256: 

282 return FieldGF256() 

283 else: 

284 return FieldGFP(order)