Finite fields

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. Like GAP3, we only implement fields of order less than 2^16.

The only dependency of this package is the package 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) # the characteristic p
2

julia> char(a)
2

julia> degree(F) # the n in p^n
3

julia> degree(a)
3

julia> length(F) # p^n
8

julia> log(a) # such that a==Z(p^n)^log(a)
5

julia> a in F
true

julia> elements(F)
8-element Vector{FFE{2}}:
   0
   1
  Z₈
 Z₈²
 Z₈³
 Z₈⁴
 Z₈⁵
 Z₈⁶

A p-integral rational number 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

Finally, one can compare fields:

julia> issubset(GF(2),GF(4))
true

FFE{p} is the type of the elements of a finite field of characteristic p.

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 𝔽ₚ.

GF(q) the finite field with q elements

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₄

tr(x::FFE{p},F1::GF,F2::GF=GF(p))

Let F2=GF(q) where q is a power of p, and let F1=GF(q^n). The trace from F1 to F2 sends x∈F1 to $∑_{i=0}^{n-1}x^{q^i}$ ∈F2.

julia> tr(Z(9),GF(9))
FFE{3}: 1

julia> tr(Z(9),GF(81))
FFE{3}: -1

norm(x::FFE{p},F1::GF,F2::GF=GF(p))

Let F2=GF(q) where q is a power of p, and let F1=GF(q^n). The norm from F1 to F2 sends x∈F1 to $∏_{i=0}^{n-1}x^{q^i}$ ∈F2.

julia> norm(Z(64),GF(64),GF(8))
FFE{2}: Z₈

julia> norm(Z(4),GF(64),GF(8))
FFE{2}: 1