# tkluck / GaloisFields.jl

Finite fields for Julia
Julia Fetching latest commit…
Cannot retrieve the latest commit at this time.
Type Name Latest commit message Commit time
Failed to load latest commit information. deps Nov 3, 2018 src Jan 20, 2020 test Jan 8, 2020 .travis.yml Feb 8, 2020 LICENSE.md Oct 20, 2018 Project.toml Jan 14, 2020 README.md Jan 18, 2020 appveyor.yml Feb 8, 2020

# GaloisFields.jl - finite fields for Julia

## 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 polynom x^2 - 2 is irreducible over F29
G = @GaloisField! F x^2 - 2
# the polynom y^3 + 2y - 2 if 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.

You can’t perform that action at this time.