# New type definition: Galois field in Julia 1.x

**URL:** <https://discourse.julialang.org/t/new-type-definition-galois-field-in-julia-1-x/17123>\
**Category:** New to Julia\
**Created:** [November 3, 2018, 8:23pm UTC](https://discourse.julialang.org/t/new-type-definition-galois-field-in-julia-1-x/17123 "2018-11-03T20:23:16Z")\
**Posts on this page:** 9\
**Page:** 1

<div class="post-metadata">

**Author:** ![KZiemian](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/kziemian/32/9020_2.png) [@KZiemian](https://discourse.julialang.org/u/KZiemian)\
**Post date:** [November 3, 2018, 8:23pm UTC](https://discourse.julialang.org/t/new-type-definition-galois-field-in-julia-1-x/17123/1 "2018-11-03T20:23:16Z")

</div>

I try to work very nice examples of defining new type, \textrm{GF}( p ) = \mathbb{Z} / p where p is prime number. It looks like there syntax is not working in 1.x version. Can it be recover with few changes here and there or better to give up it and come back after reading documentation of new version?

Code is in @johnfgibson repository: [WhyJulia](https://github.com/johnfgibson/whyjulia/blob/master/1-whyjulia.ipynb)

---

<div class="post-metadata">

**Author:** ![chrisvwx](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/chrisvwx/32/45289_2.png) [@chrisvwx](https://discourse.julialang.org/u/chrisvwx)\
**Post date:** [November 3, 2018, 9:02pm UTC](https://discourse.julialang.org/t/new-type-definition-galois-field-in-julia-1-x/17123/2 "2018-11-03T21:02:14Z")

</div>

The following recovers most of the example. Hope it’s helpful

```julia
# Type definition: Galois fields GF(p), where p is prime modulus, T is integer type
struct GF{p,T} <: Number where {p,T<:Integer}
    rep::T # representative integer which holds the value of a GF(p) variable
    function GF{p,T}(x::Integer) where {p,T<:Integer}
        return new(mod(x, p))
    end
end
GF{p}(x::T) where {p,T<:Integer} = GF{p,T}(x)

# Define some basic methods for GF(p) that all Julia Numbers must have
import Base: convert, inv, one, promote_rule, show, zero

function call(::Type{GF{p}}, x::Integer) where p
    if !isprime(p)
        throw(ArgumentError("p must be prime"))
    end
    return GF{p,typeof(x)}(mod(x, p))
end

convert(::Type{GF{p,T}}, x::Integer) where {p,T} = GF{p}(x)
convert(::Type{GF{p}}, x::Integer) where p = GF{p}(x)
convert(::Type{GF{p,T}}, x::GF{p}) where {p,T}= GF{p,T}(x.rep)
promote_rule(::Type{GF{p,T1}}, ::Type{T2}) where {p,T1,T2<:Integer} = GF{p,promote_type(T1,T2)}
show(io::IO, x::GF) = show(io, x.rep);

# Define arithmetic operations on GF(p)
import Base: +, -, *, /,isless, abs

for op in (:+, :-, :*,:isless) # loop over ops, defining each in terms of integer ops mod p
    @eval begin
        ($op)(x::GF{p,T}, y::GF{p,T}) where {p,T} = GF{p,T}($(op)(x.rep, y.rep))
    end
end

# Define inverse and ÷. Requires more care than +, -, * because dividing by zero throws error
function inv(x::GF{p,T}) where {p,T}
    if x == zero(x)
        throw(DivideError())
    end
    r, u, v = gcdx(x.rep, p)
    GF{p,T}(u)
end
(/)(x::GF{p}, y::GF{p}) where p = x*inv(y);
abs(x::GF{p,T}) where {p,T} = x;

# In[38]
subtypes(Number)

# In[39]
# Create some GF(7) variables and do arithmetic

x = GF{7}(9) # x = 9 mod 7 = 2
y = GF{7}(12) # y = 12 mod 7 = 5
@show x
@show y
@show x + y # 2 + 5 mod 7 = 0
@show x - y # 2 - 5 mod 7 = 4
@show x * y # 2 * 5 mod 7 = 3
@show x / y # 2 ÷ 5 mod 7 = 6, because 2 = 6*5 mod 7

# In[40]
A = [GF{7}(rand(0:6)) for i = 1:4, j = 1:4] # matrix of random GF(7) elems

# In[41]
b = [GF{7}(rand(0:6)) for i = 1:4] # random vector b for Ax=b problem

# In[42] doesn't work :frowning: 

```

---

<div class="post-metadata">

**Author:** ![mschauer](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mschauer/32/13946_2.png) [@mschauer](https://discourse.julialang.org/u/mschauer)\
**Post date:** [November 3, 2018, 9:19pm UTC](https://discourse.julialang.org/t/new-type-definition-galois-field-in-julia-1-x/17123/3 "2018-11-03T21:19:28Z")

</div>

`isless` should not return `0 mod p`

```julia
julia> isless(x::GF{p,T}, y::GF{p,T}) where {p,T} = isless(x.rep, y.rep)
isless (generic function with 70 methods)

julia> Base.conj(x::GF{p,T}) where {p,T} = x

julia> x = A\b
4-element Array{GF{7,Int64},1}:
 5
 1
 6
 6

```

---

<div class="post-metadata">

**Author:** ![John\_Gibson](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/john_gibson/32/5321_2.png) [@John\_Gibson](https://discourse.julialang.org/u/John_Gibson)\
**Post date:** [November 3, 2018, 9:44pm UTC](https://discourse.julialang.org/t/new-type-definition-galois-field-in-julia-1-x/17123/4 "2018-11-03T21:44:35Z")

</div>

I got the Galois Field example from [this talk](https://www.youtube.com/watch?v=VS0fnUOAKpI) by @andreasnoack, starting at about 39:20.

Thanks for bringing this up. I need this update, too.

---

<div class="post-metadata">

**Author:** ![KZiemian](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/kziemian/32/9020_2.png) [@KZiemian](https://discourse.julialang.org/u/KZiemian)\
**Post date:** [November 3, 2018, 10:57pm UTC](https://discourse.julialang.org/t/new-type-definition-galois-field-in-julia-1-x/17123/5 "2018-11-03T22:57:10Z")

</div>

Thank you, that works 😀. But I don’t understand why, I will try to understand this tomorrow.

---

<div class="post-metadata">

**Author:** ![KZiemian](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/kziemian/32/9020_2.png) [@KZiemian](https://discourse.julialang.org/u/KZiemian)\
**Post date:** [November 6, 2018, 9:58pm UTC](https://discourse.julialang.org/t/new-type-definition-galois-field-in-julia-1-x/17123/6 "2018-11-06T21:58:56Z")

</div>

I don’t understand where is a problem. Can you explain it a littel bit more?

---

<div class="post-metadata">

**Author:** ![KZiemian](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/kziemian/32/9020_2.png) [@KZiemian](https://discourse.julialang.org/u/KZiemian)\
**Post date:** [November 19, 2018, 12:11pm UTC](https://discourse.julialang.org/t/new-type-definition-galois-field-in-julia-1-x/17123/7 "2018-11-19T12:11:23Z")

</div>

This code still have a bugs and I don’t know how to remove it.

```julia
# Type definiton
struct GF{p, T} <: Number where {p, T<:Integer}
    rep::T # Representation: intyger which holds the value of element in GF(p)
    
    function GF{p, T}(x::Integer) where {p, T<:Integer}
        return new(mod(x, p))
    end
end
GF{p}(x::T) where {p, T<:Integer} = GF{p, T}(x)

import Base: convert, inv, one, promote_rule, show, zero

function call(::Type{GF{p}}, x::Integer) where p
    if !isprime(p)
        throw(ArgumentError("p must be prime"))
    end
    return GF{p, typeof(x)}(mod(x, p))
end

convert(::Type{GF{p, T}}, x::Integer) where {p, T} = GF{p}(x)
convert(::Type{GF{p}}, x::Integer) where p = GF{p}(x)
convert(::Type{GF{p, T}}, x::GF{p}) where {p, T} = GF{p, T}(x.rep)
promote_rule(::Type{GF{p, T1}}, ::Type{T2}) where {p, T1, T2<:Integer} = GF{p, promote_type(T1, T2)}

# To be able show and print GF(p)
show(io::IO, x::GF) = show(io, x.rep)

```

Since `isprime` is now not defined in global scope `GF{4}(5)` is valid expression and return `0`, of type `GF{4, Int64}`. I confused, why there is no error of using undefined `!isprime(p)` in conditional statement?

Second question: why `GF{4,5}` works and what this expression mean?

---

<div class="post-metadata">

**Author:** ![John\_Gibson](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/john_gibson/32/5321_2.png) [@John\_Gibson](https://discourse.julialang.org/u/John_Gibson)\
**Post date:** [October 10, 2021, 10:02pm UTC](https://discourse.julialang.org/t/new-type-definition-galois-field-in-julia-1-x/17123/8 "2021-10-10T22:02:47Z")

</div>

At long last I got around to bringing this code up to date. Thank you, @mschauer! @KZiemian, the `call(::Type{GF{p}}, x::Integer)` function seems to be superfluous in julia-1.6. Instead I moved the check `isprime(p)` to the `GF{p,T}(x::Integer)` inner constructor.

```julia
using Primes

# Type definition: Galois fields GF(p), where p is prime modulus, T is integer type
struct GF{p,T} <: Number where {p,T<:Integer}
    rep::T # representative integer which holds the value of a GF(p) variable
    function GF{p,T}(x::Integer) where {p,T<:Integer}
        if !isprime(p)
            throw(ArgumentError("p must be prime"))
        end
        return new(mod(x, p))
    end
end
GF{p}(x::T) where {p,T<:Integer} = GF{p,T}(x)

# Define some basic methods for GF(p) that all Julia Numbers must have
import Base: convert, inv, one, promote_rule, show, zero

convert(::Type{GF{p,T}}, x::Integer) where {p,T} = GF{p}(x)
convert(::Type{GF{p}}, x::Integer) where p = GF{p}(x)
convert(::Type{GF{p,T}}, x::GF{p}) where {p,T} = GF{p,T}(x.rep)
promote_rule(::Type{GF{p,T1}}, ::Type{T2}) where {p,T1,T2<:Integer} = GF{p,promote_type(T1,T2)}
show(io::IO, x::GF) = show(io, x.rep);

# Define arithmetic operations on GF(p)
import Base: +, -, *, /, abs, conj, isless

for op in (:+, :-, :*) # loop over ops, defining each in terms of integer ops mod p
    @eval begin
        ($op)(x::GF{p,T}, y::GF{p,T}) where {p,T} = GF{p,T}($(op)(x.rep, y.rep))
    end
end

# Define inverse and ÷. Requires more care than +, -, * because dividing by zero throws error
function inv(x::GF{p,T}) where {p,T}
    if x == zero(x)
        throw(DivideError())
    end
    r, u, v = gcdx(x.rep, p)
    GF{p,T}(u)
end

(/)(x::GF{p}, y::GF{p}) where p = x*inv(y)

abs(x::GF{p,T}) where {p,T} = x
conj(x::GF{p,T}) where {p,T} = x
isless(x::GF{p,T}, y::GF{p,T}) where {p,T} = isless(x.rep, y.rep);

```

Now the examples work:

```julia
@show subtypes(Number)

# Create some GF(7) variables and do arithmetic
x = GF{7}(9) # x = 9 mod 7 = 2
y = GF{7}(12) # y = 12 mod 7 = 5

@show x
@show y
@show x + y # 2 + 5 mod 7 = 0
@show x - y # 2 - 5 mod 7 = 4
@show x * y # 2 * 5 mod 7 = 3
@show x / y # 2 ÷ 5 mod 7 = 6, because 2 = 6*5 mod 7

p = 17
A = [GF{p}(rand(0:p-1)) for i = 1:4, j = 1:4] # matrix of random GF(17) elems
x = [GF{p}(rand(0:p-1)) for i = 1:4]
b = A*x

@show A
@show b
@show x
@show A\b

println("Try to produce a GF with modulus p=4")
@show GF{4}(1)

```

produces output

```julia
subtypes(Number) = Any[Complex, GF, Real]
x = 2
y = 5
x + y = 0
x - y = 4
x * y = 3
x / y = 6
A = GF{17, Int64}[7 12 15 9; 15 11 16 1; 0 15 15 10; 9 15 7 5]
b = GF{17, Int64}[9, 11, 6, 14]
x = GF{17, Int64}[7, 10, 16, 16]
A \ b = GF{17, Int64}[7, 10, 16, 16]
Try to produce a GF with modulus p=4
ArgumentError: p must be prime

Stacktrace:
 [1] GF{4, Int64}(x::Int64)
   @ Main ./In[1]:8
 [2] (GF{4, T} where T)(x::Int64)
   @ Main ./In[1]:13
 [3] top-level scope
   @ show.jl:955
 [4] eval
   @ ./boot.jl:360 [inlined]
 [5] include_string(mapexpr::typeof(REPL.softscope), mod::Module, code::String, filename::String)
   @ Base ./loading.jl:1094

```

---

<div class="post-metadata">

**Author:** ![John\_Gibson](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/john_gibson/32/5321_2.png) [@John\_Gibson](https://discourse.julialang.org/u/John_Gibson)\
**Post date:** [October 10, 2021, 10:42pm UTC](https://discourse.julialang.org/t/new-type-definition-galois-field-in-julia-1-x/17123/9 "2021-10-10T22:42:38Z")

</div>

BTW, this code is merely for illustrating the definition of new numeric types in Julia. Production codes should use [GaloisField.jl](https://github.com/tkluck/GaloisFields.jl) or [Nemo.jl](http://nemocas.github.io/Nemo.jl/latest/gfp.html).