New type definition: Galois field in Julia 1.x

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

2 Likes

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

# 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: 
3 Likes

isless should not return 0 mod p

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
1 Like

I got the Galois Field example from this talk by @andreasnoack, starting at about 39:20.

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

3 Likes

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

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

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

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

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.

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:

@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

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
1 Like

BTW, this code is merely for illustrating the definition of new numeric types in Julia. Production codes should use GaloisField.jl or Nemo.jl.