## GaloisFields.jl

Finite fields for Julia
Popularity
44 Stars
Updated Last
5 Months Ago
Started In
October 2018

# 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.

### Required Packages

View all packages

### Used By Packages

No packages found.