This is a read note of Programming Bitcoin Ch01: Finite Fields.

1 Finite Field Definition

Mathematically, a finite field is defined as a finite set of numbers and two operations + (addition) and ⋅ (multiplication) that satisfy the following:

  1. If a and b are in the set, a + b and a ⋅ b are in the set. We call this property closed.
  2. 0 exists and has the property a + 0 = a. We call this the additive identity.
  3. 1 exists and has the property a ⋅ 1 = a. We call this the multiplicative identity.
  4. If a is in the set, –a is in the set, which is defined as the value that makes a + (–a) = 0. This is what we call the additive inverse.
  5. If a is in the set and is not 0, 1/a is in the set, which is defined as the value that makes a ⋅ (1/a) = 1. This is what we call the multiplicative inverse.

Because the set is finite, we can designate a number p, which is how big the set is. This is what we call the order of the set or the size of the set.

If the order (or size) of the set is p, we can call the elements of the set, 0, 1, 2, … p – 1.

In math notation the finite field set looks like this: Fp = {0, 1, 2, ... p–1}. What’s in the finite field set are the elements. Fp is called a finite field of p or field of p or whatever the size of it is (again, the size is what mathematicians call order). For example, A finite field of order 983 is: F983= {0, 1, 2, ... 982}. Notice the order of the field is always 1 more than the largest element.

2 Finite Field Operations

Addition operation __add__ is defined as: __add__(a, b) = (a + b ) % p.

Field substraction is defined as __sub__(a, b) = (a - b) % p. For example, __sub__(11, 9) = (11 - 9) % 19 = 2, __sub__(6, 13) = (-7) % 19 = 12.

The additive inverse is defined as __neg__(a) = (-a) % p. For example, if p = 19, then __neg__(9) = (-9) % 19 = 10, and __add__(9, 10) = 0.

Multiplication __mul__ is adding multiple times: __mul__(a, b) = (a * b) % p. Exponentiation __pow__ is multiplicating multiple times: __pow__(a, n) = (a ** n) % p. The exponent here could be any integer, not a field element.

Intuitively, the fact that we have a prime order results in every element of a finite field being equivalent. If the order of the set was a composite number, multiplying the set by one of the divisors would result in a smaller set.

Finete fields are closed under division: dividing any two numbers where the denominator is not 0 will result in another finite field element.

Fermat’s littel theorem: n ** (p - 1) % p = 1 for every 0 < n < p. Then b ** (-1) = b ** (-1) * b ** (p - 1) = b ** (p - 2). Therefore, __div__(a, b) = a * b ** (p - 2) % p.

Similarly, if n is negative, __pow__(a, n) = a ** (p - 1 - n) % p. The __pow__ can be defined as the following:

1
2
3
4

def __pow__(self, exponent):
  n = exponent % (self.prime - 1)
  num = pow(self.num, n, self.prime)
  return self.__class__(num, self.prime)