3.1.1.6.1.2 Multiplication and Division

Multiplication in the finite field can be performed in one of the following two ways:

  • Using logarithms

  • Multiplying the two polynomials and reducing the result with an irreducible polynomial to bring it back in the finite field

It is simpler to perform multiplications and divisions using logarithms, as it involves a table lookup for the log function, followed by an addition of the polynomials, followed by an exponent function.

Multiplication equation

Figure 7: Multiplication equation

Division is performed similarly using logarithms and exponentiation.

Division equation

Figure 8: Division equation

Since the discrete logarithm of an element in the finite field is a regular integer, the addition in the exponent is a regular addition modulo 2n.

Pseudo-code example:

 BYTE Div(const int x, const int y)
 {
   if (y==0) return 0;
   if (x==0) return 0;
  
   return (BYTE)(m_ffExp2Poly[m_ffPoly2Exp[x] - m_ffPoly2Exp[y] + (MAX_FIELD_SIZE-1)]);
 }
  
 BYTE Mul(const int x, const int y)
 {
   if (((x-1) | (y-1)) < 0)
     return (0);
  
   return (BYTE)(m_ffExp2Poly[m_ffPoly2Exp[x] + m_ffPoly2Exp[y]]);
 }

Where m_ffExp2Poly and m_ffPoly2Exp are exponent and log tables respectively.