北交大-密码学课件-第4章-数论初步和有限域.ppt

* Infinite fields are not of particular interest in the context of cryptography. However, finite fields play a crucial role in many cryptographic algorithms. It can be shown that the order of a finite field (number of elements in the field) must be a positive power of a prime, these are known as Galois fields denoted GF(p^n). We are most interested in the cases where either n=1 - GF(p), or p=2 - GF(2^n). * Start by considering GF(p) over the set of integers {0…p-1} with addition multiplication modulo p. This forms a “well-behaved” finite field. * Next introduce the interesting subject of polynomial arithmetic, using polynomials in a single variable x, with several variants as listed above. Note we are usually not interested in evaluating a polynomial for any particular value of x, which is thus referred to as the indeterminate. * Polynomial arithmetic includes the operations of addition, subtraction, and multiplication, defined in the usual way, ie add or subtract corresponding coefficients, or multiply all terms by each other. The examples are from the text, with working in Stallings Figure 4.3. * Consider variant where now when computing value of each coefficient do the calculation modulo some value, usually a prime. If the coefficients are computed in a field (eg GF(p)), then division on the polynomials is possible, and we have a polynomial ring. Are most interested in using GF(2) - ie all coefficients are 0 or 1, and any addition/subtraction of coefficients is done mod 2 (ie 2x is the same as 0x!), which is just the common XOR function. * Note that we can write any polynomial in the form of f(x) = q(x) g(x) + r(x), where division of f(x) by g(x) results in a quotient q(x) and remainder r(x). Can then extend the concept of divisors from the integer case, and show that the Euclidean algorithm can be extended to find the greatest common divisor of two polynomials whose coefficients are elements of a field. Define an irreducible (or prime) polynomial as one wit