Editing Finite field (section)

=== Discrete logarithm ===

If <math>a</math> is a primitive element in <math>\mathrm{GF}(q)</math>, then for any non-zero element <math>x</math> in <math>F</math>, there is a unique integer <math>n</math> with <math>0 \le n \le q-2</math> such that <math>x=a^n</math>.
This integer <math>n</math> is called the [[discrete logarithm]] of <math>x</math> to the base <math>a</math>.

While <math>a^n</math> can be computed very quickly, for example using [[exponentiation by squaring]], there is no known efficient algorithm for computing the inverse operation, the discrete logarithm. This has been used in various [[cryptographic protocol]]s, see ''[[Discrete logarithm]]'' for details.

When the nonzero elements of <math>\mathrm{GF}(q)</math> are represented by their discrete logarithms, multiplication and division are easy, as they reduce to addition and subtraction modulo <math>q-1</math>. However, addition amounts to computing the discrete logarithm of <math>a^m+a^n</math>. The identity 
<math display="block">a^m+a^n=a^n\left(a^{m-n}+1\right)</math>
allows one to solve this problem by constructing the table of the discrete logarithms of <math>a^n+1</math>, called [[Zech's logarithm]]s, for <math>n=0,\ldots,q-2</math> (it is convenient to define the discrete logarithm of zero as being <math>-\infty</math>).

Zech's logarithms are useful for large computations, such as [[linear algebra]] over medium-sized fields, that is, fields that are sufficiently large for making natural algorithms inefficient, but not too large, as one has to pre-compute a table of the same size as the order of the field.