Cryptography: Finite Fields of the Form GF(p)

•Finite fields play a crucial role in many cryptographic algorithms.

•The order of a finite field (number of elements in the field) must be a power of a prime pn, where n is a positive integer.

•The finite field of order pn is generally written GF(pn); GF stands for Galois field.

•For a given prime, p, we define the finite field of order p, GF(p), as the set Zp of integers {0, 1, … , p - 1} together with the arithmetic operations modulo p.

•Any integer in Zn has a multiplicative inverse if and only if that integer is relatively prime to n

•If n is prime, then all of the nonzero integers in Zn are relatively prime to n, and therefore there exists a multiplicative inverse for all of the nonzero integers in Zn.

•For Zp we can add the following properties

•Because w is relatively prime to p, if we multiply all the elements of Zp by w, the resulting residues are all of the elements of Zp permuted.

•Thus, exactly one of the residues has the value 1.

•Therefore, there is some integer in Zp that, when multiplied by w, yields the residue 1.

•That integer is the multiplicative inverse of w, designated w-1. 

Finite Fields of the Order p

•Zp is in fact a finite field.

•We can write (º this denotes congruence)

•if(a * b) º (a * c)(mod p) then b º c(mod p)

•Multiplying both sides of Equation by the multiplicative inverse of a, we have

  ((a-1) * a * b) º ((a-1) * a * c)(modp)

        b  º c(modp)

•

•