Programming Bitcoin

Appendix A. Solutions

Chapter 1: Finite Fields

Exercise 1

Write the corresponding method __ne__, which checks if two FieldElement objects are not equal to each other.

class FieldElement:
...
    def __ne__(self, other):
        # this should be the inverse of the == operator
        return not (self == other)

Exercise 2

Solve these problems in F₅₇ (assume all +’s here are +_f and –’s here are –_f):

• 44 + 33

• 9 – 29

• 17 + 42 + 49

• 52 – 30 – 38

>>> prime = 57
>>> print((44+33)%prime)
20
>>> print((9-29)%prime)
37
>>> print((17+42+49)%prime)
51
>>> print((52-30-38)%prime)
41

Exercise 3

Write the corresponding __sub__ method that defines the subtraction of two FieldElement objects.

class FieldElement:
...
    def __sub__(self, other):
        if self.prime != other.prime:
            raise TypeError('Cannot subtract two numbers in different Fields')
        # self.num and other.num are the actual values
        # self.prime is what we need to mod against
        num = (self.num - other.num) % self.prime
        # we return an element of the same class
        return self.__class__(num, self.prime)

Exercise 4

Solve the following equations in F₉₇ (again, assume ⋅ and exponentiation are field versions):

• 95 ⋅ 45 ⋅ 31

• 17 ⋅ 13 ⋅ 19 ⋅ 44

• 12⁷ ⋅ 77⁴⁹

>>> prime = 97
>>> print(95*45*31 % prime)
23
>>> print(17*13*19*44 % prime)
68
>>> print(12**7*77**49 % prime)
63

Exercise 5

For k = 1, 3, 7, 13, 18, what is this set in F₁₉?

• {k ⋅ 0, k ⋅ 1, k ⋅ 2, k ⋅ 3, ... k ⋅ 18}

Do you notice anything about these sets?

>>> prime = 19
>>> for k in (1,3,7,13,18):