Repository files navigation

Build Status	Test coverage

This module defines types representingfinite fields. Itsupports both fields of prime order and of prime power order.

The easiest way to create Galois fields is with the@GaloisField and@GaloisField!macros. Typically, you use the former for a field of prime order and the latterfor a field of prime power order. In the prime power case, you pass a displayname / variable name for the primitive element.

using GaloisFieldsconst F=@GaloisField29# ℤ/29ℤconst G=@GaloisField!27 β# degree-3 extension of ℤ/3ℤ; multiplicatively generated by βF(2)^29==F(2)β^27== β

The exclamation mark! is intended to convey that the macro has a side-effect:for example, in the code above, it assigns a variable calledβ.

The macros also accept special symbols for specifying the field. This is moredifficult to type (docs) but more elegant to read:

const F=@GaloisField ℤ/29ℤconst G=@GaloisField 𝔽₂₇ β

If you want to pass your own generator for the representation of a fieldof orderq = p^n, you can:

const F=@GaloisField! 𝔽₃ β^2+ β+2β^2+ β+2==0

Lastly, there's also function interfaces in cases where macros are notappropriate:

const F=GaloisField(29)# ℤ/29ℤconst G, β=GaloisField(81,:β)# degree-4 extension of ℤ/3ℤconst G, β=GaloisField(3,4,:β)# same; avoid having to factorize 81const F, β=GaloisField(3,:β=> [2,0,0,2,1])# same; pass our own custom minimum polynomial

In some cases, we make use ofZech's logarithms for faster multiplications.By default, this happens if the order of the field is less than2^16, if thecharacteristic is not 2, and if the primitive element is also a multiplicativegenerator. However, you can override this by calling either of

GaloisFields.enable_zech_multiplication(F)GaloisFields.disable_zech_multiplication(F)

before doing any multiplication operation. If you call this function on afield whose primitive element isnot a multiplicative generator, this willthrow a warning.

If you specify your own minimum polynomial, we make no assumptions aboutconversions between fields. For example, when defining

const F=@GaloisField! 𝔽₂ β^2+ β+1const G=@GaloisField! 𝔽₂ γ^2+ γ+1

an operation like

G(β)

will throw an error. The mathematical reason is that the fieldsF andGare isomorphic, but there is two different isomorphisms. ("They are notcanonicallyisomorphic.") To choose an identification, you can use theidentify function(which is not exported by default, so we use its full path):

GaloisFields.identify(β=> γ^2)GaloisFields.identify(γ=> β^2)

This allows for conversions such as

G(β)convert(F, γ+1)

The inner workings of this distinction are based on the symbol names. Soif you defineF andG with thesame symbol and minimum polynomial:

const F=@GaloisField! 𝔽₂ β^2+ β+1const G=@GaloisField! 𝔽₂ β^2+ β+1

then they are just considered equal and conversions work without extra work.

If you do not specify a minimum polynomial, for example by using

const F=@GaloisField! 𝔽₈₁ βconst G=@GaloisField! 𝔽₉ γ

then we useConway polynomials. They have special compatibilityrelations between them, allowing conversions:

β^10== γ

This works providedF andG have the same characteristicp. If the orderof either is a power of the other, we convert into the bigger field. If not, weconvert both into the field of orderp^N, whereN is the least commonmultiple of the extension degrees ofF andG over ℤ/pℤ.

In some applications of finite fields it is convenient to use extensionsof already defined finite field, i. e. the extensions of the typeG of powerq^m overF of powerq whereq = p^n for some integersm, n.It is possible to construct an extension of already defined finite field:

# creating field with 29 elementsF=@GaloisField29# the polynomial x^2 - 2 is irreducible over F29G=@GaloisField! F x^2-2# the polynomial y^3 + 2y - 2 is irreducible over GH=@GaloisField! G   y^3+2y-2# G is a subfield of H# H has |G|^3 elements

This package usesFrank Lübeck'sdatabase of Conway polynomials.For security, we make acopy available over https for this package.It is downloaded as part of the install process.