Editing Finite field arithmetic (section)

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