aeslua/gf.lua

local bit = require("bit");

-- finite field with base 2 and modulo irreducible polynom x^8+x^4+x^3+x+1 = 0x11d
local private = {};
local public = {};

local aeslua = require("aeslua");
aeslua.gf = public;

-- private data of gf
private.n = 0x100;
private.ord = 0xff;
private.irrPolynom = 0x11b;
private.exp = {};
private.log = {};

--
-- add two polynoms (its simply xor)
--
function public.add(operand1, operand2) 
	return bit.bxor(operand1,operand2);
end

-- 
-- subtract two polynoms (same as addition)
--
function public.sub(operand1, operand2) 
	return bit.bxor(operand1,operand2);
end

--
-- inverts element
-- a^(-1) = g^(order - log(a))
--
function public.invert(operand)
	-- special case for 1 
	if (operand == 1) then
		return 1;
	end;
	-- normal invert
	local exponent = private.ord - private.log[operand];
	return private.exp[exponent];
end

--
-- multiply two elements using a logarithm table
-- a*b = g^(log(a)+log(b))
--
function public.mul(operand1, operand2)
    if (operand1 == 0 or operand2 == 0) then
        return 0;
    end
	
    local exponent = private.log[operand1] + private.log[operand2];
	if (exponent >= private.ord) then
		exponent = exponent - private.ord;
	end
	return  private.exp[exponent];
end

--
-- divide two elements
-- a/b = g^(log(a)-log(b))
--
function public.div(operand1, operand2)
    if (operand1 == 0)  then
        return 0;
    end
    -- TODO: exception if operand2 == 0
	local exponent = private.log[operand1] - private.log[operand2];
	if (exponent < 0) then
		exponent = exponent + private.ord;
	end
	return private.exp[exponent];
end

--
-- print logarithmic table
--
function public.printLog()
	for i = 1, private.n do
		print("log(", i-1, ")=", private.log[i-1]);
	end
end

--
-- print exponentiation table
--
function public.printExp()
	for i = 1, private.n do
		print("exp(", i-1, ")=", private.exp[i-1]);
	end
end

--
-- calculate logarithmic and exponentiation table
--
function private.initMulTable()
	local a = 1;

	for i = 0,private.ord-1 do
    	private.exp[i] = a;
		private.log[a] = i;

		-- multiply with generator x+1 -> left shift + 1	
		a = bit.bxor(bit.lshift(a, 1), a);

		-- if a gets larger than order, reduce modulo irreducible polynom
		if a > private.ord then
			a = public.sub(a, private.irrPolynom);
		end
	end
end

private.initMulTable();

return public;