GaloisFields.jl - finite fields for Julia

Build Status	Test coverage

Introduction

This module defines types representing finite fields. It supports both fields of prime order and of prime power order.

Synopsis

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 latter for a field of prime power order. In the prime power case, you pass a display name / variable name for the primitive element.

using GaloisFields

const F = @GaloisField 29     # ℤ/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 more difficult 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 field of order q = p^n, you can:

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

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

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

Fast multiplications

In some cases, we make use of Zech's logarithms for faster multiplications. By default, this happens if the order of the field is less than 2^16, if the characteristic is not 2, and if the primitive element is also a multiplicative generator. 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 a field whose primitive element is not a multiplicative generator, this will throw a warning.

Conversions

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

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

an operation like

G(β)

will throw an error. The mathematical reason is that the fields F and G are isomorphic, but there is two different isomorphisms. ("They are not canonically isomorphic.") To choose an identification, you can use the identify 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. So if you define F and G with the same symbol and minimum polynomial:

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

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

Conversions for the default minimum polynomials

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

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

then we use Conway polynomials. They have special compatibility relations between them, allowing conversions:

β^10 == γ

This works provided F and G have the same characteristic p. If the order of either is a power of the other, we convert into the bigger field. If not, we convert both into the field of order p^N, where N is the least common multiple of the extension degrees of F and G over ℤ/pℤ.

Constructing a tower of field extensions

In some applications of finite fields it is convenient to use extensions of already defined finite field, i. e. the extensions of the type G of power q^m over F of power q where q = p^n for some integers m, n. It is possible to construct an extension of already defined finite field:

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

Acknowledgements

This package uses Frank Lübeck's database of Conway polynomials. For security, we make a copy available over https for this package. It is downloaded as part of the install process.