| Build Status | Test coverage |
|---|---|
 |
 |
This module defines types representing finite fields. It supports 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 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 == 0Lastly, 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 polynomialIn 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.
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 + γ + 1an 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 + β + 1then 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 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ℤ.
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 elementsThis 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.