New type definition: Galois field in Julia 1.x


#1

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

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

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

#4

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.


#5

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


#6

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