ethereum.crypto.finite_field

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

F

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

Field

A type protocol for defining fields.

class Field:

__slots__

21
    __slots__ = ()

zero

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

from_int

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

__radd__

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

__add__

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

__iadd__

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

__sub__

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

__rsub__

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

__mul__

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

__rmul__

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

__imul__

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

__pow__

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

__ipow__

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

__neg__

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

__truediv__

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

T

68
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__

77
    __slots__ = ()

PRIME

78
    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.

80
    @classmethod
def from_be_bytes(​cls: Type[T], ​​buffer: "Bytes"​) -> T:
82
        """
83
        Converts a sequence of bytes into a element of the field.
84
        Parameters
85
        ----------
86
        buffer :
87
            Bytes to decode.
88
        Returns
89
        -------
90
        self : `T`
91
            Unsigned integer decoded from `buffer`.
92
        """
93
        return cls(int.from_bytes(buffer, "big"))

zero

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

from_int

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

__new__

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

__radd__

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

__add__

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

__iadd__

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

__sub__

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

__rsub__

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

__mul__

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

__rmul__

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

__imul__

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

__floordiv__

142
    __floordiv__ = None

__rfloordiv__

143
    __rfloordiv__ = None

__ifloordiv__

144
    __ifloordiv__ = None

__divmod__

145
    __divmod__ = None

__rdivmod__

146
    __rdivmod__ = None

__pow__

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

__rpow__

155
    __rpow__ = None

__ipow__

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

__and__

160
    __and__ = None

__or__

161
    __or__ = None

__xor__

162
    __xor__ = None

__rxor__

163
    __rxor__ = None

__ixor__

164
    __ixor__ = None

__rshift__

165
    __rshift__ = None

__lshift__

166
    __lshift__ = None

__irshift__

167
    __irshift__ = None

__ilshift__

168
    __ilshift__ = None

__neg__

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

__truediv__

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

multiplicative_inverse

def multiplicative_inverse(​self: T​) -> T:
177
        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":
180
        """
181
        Converts this arbitrarily sized unsigned integer into its big endian
182
        representation with exactly 32 bytes.
183
        Returns
184
        -------
185
        big_endian : `Bytes32`
186
            Big endian (most significant bits first) representation.
187
        """
188
        return Bytes32(self.to_bytes(32, "big"))

U

191
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__

207
    __slots__ = ()

PRIME

209
    PRIME: int

MODULUS

210
    MODULUS: Tuple[int, ...]

FROBENIUS_COEFFICIENTS

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

zero

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

from_int

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

__new__

def __new__(​cls: Type[U], ​​iterable: Iterable[int]​) -> U:
222
        self = tuple.__new__(cls, (x % cls.PRIME for x in iterable))
223
        assert len(self) == len(cls.MODULUS)
224
        return self

__add__

def __add__(​self: U, ​​right: U​) -> U:
227
        if not isinstance(right, type(self)):
228
            return NotImplemented
229
230
        return self.__new__(
231
            type(self),
232
            (
233
                x + y
234
                for (x, y) in cast(Iterable[Tuple[int, int]], zip(self, right))
235
            ),
236
        )

__radd__

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

__iadd__

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

__sub__

def __sub__(​self: U, ​​right: U​) -> U:
245
        if not isinstance(right, type(self)):
246
            return NotImplemented
247
248
        x: int
249
        y: int
250
        return self.__new__(
251
            type(self),
252
            (
253
                x - y
254
                for (x, y) in cast(Iterable[Tuple[int, int]], zip(self, right))
255
            ),
256
        )

__rsub__

def __rsub__(​self: U, ​​left: U​) -> U:
259
        if not isinstance(left, type(self)):
260
            return NotImplemented
261
262
        return self.__new__(
263
            type(self),
264
            (
265
                x - y
266
                for (x, y) in cast(Iterable[Tuple[int, int]], zip(left, self))
267
            ),
268
        )

__mul__

def __mul__(​self: U, ​​right: U​) -> U:
271
        modulus = self.MODULUS
272
        degree = len(modulus)
273
        prime = self.PRIME
274
        mul = [0] * (degree * 2)
275
276
        for i in range(degree):
277
            for j in range(degree):
278
                mul[i + j] += self[i] * right[j]
279
280
        for i in range(degree * 2 - 1, degree - 1, -1):
281
            for j in range(i - degree, i):
282
                mul[j] -= (mul[i] * modulus[degree - (i - j)]) % prime
283
284
        return self.__new__(
285
            type(self),
286
            mul[:degree],
287
        )

__rmul__

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

__imul__

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

__truediv__

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

__neg__

def __neg__(​self: U​) -> U:
299
        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:
302
        """
303
        Multiply a field element by a integer. This is faster than using
304
        `from_int()` and field multiplication.
305
        """
306
        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:
309
        """
310
        This is a support function for `multiplicative_inverse()`.
311
        """
312
        for i in range(len(self.MODULUS) - 1, -1, -1):
313
            if self[i] != 0:
314
                return i
315
        raise ValueError("deg() does not support zero")

multiplicative_inverse

Calculate the multiplicative inverse. Uses the Euclidean algorithm.

def multiplicative_inverse(​self: U​) -> U:
318
        """
319
        Calculate the multiplicative inverse. Uses the Euclidean algorithm.
320
        """
321
        x2: List[int]
322
        p = self.PRIME
323
        x1, f1 = list(self.MODULUS), [0] * len(self)
324
        x2, f2, d2 = list(self), [1] + [0] * (len(self) - 1), self.deg()
325
        q_0 = pow(x2[d2], -1, p)
326
        for i in range(d2):
327
            x1[i + len(x1) - d2] = (x1[i + len(x1) - d2] - q_0 * x2[i]) % p
328
            f1[i + len(x1) - d2] = (f1[i + len(x1) - d2] - q_0 * f2[i]) % p
329
        for i in range(len(self.MODULUS) - 1, -1, -1):
330
            if x1[i] != 0:
331
                d1 = i
332
                break
333
        while True:
334
            if d1 == 0:
335
                ans = f1
336
                q = pow(x1[0], -1, self.PRIME)
337
                for i in range(len(ans)):
338
                    ans[i] *= q
339
                break
340
            elif d2 == 0:
341
                ans = f2
342
                q = pow(x2[0], -1, self.PRIME)
343
                for i in range(len(ans)):
344
                    ans *= q
345
                break
346
            if d1 < d2:
347
                q = x2[d2] * pow(x1[d1], -1, self.PRIME)
348
                for i in range(len(self.MODULUS) - (d2 - d1)):
349
                    x2[i + (d2 - d1)] = (x2[i + (d2 - d1)] - q * x1[i]) % p
350
                    f2[i + (d2 - d1)] = (f2[i + (d2 - d1)] - q * f1[i]) % p
351
                while x2[d2] == 0:
352
                    d2 -= 1
353
            else:
354
                q = x1[d1] * pow(x2[d2], -1, self.PRIME)
355
                for i in range(len(self.MODULUS) - (d1 - d2)):
356
                    x1[i + (d1 - d2)] = (x1[i + (d1 - d2)] - q * x2[i]) % p
357
                    f1[i + (d1 - d2)] = (f1[i + (d1 - d2)] - q * f2[i]) % p
358
                while x1[d1] == 0:
359
                    d1 -= 1
360
        return self.__new__(type(self), ans)

__pow__

def __pow__(​self: U, ​​exponent: int​) -> U:
363
        degree = len(self.MODULUS)
364
        if exponent < 0:
365
            self = self.multiplicative_inverse()
366
            exponent = -exponent
367
368
        res = self.__new__(type(self), [1] + [0] * (degree - 1))
369
        s = self
370
        while exponent != 0:
371
            if exponent % 2 == 1:
372
                res *= s
373
            s *= s
374
            exponent //= 2
375
        return res

__ipow__

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

calculate_frobenius_coefficients

Calculate the coefficients needed by frobenius().

380
    @classmethod
def calculate_frobenius_coefficients(​cls: Type[U]​) -> Tuple[U, ...]:
382
        """
383
        Calculate the coefficients needed by `frobenius()`.
384
        """
385
        coefficients = []
386
        for i in range(len(cls.MODULUS)):
387
            x = [0] * len(cls.MODULUS)
388
            x[i] = 1
389
            coefficients.append(cls.__new__(cls, x) ** cls.PRIME)
390
        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:
393
        """
394
        Returns `self ** p`. This function is known as the Frobenius
395
        endomorphism and has many special mathematical properties. In
396
        particular it is extremely cheap to compute compared to other
397
        exponentiations.
398
        """
399
        ans = self.from_int(0)
400
        a: int
401
        for i, a in enumerate(self):
402
            ans += cast(U, self.FROBENIUS_COEFFICIENTS[i]).scalar_mul(a)
403
        return ans