Extension for Galois Field of order 2

New to Julia
1

Hello,
New to Julia and to Galois Field, I would like to calculate in GF(2^8). Using Nemo, here is what I start with:

julia> using Nemo

Welcome to Nemo version 0.33.7

Nemo comes with absolutely no warranty whatsoever

julia> R, x = FiniteField(2, 8, "x")
(Finite field of degree 8 over F_2, x)

Then I need to use elements of GF(256). I tried to cast them from integers like this:

julia> R(3)
1

but it doesn’t seem to work as I expected (output 3). How can I input GF(256) values? Should I use polynomial expressions only? If so, is there a way to convert Int to polynomial expression?
thanks for your help,
B.R.

2

I found this way to do it. I post it if anyone is interested (or to get expert’s point of view). You will find respectively the GF-> Int conversion, the Int → GF conversion (restricted to GF(256) but change UInt8 to greater if needed), and a simple test.

function Int(a::fqPolyRepFieldElem)
    dum = 0
    if !iszero(a)
        for i=a.length-1:-1:0
            if coeff(a,i)>0
                dum+=2^i
            end
        end
    end
    return dum
end

function GF(a::Integer,F::fqPolyRepField)
    b = bitstring(UInt8(mod(a,2^8)))
    res = F(0);
    for i=1:8
        if b[i]=='1'

            res+=(gen(R))^(8-i)
        end
    end
    return res
end

R, x = FiniteField(2, 8, "x")
a = 253
agf = GF(a,R)
Int(agf)==a

thanks!

3

The element 3 is the same as 1 in GF(256) (or any GF(2^n)).

5

To me GF(2^p) has 2^p elements, not only 2 like in GF(2), no?

6

Sure. I did not claim that there are only two elements. But one has 1 + 1 = 0 in \mathrm{GF}(2^n) for any n \geq 1 (all these fields contain \mathrm{GF}(2) or in other words, have characteristic 2). In particular 3 = 1 + 1 + 1 = 1 in \mathrm{GF}(2^n).

7

I agree with your 1+1+1 = 1. But how do you manipulate other elements than 0 and 1 in GF(256)? can you write an element in GF(256) that is not 0 or 1? (it seems that there is no other way than the form using the root of the irreducible polynomial, am I correct?)
I thought the integer representation could also be useful (and quite common), hence my 2 conversion functions, but I do not know if this was already provided by Nemos?

8

Yes, one just writes an arbitrary element using powers of x, e.g., 1 + x + x^2 + x^7. What I have seen in a more applied context is something like 11001101 to represent the element a = 1 + x + 0*x^2 + 0*x^3 + x^4 + x^5 + 0*x^6 + 1*x^7 (or maybe reversed, I don’t remember). I have never seen the “integer representation” in a math paper before. The “integer representation” has the big disadvantage, that it does not respect addition nor multiplication. It is just a bijection from \{1,\dotsc,2^n\} \to \mathrm{GF}(2^n).

9

Yes the integer representation might seem strange when looking at the multiplication and addition tables, but it is quite convenient to write C programs for example. It just a data format trick, nothing to be worth describing in an article :slight_smile: You can see it also in matlab, so I thought it might be the same.
However thank you for your confirmation and your replies!