ethereum.crypto.finite_field
Finite Fields ^^^^^^^^^^^^^
1""" 2Finite Fields 3^^^^^^^^^^^^^ 4""" 5 6# flake8: noqa: D102, D105 7 8from typing import Iterable, List, Tuple, Type, TypeVar, cast 9 10from typing_extensions import Protocol 11 12from ..base_types import Bytes, Bytes32 13 14F = TypeVar("F", bound="Field") 15 16 17class Field(Protocol): 18 """ 19 A type protocol for defining fields. 20 """ 21 22 __slots__ = () 23 24 @classmethod 25 def zero(cls: Type[F]) -> F: 26 ... 27 28 @classmethod 29 def from_int(cls: Type[F], n: int) -> F: 30 ... 31 32 def __radd__(self: F, left: F) -> F: 33 ... 34 35 def __add__(self: F, right: F) -> F: 36 ... 37 38 def __iadd__(self: F, right: F) -> F: 39 ... 40 41 def __sub__(self: F, right: F) -> F: 42 ... 43 44 def __rsub__(self: F, left: F) -> F: 45 ... 46 47 def __mul__(self: F, right: F) -> F: 48 ... 49 50 def __rmul__(self: F, left: F) -> F: 51 ... 52 53 def __imul__(self: F, right: F) -> F: 54 ... 55 56 def __pow__(self: F, exponent: int) -> F: 57 ... 58 59 def __ipow__(self: F, right: int) -> F: 60 ... 61 62 def __neg__(self: F) -> F: 63 ... 64 65 def __truediv__(self: F, right: F) -> F: 66 ... 67 68 69T = TypeVar("T", bound="PrimeField") 70 71 72class PrimeField(int, Field): 73 """ 74 Superclass for integers modulo a prime. Not intended to be used 75 directly, but rather to be subclassed. 76 """ 77 78 __slots__ = () 79 PRIME: int 80 81 @classmethod 82 def from_be_bytes(cls: Type[T], buffer: "Bytes") -> T: 83 """ 84 Converts a sequence of bytes into a element of the field. 85 Parameters 86 ---------- 87 buffer : 88 Bytes to decode. 89 Returns 90 ------- 91 self : `T` 92 Unsigned integer decoded from `buffer`. 93 """ 94 return cls(int.from_bytes(buffer, "big")) 95 96 @classmethod 97 def zero(cls: Type[T]) -> T: 98 return cls.__new__(cls, 0) 99 100 @classmethod 101 def from_int(cls: Type[T], n: int) -> T: 102 return cls(n) 103 104 def __new__(cls: Type[T], value: int) -> T: 105 return int.__new__(cls, value % cls.PRIME) 106 107 def __radd__(self: T, left: T) -> T: # type: ignore[override] 108 return self.__add__(left) 109 110 def __add__(self: T, right: T) -> T: # type: ignore[override] 111 if not isinstance(right, int): 112 return NotImplemented 113 114 return self.__new__(type(self), int.__add__(self, right)) 115 116 def __iadd__(self: T, right: T) -> T: # type: ignore[override] 117 return self.__add__(right) 118 119 def __sub__(self: T, right: T) -> T: # type: ignore[override] 120 if not isinstance(right, int): 121 return NotImplemented 122 123 return self.__new__(type(self), int.__sub__(self, right)) 124 125 def __rsub__(self: T, left: T) -> T: # type: ignore[override] 126 if not isinstance(left, int): 127 return NotImplemented 128 129 return self.__new__(type(self), int.__rsub__(self, left)) 130 131 def __mul__(self: T, right: T) -> T: # type: ignore[override] 132 if not isinstance(right, int): 133 return NotImplemented 134 135 return self.__new__(type(self), int.__mul__(self, right)) 136 137 def __rmul__(self: T, left: T) -> T: # type: ignore[override] 138 return self.__mul__(left) 139 140 def __imul__(self: T, right: T) -> T: # type: ignore[override] 141 return self.__mul__(right) 142 143 __floordiv__ = None # type: ignore 144 __rfloordiv__ = None # type: ignore 145 __ifloordiv__ = None 146 __divmod__ = None # type: ignore 147 __rdivmod__ = None # type: ignore 148 149 def __pow__(self: T, exponent: int) -> T: # type: ignore[override] 150 # For reasons that are unclear, self must be cast to int here under 151 # PyPy. 152 return self.__new__( 153 type(self), int.__pow__(int(self), exponent, self.PRIME) 154 ) 155 156 __rpow__ = None # type: ignore 157 158 def __ipow__(self: T, right: int) -> T: # type: ignore[override] 159 return self.__pow__(right) 160 161 __and__ = None # type: ignore 162 __or__ = None # type: ignore 163 __xor__ = None # type: ignore 164 __rxor__ = None # type: ignore 165 __ixor__ = None 166 __rshift__ = None # type: ignore 167 __lshift__ = None # type: ignore 168 __irshift__ = None 169 __ilshift__ = None 170 171 def __neg__(self: T) -> T: 172 return self.__new__(type(self), int.__neg__(self)) 173 174 def __truediv__(self: T, right: T) -> T: # type: ignore[override] 175 return self * right.multiplicative_inverse() 176 177 def multiplicative_inverse(self: T) -> T: 178 return self ** (-1) 179 180 def to_be_bytes32(self) -> "Bytes32": 181 """ 182 Converts this arbitrarily sized unsigned integer into its big endian 183 representation with exactly 32 bytes. 184 Returns 185 ------- 186 big_endian : `Bytes32` 187 Big endian (most significant bits first) representation. 188 """ 189 return Bytes32(self.to_bytes(32, "big")) 190 191 192U = TypeVar("U", bound="GaloisField") 193 194 195class GaloisField(tuple, Field): 196 """ 197 Superclass for defining finite fields. Not intended to be used 198 directly, but rather to be subclassed. 199 200 Fields are represented as `F_p[x]/(x^n + ...)` where the `MODULUS` is a 201 tuple of the non-leading coefficients of the defining polynomial. For 202 example `x^3 + 2x^2 + 3x + 4` is `(2, 3, 4)`. 203 204 In practice the polynomial is likely to be be sparse and you should overload 205 the `__mul__()` function to take advantage of this fact. 206 """ 207 208 __slots__ = () 209 210 PRIME: int 211 MODULUS: Tuple[int, ...] 212 FROBENIUS_COEFFICIENTS: Tuple["GaloisField", ...] 213 214 @classmethod 215 def zero(cls: Type[U]) -> U: 216 return cls.__new__(cls, [0] * len(cls.MODULUS)) 217 218 @classmethod 219 def from_int(cls: Type[U], n: int) -> U: 220 return cls.__new__(cls, [n] + [0] * (len(cls.MODULUS) - 1)) 221 222 def __new__(cls: Type[U], iterable: Iterable[int]) -> U: 223 self = tuple.__new__(cls, (x % cls.PRIME for x in iterable)) 224 assert len(self) == len(cls.MODULUS) 225 return self 226 227 def __add__(self: U, right: U) -> U: # type: ignore[override] 228 if not isinstance(right, type(self)): 229 return NotImplemented 230 231 return self.__new__( 232 type(self), 233 ( 234 x + y 235 for (x, y) in cast(Iterable[Tuple[int, int]], zip(self, right)) 236 ), 237 ) 238 239 def __radd__(self: U, left: U) -> U: 240 return self.__add__(left) 241 242 def __iadd__(self: U, right: U) -> U: # type: ignore[override] 243 return self.__add__(right) 244 245 def __sub__(self: U, right: U) -> U: 246 if not isinstance(right, type(self)): 247 return NotImplemented 248 249 x: int 250 y: int 251 return self.__new__( 252 type(self), 253 ( 254 x - y 255 for (x, y) in cast(Iterable[Tuple[int, int]], zip(self, right)) 256 ), 257 ) 258 259 def __rsub__(self: U, left: U) -> U: 260 if not isinstance(left, type(self)): 261 return NotImplemented 262 263 return self.__new__( 264 type(self), 265 ( 266 x - y 267 for (x, y) in cast(Iterable[Tuple[int, int]], zip(left, self)) 268 ), 269 ) 270 271 def __mul__(self: U, right: U) -> U: # type: ignore[override] 272 modulus = self.MODULUS 273 degree = len(modulus) 274 prime = self.PRIME 275 mul = [0] * (degree * 2) 276 277 for i in range(degree): 278 for j in range(degree): 279 mul[i + j] += self[i] * right[j] 280 281 for i in range(degree * 2 - 1, degree - 1, -1): 282 for j in range(i - degree, i): 283 mul[j] -= (mul[i] * modulus[degree - (i - j)]) % prime 284 285 return self.__new__( 286 type(self), 287 mul[:degree], 288 ) 289 290 def __rmul__(self: U, left: U) -> U: # type: ignore[override] 291 return self.__mul__(left) 292 293 def __imul__(self: U, right: U) -> U: # type: ignore[override] 294 return self.__mul__(right) 295 296 def __truediv__(self: U, right: U) -> U: 297 return self * right.multiplicative_inverse() 298 299 def __neg__(self: U) -> U: 300 return self.__new__(type(self), (-a for a in self)) 301 302 def scalar_mul(self: U, x: int) -> U: 303 """ 304 Multiply a field element by a integer. This is faster than using 305 `from_int()` and field multiplication. 306 """ 307 return self.__new__(type(self), (x * n for n in self)) 308 309 def deg(self: U) -> int: 310 """ 311 This is a support function for `multiplicative_inverse()`. 312 """ 313 for i in range(len(self.MODULUS) - 1, -1, -1): 314 if self[i] != 0: 315 return i 316 raise ValueError("deg() does not support zero") 317 318 def multiplicative_inverse(self: U) -> U: 319 """ 320 Calculate the multiplicative inverse. Uses the Euclidean algorithm. 321 """ 322 x2: List[int] 323 p = self.PRIME 324 x1, f1 = list(self.MODULUS), [0] * len(self) 325 x2, f2, d2 = list(self), [1] + [0] * (len(self) - 1), self.deg() 326 q_0 = pow(x2[d2], -1, p) 327 for i in range(d2): 328 x1[i + len(x1) - d2] = (x1[i + len(x1) - d2] - q_0 * x2[i]) % p 329 f1[i + len(x1) - d2] = (f1[i + len(x1) - d2] - q_0 * f2[i]) % p 330 for i in range(len(self.MODULUS) - 1, -1, -1): 331 if x1[i] != 0: 332 d1 = i 333 break 334 while True: 335 if d1 == 0: 336 ans = f1 337 q = pow(x1[0], -1, self.PRIME) 338 for i in range(len(ans)): 339 ans[i] *= q 340 break 341 elif d2 == 0: 342 ans = f2 343 q = pow(x2[0], -1, self.PRIME) 344 for i in range(len(ans)): 345 ans *= q 346 break 347 if d1 < d2: 348 q = x2[d2] * pow(x1[d1], -1, self.PRIME) 349 for i in range(len(self.MODULUS) - (d2 - d1)): 350 x2[i + (d2 - d1)] = (x2[i + (d2 - d1)] - q * x1[i]) % p 351 f2[i + (d2 - d1)] = (f2[i + (d2 - d1)] - q * f1[i]) % p 352 while x2[d2] == 0: 353 d2 -= 1 354 else: 355 q = x1[d1] * pow(x2[d2], -1, self.PRIME) 356 for i in range(len(self.MODULUS) - (d1 - d2)): 357 x1[i + (d1 - d2)] = (x1[i + (d1 - d2)] - q * x2[i]) % p 358 f1[i + (d1 - d2)] = (f1[i + (d1 - d2)] - q * f2[i]) % p 359 while x1[d1] == 0: 360 d1 -= 1 361 return self.__new__(type(self), ans) 362 363 def __pow__(self: U, exponent: int) -> U: 364 degree = len(self.MODULUS) 365 if exponent < 0: 366 self = self.multiplicative_inverse() 367 exponent = -exponent 368 369 res = self.__new__(type(self), [1] + [0] * (degree - 1)) 370 s = self 371 while exponent != 0: 372 if exponent % 2 == 1: 373 res *= s 374 s *= s 375 exponent //= 2 376 return res 377 378 def __ipow__(self: U, right: int) -> U: 379 return self.__pow__(right) 380 381 @classmethod 382 def calculate_frobenius_coefficients(cls: Type[U]) -> Tuple[U, ...]: 383 """ 384 Calculate the coefficients needed by `frobenius()`. 385 """ 386 coefficients = [] 387 for i in range(len(cls.MODULUS)): 388 x = [0] * len(cls.MODULUS) 389 x[i] = 1 390 coefficients.append(cls.__new__(cls, x) ** cls.PRIME) 391 return tuple(coefficients) 392 393 def frobenius(self: U) -> U: 394 """ 395 Returns `self ** p`. This function is known as the Frobenius 396 endomorphism and has many special mathematical properties. In 397 particular it is extremely cheap to compute compared to other 398 exponentiations. 399 """ 400 ans = self.from_int(0) 401 a: int 402 for i, a in enumerate(self): 403 ans += cast(U, self.FROBENIUS_COEFFICIENTS[i]).scalar_mul(a) 404 return ans
class
Field(typing.Protocol):
18class Field(Protocol): 19 """ 20 A type protocol for defining fields. 21 """ 22 23 __slots__ = () 24 25 @classmethod 26 def zero(cls: Type[F]) -> F: 27 ... 28 29 @classmethod 30 def from_int(cls: Type[F], n: int) -> F: 31 ... 32 33 def __radd__(self: F, left: F) -> F: 34 ... 35 36 def __add__(self: F, right: F) -> F: 37 ... 38 39 def __iadd__(self: F, right: F) -> F: 40 ... 41 42 def __sub__(self: F, right: F) -> F: 43 ... 44 45 def __rsub__(self: F, left: F) -> F: 46 ... 47 48 def __mul__(self: F, right: F) -> F: 49 ... 50 51 def __rmul__(self: F, left: F) -> F: 52 ... 53 54 def __imul__(self: F, right: F) -> F: 55 ... 56 57 def __pow__(self: F, exponent: int) -> F: 58 ... 59 60 def __ipow__(self: F, right: int) -> F: 61 ... 62 63 def __neg__(self: F) -> F: 64 ... 65 66 def __truediv__(self: F, right: F) -> F: 67 ...
A type protocol for defining fields.
73class PrimeField(int, Field): 74 """ 75 Superclass for integers modulo a prime. Not intended to be used 76 directly, but rather to be subclassed. 77 """ 78 79 __slots__ = () 80 PRIME: int 81 82 @classmethod 83 def from_be_bytes(cls: Type[T], buffer: "Bytes") -> T: 84 """ 85 Converts a sequence of bytes into a element of the field. 86 Parameters 87 ---------- 88 buffer : 89 Bytes to decode. 90 Returns 91 ------- 92 self : `T` 93 Unsigned integer decoded from `buffer`. 94 """ 95 return cls(int.from_bytes(buffer, "big")) 96 97 @classmethod 98 def zero(cls: Type[T]) -> T: 99 return cls.__new__(cls, 0) 100 101 @classmethod 102 def from_int(cls: Type[T], n: int) -> T: 103 return cls(n) 104 105 def __new__(cls: Type[T], value: int) -> T: 106 return int.__new__(cls, value % cls.PRIME) 107 108 def __radd__(self: T, left: T) -> T: # type: ignore[override] 109 return self.__add__(left) 110 111 def __add__(self: T, right: T) -> T: # type: ignore[override] 112 if not isinstance(right, int): 113 return NotImplemented 114 115 return self.__new__(type(self), int.__add__(self, right)) 116 117 def __iadd__(self: T, right: T) -> T: # type: ignore[override] 118 return self.__add__(right) 119 120 def __sub__(self: T, right: T) -> T: # type: ignore[override] 121 if not isinstance(right, int): 122 return NotImplemented 123 124 return self.__new__(type(self), int.__sub__(self, right)) 125 126 def __rsub__(self: T, left: T) -> T: # type: ignore[override] 127 if not isinstance(left, int): 128 return NotImplemented 129 130 return self.__new__(type(self), int.__rsub__(self, left)) 131 132 def __mul__(self: T, right: T) -> T: # type: ignore[override] 133 if not isinstance(right, int): 134 return NotImplemented 135 136 return self.__new__(type(self), int.__mul__(self, right)) 137 138 def __rmul__(self: T, left: T) -> T: # type: ignore[override] 139 return self.__mul__(left) 140 141 def __imul__(self: T, right: T) -> T: # type: ignore[override] 142 return self.__mul__(right) 143 144 __floordiv__ = None # type: ignore 145 __rfloordiv__ = None # type: ignore 146 __ifloordiv__ = None 147 __divmod__ = None # type: ignore 148 __rdivmod__ = None # type: ignore 149 150 def __pow__(self: T, exponent: int) -> T: # type: ignore[override] 151 # For reasons that are unclear, self must be cast to int here under 152 # PyPy. 153 return self.__new__( 154 type(self), int.__pow__(int(self), exponent, self.PRIME) 155 ) 156 157 __rpow__ = None # type: ignore 158 159 def __ipow__(self: T, right: int) -> T: # type: ignore[override] 160 return self.__pow__(right) 161 162 __and__ = None # type: ignore 163 __or__ = None # type: ignore 164 __xor__ = None # type: ignore 165 __rxor__ = None # type: ignore 166 __ixor__ = None 167 __rshift__ = None # type: ignore 168 __lshift__ = None # type: ignore 169 __irshift__ = None 170 __ilshift__ = None 171 172 def __neg__(self: T) -> T: 173 return self.__new__(type(self), int.__neg__(self)) 174 175 def __truediv__(self: T, right: T) -> T: # type: ignore[override] 176 return self * right.multiplicative_inverse() 177 178 def multiplicative_inverse(self: T) -> T: 179 return self ** (-1) 180 181 def to_be_bytes32(self) -> "Bytes32": 182 """ 183 Converts this arbitrarily sized unsigned integer into its big endian 184 representation with exactly 32 bytes. 185 Returns 186 ------- 187 big_endian : `Bytes32` 188 Big endian (most significant bits first) representation. 189 """ 190 return Bytes32(self.to_bytes(32, "big"))
Superclass for integers modulo a prime. Not intended to be used directly, but rather to be subclassed.
@classmethod
def
from_be_bytes(cls: Type[~T], buffer: bytes) -> ~T:
82 @classmethod 83 def from_be_bytes(cls: Type[T], buffer: "Bytes") -> T: 84 """ 85 Converts a sequence of bytes into a element of the field. 86 Parameters 87 ---------- 88 buffer : 89 Bytes to decode. 90 Returns 91 ------- 92 self : `T` 93 Unsigned integer decoded from `buffer`. 94 """ 95 return cls(int.from_bytes(buffer, "big"))
Converts a sequence of bytes into a element of the field.
Parameters
buffer : Bytes to decode.
Returns
self : T
Unsigned integer decoded from buffer.
181 def to_be_bytes32(self) -> "Bytes32": 182 """ 183 Converts this arbitrarily sized unsigned integer into its big endian 184 representation with exactly 32 bytes. 185 Returns 186 ------- 187 big_endian : `Bytes32` 188 Big endian (most significant bits first) representation. 189 """ 190 return Bytes32(self.to_bytes(32, "big"))
Converts this arbitrarily sized unsigned integer into its big endian representation with exactly 32 bytes.
Returns
big_endian : Bytes32
Big endian (most significant bits first) representation.
Inherited Members
- builtins.int
- conjugate
- bit_length
- to_bytes
- from_bytes
- as_integer_ratio
- real
- imag
- numerator
- denominator
196class GaloisField(tuple, Field): 197 """ 198 Superclass for defining finite fields. Not intended to be used 199 directly, but rather to be subclassed. 200 201 Fields are represented as `F_p[x]/(x^n + ...)` where the `MODULUS` is a 202 tuple of the non-leading coefficients of the defining polynomial. For 203 example `x^3 + 2x^2 + 3x + 4` is `(2, 3, 4)`. 204 205 In practice the polynomial is likely to be be sparse and you should overload 206 the `__mul__()` function to take advantage of this fact. 207 """ 208 209 __slots__ = () 210 211 PRIME: int 212 MODULUS: Tuple[int, ...] 213 FROBENIUS_COEFFICIENTS: Tuple["GaloisField", ...] 214 215 @classmethod 216 def zero(cls: Type[U]) -> U: 217 return cls.__new__(cls, [0] * len(cls.MODULUS)) 218 219 @classmethod 220 def from_int(cls: Type[U], n: int) -> U: 221 return cls.__new__(cls, [n] + [0] * (len(cls.MODULUS) - 1)) 222 223 def __new__(cls: Type[U], iterable: Iterable[int]) -> U: 224 self = tuple.__new__(cls, (x % cls.PRIME for x in iterable)) 225 assert len(self) == len(cls.MODULUS) 226 return self 227 228 def __add__(self: U, right: U) -> U: # type: ignore[override] 229 if not isinstance(right, type(self)): 230 return NotImplemented 231 232 return self.__new__( 233 type(self), 234 ( 235 x + y 236 for (x, y) in cast(Iterable[Tuple[int, int]], zip(self, right)) 237 ), 238 ) 239 240 def __radd__(self: U, left: U) -> U: 241 return self.__add__(left) 242 243 def __iadd__(self: U, right: U) -> U: # type: ignore[override] 244 return self.__add__(right) 245 246 def __sub__(self: U, right: U) -> U: 247 if not isinstance(right, type(self)): 248 return NotImplemented 249 250 x: int 251 y: int 252 return self.__new__( 253 type(self), 254 ( 255 x - y 256 for (x, y) in cast(Iterable[Tuple[int, int]], zip(self, right)) 257 ), 258 ) 259 260 def __rsub__(self: U, left: U) -> U: 261 if not isinstance(left, type(self)): 262 return NotImplemented 263 264 return self.__new__( 265 type(self), 266 ( 267 x - y 268 for (x, y) in cast(Iterable[Tuple[int, int]], zip(left, self)) 269 ), 270 ) 271 272 def __mul__(self: U, right: U) -> U: # type: ignore[override] 273 modulus = self.MODULUS 274 degree = len(modulus) 275 prime = self.PRIME 276 mul = [0] * (degree * 2) 277 278 for i in range(degree): 279 for j in range(degree): 280 mul[i + j] += self[i] * right[j] 281 282 for i in range(degree * 2 - 1, degree - 1, -1): 283 for j in range(i - degree, i): 284 mul[j] -= (mul[i] * modulus[degree - (i - j)]) % prime 285 286 return self.__new__( 287 type(self), 288 mul[:degree], 289 ) 290 291 def __rmul__(self: U, left: U) -> U: # type: ignore[override] 292 return self.__mul__(left) 293 294 def __imul__(self: U, right: U) -> U: # type: ignore[override] 295 return self.__mul__(right) 296 297 def __truediv__(self: U, right: U) -> U: 298 return self * right.multiplicative_inverse() 299 300 def __neg__(self: U) -> U: 301 return self.__new__(type(self), (-a for a in self)) 302 303 def scalar_mul(self: U, x: int) -> U: 304 """ 305 Multiply a field element by a integer. This is faster than using 306 `from_int()` and field multiplication. 307 """ 308 return self.__new__(type(self), (x * n for n in self)) 309 310 def deg(self: U) -> int: 311 """ 312 This is a support function for `multiplicative_inverse()`. 313 """ 314 for i in range(len(self.MODULUS) - 1, -1, -1): 315 if self[i] != 0: 316 return i 317 raise ValueError("deg() does not support zero") 318 319 def multiplicative_inverse(self: U) -> U: 320 """ 321 Calculate the multiplicative inverse. Uses the Euclidean algorithm. 322 """ 323 x2: List[int] 324 p = self.PRIME 325 x1, f1 = list(self.MODULUS), [0] * len(self) 326 x2, f2, d2 = list(self), [1] + [0] * (len(self) - 1), self.deg() 327 q_0 = pow(x2[d2], -1, p) 328 for i in range(d2): 329 x1[i + len(x1) - d2] = (x1[i + len(x1) - d2] - q_0 * x2[i]) % p 330 f1[i + len(x1) - d2] = (f1[i + len(x1) - d2] - q_0 * f2[i]) % p 331 for i in range(len(self.MODULUS) - 1, -1, -1): 332 if x1[i] != 0: 333 d1 = i 334 break 335 while True: 336 if d1 == 0: 337 ans = f1 338 q = pow(x1[0], -1, self.PRIME) 339 for i in range(len(ans)): 340 ans[i] *= q 341 break 342 elif d2 == 0: 343 ans = f2 344 q = pow(x2[0], -1, self.PRIME) 345 for i in range(len(ans)): 346 ans *= q 347 break 348 if d1 < d2: 349 q = x2[d2] * pow(x1[d1], -1, self.PRIME) 350 for i in range(len(self.MODULUS) - (d2 - d1)): 351 x2[i + (d2 - d1)] = (x2[i + (d2 - d1)] - q * x1[i]) % p 352 f2[i + (d2 - d1)] = (f2[i + (d2 - d1)] - q * f1[i]) % p 353 while x2[d2] == 0: 354 d2 -= 1 355 else: 356 q = x1[d1] * pow(x2[d2], -1, self.PRIME) 357 for i in range(len(self.MODULUS) - (d1 - d2)): 358 x1[i + (d1 - d2)] = (x1[i + (d1 - d2)] - q * x2[i]) % p 359 f1[i + (d1 - d2)] = (f1[i + (d1 - d2)] - q * f2[i]) % p 360 while x1[d1] == 0: 361 d1 -= 1 362 return self.__new__(type(self), ans) 363 364 def __pow__(self: U, exponent: int) -> U: 365 degree = len(self.MODULUS) 366 if exponent < 0: 367 self = self.multiplicative_inverse() 368 exponent = -exponent 369 370 res = self.__new__(type(self), [1] + [0] * (degree - 1)) 371 s = self 372 while exponent != 0: 373 if exponent % 2 == 1: 374 res *= s 375 s *= s 376 exponent //= 2 377 return res 378 379 def __ipow__(self: U, right: int) -> U: 380 return self.__pow__(right) 381 382 @classmethod 383 def calculate_frobenius_coefficients(cls: Type[U]) -> Tuple[U, ...]: 384 """ 385 Calculate the coefficients needed by `frobenius()`. 386 """ 387 coefficients = [] 388 for i in range(len(cls.MODULUS)): 389 x = [0] * len(cls.MODULUS) 390 x[i] = 1 391 coefficients.append(cls.__new__(cls, x) ** cls.PRIME) 392 return tuple(coefficients) 393 394 def frobenius(self: U) -> U: 395 """ 396 Returns `self ** p`. This function is known as the Frobenius 397 endomorphism and has many special mathematical properties. In 398 particular it is extremely cheap to compute compared to other 399 exponentiations. 400 """ 401 ans = self.from_int(0) 402 a: int 403 for i, a in enumerate(self): 404 ans += cast(U, self.FROBENIUS_COEFFICIENTS[i]).scalar_mul(a) 405 return ans
Superclass for defining finite fields. Not intended to be used directly, but rather to be subclassed.
Fields are represented as F_p[x]/(x^n + ...) where the MODULUS is a
tuple of the non-leading coefficients of the defining polynomial. For
example x^3 + 2x^2 + 3x + 4 is (2, 3, 4).
In practice the polynomial is likely to be be sparse and you should overload
the __mul__() function to take advantage of this fact.
def
scalar_mul(self: ~U, x: int) -> ~U:
303 def scalar_mul(self: U, x: int) -> U: 304 """ 305 Multiply a field element by a integer. This is faster than using 306 `from_int()` and field multiplication. 307 """ 308 return self.__new__(type(self), (x * n for n in self))
Multiply a field element by a integer. This is faster than using
from_int() and field multiplication.
def
deg(self: ~U) -> int:
310 def deg(self: U) -> int: 311 """ 312 This is a support function for `multiplicative_inverse()`. 313 """ 314 for i in range(len(self.MODULUS) - 1, -1, -1): 315 if self[i] != 0: 316 return i 317 raise ValueError("deg() does not support zero")
This is a support function for multiplicative_inverse().
def
multiplicative_inverse(self: ~U) -> ~U:
319 def multiplicative_inverse(self: U) -> U: 320 """ 321 Calculate the multiplicative inverse. Uses the Euclidean algorithm. 322 """ 323 x2: List[int] 324 p = self.PRIME 325 x1, f1 = list(self.MODULUS), [0] * len(self) 326 x2, f2, d2 = list(self), [1] + [0] * (len(self) - 1), self.deg() 327 q_0 = pow(x2[d2], -1, p) 328 for i in range(d2): 329 x1[i + len(x1) - d2] = (x1[i + len(x1) - d2] - q_0 * x2[i]) % p 330 f1[i + len(x1) - d2] = (f1[i + len(x1) - d2] - q_0 * f2[i]) % p 331 for i in range(len(self.MODULUS) - 1, -1, -1): 332 if x1[i] != 0: 333 d1 = i 334 break 335 while True: 336 if d1 == 0: 337 ans = f1 338 q = pow(x1[0], -1, self.PRIME) 339 for i in range(len(ans)): 340 ans[i] *= q 341 break 342 elif d2 == 0: 343 ans = f2 344 q = pow(x2[0], -1, self.PRIME) 345 for i in range(len(ans)): 346 ans *= q 347 break 348 if d1 < d2: 349 q = x2[d2] * pow(x1[d1], -1, self.PRIME) 350 for i in range(len(self.MODULUS) - (d2 - d1)): 351 x2[i + (d2 - d1)] = (x2[i + (d2 - d1)] - q * x1[i]) % p 352 f2[i + (d2 - d1)] = (f2[i + (d2 - d1)] - q * f1[i]) % p 353 while x2[d2] == 0: 354 d2 -= 1 355 else: 356 q = x1[d1] * pow(x2[d2], -1, self.PRIME) 357 for i in range(len(self.MODULUS) - (d1 - d2)): 358 x1[i + (d1 - d2)] = (x1[i + (d1 - d2)] - q * x2[i]) % p 359 f1[i + (d1 - d2)] = (f1[i + (d1 - d2)] - q * f2[i]) % p 360 while x1[d1] == 0: 361 d1 -= 1 362 return self.__new__(type(self), ans)
Calculate the multiplicative inverse. Uses the Euclidean algorithm.
@classmethod
def
calculate_frobenius_coefficients(cls: Type[~U]) -> Tuple[~U, ...]:
382 @classmethod 383 def calculate_frobenius_coefficients(cls: Type[U]) -> Tuple[U, ...]: 384 """ 385 Calculate the coefficients needed by `frobenius()`. 386 """ 387 coefficients = [] 388 for i in range(len(cls.MODULUS)): 389 x = [0] * len(cls.MODULUS) 390 x[i] = 1 391 coefficients.append(cls.__new__(cls, x) ** cls.PRIME) 392 return tuple(coefficients)
Calculate the coefficients needed by frobenius().
def
frobenius(self: ~U) -> ~U:
394 def frobenius(self: U) -> U: 395 """ 396 Returns `self ** p`. This function is known as the Frobenius 397 endomorphism and has many special mathematical properties. In 398 particular it is extremely cheap to compute compared to other 399 exponentiations. 400 """ 401 ans = self.from_int(0) 402 a: int 403 for i, a in enumerate(self): 404 ans += cast(U, self.FROBENIUS_COEFFICIENTS[i]).scalar_mul(a) 405 return ans
Returns self ** p. This function is known as the Frobenius
endomorphism and has many special mathematical properties. In
particular it is extremely cheap to compute compared to other
exponentiations.
Inherited Members
- builtins.tuple
- index
- count