Mapping to/from extension fields

[infogulch]

I've been using an extension field, but I'm finding it very awkward to convert integers to/from the field. This is the extension field I'm using:

const G = @GaloisField! 2^8 β

I can map integers to it with exponentiation syntax, and it is output after being reduced by the characteristic polynomial as expected:

julia> β^10
β^6 + β^5 + β^4 + β^2

However this doesn't work as a general interface to map integers into the field to cover its whole range. E.g. this definition fails because there's no way to map to the 0 value:

itog(i::Int) -> β^i
itog(0) == 1
itog(1) == β
...
itog(255) == 1
itog(256) == β

This is not exactly surprising (it's exponentiation after all), it's just not very complete. I don't believe any integer put into this itog can result in 0. So I'm currently using this definition of itog:

function itog(i)
	if iszero(i)
		0*β
	else
		β^i
	end
end

This works but is... lets say not very pretty.

I also tried to use G directly, but aiui G only represents the prime order field (2 in this case) and isn't useful for obtaining instances of the extension field.

---

Also, how do I convert extension field elements back into integers? Say, convert β^6 + β^5 + β^4 + β^2 from above back into Int(10)? I checked through the implementation and didn't see anything obvious (to me) that provides for this, so I ended up making a crude workaround by just enumerating all the extension field elements and storing the reverse mapping in a Dict like Dict(map(x -> (β^x, x), 0:255)). (This is where I discovered that I didn't map 0 correctly so it wasn't present in this Dict and caused problems until I used my itog function.)

---

To me these seem to be general 'API issues'. What do you think? Am I missing something?

[tkluck]

G does represent the full field 𝔽₂₅₆ but the only ring homomorphism ℤ → G is the one that maps onto 𝔽₂ ⊂𝔽₂₅₆, so that's what you get from conversions.

I do understand that that's not helpful if you are looking for some bijection between G and some range of integers. Because you are working in base-2, is it just the binary expansion that you are looking for (e.g. + is xor, etc)? If so, you can get this as follows:

julia> (β^6 + β^5 + β^4 + β^2).n # get the binary representation as an UInt8
0x74

julia> typeof(ans)
UInt8

julia> G(GaloisFields.Bits(), 0x74) # constructor that accepts a UInt8 bit mask for the expansion
β^6 + β^5 + β^4 + β^2

This should probably get a dedicated API rather than using the undocumented internals in this way. Let's keep this bug open for that.

[infogulch]

Ah, I'd seen the .n field but I didn't think to connect it to the 2-parameter G constructor to be able to round-trip integers directly via the binary expansion. Yes that works for me, thank you!

[infogulch]

I created these conversions for my use-case which made it kinda nice. I'm not sure how useful they would be in general.

Base.convert(::Type{<:UInt8}, gf::G) = gf.n
Base.convert(::Type{G}, i::UInt8) = G(GaloisFields.Bits(), i)

[tkluck]

@infogulch happy that it works for you. Having said that, I might advice against defining a conversion in that way: people will usually expect conversions to be canonical, but with these definitions, you get

convert(G, convert(Int, convert(UInt8, gf))) != gf

for many gf ∈ G.

I should really include functions for this in the module, and when I do I'll probably call it something like frombits and tobits. Or maybe I'll go with Base.reinterpret. Either of those might be a better choice for you as well?

[infogulch]

Yes you're probably right, those would work for me. I noticed that problem, but I'm just being careful so far. In my case, there's a nice bijection between the bit representation of the extension field and the integer range of UInt8, but I wonder how that would work with other prime bases? Take the 3^3 field from the Readme, is the bits representation of it dense below 27? Or would this only apply to binary extensions?

[tkluck]

This only applies to binary extensions. For a field like F_{3^3} we use a full byte for each of the three entries. That's wasteful if you're storing them or sending them over the wire, but I still think it's the right choice because we can use normal integer operations byte-by-byte, rather than having to shift/mask before every operation.

This problem doesn't exist for binary fields specifically because the intel instruction set has dedicated instructions for that case (because of their use in cryptography).

[infogulch]

I suspected that fields besides binary used a different representation. This design makes a lot of sense for operational performance, thanks for explaining.

The direction of my questioning about F_{3^3} is aimed along the lines of: Would a user of such a (not binary) extension field also want an easy to use bijection between their field and the integers? (Well, the integers less than the number of elements in the field.) I would guess yes; if so a general API to provide this mapping that is applicable to all fields including towers might be the best design for the package. That said, I suppose you're in a better position to answer the question of whether it would be valuable to such users and whether such an API would be reasonably implementable.

Due to their relationship to cryptography and potential need for performance, perhaps binary fields still deserve a dedicated API just to get UInt8's into and out of the field. But a general API might be good too.