Arithmetic modulo primes

General Usage
1

Hi

Does Julia have a package for arithmetic modulo primes (Zp)?

I found a repository for Mod(:val, :mod) (link) but that requires storing the prime as a field of each variable.
I would like to instantiate variable from a Z( p ) parametric type.
If no package currently exist, please outline the best practice for creating such a type, with the ability to convert numbers to/from “regular” integers

1 Like
2

Hi, welcome to the discourse forum!

Can you give a code example of what behavior do you want? maybe i can help. if you are defining a concrete type, you can always make that type an instance of an abstract class, for example:

struct MyInteger <: Integer
...
end

maybe you can use the package as a base for what you pretend to build

1 Like
3

I think you could take Julia’s Rationals as an example of how to build a number type on top of Integers, including constructors and overloading arithmetic operations.

4

Have you tried https://github.com/tkluck/GaloisFields.jl? It has a PrimeField type that seems to be what you want.

2 Likes
5

AbstractAlgebra.jl also has this functionality:

julia> using AbstractAlgebra

julia> F = GF(3)
Finite field F_3

julia> F(2) + F(2)
1

PS: If you want it fast with a C backend, you can also try Nemo.jl.

1 Like
6

Here is a simple code doing what you want

module Mods

export Mod

const T=UInt8 # this allows moduli up to 255

struct Mod{p} <: Number
   val::T
   function Mod{n}(a) where {n}
        new(T(mod(a,n)))
   end
end

Base.promote(x::Mod{n}, y::Integer) where {n}=(x,Mod{n}(y))
Base.promote(y::Integer, x::Mod{n}) where {n}=(Mod{n}(y),x)
Base.zero(::Type{Mod{n}}) where {n} = Mod{n}(T(0))
Base.:(==)(x::Mod,y::Mod) = x.val==y.val
Base.:(==)(x::Mod{n}, k::Integer) where n = mod(k,n) == x.val
Base.:(==)(k::Integer, x::Mod) = x==k
Base.:+(x::Mod{n}, y::Mod{n}) where {n} = Mod{n}(Int(x.val)+y.val)
Base.:*(x::Mod{n}, y::Mod{n}) where {n} = Mod{n}(Int(x.val)*y.val)
Base.:-(x::Mod{n}, y::Mod{n}) where {n} = Mod{n}(Int(x.val)-y.val)
Base.:-(x::Mod{n}) where {n} = Mod{n}(-Int(x.val))
Base.:/(x::Mod{n}, y::Mod{n}) where n = x * inv(y)
Base.inv(x::Mod{n}) where {n} = Mod{n}(invmod(x.val,n))

function Base.show(io::IO, m::Mod{n}) where n
   if get(io,:limit,false)
     sub=Dict(zip("0123456789,()","₀₁₂₃₄₅₆₇₈₉‚₍₎"))
     print(io,m.val,map(x->sub[x],repr(n)))
   else print(io,"Mod{$n}($(m.val))")
   end
end

end
5 Likes
7

WOW!
What an active community.
It is very encouraging to to start learning Julia with such community support.

I am looking to build a highly performant implementation using SIMD instructions.
I want to focus on fields of Mersenne primes, which enable field-arithmetic (even multiplication) without the modulo operation, i.e. using SIMD available op-codes.

  1. How would I integrate the undelying simd implementation of the arithmetic method on my new type with Julia’s dot operation for vectorized implementation?
  2. A more general question: I understand that the initial run of a program is longer as it jit compiles code. Is there a way to save these initial compilation so that subsequent launches of the program will not need the initial compilation phase?
3 Likes