Solving a quadratic equation in a prime (finite) field
A finite field is a bounded set of mathematical entities -- often numbers,
but not exclusively
-- that obey fundamental rules of arithmetic.
Of course, ordinary real numbers obey the everyday rules of arithmetic,
and so constitute a field. However, it's easy to do arithmetic on real
numbers because there's such a lot of them.
The defining feature of a finite field is
that its arithmetic yields results that lie entirely within the limited
set of objects that comprise the field.
A cornerstone of the manipulation of finite fields
is the use of modular arithmetic.
Finite fields, sometimes referred to as Galois fields, are a key feature of coding theory, communications theory, and cryptography.
If you've never seen finite fields before, then I have an overview article. This present article only concerns numeric fields, which must by their very nature have a prime number of elements starting at zero. Such fields are often called prime fields, and denoted "GF(n)" where n is the number of members of the field. All arithmetic in GF(5), for example, is carried out modulo 5, so the entire set of field members is {0, 1, 2, 3, 4}.
In principle, arithmetic on finite fields is simple -- at least with small fields -- but there are a number of things to watch out for.
Although addition and multiplication can be defined in terms of simple modular arithmetic, division is more complicated. We can't do division by applying a regular integer division and then taking the remainder -- we must find a multiplicative inverse (more on this below).
There are no negative numbers in a prime field -- subtracting a larger number from a smaller one must yield a positive number.
Square (and higher) roots don't behave the same as they do in regular arithmetic -- for example, a number can have two positive square roots.
In this article I use as an example solving the solution of a simple quadratic equation in GF(5). Not only does this demonstrate the relevant arithmetic, but such solutions are frequently necessary in applications of finite fields. For example, correcting errors in data encoded using a Reed-Solomon code amounts, in effect, to finding solutions to a polynomial equation that indicates the location of the errors in the data block.
The problem
Suppose we want to solve the following quadratic equation for r:
2 r2 + r + 4 = 0
For real numbers, and in a finite field, we can use the traditional 'quadratic formula', that everybody learns by heart in high school:
r = [ -b ± √ (b2 - 4ac) ] / 2a,
where a, b, and c are the coefficients of the three terms in the quadratic expression. In my example
a=2,
b=1,
c=4.
To use this formula with a finite field, all arithmetic must be carried out using the rules of that field. In GF(5), fundamentally this means doing all arithmetic modulo 5, and using particular procedures for division and the taking of square roots.
Understanding the arithmetic of GF(5)
Let's start by constructing the multiplication table for GF(5). This is just ordinary integer multiplication, with the result reduced modulo 5. It helps to write out the whole table (which is, of course, only practicable in a small field like GF(5)), because we will use the table to pick out the inverses and square roots later. Here's the table:
x | 0 1 2 3 4 --------------- 0 | 0 0 0 0 0 1 | 0 1 2 3 4 2 | 0 2 4 1 3 3 | 0 3 1 4 2 4 | 0 4 3 2 1
To be able to divide, we need the multiplicative inverse of each number in the field, that is, the number by which can it can be multiplied to give 1. We can just pick the row and column corresponding to each 1 in the body of the multiplication table. I will use the notation inv(a) to indicate the multiplicative inverse for a. Here are the relevant values for GF(5), taken from the multiplication table.
a | inv(a) --------------- 0 | - 1 | 1 2 | 3 3 | 2 4 | 4
Notice that, while 1 is its own inverse in any field, in GF(5) 4 is also self-inverse.
Note:
For larger fields, there is an algorithmic method for finding inverse called the extended Euclidean method.
Now let's work out which numbers in GF(5) have square roots -- not all of them do. Start by constructing a table of squares. These are just the values on the diagonal of the multiplication table.
a | sqr(a) --------------- 0 | 0 1 | 1 2 | 4 3 | 4 4 | 1
From this squares table, we can see that only 1 and 4 have non-zero square roots, and that 4 has two square roots: 2 and 3. So here is the square root table:
a | sqrt(a) --------------- 0 | 0 1 | 1 4 | 2,3
There's nothing particularly striking about a number having two square roots -- after all, real numbers have two square roots. The square roots of 4 (in real numbers) are ±2. In GF(5) it's easy to see that 22=4, but 32 is also 4, because (3 x 3) mod 5 = 4. Note that in modulo-5 arithmetic, 3 is congruent to -2, which is another way of understanding why the square of 3 is 4. Nevertheless, a number's having two positive square roots can seem a little disconcerting.
Similarly, there's nothing striking about a number having no square root in GF(5). -2, for example, is a member of the real number field, but has no real-number square root. The operation of square root does not have to apply to every number in the field in order to be valid. This does mean that not every conceivable quadration equation in GF(5) has solutions in GF(5) -- just as X2 = -1 has no solutions in the real numbers.
So now we have all the arithmetic we need, to evaluate the quadratic formula in GF(5).
Evaluating the quadratic formula in GF(5)
The denominator of the quadratic formula is 2a, which is 2 x 2 = 4. No adjustment has to be made for GF(5) here. However, in order to divide by 4 we must multiply by the inverse of 4. From the table of inverses above we see that the inverse of 4 is 4, so to divide by 4 in GF(5) we must multiply by 4.
The quadratic formula also has a -b term, but there are no negative numbers in GF(5). In this example -b is -1, which is congruent to 4 in modulo-5 arithmetic (becuse 5 - 1 = 4).
Note:
Some calculators, and some programming languages, treat the modular reduction of a negative number as giving a negative result. While a case can be made for this interpretation, it's unhelpful with finite fields, and a negative result must be shifted to lie in the range of the field.
So we can re-write the quadratic formula like this:
r = [ 4 ± √ (42 - 4 x 2 x 4) ] * 4,
Using the tables above, or just modular arithmetic, we can evalute the argument of the square root to be(42 - 4 x 2 x 4) mod 5 = 4.
4 has a square root in GF(5) -- in fact it has two: 2 and 3. These different square roots won't give different solutions to the quadratic equation. Why? a + 2 is essentially the same as a - 3, and a + 3 the same as a - 2 (in GF(5)). We don't get additional solutions here, any more than we get additional solutions in real numbers from the quadratic formula, by taking the negative square root as well as the positive.
So we have
r = [ 4 ± 2 ] * 4,
Doing this arithmetic modulo 5 we arrive at the two solutions, r = 3 and r = 4.
We can check that these two values do, in fact, satisfy the original quadratic equation, by substituting them into the left-hand side of the equation and checking that it evaluates to zero. Of course, the substituted formula has to be evaluated using GF(5) arithmetic throughout.
Summary
The application of the quadratic formula demonstrates how mathematical operations originally defined on real numbers can equally be applied to finite fields. However, when doing the arithmetic manually, care has to be taken to apply the arithmetic rules of the field rigorously.