Applied Cryptography, Second Edition: Protocols, Algorthms, and Source Code in C (cloth)
(Publisher: John Wiley & Sons, Inc.)
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(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:

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(2127) where p (x) = x127 + x + 1 [1631, 1632, 1129]. Efficient hardware architectures for implementing exponentiation in GF(2n) are discussed in [147].

11.4 Factoring

Factoring a number means finding its prime factors.

10 = 2*5
60 = 2*2*3*5
252601 = 41*61*101
2113 - 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: 2512 + 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
[an error occurred while processing this directive]