Cryptography: Theory and Practice by Douglas Stinson CRC Press, CRC Press LLC ISBN: 0849385210 Pub Date: 03/17/95 |
Previous | Table of Contents | Next |
For example, to compute (x2 + 1)(x2 + x + 1) in , we first compute the product in , which is x4 + x3 + x + 1. Then we divide by x3 + x + 1, obtaining the expression
Hence, in the field , we have that
Below, we present a complete multiplication table for the non-zero field elements. To save space, we write a polynomial a2x2 + a1 x + a0 as the ordered triple a2a1 a0.
Computation of inverses can be done by using a straightforward adaptation of the extended Euclidean algorithm.
Finally, the multiplicative group of the non-zero polynomials in the field is a cyclic group of order seven. Since 7 is prime, it follows that any non-zero field element is a generator of this group, i.e., a primitive element of the field.
For example, if we compute the powers of x, we obtain
which comprise all the non-zero field elements.
It remains to discuss existence and uniqueness of fields of this type. It can be shown that there is at least one irreducible polynomial of any given degree n ≥ 1 in . Hence, there is a finite field with pn elements for all primes p and all integers n ≥ 1. There are usually many irreducible polynomials of degree n in . But the finite fields constructed from any two irreducible polynomials of degree n can be shown to be isomorphic. Thus there is a unique finite field of any size pn (p prime, n ≥ 1), which is denoted by GF(pn). In the case n = 1, the resulting field GF(p) is the same thing as . Finally, it can be shown that there does not exist a finite field with r elements unless r = pn for some prime p and some integer n ≥ 1.
We have already noted that the multiplicative group (p prime) is a cyclic group of order p - 1. In fact, the multiplicative group of any finite field is cyclic: GF(pn)\{0} is a cyclic group of order pn - 1. This provides further examples of cyclic groups in which the discrete log problem can be studied.
In practice, the finite fields GF(2n) have been most studied. Both the Shanks and Pohlig-Hellman discrete logarithm algorithms work for fields GF(2n). The index calculus method can be modified to work in these fields. The precomputation time of the index calculus algorithm turns out to be
and the time to find an individual discrete log is
However, for large values of n (say n > 800), the discrete log problem in GF(2n) is thought to be intractible provided 2n - 1 has at least one large prime factor (in order to thwart a Pohlig-Hellman attack).
We begin by defining the concept of an elliptic curve.
DEFINITION 5.3 Let p > 3 be prime. The elliptic curve y2 = x3 + ax + b over , is the set of solutions to the congruence
where a, are constants such that 4a3 + 27b2 ≠ 0 (mod p), together with a special point O called the point at infinity.1
1Equation 5.1 can be used to define an elliptic curve over any field GF(pn), for p > 3 prime. An elliptic curve over GF(2n) or GF(3n) is defined by a slightly different equation.
An elliptic curve E can be made into an abelian group by defining a suitable operation on its points. The operation is written additively, and is defined as follows (where all arithmetic operations are performed in : Suppose
and
are points on E. If x2 = x1 and y2 = -y1, then ; otherwise P + Q = (x3, y3), where
and
Finally, define
for all P ∈ E. With this definition of addition, it can be shown that E is an abelian group with identity element (most of the verifications are tedious but straightforward, but proving associativity is quite difficult).
Note that inverses are very easy to compute. The inverse of (x, y) (which we write as -(x, y) since the group operation is additive) is (x, -y), for all (x, y) ∈ E.
Let us look at a small example.
Example 5.7
Let E be the elliptic curve y2 = x3 + x + 6 over . Lets first determine the points on E. This can be done by looking at each possible , computing x3 + x + 6 mod 11, and then trying to solve Equation 5.1 for y. For a given x we can test to see if z = x3 + x + 6 mod 11 is a quadratic residue by applying Eulers criterion. Recall that there is an explicit formula to compute square roots of quadratic residues modulo p for primes p ≡ 3 (mod 4). Applying this formula, we have that the square roots of a quadratic residue z are
The results of these computations are tabulated in Table 5.2.
Previous | Table of Contents | Next |
Copyright © CRC Press LLC