| Previous | Table of Contents | Next |
Neither result is 1, so 2 is a generator.
To test whether 3 is a generator:
Therefore, 3 is not a generator.
If you need to find a generator mod p, simply choose a random number from 1 to p - 1 and test whether it is a generator. Enough of them will be, so you’ll probably find one fast.
Computing in a Galois Field
Don’t be alarmed; that’s what we were just doing. If n is prime or the power of a large prime, then we have what mathematicians call a finite field . In honor of that fact, we use p instead of n. In fact, this type of finite field is so exciting that mathematicians gave it its own name: a Galois field, denoted as GF(p). (variste Galois was a French mathematician who lived in the early nineteenth century and did a lot of work in number theory before he was killed at age 20 in a duel.)
In a Galois field, addition, subtraction, multiplication, and division by nonzero elements are all well-defined. There is an additive identity, 0, and a multiplicative identity, 1. Every nonzero number has a unique inverse (this would not be true if p were not prime). The commutative, associative, and distributive laws are true.
Arithmetic in a Galois field is used a great deal in cryptography. All of the number theory works; it keeps numbers a finite size, and division doesn’t have any rounding errors. Many cryptosystems are based on GF(p), where p is a large prime.
To make matters even more complicated, cryptographers also use arithmetic modulo irreducible polynomials of degree n whose coefficients are integers modulo q, where q is prime. These fields are called GF(qn). All arithmetic is done modulo p (x), where p (x) is an irreducible polynomial of degree n.
The mathematical theory behind this is far beyond the scope of the book, although I will describe some cryptosystems that use it. If you want to try to work more with this, GF(23) has the following elements: 0, 1, x, x + 1, x2, x2 + 1, x2 + x, x2 + x + 1. There is an algorithm for computing inverses in GF(2n) that is suitable for parallel implementation [421].
When talking about polynomials, the term “prime” is replaced by “irreducible.” A polynomial is irreducible if it cannot be expressed as the product of two other polynomials (except for 1 and itself, of course). The polynomial x2 + 1 is irreducible over the integers. The polynomial x3 + 2x2 + x is not; it can be expressed as x (x + 1)(x + 1).
A polynomial that is a generator in a given field is called primitive; all its coefficients are relatively prime. We’ll see primitive polynomials again when we talk about linear-feedback shift registers (see Section 16.2).
Computation in GF(2n) can be quickly implemented in hardware with linear-feedback shift registers. For that reason, computation over GF(2n) is often quicker than computation over GF(p). Just as exponentiation is much more efficient in GF(2n), so is calculating discrete logarithms [180, 181, 368, 379]. If you want to learn more about this, read [140].
For a Galois field GF(2n), cryptographers like to use the trinomial p (x) = xn + x + 1 as the modulus, because the long string of zeros between the xn and x coefficients makes it easy to implement a fast modular multiplication [183]. The trinomial must be primitive, otherwise the math does not work. Values of n less than 1000 [1649, 1648] for which xn + x + 1 is primitive are:
There exists a hardware implementation of GF(2127) where p (x) = x127 + x + 1 [1631, 1632, 1129]. Efficient hardware architectures for implementing exponentiation in GF(2n) are discussed in [147].
Factoring a number means finding its prime factors.
The factoring problem is one of the oldest in number theory. It’s simple to factor a number, but it’s time-consuming. This is still true, but there have been some major advances in the state of the art.
Currently, the best factoring algorithm is:
Other factoring algorithms have been supplanted by the NFS:
| Previous | Table of Contents | Next |