Modern Cryptography: Theory and Practice
| Cryptography: Theory and Practice by Douglas Stinson CRC Press, CRC Press LLC ISBN: 0849385210 Pub Date: 03/17/95 |
Previous | Table of Contents | Next |
We previously discussed the Discrete Log problem in the multiplicative group
Let us think about how this could be done. The statement that
such that
It follows easily that
so we have that
Hence, solving for a as described above, we have that
Consequently, if we have an efficient method of computing the isomorphism φ, then we would have an efficient algorithm to compute discrete logs in
This method can be applied to the Discrete Log problem in any group G. If there is an efficient method of computing the isomorphism between H and
This discussion has shown that the Discrete Log problem may be easy or (apparently) difficult, depending on the representation of the (cyclic) group that is used. So it may be useful to look at other groups in the hope of finding other settings where the Discrete Log problem seems to be intractible.
Two such classes of groups are
- 1. the multiplicative group of the Galois field GF(pn)
- 2. the group of an elliptic curve defined over a finite field.
We will discuss these two classes of groups in the next subsections.
- 2. the group of an elliptic curve defined over a finite field.
5.2.1 Galois Fields
We have already discussed the fact that
DEFINITION 5.1 Suppose p is prime. Define
For
For
Suppose f(x), g(x),
if
Notice the resemblance of the definition of congruence of polynomials to that of congruence of integers.
We are now going to define a ring of polynomials modulo f(x) which we denote by
Suppose deg(f) = n. If we divide g(x) by f(x), we obtain a (unique) quotient q(x) and remainder r(x), where
and
This can be done by usual long division of polynomials. Hence any polynomial in
Now we define the elements of
Recall that
DEFINITION 5.2 A polynomial
where deg(f1) > 0 and deg (f2) > 0.
A very important fact is that
Here is an example to illustrate the concepts described above.
Example 5.6
Lets attempt to construct a field having eight elements. This can be done by finding an irreducible polynomial of degree three in
Now, f1 (x) is reducible, since
(remember that all coefficients are to be reduced modulo 2). Also, f4 is reducible since
However, f2(x) and f3(x) are both irreducible, and either one can be used to construct a field having eight elements.
Let us use f2(x), and thus construct the field
To compute a product of two field elements, we multiple the two polynomials together, and reduce modulo x3 + x + 1 (i.e., divide by x3 + x + 1 and find the remainder polynomial). Since we are dividing by a polynomial of degree three, the remainder will have degree at most two and hence is an element of the field.
Previous | Table of Contents | Next |
Copyright © CRC Press LLC