# Expressing a given linear transformation in Galois Field GF(256) in terms of another linear transformation with a different reduction polynomial

Before giving a better and detailed description of what I ask, let me first tell why I need what I am looking for: Intel processors already provide instructions (AES-NI) for very efficient AES MixColumns state transformation. Actually existing instruction performs a couple of steps combined at once but it is easy to isolate MixColumn step and re-use it in isolated form. Standard AES MixColumn step being a linear transformation is represented in GF(256) with a 4x4 MDS matrix where reduction polynomial is x^4 + 1. This means that with Intel AES-NI, I can very very efficiently calculate the MDS matrix multiplication.

Suppose that I want to customize MixColumn step with a different linear transformation than the one AES standardizes. Then I will end up with a different MDS-custom (4x4) matrix as I will be using a different mixing polynomial and a different reduction polynomial.

Here is my primary goal: How can I implement my custom GF(256) matrix multiplication USING ALREADY AVAILABLE standard MDS matrix multiplication? Despite I am an engineer with some math ground university years are way too behind. Still I can "understand" basic matrix and/or GF algebra.

Maybe I should put it in that way: I am after implementing MDS-custom[4x4] * [s1, s2, s3, s4] with minimal computation which I hope would be possible if I express this transformation in a very simple-to calculate series of reusing MDS-original[4x4] * [s1, s2, s3, s4] results. Is there an algorithm to find the minimal-computation GF(256) transformation of a given transformation? MDS-custom = Some_Easy_To_Compute_Transformation_Of{MDS Standard AES}?

It would be pity if I cannot exploit standard MDS matrix multiplication (isolated) instructions for my custom MDS matrix. Well if my custom MDS matrix would be simply k*MDS where k is in {GF(256), x^4+1} re-use would be obvious.Case when k is a [1x4] column vector is also obvious. But, first, my custom MDS might not be in that simple a relation with original MDS matrix, and secondly, my reduction polynomial is not x^4+1? How should I proceed?

• I have a hunch that the math topic related with my question is "basis transformation in finite fields". I can read text on that topic but that is it. I cannot infer any implementation hints (my math's gotten worse in so many years) – mami Feb 1 '18 at 0:54