ethereum.crypto.finite_field

Finite Fields ^^^^^^^^^^^^^

F

14
F = TypeVar("F", bound="Field")

Field

A type protocol for defining fields.

class Field:

__slots__

22
    __slots__ = ()

zero

24
    @classmethod
def zero(​cls: Type[F]​) -> F:
26
        ...

from_int

28
    @classmethod
def from_int(​cls: Type[F], ​​n: int​) -> F:
30
        ...

__radd__

def __radd__(​self: F, ​​left: F​) -> F:
33
        ...

__add__

def __add__(​self: F, ​​right: F​) -> F:
36
        ...

__iadd__

def __iadd__(​self: F, ​​right: F​) -> F:
39
        ...

__sub__

def __sub__(​self: F, ​​right: F​) -> F:
42
        ...

__rsub__

def __rsub__(​self: F, ​​left: F​) -> F:
45
        ...

__mul__

def __mul__(​self: F, ​​right: F​) -> F:
48
        ...

__rmul__

def __rmul__(​self: F, ​​left: F​) -> F:
51
        ...

__imul__

def __imul__(​self: F, ​​right: F​) -> F:
54
        ...

__pow__

def __pow__(​self: F, ​​exponent: int​) -> F:
57
        ...

__ipow__

def __ipow__(​self: F, ​​right: int​) -> F:
60
        ...

__neg__

def __neg__(​self: F​) -> F:
63
        ...

__truediv__

def __truediv__(​self: F, ​​right: F​) -> F:
66
        ...

T

69
T = TypeVar("T", bound="PrimeField")

PrimeField

Superclass for integers modulo a prime. Not intended to be used directly, but rather to be subclassed.

class PrimeField:

__slots__

78
    __slots__ = ()

PRIME

79
    PRIME: int

from_be_bytes

Converts a sequence of bytes into a element of the field. Parameters

buffer : Bytes to decode. Returns

self : T Unsigned integer decoded from buffer.

81
    @classmethod
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"))

zero

96
    @classmethod
def zero(​cls: Type[T]​) -> T:
98
        return cls.__new__(cls, 0)

from_int

100
    @classmethod
def from_int(​cls: Type[T], ​​n: int​) -> T:
102
        return cls(n)

__new__

def __new__(​cls: Type[T], ​​value: int​) -> T:
105
        return int.__new__(cls, value % cls.PRIME)

__radd__

def __radd__(​self: T, ​​left: T​) -> T:
108
        return self.__add__(left)

__add__

def __add__(​self: T, ​​right: T​) -> T:
111
        if not isinstance(right, int):
112
            return NotImplemented
113
114
        return self.__new__(type(self), int.__add__(self, right))

__iadd__

def __iadd__(​self: T, ​​right: T​) -> T:
117
        return self.__add__(right)

__sub__

def __sub__(​self: T, ​​right: T​) -> T:
120
        if not isinstance(right, int):
121
            return NotImplemented
122
123
        return self.__new__(type(self), int.__sub__(self, right))

__rsub__

def __rsub__(​self: T, ​​left: T​) -> T:
126
        if not isinstance(left, int):
127
            return NotImplemented
128
129
        return self.__new__(type(self), int.__rsub__(self, left))

__mul__

def __mul__(​self: T, ​​right: T​) -> T:
132
        if not isinstance(right, int):
133
            return NotImplemented
134
135
        return self.__new__(type(self), int.__mul__(self, right))

__rmul__

def __rmul__(​self: T, ​​left: T​) -> T:
138
        return self.__mul__(left)

__imul__

def __imul__(​self: T, ​​right: T​) -> T:
141
        return self.__mul__(right)

__floordiv__

143
    __floordiv__ = None

__rfloordiv__

144
    __rfloordiv__ = None

__ifloordiv__

145
    __ifloordiv__ = None

__divmod__

146
    __divmod__ = None

__rdivmod__

147
    __rdivmod__ = None

__pow__

def __pow__(​self: T, ​​exponent: int​) -> T:
152
        return self.__new__(
153
            type(self), int.__pow__(int(self), exponent, self.PRIME)
154
        )

__rpow__

156
    __rpow__ = None

__ipow__

def __ipow__(​self: T, ​​right: int​) -> T:
159
        return self.__pow__(right)

__and__

161
    __and__ = None

__or__

162
    __or__ = None

__xor__

163
    __xor__ = None

__rxor__

164
    __rxor__ = None

__ixor__

165
    __ixor__ = None

__rshift__

166
    __rshift__ = None

__lshift__

167
    __lshift__ = None

__irshift__

168
    __irshift__ = None

__ilshift__

169
    __ilshift__ = None

__neg__

def __neg__(​self: T​) -> T:
172
        return self.__new__(type(self), int.__neg__(self))

__truediv__

def __truediv__(​self: T, ​​right: T​) -> T:
175
        return self * right.multiplicative_inverse()

multiplicative_inverse

def multiplicative_inverse(​self: T​) -> T:
178
        return self ** (-1)

to_be_bytes32

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.

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

U

192
U = TypeVar("U", bound="GaloisField")

GaloisField

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 sparse and you should overload the __mul__() function to take advantage of this fact.

class GaloisField:

__slots__

208
    __slots__ = ()

PRIME

210
    PRIME: int

MODULUS

211
    MODULUS: Tuple[int, ...]

FROBENIUS_COEFFICIENTS

212
    FROBENIUS_COEFFICIENTS: Tuple["GaloisField", ...]

zero

214
    @classmethod
def zero(​cls: Type[U]​) -> U:
216
        return cls.__new__(cls, [0] * len(cls.MODULUS))

from_int

218
    @classmethod
def from_int(​cls: Type[U], ​​n: int​) -> U:
220
        return cls.__new__(cls, [n] + [0] * (len(cls.MODULUS) - 1))

__new__

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

__add__

def __add__(​self: U, ​​right: U​) -> U:
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
        )

__radd__

def __radd__(​self: U, ​​left: U​) -> U:
240
        return self.__add__(left)

__iadd__

def __iadd__(​self: U, ​​right: U​) -> U:
243
        return self.__add__(right)

__sub__

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
        )

__rsub__

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
        )

__mul__

def __mul__(​self: U, ​​right: U​) -> U:
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
        )

__rmul__

def __rmul__(​self: U, ​​left: U​) -> U:
291
        return self.__mul__(left)

__imul__

def __imul__(​self: U, ​​right: U​) -> U:
294
        return self.__mul__(right)

__truediv__

def __truediv__(​self: U, ​​right: U​) -> U:
297
        return self * right.multiplicative_inverse()

__neg__

def __neg__(​self: U​) -> U:
300
        return self.__new__(type(self), (-a for a in self))

scalar_mul

Multiply a field element by a integer. This is faster than using from_int() and field multiplication.

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

deg

This is a support function for multiplicative_inverse().

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

multiplicative_inverse

Calculate the multiplicative inverse. Uses the Euclidean algorithm.

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)

__pow__

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

__ipow__

def __ipow__(​self: U, ​​right: int​) -> U:
379
        return self.__pow__(right)

calculate_frobenius_coefficients

Calculate the coefficients needed by frobenius().

381
    @classmethod
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)

frobenius

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.

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