Editing Finite field arithmetic (section)

=== 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.