# Arithmetic modulo primes

**URL:** <https://discourse.julialang.org/t/arithmetic-modulo-primes/23895>\
**Category:** General Usage\
**Created:** [May 6, 2019, 1:09am UTC](https://discourse.julialang.org/t/arithmetic-modulo-primes/23895 "2019-05-06T01:09:51Z")\
**Posts on this page:** 7\
**Page:** 1

<div class="post-metadata">

**Author:** ![hros](https://avatars.discourse-cdn.com/v4/letter/h/97f17d/32.png) [@hros](https://discourse.julialang.org/u/hros)\
**Post date:** [May 6, 2019, 1:09am UTC](https://discourse.julialang.org/t/arithmetic-modulo-primes/23895/1 "2019-05-06T01:09:51Z")

</div>

Hi

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

I found a repository for Mod(:val, :mod) ([link](https://github.com/scheinerman/Mods.jl)) 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

---

<div class="post-metadata">

**Author:** ![longemen3000](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/longemen3000/32/7298_2.png) [@longemen3000](https://discourse.julialang.org/u/longemen3000)\
**Post date:** [May 6, 2019, 3:33am UTC](https://discourse.julialang.org/t/arithmetic-modulo-primes/23895/2 "2019-05-06T03:33:23Z")

</div>

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:

```julia
struct MyInteger <: Integer
...
end

```

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

---

<div class="post-metadata">

**Author:** ![dkarrasch](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dkarrasch/32/7410_2.png) [@dkarrasch](https://discourse.julialang.org/u/dkarrasch)\
**Post date:** [May 6, 2019, 6:45pm UTC](https://discourse.julialang.org/t/arithmetic-modulo-primes/23895/3 "2019-05-06T18:45:03Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![stevengj](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stevengj/32/71_2.png) [@stevengj](https://discourse.julialang.org/u/stevengj)\
**Post date:** [May 6, 2019, 6:54pm UTC](https://discourse.julialang.org/t/arithmetic-modulo-primes/23895/4 "2019-05-06T18:54:05Z")

</div>

Have you tried [https://github.com/tkluck/GaloisFields.jl](https://github.com/tkluck/GaloisFields.jl)? It has a [`PrimeField` type](https://github.com/tkluck/GaloisFields.jl/blob/master/src/PrimeFields.jl) that seems to be what you want.

---

<div class="post-metadata">

**Author:** ![thofma](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/thofma/32/1691_2.png) [@thofma](https://discourse.julialang.org/u/thofma)\
**Post date:** [May 6, 2019, 7:15pm UTC](https://discourse.julialang.org/t/arithmetic-modulo-primes/23895/5 "2019-05-06T19:15:14Z")

</div>

[AbstractAlgebra.jl](https://github.com/Nemocas/AbstractAlgebra.jl/) also has this functionality:

```julia
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](https://github.com/Nemocas/Nemo.jl).

---

<div class="post-metadata">

**Author:** ![Jean\_Michel](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jean_michel/32/8282_2.png) [@Jean\_Michel](https://discourse.julialang.org/u/Jean_Michel)\
**Post date:** [May 6, 2019, 11:53pm UTC](https://discourse.julialang.org/t/arithmetic-modulo-primes/23895/6 "2019-05-06T23:53:59Z")

</div>

Here is a simple code doing what you want

```julia
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

```

---

<div class="post-metadata">

**Author:** ![hros](https://avatars.discourse-cdn.com/v4/letter/h/97f17d/32.png) [@hros](https://discourse.julialang.org/u/hros)\
**Post date:** [May 7, 2019, 8:05pm UTC](https://discourse.julialang.org/t/arithmetic-modulo-primes/23895/7 "2019-05-07T20:05:48Z")

</div>

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?