Galois Fields

  • A Galois field is finite set of elements and two operations
    ++
    (addition) and
    ร—\times
    (multiplication), with the following properties:
    • Closure: if
      aa
      and
      bb
      are in the set,
      a+ba + b
      and
      aร—ba \times b
      are also in the set.
    • Additive identity:
      a+0=aa + 0 = a
      โ€‹
    • Multiplicative identity:
      aร—1=aa \times 1 = a
      โ€‹
    • Additive inverse:
      a+(โˆ’a)=0a + (-a) = 0
    • Multiplicative inverse:
      aร—aโˆ’ยน=1a \times a^-ยน = 1
  • Field size is the number of elements in the set.
Elliptic curves that are defined over a finite field with a prime field size have interesting properties and are key to building of elliptic curve cryptographic protocols.
Let's define a PrimeGaloisField class that contains the intrinsic property of a finite field, prime. We also define a membership rule for a value in a given finite field, by overriding the __contains__ method.
from dataclasses import dataclass
โ€‹
โ€‹
@dataclass
class PrimeGaloisField:
prime: int
โ€‹
def __contains__(self, field_value: "FieldElement") -> bool:
# called whenever you do: <FieldElement> in <PrimeGaloisField>
return 0 <= field_value.value < self.prime
Let's also define a FieldElement class to make sure all mathematical operations are contained within a given PrimeGaloisField.
@dataclass
class FieldElement:
value: int
field: PrimeGaloisField
โ€‹
def __repr__(self):
return "0x" + f"{self.value:x}".zfill(64)
@property
def P(self) -> int:
return self.field.prime
def __add__(self, other: "FieldElement") -> "FieldElement":
return FieldElement(
value=(self.value + other.value) % self.P,
field=self.field
)
def __sub__(self, other: "FieldElement") -> "FieldElement":
return FieldElement(
value=(self.value - other.value) % self.P,
field=self.field
)
โ€‹
def __rmul__(self, scalar: int) -> "FieldValue":
return FieldElement(
value=(self.value * scalar) % self.P,
field=self.field
)
โ€‹
def __mul__(self, other: "FieldElement") -> "FieldElement":
return FieldElement(
value=(self.value * other.value) % self.P,
field=self.field
)
def __pow__(self, exponent: int) -> "FieldElement":
return FieldElement(
value=pow(self.value, exponent, self.P),
field=self.field
)
โ€‹
def __truediv__(self, other: "FieldElement") -> "FieldElement":
other_inv = other ** -1
return self * other_inv
All parameters in an elliptic curve equation are actually elements in a given prime Galois field. This includes a,b,x, andy.
Copy link