Author(s): Bruce Schneier

ISBN: 0471128457

Publication Date: 01/01/96

Previous | Table of Contents | Next |

Neither result is 1, so 2 is a generator.

To test whether 3 is a generator:

- 3
^{(11- 1)/5}(mod 11) = 9 - 3
^{(11- 1)/2}(mod 11) = 1

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(*q ^{n}*). All arithmetic is done modulo

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(2^{3}) has the following elements: 0, 1, *x, x* + 1, *x ^{2}*,

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 *x ^{2}* + 1 is irreducible over the integers. The polynomial

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(2^{n}) can be quickly implemented in hardware with linear-feedback shift registers. For that reason, computation over GF(2^{n}) is often quicker than computation over GF(*p*). Just as exponentiation is much more efficient in GF(2^{n}), so is calculating discrete logarithms [180, 181, 368, 379]. If you want to learn more about this, read [140].

For a Galois field GF(2^{n}), cryptographers like to use the trinomial *p* (*x*) = *x ^{n}* +

- 1, 3, 4, 6, 9, 15, 22, 28, 30, 46, 60, 63, 127, 153, 172, 303, 471, 532,
- 865, 900

There exists a hardware implementation of GF(2^{127}) where *p* (*x*) = *x ^{127}* +

Factoring a number means finding its prime factors.

- 10 = 2*5
- 60 = 2*2*3*5
- 252601 = 41*61*101
- 2
^{113}- 1 = 3391*23279*65993*1868569*1066818132868207

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:

**Number field sieve (NFS)**[953] (see also [952,16,279]). The**general number field sieve**is the fastest-known factoring algorithm for numbers larger than 110 digits or so [472,635]. It was impractical when originally proposed, but that has changed due to a series of improvements over the last few years [953]. The NFS is still too new to have broken any factoring records, but this will change soon. An early version was used to factor the ninth Fermat number: 2^{512}+ 1 [955,954].

Other factoring algorithms have been supplanted by the NFS:

**Quadratic sieve (QS)**[1257,1617,1259]. This is the fastest-known algorithm for numbers less than 110 decimal digits long and has been used extensively [440]. A faster version of this algorithm is called the multiple polynomial quadratic sieve [1453,302]. The fastest version of this algorithm is called the double large prime variation of the multiple polynomial quadratic sieve.**Elliptic curve method (ECM)**[957,1112,1113]. This method has been used to find 43-digit factors, but nothing larger.**Pollard’s Monte Carlo algorithm**[1254,248]. (This algorithm also appears in volume 2, page 370 of Knuth [863].)**Continued fraction algorithm.**See [1123,1252,863]. This algorithm isn’t even in the running.**Trial division.**This is the oldest factoring algorithm and consists of testing every prime number less than or equal to the square root of the candidate number.

Previous | Table of Contents | Next |