![]() |
|
|||
![]() |
![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() |
![]() |
|
![]() |
[an error occurred while processing this directive]
For example, to compute (x2 + 1)(x2 + x + 1) in Hence, in the field 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 We have already noted that the multiplicative group 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). 5.2.2 Elliptic CurvesWe 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 where a,
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 and are points on E. If x2 = x1 and y2 = -y1, then 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 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 The results of these computations are tabulated in Table 5.2.
Copyright © CRC Press LLC
![]() |
![]() |
![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() |
![]() |
![]() |