# Finite fields

#
** FiniteFields** —

*Module*.

This package introduces finite fields using the GAP syntax. This compatibility with GAP is the motivation not to use the existing `GaloisFields`

. The speed is comparable with `GaloisFields`

, slightly slower for prime fields and faster for composite fields. Lke GAP3, we only implement fields of order less than 2^16. This package comes with the module `Modulo`

implementing modular arithmetic without restriction on the modulus (the modulus can be a `BigInt`

).

This only dependency of this package is `Primes`

.

The Galois field with `p^n`

elements is obtained as `GF(p^n)`

. All elements of Galois fields of characteristic `p`

have the same type, the parametric type `FFE{p}`

. The function `Z(p^n)`

returns a generator of the multiplicative group of `GF(p^n)`

. Other elements of `GF(p^n)`

are obtained as powers of `Z(p^n)`

, except `0`

, obtained as `0*Z(p^n)`

. Elements of the prime field can also be obtained as `FFE{p}(n)`

(which is the same as `n*Z(p)^0`

).

```
julia> a=Z(64)
FFE{2}: Z₆₄
julia> a^9 # automatic conversion to smaller fields
FFE{2}: Z₈
julia> a^21
FFE{2}: Z₄
julia> a+1
FFE{2}: Z₆₄⁵⁶
```

Elements of the prime field can be converted to `Mod(,p)`

or to integers:

```
julia> a=Z(19)+3
FFE{19}: 5
julia> Mod(a)
Mod{UInt64}: 5₁₉
julia> Int(a)
5
julia> order(a) # order as element of the multiplicative group
9
```

The field, `p`

, `n`

and `p^n`

can be obtained back from an `FFE{p}`

as well as which power of `Z(p^n)`

is considered

```
julia> a=Z(8)^5
FFE{2}: Z₈⁵
julia> F=field(a)
GF(2^3)
julia> char(F)
2
julia> char(a)
2
julia> degree(F)
3
julia> degree(a)
3
julia> length(F)
8
julia> log(a)
5
julia> elements(F)
8-element Vector{FFE{2}}:
0
1
Z₈
Z₈²
Z₈³
Z₈⁴
Z₈⁵
Z₈⁶
```

A `p`

-integral integer or rational or a `Mod(,p)`

can be converted to a prime field element using `FFE{p}`

as a constructor.

```
julia> FFE{19}(2)
FFE{19}: 2
julia> FFE{19}(5//3)
FFE{19}: 8
julia> FFE{19}(Mod(2,19))
FFE{19}: 2
```

```
julia> m=rand(GF(49),4,4)
4×4 Matrix{FFE{7}}:
Z₄₉²⁴ Z₄₉¹⁸ Z₄₉⁹ Z₄₉⁴²
Z₄₉²² Z₄₉⁴¹ Z₄₉⁴⁶ Z₄₉²⁴
Z₄₉¹⁵ Z₄₉¹⁹ Z₄₉⁴⁰ Z₄₉³
Z₄₉²⁰ Z₄₉²⁹ Z₄₉³⁶ Z₄₉²⁰
julia> inv(m)
4×4 Matrix{FFE{7}}:
Z₄₉³⁷ Z₄₉⁵ Z₄₉³⁶ 1
Z₄₉¹⁰ Z₄₉ Z₄₉⁶ Z₄₉⁴⁷
Z₄₉³⁰ Z₄₉³⁸ Z₄₉ -2
Z₄₉¹⁵ Z₄₉² 1 Z₄₉²⁸
julia> inv(m)*m
4×4 Matrix{FFE{7}}:
1 0 0 0
0 1 0 0
0 0 1 0
0 0 0 1
```

#
** FiniteFields.FFE** —

*Type*.

`FFE{p}`

is the type of the elements of a finite field of characteristic `p`

.

#
** FiniteFields.FFE** —

*Method*.

`FFE{p}(i)`

for `i`

an integer or a fraction with denominator prime to `p`

returns the reduction mod `p`

of `i`

, an element of the prime field `𝔽ₚ`

.

#
** FiniteFields.Z** —

*Method*.

`Z(p^d)`

returns a generator of the multiplicative group of the finite field `𝔽_{pᵈ}`

, where `p`

must be prime and `pᵈ`

smaller than `2¹⁵`

. This multiplicative group is cyclic thus `Z(pᵈ)ᵃ`

runs over it for `a`

in `0:pᵈ-1`

. The zero of the field is `0*Z(p)`

(the same as `0*Z(pᵈ)`

; we automatically lower an element to the smallest field which contains it).

The various generators returned by `Z`

for finite fields of characteristic `p`

are compatible. That is, if the field `𝔽_{pⁿ}`

is a subfield of the field `𝔽_{pᵐ}`

, that is, `n`

divides `m`

, then `Z(pⁿ)=Z(pᵐ)^div(pᵐ-1,pⁿ-1)`

. This is achieved by choosing `Z(p)`

as the smallest primitive root modulo `p`

and `Z(pⁿ)`

as a root of the `n`

-th Conway polynomial of characteristic `p`

. Those polynomials where defined by J.H.~Conway and computed by R.A.~Parker.

```
julia> z=Z(16)
FFE{2}: Z₁₆
julia> z^5
FFE{2}: Z₄
```

# Modular numbers

#
** FiniteFields.Modulo** —

*Module*.

This module introduces modular arithmetic.

The integer `x`

mod. `n`

is constructed by the function `Mod(x,n)`

. If `n isa Int`

the result is of type `Mod{UInt64}`

. If `n isa BigInt`

the result is of type `Mod{BigInt}`

. Since `n`

is not encoded in the type, the elements `0`

and `1`

mod. `n`

cannot be constructed from the type, which causes some problems for some Julia functionality (for instance `inv`

on a matrix does not work). For prime moduli `p`

, the type `FFE{p}`

in `FiniteFields`

does not have such limitations.

Example:

```
julia> a=Mod(5,19)
Mod{UInt64}: 5₁₉
julia> a^2
Mod{UInt64}: 6₁₉
julia> inv(a)
Mod{UInt64}: 4₁₉
julia> a*inv(a)
Mod{UInt64}: 1₁₉
julia> a+2
Mod{UInt64}: 7₁₉
julia> a*2
Mod{UInt64}: -9₁₉
julia> a+1//2
Mod{UInt64}: -4₁₉
julia> Integer(a) # get back an integer from a
5
julia> order(a) # multiplicative order of a
9
```