 # 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
subtypes(Number)

# In
# 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
A = [GF{7}(rand(0:6)) for i = 1:4, j = 1:4] # matrix of random GF(7) elems

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

# In 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 . 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:
 GF{4, Int64}(x::Int64)
@ Main ./In:8
 (GF{4, T} where T)(x::Int64)
@ Main ./In:13
 top-level scope
@ show.jl:955
 eval
@ ./boot.jl:360 [inlined]
 include_string(mapexpr::typeof(REPL.softscope), mod::Module, code::String, filename::String)