Sage, Galois field and ModulusA finite field or Galois field (GF) has a finite number of elements, and has an order which is equal to a prime number (GF(p)) or to the power of a prime number (GF(\(2^p\))). For example, GF(\(2^n\)) has \(2^n\) elements, and its elements are known as binary polynomials (where the coefficients of the polynomial factors either are either zero or one value. In order to reduce a polynomial to a given size, we use a modulus polynomial, and which divides the output value. For GF(128), we can use a modulus of \(x^7 + x + 1\). So, let's take an example: \(a = x^3+ x^2 + 1\) \(b = x^6 + x^4+ x^3 + 1\) To add these together we get: \(a+b = x^3+ x^2 + 1 + x^6 + x^4+ x^3 + 1 = x^6 + x^4 + x^2 \) Now we can multiply them: \(a \times b = (x^3+ x^2 + 1) \times (x^6 + x^4+ x^3 + 1) = x^9 + x^7 + x^6 + x^3 + x^8 + x^6 + x^5 + x^2 + x^6 + x^4+ x^3 + 1 = x^9 + x^8 + x^7 + x^5 + x^4 + x^2 + 1 \) We now divide this value by the modulus. In this case for GF(128), the modulus is \(x^7 + x + 1\): x^2 + x + 1 ------------------------------------------------------- x^7 + x + 1 | x^9 + x^8 + x^7 + x^6 + x^5 + x^4 + x^2 + 1 x^9 + x^3 +x^2 ----------------------------------------------- x^8 + x^7 + x^6 + x^5 + x^4 + x^3 + 1 x^8 +x^2 + x ----------------------------------------------- x^7 + x^6 + x^5 + x^4 + x^3 + x^2 + x + 1 x^7 + x + 1 ----------------------------------------------- x^6 + x^5 + x^4 + x^3 + x^2 For GF(128), the result of \(a \times b\) is thus: \(a \times b = x^6 + x^5 + x^4 + x^3 + x^2 \) The code is: print (f"GF: {GF(128)}") F. And a sample run is: a = x^3 + x^2 + 1 b = x^6 + x^4 + x^3 + 1 Modulus = x^7 + x + 1 a - b = x^6 + x^4 + x^2 a + b = x^6 + x^4 + x^2 a * b = x^6 + x^5 + x^4 + x^3 + x^2 a / b = x^4 a^-1 = x^6 + x^3 + x^2 + x + 1 1/b = x^6 + x^5 + x^3 + x + 1 If we now use GF(256): print (f"GF: {GF(256)}") F. A sample run is: GF: Finite Field in z7 of size 2^7 Modulus = x^8 + x^4 + x^3 + x^2 + 1 a = x^3 + x^2 + 1 b = x^6 + x^4 + x^3 + 1 a - b = x^6 + x^4 + x^2 a + b = x^6 + x^4 + x^2 a * b = x^7 + x^6 + x^4 + x a / b = x^7 + x^5 + x^2 a^-1 = x^7 + x^5 + x^3 + x 1/b = x^7 + x^6 + 1 The default modulus of GF(256) is then: \(x^8 + x^4 + x^3 + x^2 + 1\) ModulusWe can list the default modulus with: F. This gives: GF(2) Modulus = x + 1 GF(4) Modulus = x^2 + x + 1 GF(8) Modulus = x^3 + x + 1 GF(16) Modulus = x^4 + x + 1 GF(32) Modulus = x^5 + x^2 + 1 GF(64) Modulus = x^6 + x^4 + x^3 + x + 1 GF(128) Modulus = x^7 + x + 1 GF(256) Modulus = x^8 + x^4 + x^3 + x^2 + 1 GF(512) Modulus = x^9 + x^4 + 1 |