|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 youll probably find one fast.
Computing in a Galois Field
Dont be alarmed; thats 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 doesnt 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 .
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. Well 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 .
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 . 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 .
Factoring a number means finding its prime factors.
The factoring problem is one of the oldest in number theory. Its simple to factor a number, but its 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|