Editing Finite field arithmetic

{{Short description|Arithmetic in a field with a finite number of elements}}
In [[mathematics]], '''finite field arithmetic''' is [[arithmetic]] in a [[finite field]] (a [[field (mathematics)|field]] containing a finite number of [[element (mathematics)|element]]s) contrary to arithmetic in a field with an infinite number of elements, like the field of [[rational number]]s.

There are infinitely many different finite fields. Their [[Cardinality|number of elements]] is necessarily of the form ''p<sup>n</sup>'' where ''p'' is a [[prime number]] and ''n'' is a [[positive integer]], and two finite fields of the same size are [[isomorphism|isomorphic]]. The prime ''p'' is called the [[characteristic (algebra)|characteristic]] of the field, and the positive integer ''n'' is called the [[dimension (vector space)|dimension]] of the field over its [[characteristic (algebra)#Case of fields|prime field]].

Finite fields are used in a variety of applications, including in classical [[coding theory]] in [[linear block code]]s such as [[BCH code]]s and [[Reed–Solomon error correction]], in [[cryptography]] algorithms such as the [[Advanced Encryption Standard|Rijndael]] ([[Advanced Encryption Standard|AES]]) encryption algorithm, in tournament scheduling, and in the [[design of experiments]].

==Effective polynomial representation==
The finite field with ''p''<sup>''n''</sup> elements is denoted GF(''p''<sup>''n''</sup>) and is also called the '''Galois field''' of order ''p''<sup>''n''</sup>, in honor of the founder of finite field theory, [[Évariste Galois]]. GF(''p''), where ''p'' is a prime number, is simply the [[ring (algebra)|ring]] of integers [[Modular arithmetic|modulo]] ''p''. That is, one can perform operations (addition, subtraction, multiplication) using the usual operation on integers, followed by reduction modulo ''p''. For instance, in GF(5), {{nowrap|1=4 + 3 = 7}} is reduced to 2 modulo 5. Division is multiplication by the inverse modulo ''p'', which may be computed using the [[extended Euclidean algorithm]].

A particular case is [[GF(2)]], where addition is [[XOR gate|exclusive OR]] (XOR) and multiplication is [[AND gate|AND]]. Since the only invertible element is 1, division is the [[identity function]].

Elements of GF(''p''<sup>''n''</sup>) may be represented as [[polynomial]]s of degree strictly less than ''n'' over GF(''p''). Operations are then performed modulo ''m(x)'' where ''m(x)'' is an [[irreducible polynomial]] of degree ''n'' over GF(''p''), for instance using [[polynomial long division]]. Addition is the usual addition of polynomials, but the coefficients are reduced modulo ''p''. Multiplication is also the usual multiplication of polynomials, but with coefficients multiplied modulo ''p'' and polynomials multiplied modulo the polynomial ''m(x)''.<ref>{{harvnb|Hankerson|Vanstone|Menezes|2004|loc=p. 28}}</ref> This representation in terms of polynomial coefficients is called a [[monomial basis]] (a.k.a. 'polynomial basis').

There are other representations of the elements of GF(''p''<sup>''n''</sup>); some are isomorphic to the polynomial representation above and others look quite different (for instance, using matrices). Using a [[normal basis]] may have advantages in some contexts.

When the prime is 2, it is conventional to express elements of GF(''p''<sup>''n''</sup>) as [[binary numeral system|binary numbers]], with the coefficient of each term in a polynomial represented by one bit in the corresponding element's binary expression. Braces ( "{" and "}" ) or similar delimiters are commonly added to binary numbers, or to their hexadecimal equivalents, to indicate that the value gives the coefficients of a basis of a field, thus representing an element of the field. For example, the following are equivalent representations of the same value in a characteristic 2 finite field:

{| class="wikitable"
|-
! Polynomial
| ''x''<sup>6</sup> + ''x''<sup>4</sup> + ''x'' + 1
|-
! Binary
| {01010011}
|-
! Hexadecimal
| {53}
|}

== Primitive polynomials ==
There are many irreducible polynomials (sometimes called '''reducing polynomials''') that can be used to generate a finite field, but they do not all give rise to the same representation of the field.

A [[Monic polynomial|monic]] [[irreducible polynomial]] of degree {{math|''n''}} having coefficients in the finite field GF({{math|''q''}}), where {{math|1=''q'' = ''p''<sup>''t''</sup>}} for some prime {{mvar|p}} and positive integer {{mvar|t}}, is called a '''primitive polynomial''' if all of its roots are [[Primitive element (finite field)|primitive elements]] of GF({{math|''q<sup>n</sup>''}}).<ref>The roots of such a polynomial must lie in an [[extension field]] of GF({{mvar|q}}) since the polynomial is irreducible, and so, has no roots in GF({{mvar|q}}).</ref><ref>{{harvnb|Mullen|Panario|2013|loc=p. 17}}</ref> In the polynomial representation of the finite field, this implies that {{mvar|x}} is a primitive element. There is at least one irreducible polynomial for which {{mvar|x}} is a primitive element.<ref>{{Cite book|title=Design and Analysis of Experiments|date=August 8, 2005|publisher=John Wiley & Sons, Ltd|pages=716–720|doi=10.1002/0471709948.app1}}</ref> In other words, for a primitive polynomial, the powers of {{math|''x''}} generate every nonzero value in the field.

In the following examples it is best not to use the polynomial representation, as the meaning of {{math|''x''}} changes between the examples. The monic irreducible polynomial {{math|''x''<sup>8</sup> + ''x''<sup>4</sup> + ''x''<sup>3</sup> + ''x'' + 1}} over [[GF(2)]] is not primitive. Let {{math|''λ''}} be a root of this polynomial (in the polynomial representation this would be {{math|''x''}}), that is, {{math|1=''λ''<sup>8</sup> + ''λ''<sup>4</sup> + ''λ''<sup>3</sup> + ''λ'' + 1 = 0}}. Now {{math|1=''λ''<sup>51</sup> = 1}}, so {{math|''λ''}} is not a primitive element of GF(2<sup>8</sup>) and generates a multiplicative subgroup of order 51.<ref name=LN>{{harvnb|Lidl|Niederreiter|1983|loc=p. 553}}</ref> The monic irreducible polynomial {{math|''x''<sup>8</sup> + ''x''<sup>4</sup> + ''x''<sup>3</sup> + ''x''<sup>2</sup> + 1}} over [[GF(2)]] is primitive, and all 8 roots are generators of {{math|GF(2<sup>8</sup>)}}.

All GF(2<sup>8</sup>) have a total of 128 generators (see [[Primitive element (finite field)#Number of primitive elements|Number of primitive elements]]), and for a primitive polynomial, 8 of them are roots of the reducing polynomial. Having {{math|''x''}} as a generator for a finite field is beneficial for many computational mathematical operations.

==Addition and subtraction==
Addition and subtraction are performed by adding or subtracting two of these polynomials together, and reducing the result modulo the characteristic.

In a finite field with characteristic 2, addition modulo 2, subtraction modulo 2, and XOR are identical. Thus,

{| class="wikitable"
|-
! Polynomial
| (''x''<sup>6</sup> + ''x''<sup>4</sup> + ''x'' + 1) + (''x''<sup>7</sup> + ''x''<sup>6</sup> + ''x''<sup>3</sup> + ''x'') = ''x''<sup>7</sup> + ''x''<sup>4</sup> + ''x''<sup>3</sup> + 1
|-
! Binary
| {01010011} + {11001010} = {10011001}
|-
! Hexadecimal
| {53} + {CA} = {99}
|}

Under regular addition of polynomials, the sum would contain a term 2''x''<sup>6</sup>. This term becomes 0''x''<sup>6</sup> and is dropped when the answer is reduced modulo 2.

Here is a table with both the normal algebraic sum and the characteristic 2 finite field sum of a few polynomials:

{| class="wikitable"
 |-
 ! rowspan=2 | ''p''<sub>1</sub>
 ! rowspan=2 | ''p''<sub>2</sub>
 ! colspan=2 | ''p''<sub>1</sub> + ''p''<sub>2</sub> under...
 |-
 ! [[Polynomial ring|K[''x'']]]
 ! GF(2<sup>''n''</sup>)
 |- 
 | ''x''<sup>3</sup> + ''x'' + 1
 | ''x''<sup>3</sup> + ''x''<sup>2</sup>
 | 2''x''<sup>3</sup> + ''x''<sup>2</sup> + ''x'' + 1
 | ''x''<sup>2</sup> + ''x'' + 1
 |-
 | ''x''<sup>4</sup> + ''x''<sup>2</sup>
 | ''x''<sup>6</sup> + ''x''<sup>2</sup>
 | ''x''<sup>6</sup> + ''x''<sup>4</sup> + 2''x''<sup>2</sup>
 | ''x''<sup>6</sup> + ''x''<sup>4</sup>
 |-
 | ''x'' + 1
 | ''x''<sup>2</sup> + 1
 | ''x''<sup>2</sup> + ''x'' + 2
 | ''x''<sup>2</sup> + ''x''</tr>
 |-
 | ''x''<sup>3</sup> + ''x''
 | ''x''<sup>2</sup> + 1
 | ''x''<sup>3</sup> + ''x''<sup>2</sup> + ''x'' + 1
 | ''x''<sup>3</sup> + ''x''<sup>2</sup> + ''x'' + 1
 |-
 | ''x''<sup>2</sup> + ''x''
 | ''x''<sup>2</sup> + ''x''
 | 2''x''<sup>2</sup> + 2''x''
 | 0
 |}

In computer science applications, the operations are simplified for finite fields of characteristic 2, also called GF(2<sup>''n''</sup>) [[Galois field]]s, making these fields especially popular choices for applications.

==Multiplication==
<!-- Please do not change the examples to use a finite field besides x8 + x4 + x3 + x + 1; the Rijndael page links here and so people are expecting to get help figuring out Rijndael's finite field form this article -->
Multiplication in a finite field is multiplication [[Modular arithmetic|modulo]] an [[irreducible polynomial|irreducible]] reducing polynomial used to define the finite field. (I.e., it is multiplication followed by division using the reducing polynomial as the divisor&mdash;the remainder is the product.) The symbol "•" may be used to denote multiplication in a finite field.

=== Rijndael's (AES) finite field ===
[[Rijndael]] (standardised as AES) uses the characteristic 2 finite field with 256 elements, which can also be called the Galois field GF(2<sup>8</sup>). It employs the following reducing polynomial for multiplication:

:''x''<sup>8</sup> + ''x''<sup>4</sup> + ''x''<sup>3</sup> + ''x'' + 1.

For example, {53} • {CA} = {01} in Rijndael's field because

: {|
|-
| || (''x''<sup>6</sup> + ''x''<sup>4</sup> + ''x'' + 1)(''x''<sup>7</sup> + ''x''<sup>6</sup> + ''x''<sup>3</sup> + ''x'')
|-
| = || (''x''<sup>13</sup> + ''x''<sup>12</sup> + ''x''<sup>9</sup> + '''''x''<sup>7</sup>''') + (''x''<sup>11</sup> + ''x''<sup>10</sup> + '''''x''<sup>7</sup>''' + ''x''<sup>5</sup>) + (''x''<sup>8</sup> + '''''x''<sup>7</sup>''' + ''x''<sup>4</sup> + ''x''<sup>2</sup>) + ('''''x''<sup>7</sup>''' + ''x''<sup>6</sup> + ''x''<sup>3</sup> + ''x'')
|-
| = || ''x''<sup>13</sup> + ''x''<sup>12</sup> + ''x''<sup>9</sup> + ''x''<sup>11</sup> + ''x''<sup>10</sup> + ''x''<sup>5</sup> + ''x''<sup>8</sup> + ''x''<sup>4</sup> + ''x''<sup>2</sup> + ''x''<sup>6</sup> + ''x''<sup>3</sup> + ''x''
|-
| = || ''x''<sup>13</sup> + ''x''<sup>12</sup> + ''x''<sup>11</sup> + ''x''<sup>10</sup> + ''x''<sup>9</sup> + ''x''<sup>8</sup> + ''x''<sup>6</sup> + ''x''<sup>5</sup> + ''x''<sup>4</sup> + ''x''<sup>3</sup> + ''x''<sup>2</sup> + ''x''
|}

and

: {|
|-
| || ''x''<sup>13</sup> + ''x''<sup>12</sup> + ''x''<sup>11</sup> + ''x''<sup>10</sup> + ''x''<sup>9</sup> + ''x''<sup>8</sup> + ''x''<sup>6</sup> + ''x''<sup>5</sup> + ''x''<sup>4</sup> + ''x''<sup>3</sup> + ''x''<sup>2</sup> + ''x'' mod ''x''<sup>8</sup> + ''x''<sup>4</sup> + ''x''<sup>3</sup> + ''x''<sup>1</sup> + 1
|-
| = || (11111101111110 mod 100011011)
|-
| = || {3F7E mod 11B} = {01}
|-
| = || 1 (decimal)
|}

The latter can be demonstrated through [[long division]] (shown using binary notation, since it lends itself well to the task. Notice that [[exclusive or#Definition|exclusive OR]] is applied in the example and not arithmetic subtraction, as one might use in grade-school long division.):

          <u>               </u>
           11111101111110 (mod) 100011011
          <u>^100011011     </u>
           01110000011110
           ^<u>100011011    </u>
            0110110101110
            <u>^100011011   </u>
             010101110110
             <u>^100011011  </u>
              00100011010
               <u>^100011011  </u>
                000000001

(The elements {53} and {CA} are [[multiplicative inverse]]s of one another since their product is [[1 (number)|1]].)

Multiplication in this particular finite field can also be done using a modified version of the "[[multiplication algorithm#Russian peasant multiplication|peasant's algorithm]]". Each polynomial is represented using the same binary notation as above. Eight bits is sufficient because only degrees 0 to 7 are possible in the terms of each (reduced) polynomial.

This algorithm uses three [[Variable (programming)|variable]]s (in the computer programming sense), each holding an eight-bit representation. '''a''' and '''b''' are initialized with the multiplicands; '''p''' accumulates the product and must be initialized to 0.

At the start and end of the algorithm, and the start and end of each iteration, this [[invariant (computer science)|invariant]] is true: '''a''' '''b''' + '''p''' is the product. This is obviously true when the algorithm starts. When the algorithm terminates, '''a''' or '''b''' will be zero so '''p''' will contain the product.

* Run the following loop eight times (once per bit). It is OK to stop when '''a''' or '''b''' is zero before an iteration:
*# If the rightmost bit of '''b''' is set, exclusive OR the product '''p''' by the value of '''a'''. This is polynomial addition.
*# Shift '''b''' one bit to the right, discarding the rightmost bit, and making the leftmost bit have a value of zero. This divides the polynomial by '''x''', discarding the ''x''<sup>0</sup> term.
*# Keep track of whether the leftmost bit of '''a''' is set to one and call this value '''carry'''.
*# Shift '''a''' one bit to the left, discarding the leftmost bit, and making the new rightmost bit zero. This multiplies the polynomial by '''x''', but we still need to take account of '''carry''' which represented the coefficient of ''x''<sup>7</sup>.
*# If '''carry''' had a value of one, exclusive or '''a''' with the hexadecimal number <code>0x1b</code> (00011011 in binary). <code>0x1b</code> corresponds to the irreducible polynomial with the high term eliminated. Conceptually, the high term of the irreducible polynomial and '''carry''' add modulo 2 to 0.
* '''p''' now has the product

This algorithm generalizes easily to multiplication over other fields of characteristic 2, changing the lengths of '''a''', '''b''', and '''p''' and the value <code>0x1b</code> appropriately.

==Multiplicative inverse==
{{See also|Itoh–Tsujii inversion algorithm}}

The [[multiplicative inverse]] for an element '''a''' of a finite field can be calculated a number of different ways:

* By multiplying '''a''' by every number in the field until the product is one. This is a [[brute-force search]].
* Since the nonzero elements of GF(''p<sup>n</sup>'') form a [[finite group]] with respect to multiplication, {{nowrap|1=''a''{{i sup|''p<sup>n</sup>''−1}} = 1}} (for {{nowrap|''a'' ≠ 0}}),  thus the inverse of ''a'' is ''a''{{i sup|''p<sup>n</sup>''−2}}. This algorithm is a generalization of the [[modular multiplicative inverse]] based on  [[Fermat's little theorem]].
* Multiplicative inverse based on the [[Fermat's little theorem]] can also be interpreted using the multiplicative Norm function in [[finite field]]. This new viewpoint leads to an inverse algorithm based on the additive Trace function in [[finite field]].<ref>{{cite web |url=http://eprint.iacr.org/2020/482.pdf |title=A Trace Based {{math|GF(2<sup>''n''</sup>)}} Inversion Algorithm |first1=Haining|last1=Fan
|access-date=Jan 10, 2025 |archive-url=http://eprint.iacr.org/2020/482
|archive-date=May 6, 2020 }}</ref>
* By using the [[extended Euclidean algorithm]].
* By making [[logarithm]] and [[exponentiation]] tables for the finite field, subtracting the logarithm from ''p<sup>n</sup>''&nbsp;−&nbsp;1 and exponentiating the result.
* By making a [[modular multiplicative inverse]] table for the finite field and doing a lookup.
* By mapping to a [[Finite field arithmetic#Composite field|composite field]] where inversion is simpler, and mapping back.
* By constructing a special integer (in case of a finite field of a prime order) or a special polynomial (in case of a finite field of a non-prime order) and dividing it by ''a''.<ref>{{citation|last1=Grošek|first1= O.|last2=Fabšič|first2= T.|year= 2018|title= Computing multiplicative inverses in finite fields by long division|journal= Journal of Electrical Engineering|volume= 69|issue=5|pages=400–402|url= https://www.degruyter.com/downloadpdf/j/jee.2018.69.issue-5/jee-2018-0059/jee-2018-0059.pdf|doi=10.2478/jee-2018-0059|s2cid= 115440420|doi-access= free|bibcode= 2018JEE....69..400G}}</ref>

==Implementation tricks==
===Generator based tables===
When developing algorithms for Galois field computation on small Galois fields, a common performance optimization approach is to find a [[Generating set of a group#Finitely generated group|generator]] ''g'' and use the identity:

:<math>ab = g^{\log_g(ab)} = g^{\log_g(a) + \log_g (b)}</math>

to implement multiplication as a sequence of table look ups for the log<sub>''g''</sub>(''a'') and ''g''<sup>''y''</sup> functions and an integer addition operation. This exploits the property that every finite field contains generators. In the Rijndael field example, the polynomial {{nowrap|''x'' + 1}} (or {03}) is one such generator. A necessary but not sufficient condition for a polynomial to be a generator is to be [[irreducible polynomial|irreducible]].

An implementation must test for the special case of ''a'' or ''b'' being zero, as the product will also be zero.

This same strategy can be used to determine the multiplicative inverse with the identity:

:<math>a^{-1} = g^{\log_g\left(a^{-1}\right)} = g^{-\log_g(a)} = g^{|g| - \log_g(a)}</math>

Here, the [[order (group theory)|order]] of the generator, {{abs|''g''}}, is the number of non-zero elements of the field.  In the case of GF(2<sup>8</sup>) this is {{nowrap|1=2<sup>8</sup> − 1 = 255}}. That is to say, for the Rijndael example: {{nowrap|1=(''x'' + 1)<sup>255</sup> = 1}}.  So this can be performed with two look up tables and an integer subtract. Using this idea for exponentiation also derives benefit:

:<math>a^n = g^{\log_g\left(a^n\right)} = g^{n\log_g(a)} = g^{n\log_g(a) \pmod{|g|}}</math>

This requires two table look ups, an integer multiplication and an integer modulo operation. Again a test for the special case {{nowrap|1=''a'' = 0}} must be performed.

However, in cryptographic implementations, one has to be careful with such implementations since the [[CPU cache|cache architecture]] of many microprocessors leads to variable timing for memory access.  This can lead to implementations that are vulnerable to a [[timing attack]].

===Carryless multiply===
For binary fields GF(2<sup>''n''</sup>), field multiplication can be implemented using a carryless multiply such as [[CLMUL instruction set]], which is good for ''n'' ≤ 64. A multiplication uses one carryless multiply to produce a product (up to 2''n'' − 1 bits), another carryless multiply of a pre-computed inverse of the field polynomial to produce a quotient = ⌊product / (field polynomial)⌋, a multiply of the quotient by the field polynomial, then an xor: result = product &oplus; ((field polynomial) ⌊product / (field polynomial)⌋). The last 3 steps (pclmulqdq, pclmulqdq, xor) are used in the [[Barrett reduction]] step for fast computation of CRC using the [[x86]] pclmulqdq instruction.<ref>{{cite web |url=https://www.intel.com/content/dam/www/public/us/en/documents/white-papers/fast-crc-computation-generic-polynomials-pclmulqdq-paper.pdf |title=Fast CRC Computation for Generic Polynomials Using PCLMULQDQ Instruction |date=2009 |website=www.intel.com |access-date=2020-08-08}}</ref>

===Composite exponent===
When ''k'' is a [[composite number]], there will exist [[isomorphism]]s from a binary field GF(2<sup>''k''</sup>) to an extension field of one of its subfields, that is, GF((2<sup>''m''</sup>)<sup>''n''</sup>) where {{nowrap|1=''k'' = ''m'' ''n''}}. Utilizing one of these isomorphisms can simplify the mathematical considerations as the degree of the extension is smaller with the trade off that the elements are now represented over a larger subfield.<ref>{{cite web |url=http://www.ccs.neu.edu/home/alina/papers/tos-gf.pdf |title=Efficient Software Implementations of Large FiniteFieldsGF(2n) for Secure Storage Applications |website=www.ccs.neu.edu |access-date=2020-08-08}}</ref> To reduce gate count for hardware implementations, the process may involve multiple nesting, such as mapping from GF(2<sup>8</sup>) to GF(((2<sup>2</sup>)<sup>2</sup>)<sup>2</sup>).<ref>{{Cite web|url=https://github.com/bpdegnan/aes|title=bpdegnan/aes|website=GitHub}}</ref>

== Program examples ==
=== C programming example ===
Here is some [[C (programming language)|C]] code which will add and multiply numbers in the characteristic 2  finite field of order 2<sup>8</sup>, used for example by Rijndael algorithm or Reed–Solomon, using the [[Ancient Egyptian multiplication#Russian peasant multiplication|Russian peasant multiplication algorithm]]:

<syntaxhighlight lang="c">
/* Add two numbers in the GF(2^8) finite field */
uint8_t gadd(uint8_t a, uint8_t b) {
	return a ^ b;
}

/* Multiply two numbers in the GF(2^8) finite field defined 
 * by the modulo polynomial relation x^8 + x^4 + x^3 + x + 1 = 0
 * (the other way being to do carryless multiplication followed by a modular reduction)
 */
uint8_t gmul(uint8_t a, uint8_t b) {
	uint8_t p = 0; /* accumulator for the product of the multiplication */
	while (a != 0 && b != 0) {
        if (b & 1) /* if the polynomial for b has a constant term, add the corresponding a to p */
            p ^= a; /* addition in GF(2^m) is an XOR of the polynomial coefficients */

        if (a & 0x80) /* GF modulo: if a has a nonzero term x^7, then must be reduced when it becomes x^8 */
            a = (a << 1) ^ 0x11b; /* subtract (XOR) the primitive polynomial x^8 + x^4 + x^3 + x + 1 (0b1_0001_1011) – you can change it but it must be irreducible */
        else
            a <<= 1; /* equivalent to a*x */
        b >>= 1;
	}
	return p;
}
</syntaxhighlight>

This example has [[Timing attack|cache, timing, and branch prediction side-channel]] leaks, and is not suitable for use in cryptography.

=== D programming example ===
This [[D (programming language)|D]] program will multiply numbers in Rijndael's finite field and generate a [[Netpbm format#PGM example|PGM]] image:
<syntaxhighlight lang="D">
/**
Multiply two numbers in the GF(2^8) finite field defined
by the polynomial x^8 + x^4 + x^3 + x + 1.
*/
ubyte gMul(ubyte a, ubyte b) pure nothrow {
    ubyte p = 0;

    foreach (immutable ubyte counter; 0 .. 8) {
        p ^= -(b & 1) & a;
        auto mask = -((a >> 7) & 1);
        // 0b1_0001_1011 is x^8 + x^4 + x^3 + x + 1.
        a = cast(ubyte)((a << 1) ^ (0b1_0001_1011 & mask));
        b >>= 1;
    }

    return p;
}

void main() {
    import std.stdio, std.conv;
    enum width = ubyte.max + 1, height = width;

    auto f = File("rijndael_finite_field_multiplication.pgm", "wb");
    f.writefln("P5\n%d %d\n255", width, height);
    foreach (immutable y; 0 .. height)
        foreach (immutable x; 0 .. width) {
            immutable char c = gMul(x.to!ubyte, y.to!ubyte);
            f.write(c);
        }
}</syntaxhighlight>

This example does not use any branches or table lookups in order to avoid side channels and is therefore suitable for use in cryptography.

== See also ==
* [[Zech's logarithm]]

==References==
{{reflist}}

==Sources==
*{{citation|first1=Rudolf|last1=Lidl|first2=Harald|last2=Niederreiter|title=Finite Fields|year=1983|publisher=Addison-Wesley|isbn=0-201-13519-1}} (reissued in 1984 by Cambridge University Press {{isbn|0-521-30240-4}}).
*{{citation|first1=Gary L.|last1=Mullen|first2=Daniel|last2=Panario|title=Handbook of Finite Fields|year=2013|publisher=CRC Press|isbn=978-1-4398-7378-6}}
*{{citation|first1=Darrel|last1=Hankerson|first2=Scott|last2=Vanstone|first3=Alfred|last3=Menezes|title=Guide to Elliptic Curve Cryptography|year=2004|publisher=Springer|isbn=978-0-387-21846-5}}

== External links ==
* {{cite journal|first1=G. |last1=Gordon | title=Very simple method to find the minimum polynomial of an arbitrary nonzero element of a finite field|journal=  Electronics Letters| volume=12 | pages=663–664| year=1976 | number=25|doi=10.1049/el:19760508|bibcode=1976ElL....12..663G }}
* {{cite journal| first1=V. C. | last1=da Rocha | first2=G. | last2=Markarian| title=Simple method to find trace of arbitrary element of a finite field| journal= Electronics Letters| year=2006|volume=42|number=7|doi=10.1049/el:20060473|pages=423–325| bibcode=2006ElL....42..423D }}
* {{cite web|url=http://www.samiam.org/galois.html|title=AE's Galois field|first1=Sam |last1=Trenholme}}
* {{cite web|url=http://web.eecs.utk.edu/~plank/plank/papers/CS-07-593/|title=Fast Galois Field Arithmetic Library in C/C++|first1=James S.|last1=Planck|year=2007}}
* [[Wikiversity:Reed–Solomon codes for coders#Finite field arithmetic|Wikiversity: Reed–Solomon for Coders – Finite Field Arithmetic]]

[[Category:Arithmetic]]
[[Category:Finite fields|Arithmetic]]
[[Category:Articles with example D code]]
[[Category:Articles with example C code]]