Editing Finite field arithmetic (section)

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