Answering a PM from IpseDixit. For the benefit of posterity (and boring people to hell), let me answer this in the public forum.
Do you mean the division, in a Galois Field, of the element (Âµ^3), by the element (Âµ^3+Âµ+1) ? (Your use of the letter “x” here is a bit confusing - it suggests you may be talking about a polynomial in a general field).
If yes, you should realize that every nonzero element in a field has a “multiplicative inverse”.
First, let’s define the “neutral element for multiplication”. In a field, it is the unique element for which the following holds:
x * n = n * x = x
(you can think of this element n simply as “1”). The “1” element is unique and always exists in a field.
Now in a field, for every element x except zero, there exists an element y such that:
x * y = y * x = n
The element y is called the “multiplicative inverse” or “reciprocal” of x.
now when you and I are asked to do a “division”:
A = z/x
We are really asked to calculate A such that
x*A == z
Now let y (again) be the inverse of x; we can multiply both sides of the equation by y:
yxA == y*z
… and since y*x == n:
nA == yz
… and since n * x = x:
A = y*z
The bottom line is this: dividing by x is the same as multiplying with the multiplicative inverse of x.
We already know how to multiply; the question that remains is to determine the multiplicative inverse of a field element such as (Âµ^3+Âµ+1).
Remember that Âµ^i generates the entire set of nonzero field elements (Âµ being a generator)? And remember that both Âµ^0 and Âµ^(some number) are “1”.
The “some number” is equal to the number of elements in the field, minus one (this follows from the fact that it generates all nonzero elements). Lets call this cycle length L.
Now imagine a “cycle” of all nonzero elements: 1 -> Âµ -> Âµ^2 -> m^3 -> … -> 1
Each arrow in the cycle represents multiplication by Âµ.
A very central insight is this: we can UNDO the operation of “multiplication by Âµ” be making one step in the ‘wrong’ direction - but this is exactly equivalent to making (L-1) steps in the right direction, since we’re on an L-step cycle!
Similarly, multiplication by Âµ^i of a given element is exactly making i steps on the cycle; UNDOing the multiplication by Âµ^i is equal to multiplying by Âµ^(L-i).
Now the crucial last step: asking to find the multiplicative inverse of Âµ^i in a GF is exactly equal to asking: which element shall take me to Âµ^0 (==1!) upon multiplication? And when you like at it in this simple way, you will see it has to be Âµ^(L-i).
So, in essence, dividing in a GF is multiplying with an inverse, and finding the inverse is taking the power of an element to a known integer exponent (L-i). So to summarize:
Let a and b be field elements.
To calculate a/b:
(1) make sure b is not zero (in case b = 0, the question a*b==x we’re trying to find has either zero or many solutions - no good, most of the time!)
(2) Find the multiplicative inverse of b, as follows:
(2.1) Lookup b as a power-of-Âµ in a lookup table; say, b = Âµ^i
(2.2) Calculate the multiplicative inverse of Âµ which is easy: it is simply Âµ^(L-i) where L is the number of field elements minus one. Let’s call this Âµ^j.
(3) Multiply a by Âµ^j. This is easily done if a = 0 (the answer is 0). Otherwise, use the logarithm table once again: a * Âµ^j = Âµ^(log(a)) * Âµ^j = Âµ^(log(a)+(L-log(b))), or:
a/b = Âµ ^ (L+log(a)-log(b))
(Print that in a big font and hang it on your wall!)
… So now you may see why we’re keeping the “log” and “power” tables for doing GF(256) calculations in laser2wav: it is essential to hop between the “normal” polynomial (aÂµ^3 + bÂµ^2 + … + z) and power (Âµ^i) representations; they are EQUAL (in a mathematical sense), but the one is nice for adding and subtracting, and the other is nice for multiplying, dividing, and calculating powers.