section_path: Integer powers in algebra/Finite fields
section_name: Finite fields
paragraph_text: Finite fields
  
  A field is an algebraic structure in which multiplication, addition, subtraction, and division are defined and satisfy the properties that multiplication is associative and every nonzero element has a multiplicative inverse. This implies that exponentiation with integer exponents is well-defined, except for nonpositive powers of 0. Common examples are the field of complex numbers, the real numbers and the rational numbers, considered earlier in this article, which are all infinite.
  
  A finite field is a field with a finite number of elements. This number of elements is either a prime number or a prime power; that is, it has the form q = p k, {\displaystyle q=p^{k},} where p is a prime number, and k is a positive integer. For every such q, there are fields with q elements. The fields with q elements are all isomorphic, which allows, in general, working as if there were only one field with q elements, denoted F q. {\displaystyle \mathbb {F} _{q}.}
  
  One has
  
  for every x ∈ F q. {\displaystyle x\in \mathbb {F} _{q}.}
  
  A primitive element in F q {\displaystyle \mathbb {F} _{q}} is an element g such that the set of the q − 1 first powers of g (that is, { g 1 = g, g 2, …, g p − 1 = g 0 = 1 } {\displaystyle \{g^{1}=g,g^{2},\ldots,g^{p-1}=g^{0}=1\}}) equals the set of the nonzero elements of F q. {\displaystyle \mathbb {F} _{q}.} There are φ (p − 1) {\displaystyle \varphi (p-1)} primitive elements in F q, {\displaystyle \mathbb {F} _{q},} where φ {\displaystyle \varphi } is Euler's totient function.
  
  In F q, {\displaystyle \mathbb {F} _{q},} the freshman's dream identity
  
  is true for the exponent p. As x p = x {\displaystyle x^{p}=x} in F q, {\displaystyle \mathbb {F} _{q},} It follows that the map
  
  is linear over F q, {\displaystyle \mathbb {F} _{q},} and is a field automorphism, called the Frobenius automorphism. If q = p k, {\displaystyle q=p^{k},} the field F q {\displaystyle \mathbb {F} _{q}} has k automorphisms, which are the k first powers (under composition) of F. In other words, the Galois group of F q {\displaystyle \mathbb {F} _{q}} is cyclic of order k, generated by the Frobenius automorphism.
  
  The Diffie–Hellman key exchange is an application of exponentiation in finite fields that is widely used for secure communications. It uses the fact that exponentiation is computationally inexpensive, whereas the inverse operation, the discrete logarithm, is computationally expensive. More precisely, if g is a primitive element in F q, {\displaystyle \mathbb {F} _{q},} then g e {\displaystyle g^{e}} can be efficiently computed with exponentiation by squaring for any e, even if q is large, while there is no known computationally practical algorithm that allows retrieving e from g e {\displaystyle g^{e}} if q is sufficiently large.