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