2 Description of finite field mathematics
This chapter covers
- Fundamentals of finite fields
- Subroutines for modular operations
- Concept of quadratic residues
- Computing square roots mod n
Fields are mathematical objects that obey specific rules. Finite fields have a fixed number of objects. This chapter introduces finite fields over prime numbers and the code we will need in the rest of the book to manipulate these objects.
In this chapter, I’ll start at the bottom of finite field mathematics by using prime numbers to define the core concept of a finite field. Every formula in this book depends on prime numbers to create a finite field. I’ll first go over the rules of finite fields we need to know and then introduce simple subroutines that exploit the GNU Multiple Precision Arithmetic Library (GMP library) to implement some of those rules. The library is exceptionally useful for very large integers used in cryptographic protocols. You can learn about retrieving the GMP library and its documentation in appendix A.
The general equation of an elliptic curve is given by
\[y^2+a_1x y + a_3 y=x^3+a_2 x^2 + a_4 x + a_6\]
Fortunately, we don’t need the general curve because we work over finite fields. The ordinary equation used throughout this book has \(a_1=a_2=a_3=0\):
\[y^2=x^3+a_4x+a_6\]