One of the most difficult things about learning how to program Bitcoin is knowing where to start. There are so many components that depend on each other that learning one thing may lead you to have to learn another, which in turn may lead you to need to learn something else before you can understand the original thing.
This chapter is going to get you off to a more manageable start. It may seem strange, but we’ll start with the basic math that you need to understand elliptic curve cryptography. Elliptic curve cryptography, in turn, gives us the signing and verification algorithms. These are at the heart of how transactions work, and transactions are the atomic unit of value transfer in Bitcoin. By learning about finite fields and elliptic curves first, you’ll get a firm grasp of concepts that you’ll need to progress logically.
Be aware that this chapter and the next two chapters may feel a bit like you’re eating vegetables, especially if you haven’t done formal math in a long time. I would encourage you to get through them, though, as the concepts and code presented here will be used throughout the book.
Learning about new mathematical structures can be a bit intimidating, and in this chapter, I hope to dispel the myth that highlevel math is difficult. Finite fields, in particular, don’t require all that much more in terms of prior mathematical knowledge than, say, algebra.
Think of finite fields as something that you could have learned instead of trigonometry, except that the education system you’re a part of decided that trigonometry was more important for you to learn. This is my way of telling you that finite fields are not that hard to learn and require no more background than algebra.
This chapter is required if you want to understand elliptic curve cryptography. Elliptic curve cryptography is required for understanding signing and verification, which is at the heart of Bitcoin itself. As I’ve said, this chapter and the next two may feel a bit unrelated, but I encourage you to endure. The fundamentals here will not only make understanding Bitcoin a lot easier, but also make understanding Schnorr signatures, confidential transactions, and other leadingedge Bitcoin technologies easier.
Mathematically, a finite field is defined as a finite set of numbers and two operations + (addition) and ⋅ (multiplication) that satisfy the following:
If a and b are in the set, a + b and a ⋅ b are in the set. We call this property closed.
0 exists and has the property a + 0 = a. We call this the additive identity.
1 exists and has the property a ⋅ 1 = a. We call this the multiplicative identity.
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.
If a is in the set and is not 0, a^{–1} is in the set, which is defined as the value that makes a ⋅ a^{–1} = 1. This is what we call the multiplicative inverse.
Let’s unpack each of these criteria.
We have a set of numbers that’s finite. 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.
#1 says we are closed under addition and multiplication. This means that we have to define addition and multiplication in a way that ensures the results stay in the set. For example, a set containing {0,1,2} is not closed under addition, since 1 + 2 = 3 and 3 is not in the set; neither is 2 + 2 = 4. Of course we can define addition a little differently to make this work, but using “normal” addition, this set is not closed. On the other hand, the set {–1,0,1} is closed under normal multiplication. Any two numbers can be multiplied (there are nine such combinations), and the result is always in the set.
The other option we have in mathematics is to define multiplication in a particular way to make these sets closed. We’ll get to how exactly we define addition and multiplication later in this chapter, but the key concept here is that we can define addition and subtraction differently than the addition and subtraction you are familiar with.
#2 and #3 mean that we have the additive and multiplicative identities. That means 0 and 1 are in the set.
#4 means that we have the additive inverse. That is, if a is in the set, –a is in the set. Using the additive inverse, we can define subtraction.
#5 means that multiplication has the same property. If a is in the set, a^{–1} is in the set. That is a ⋅ a^{–1} = 1. Using the multiplicative inverse, we can define division. This will be the trickiest to define in a finite field.
If the order (or size) of the set is p, we can call the elements of the set, 0, 1, 2, … p – 1. These numbers are what we call the elements of the set, not necessarily the traditional numbers 0, 1, 2, 3, etc. They behave in many ways like traditional numbers, but have some differences in how we add, subtract, multiply, and so forth.
In math notation the finite field set looks like this:
What’s in the finite field set are the elements. F_{p} is a specific finite field called “field of p" or “field of 29” or whatever the size of it is (again, the size is what mathematicians call order). The numbers between the {}s represent what elements are in the field. We name the elements 0, 1, 2, etc. because these names are convenient for our purposes.
A finite field of order 11 looks like this:
A finite field of order 17 looks like this:
A finite field of order 983 looks like this:
Notice the order of the field is always 1 more than the largest element. You might have noticed that the field has a prime order every time. For a variety of reasons that will become clear later, it turns out that fields must have an order that is a power of a prime, and that the finite fields whose order is prime are the ones we’re interested in.
We want to represent each finite field element, so in Python, we’ll be creating a class that represents a single finite field element.
Naturally, we’ll name the class FieldElement
.
The class represents an element in a field F_{prime}. The bare bones of the class look like this:
class
FieldElement
:
def
__init__
(
self
,
num
,
prime
)
:
if
num
>
=
prime
or
num
<
0
:
error
=
'
Num {} not in field range 0 to {}
'
.
format
(
num
,
prime

1
)
raise
ValueError
(
error
)
self
.
num
=
num
self
.
prime
=
prime
def
__repr__
(
self
)
:
return
'
FieldElement_{}({})
'
.
format
(
self
.
prime
,
self
.
num
)
def
__eq__
(
self
,
other
)
:
if
other
is
None
:
return
False
return
self
.
num
==
other
.
num
and
self
.
prime
==
other
.
prime
We first check that num
is between 0
and prime1
inclusive.
If not, we get an invalid FieldElement
and we raise a ValueError
, which is what we should raise when we get an inappropriate value.
The rest of the __init__
method assigns the initialization values to the object.
The __eq__
method checks if two objects of class FieldElement
are equal.
This is only true when the num
and prime
properties are equal.
What we’ve defined already allows us to do this:
>>>
from
ecc
import
FieldElement
>>>
a
=
FieldElement
(
7
,
13
)
>>>
b
=
FieldElement
(
6
,
13
)
>>>
(
a
==
b
)
False
>>>
(
a
==
a
)
True
Python allows us to override the ==
operator on FieldElement
with the __eq__
method, which is something we’ll be taking advantage of going forward.
You can see this in action in the code that accompanies this book. Once you’ve set up Jupyter Notebook (see “Setting Up”), you can navigate to codech01/Chapter1.ipynb and run the code to see the results. For the next exercise, you’ll want to open up ecc.py by clicking the link in the Exercise 1 box. If you get stuck, please remember that the answers to every exercise are in Appendix A.
Write the corresponding method __ne__
, which checks if two FieldElement
objects are not equal to each other.
One of the tools we can use to make a finite field closed under addition, subtraction, multiplication, and division is something called modulo arithmetic.
We can define addition on the finite set using modulo arithmetic, which is something you probably learned when you first learned division. Remember problems like the one in Figure 11?
Whenever the division wasn’t even, there was something called the “remainder,” which is the amount left over from the actual division. We define modulo in the same way. We use the operator % for modulo:
Figure 12 shows another example.
Formally speaking, the modulo operation is the remainder after division of one number by another. Let’s look at another example with larger numbers:
If it helps, you can think of modulo arithmetic as “wraparound” or “clock” math. Imagine a problem like this:
The answer is 2 o’clock because (3 + 47) % 12 = 2 (see Figure 13).
We can also see this as “wrapping around” in the sense that we go past 0 every time we move ahead 12 hours.
We can perform modulo on negative numbers. For example, you can ask:
The answer is 11 o’clock:
The minute hand is also a modulo operation. For example, you can ask:
It will be 15 minutes past the hour:
Likewise, we can ask:
In this case, the answer is 0:
0 is another way of saying there is no remainder.
The result of the modulo (%) operation for minutes is always between 0 and 59, inclusive. This happens to be a very useful property as even very large numbers can be brought down to a relatively small range with modulo:
We’ll be using modulo as we define field arithmetic. Most operations in finite fields use the modulo operator in some capacity.
Remember that we need to define finite field addition such that we ensure the result is still in the set. That is, we want to make sure that addition in a finite field is closed.
We can use what we just learned, modulo arithmetic, to make addition closed. Let’s say we have a finite field of 19:
where a, b ∈ F_{19}. Note that the symbol ∈ means “is an element of.” In our case, a and b are elements of F_{19}.
Addition being closed means:
We denote finite field addition with +_{f} to avoid confusion with normal integer addition, +.
If we utilize modulo arithmetic, we can guarantee this to be the case. We can define a+_{f}b this way:
For example:
and so on.
We take any two numbers in the set, add, and “wrap around” the end to get the sum. We are creating our own addition operator here and the result is a bit unintuitive. After all, 11+_{f}17 = 9 just doesn’t look right because we’re not used to finite field addition.
More generally, we define field addition this way:
where a, b ∈ F_{p}.
We also define the additive inverse this way. a ∈ F_{p} implies that –_{f}a ∈ F_{p}:
Again, for clarity, we use –_{f} to distinguish field subtraction and negation from integer subtraction and negation.
In F_{19}:
which means that:
And that turns out to be true.
Similarly, we can do field subtraction:
where a, b ∈ F_{p}.
In F_{19}:
and so on.
Solve these problems in F_{57} (assume all +’s here are +_{f} and –’s here are –_{f}):
44 + 33
9 – 29
17 + 42 + 49
52 – 30 – 38
In the class FieldElement
we can now define __add__
and __sub__
methods.
The idea of these methods is that we want something like this to work:
>>>
from
ecc
import
FieldElement
>>>
a
=
FieldElement
(
7
,
13
)
>>>
b
=
FieldElement
(
12
,
13
)
>>>
c
=
FieldElement
(
6
,
13
)
>>>
(
a
+
b
==
c
)
True
In Python we can define what addition (or the + operator) means for our class with the __add__
method.
So how do we do this?
We combine what we learned with modulo arithmetic and create a new method of the class FieldElement
like so:
def
__add__
(
self
,
other
)
:
if
self
.
prime
!=
other
.
prime
:
raise
TypeError
(
'
Cannot add two numbers in different Fields
'
)
num
=
(
self
.
num
+
other
.
num
)
%
self
.
prime
return
self
.
__class__
(
num
,
self
.
prime
)
We have to ensure that the elements are from the same finite field, otherwise this calculation doesn’t have any meaning.
Addition in a finite field is defined with the modulo operator, as explained earlier.
We have to return an instance of the class, which we can conveniently access with self.__class__
.
We pass the two initializing arguments, num
and self.prime
, for the __init__
method we saw earlier.
Note that we could use FieldElement
instead of self.__class__
, but this would not make the method easily inheritable.
We will be subclassing FieldElement
later, so making the method inheritable is important here.
Write the corresponding __sub__
method that defines the subtraction of two FieldElement
objects.
Just as we defined a new addition (+_{f}) for finite fields that was closed, we can also define a new multiplication for finite fields that’s closed. By multiplying the same number many times, we can also define exponentiation. In this section, we’ll go through exactly how to define this using modulo arithmetic.
Multiplication is adding multiple times:
We can define multiplication on a finite field the same way. Operating in F_{19} once again:
We already know how to do the right side, and that yields a number within the F_{19} set:
Note that the second result is pretty unintuitive. We don’t normally think of 8 ⋅_{f} 17 = 3, but that’s part of what’s necessary in order to define multiplication to be closed. That is, the result of field multiplication is always in the set {0, 1, … p–1}.
Exponentiation is simply multiplying a number many times:
In a finite field, we can do exponentiation using modulo arithmetic.
In F_{19}:
Exponentiation again gives us counterintuitive results. We don’t normally think 7^{3} = 1 or 9^{12} = 7. Again, finite fields have to be defined so that the operations always result in a number within the field.
Solve the following equations in F_{97} (again, assume ⋅ and exponentiation are field versions):
95 ⋅ 45 ⋅ 31
17 ⋅ 13 ⋅ 19 ⋅ 44
12^{7} ⋅ 77^{49}
For k = 1, 3, 7, 13, 18, what is this set in F_{19}?
Do you notice anything about these sets?
The answer to Exercise 5 is why we choose to use finite fields with a prime number of elements. No matter what k you choose, as long as it’s greater than 0, multiplying the entire set by k will result in the same set as you started with.
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.
Now that we understand what multiplication should be in FieldElement
, we want to define the __mul__
method that overrides the *
operator.
We want this to work:
>>>
from
ecc
import
FieldElement
>>>
a
=
FieldElement
(
3
,
13
)
>>>
b
=
FieldElement
(
12
,
13
)
>>>
c
=
FieldElement
(
10
,
13
)
>>>
(
a
*
b
==
c
)
True
As with addition and subtraction, the next exercise is to make multiplication work for our class by defining the __mul__
method.
Write the corresponding __mul__
method that defines the multiplication of two finite field elements.
We need to define the exponentiation for FieldElement
, which in Python can be defined with the __pow__
method, overriding the **
operator.
The difference here is that the exponent is not a FieldElement
, so it has to be treated a bit differently.
We want something like this to work:
>>>
from
ecc
import
FieldElement
>>>
a
=
FieldElement
(
3
,
13
)
>>>
b
=
FieldElement
(
1
,
13
)
>>>
(
a
**
3
==
b
)
True
Note that because the exponent is an integer, instead of another instance of FieldElement
, the method receives the variable exponent
as an integer.
We can code it this way:
class
FieldElement
:
.
.
.
def
__pow__
(
self
,
exponent
)
:
num
=
(
self
.
num
*
*
exponent
)
%
self
.
prime
return
self
.
__class__
(
num
,
self
.
prime
)
This is a perfectly fine way to do it, but pow(self.num, exponent, self.prime)
is more efficient.
We have to return an instance of the class as before.
Why don’t we force the exponent to be a FieldElement
object?
It turns out that the exponent doesn’t have to be a member of the finite field for the math to work.
In fact, if it were, the exponents wouldn’t display the intuitive behavior we expect, like being able to add the exponents when we multiply with the same base.
Some of what we’re doing now may seem slow for large numbers, but we’ll use some clever tricks to improve the performance of these algorithms.
For p = 7, 11, 17, 31, what is this set in F_{p}?
The intuition that helps us with addition, subtraction, multiplication, and perhaps even exponentiation unfortunately doesn’t help us quite as much with division. Because division is the hardest operation to make sense of, we’ll start with something that should make sense.
In normal math, division is the inverse of multiplication:
7 ⋅ 8 = 56 implies that 56/8 = 7
12 ⋅ 2 = 24 implies that 24/12 = 2
And so on. We can use this as the definition of division to help us. Note that like in normal math, you cannot divide by 0.
In F_{19}, we know that:
This is very unintuitive, as we generally think of 2/_{f}7 or 7/_{f}5 as fractions, not nice finite field elements. Yet that is one of the remarkable things about finite fields: finite fields are closed under division. That is, dividing any two numbers where the denominator is not 0 will result in another finite field element.
The question you might be asking yourself is, how do I calculate 2/_{f}7 if I don’t know beforehand that 3⋅_{f}7 = 2? This is indeed a very good question; to answer it, we’ll have to use the result from Exercise 7.
In case you didn’t get it, the answer is that n^{(p–1)} is always 1 for every p that is prime and every n > 0. This is a beautiful result from number theory called Fermat’s little theorem. Essentially, the theorem says:
where p is prime.
Since we are operating in prime fields, this will always be true.
Because division is the inverse of multiplication, we know:
We can reduce the division problem to a multiplication problem as long as we can figure out what b^{–1} is. This is where Fermat’s little theorem comes into play. We know:
because p is prime. Thus:
or:
In F_{19}, this means practically that b^{18} = 1 , which means that b^{–1} = b^{17} for all b > 0.
So in other words, we can calculate the inverse using the exponentiation operator. In F_{19}:
This is a relatively expensive calculation as exponentiating grows very fast.
Division is the most expensive operation for that reason.
To lessen the expense, we can use the pow
function in Python, which does exponentiation.
In Python, pow(7,17)
does the same thing as 7**17
.
The pow
function, however, has an optional third argument that makes our calculation more efficient.
Specifically, pow
will modulo by the third argument.
Thus, pow(7,17,19)
will give the same result as 7**17%19
but do so faster because the modulo function is done after each round of multiplication.
Solve the following equations in F_{31}:
3 / 24
17^{–3}
4^{–4} ⋅ 11
Write the corresponding __truediv__
method that defines the division of two field elements.
Note that in Python 3, division is separated into __truediv__
and __floordiv__
. The first does normal division and the second does integer division.
One last thing that we need to take care of before we leave this chapter is the __pow__
method, which needs to handle negative exponents.
For example, a^{–3} needs to be a finite field element, but the current code does not take care of this case.
We want, for example, something like this to work:
>>>
from
ecc
import
FieldElement
>>>
a
=
FieldElement
(
7
,
13
)
>>>
b
=
FieldElement
(
8
,
13
)
>>>
(
a
**
3
==
b
)
True
Unfortunately, the way we’ve defined __pow__
simply doesn’t handle negative exponents, because the second parameter of the builtin Python function pow
is required to be positive.
Thankfully, we can use some math we already know to solve this. We know from Fermat’s little theorem that:
This fact means that we can multiply by a^{p–1} as many times as we want. So, for a^{–3}, we can do:
This is a way we can do negative exponents. A naive implementation would do something like this:
class
FieldElement
:
.
.
.
def
__pow__
(
self
,
exponent
)
:
n
=
exponent
while
n
<
0
:
n
+
=
self
.
prime

1
num
=
pow
(
self
.
num
,
n
,
self
.
prime
)
return
self
.
__class__
(
num
,
self
.
prime
)
We add until we get a positive exponent.
We use the Python builtin pow
to make this more efficient.
Thankfully, we can do even better.
We already know how to force a number out of being negative, using our familiar friend %
!
As a bonus, we can also reduce very large exponents at the same time given that a^{p–1} = 1.
This will make the pow
function not work as hard:
class
FieldElement
:
.
.
.
def
__pow__
(
self
,
exponent
)
:
n
=
exponent
%
(
self
.
prime

1
)
num
=
pow
(
self
.
num
,
n
,
self
.
prime
)
return
self
.
__class__
(
num
,
self
.
prime
)
In this chapter we learned about finite fields and how to implement them in Python. We’ll be using finite fields in Chapter 3 for elliptic curve cryptography. We turn next to the other mathematical component that we need for elliptic curve cryptography: elliptic curves.
No credit card required