Mods

Modular arithmetic for Julia.

This module supports modular values and arithmetic. The moduli are integers (at least 2) and the values are either integers or Gaussian integers.

An element of $\mathbb{Z}_N$ is entered as Mod{N}(a) and is of type Mod{N}. An element of $\mathbb{Z}_N[i]$ is entered a Mod{N}(a+b*im) and is of type GaussMod{N}. Both types are fully interoperable with each other and with (ordinary) integers and Gaussian integers.

julia> a = Mod{17}(9); b = Mod{17}(10);

julia> a+b
Mod{17}(2)

julia> 2a
Mod{17}(1)

julia> a = Mod{17}(9-2im)
GaussMod{17}(9 + 15im)

julia> 2a
GaussMod{17}(1 + 13im)

julia> a'
GaussMod{17}(9 + 2im)

Integers modulo N (where N>1) are values in the set {0,1,2,...,N-1}. All arithmetic takes place modulo N. To create a mod-N number we use Mod{N}(a). For example:

julia> Mod{10}(3)
Mod{10}(3)

julia> Mod{10}(23)
Mod{10}(3)

julia> Mod{10}(-3)
Mod{10}(7)

The usual arithmetic operations may be used. Furthermore, oridinary integers can be combined with Mod values. However, values of different moduli cannot be used together in an arithmetic expression.

julia> a = Mod{10}(5)
Mod{10}(5)

julia> b = Mod{10}(6)
Mod{10}(6)

julia> a+b
Mod{10}(1)

julia> a-b
Mod{10}(9)

julia> a*b
Mod{10}(0)

julia> 2b
Mod{10}(2)

Division is permitted, but if the denominator is not invertible, an error is thrown.

julia> a = Mod{10}(5)
Mod{10}(5)

julia> b = Mod{10}(3)
Mod{10}(3)

julia> a/b
Mod{10}(5)

julia> b/a
ERROR: Mod{10}(5) is not invertible

Exponentiation by an integer is permitted.

julia> a = Mod{17}(2)
Mod{17}(2)

julia> a^16
Mod{17}(1)

julia> a^(-3)
Mod{17}(15)

Invertibility can be checked with is_invertible.

julia> a = Mod{10}(3)
Mod{10}(3)

julia> is_invertible(a)
true

julia> inv(a)
Mod{10}(7)

julia> a = Mod{10}(4)
Mod{10}(4)

julia> is_invertible(a)
false

julia> inv(a)
ERROR: Mod{10}(4) is not invertible

Modular numbers with different moduli cannot be combined using the usual operations.

julia> a = Mod{10}(1)
Mod{10}(1)

julia> b = Mod{9}(1)
Mod{9}(1)

julia> a+b
ERROR: Cannot promote types with different moduli

We can also work modulo N with Gaussian integers (numbers of the form a+b*im where a and b are integers).

julia> a = Mod{10}(2-3im)
GaussMod{10}(2 + 7im)

julia> b = Mod{10}(5+6im)
GaussMod{10}(5 + 6im)

julia> a+b
GaussMod{10}(7 + 3im)

julia> a*b
GaussMod{10}(8 + 7im)

In addition to the usual arithmetic operations, the following features apply to GaussMod values.

• Use the functions real and imag (or reim) to extract the real and imaginary parts:

julia> a = Mod{10}(2-3im)
GaussMod{10}(2 + 7im)

julia> real(a)
Mod{10}(2)

julia> imag(a)
Mod{10}(7)

julia> reim(a)
(Mod{10}(2), Mod{10}(7))

Use a' (or conj(a)) to get the complex conjugate value:

julia> a = Mod{10}(2-3im)
GaussMod{10}(2 + 7im)

julia> a'
GaussMod{10}(2 + 3im)

julia> a*a'
GaussMod{10}(3 + 0im)

julia> a+a'
GaussMod{10}(4 + 0im)

Given a Mod number, the modulus is recovered using the modulus function and the numerical value with value:

julia> a = Mod{23}(100)
Mod{23}(8)

julia> modulus(a)
23

julia> value(a)
8

The modulus and value of a Mod number are of type Int (or Complex{Int} for GaussMod numbers). This implies that the largest possible modulus is typemax(Int) which equals 2^63-1 (assuming a 64-bit system).

Integer operations on 64-bit numbers can give results requiring more than 64 bits. Fortunately, when working with modular numbers the results of the operations are bounded by the modulus.

julia> N = 10^18                # this is a 60-bit number
1000000000000000000

julia> a = 10^15
1000000000000000

julia> a*a                      # We see that a*a overflows
5076944270305263616

julia> Mod{N}(a*a)              # this gives an incorrect answer
Mod{1000000000000000000}(76944270305263616)

julia> Mod{N}(a) * Mod{N}(a)    # but this is correct!
Mod{1000000000000000000}(0)

This safety comes at a cost. If the modulus is large then operations may require enlarging the values to 128-bits before reducing mod N. For multipication, this widening occurs when the modulus exceeds 2^32-1; for addition, widening occurs when the modulus exceeds 2^62-1.

The standard Julia functions zero, zeros, one, and ones may be used with Mod types:

julia> zero(Mod{9})
Mod{9}(0)

julia> one(GaussMod{7})
GaussMod{7}(1 + 0im)

julia> zeros(Mod{9},2,2)
2×2 Matrix{Mod{9}}:
 Mod{9}(0)  Mod{9}(0)
 Mod{9}(0)  Mod{9}(0)

julia> ones(GaussMod{5},4)
4-element Vector{GaussMod{5}}:
 GaussMod{5}(1 + 0im)
 GaussMod{5}(1 + 0im)
 GaussMod{5}(1 + 0im)
 GaussMod{5}(1 + 0im)

The Mod{m} type can be used as an iterator (in for statements and list comprehension):

julia> for a in Mod{5}
       println(a)
       end
Mod{5}(0)
Mod{5}(1)
Mod{5}(2)
Mod{5}(3)
Mod{5}(4)

julia> collect(Mod{6})
6-element Vector{Mod{6}}:
 Mod{6}(0)
 Mod{6}(1)
 Mod{6}(2)
 Mod{6}(3)
 Mod{6}(4)
 Mod{6}(5)

julia> [k*k for k ∈ Mod{7}]
7-element Vector{Mod{7}}:
 Mod{7}(0)
 Mod{7}(1)
 Mod{7}(4)
 Mod{7}(2)
 Mod{7}(2)
 Mod{7}(4)
 Mod{7}(1)

julia> prod(k for k in Mod{5} if k!=0) == -1  # Wilson's theorem
true

One can also use GaussMod as an iterator:

julia> for z in GaussMod{3}
       println(z)
       end
GaussMod{3}(0 + 0im)
GaussMod{3}(0 + 1im)
GaussMod{3}(0 + 2im)
GaussMod{3}(1 + 0im)
GaussMod{3}(1 + 1im)
GaussMod{3}(1 + 2im)
GaussMod{3}(2 + 0im)
GaussMod{3}(2 + 1im)
GaussMod{3}(2 + 2im)

The rand function can be used to produce random Mod values:

julia> rand(Mod{17})
Mod{17}(13)

julia> rand(GaussMod{17})
GaussMod{17}(3 + 6im)

With extra arguments, rand produces random vectors or matrices populated with modular numbers:

julia> rand(GaussMod{10},4)
4-element Vector{GaussMod{10}}:
 GaussMod{10}(2 + 6im)
 GaussMod{10}(2 + 6im)
 GaussMod{10}(7 + 4im)
 GaussMod{10}(7 + 3im)

julia> rand(Mod{10},2,5)
2×5 Matrix{Mod{10}}:
 Mod{10}(9)  Mod{10}(8)  Mod{10}(1)  Mod{10}(3)  Mod{10}(1)
 Mod{10}(2)  Mod{10}(0)  Mod{10}(9)  Mod{10}(0)  Mod{10}(2)

The result of Mod{N}(a//b) is exactly Mod{N}(numerator(a)) / Mod{N}(denominator(b)). This may equal Mod{N}(a)/Mod{N}(b) if a and b are relatively prime to each other and to N.

When a Mod and a Rational are operated with each other, the Rational is first converted to a Mod, and then the operation proceeds.

Bad things happen if the denominator and the modulus are not relatively prime.

The Mod and GaussMod types work well with my SimplePolynomials and LinearAlgebraX modules.

julia> using LinearAlgebraX

julia> A = rand(GaussMod{13},3,3)
3×3 Matrix{GaussMod{13}}:
 GaussMod{13}(12 + 2im)   GaussMod{13}(3 + 5im)  GaussMod{13}(6 + 11im)
  GaussMod{13}(0 + 4im)   GaussMod{13}(2 + 1im)  GaussMod{13}(12 + 2im)
  GaussMod{13}(6 + 0im)  GaussMod{13}(3 + 11im)   GaussMod{13}(4 + 8im)

julia> detx(A)
GaussMod{13}(11 + 5im)

julia> invx(A)
3×3 Matrix{GaussMod{13}}:
 GaussMod{13}(12 + 11im)  GaussMod{13}(3 + 6im)  GaussMod{13}(12 + 11im)
   GaussMod{13}(2 + 7im)  GaussMod{13}(1 + 3im)    GaussMod{13}(9 + 2im)
   GaussMod{13}(4 + 7im)  GaussMod{13}(8 + 9im)    GaussMod{13}(9 + 1im)

julia> ans * A
3×3 Matrix{GaussMod{13}}:
 GaussMod{13}(1 + 0im)  GaussMod{13}(0 + 0im)  GaussMod{13}(0 + 0im)
 GaussMod{13}(0 + 0im)  GaussMod{13}(1 + 0im)  GaussMod{13}(0 + 0im)
 GaussMod{13}(0 + 0im)  GaussMod{13}(0 + 0im)  GaussMod{13}(1 + 0im)

julia> char_poly(A)
GaussMod{13}(2 + 8im) + GaussMod{13}(11 + 2im)*x + GaussMod{13}(8 + 2im)*x^2 + GaussMod{13}(1 + 0im)*x^3

In version 2 the modulus of a Mod number must be of type Int. If a Mod number is constructed with any other typeof Integer, the constructor will (try to) convert it to type Int.

The old style Mod{N,T}(v) no longer works.

There were various issues in the earlier version of Mods that are resolved by requiring N to be of type Int.

• Previously Mod numbers created with different sorts of integer parameters would be different. So if N = 17 and M = 0x11, then Mod{N}(1) would not be interoperable with Mod{M}(1).

• The internal storage of the value of the Mod numbers could be different. For example, Mod{17}(-1) would store the value internally as -1 whereas Mod{17}(16) would store the value as 16.

• Finally, if the modulus were a large Int128 number, then arithmetic operations could silently fail.

We believe that the dominant use case for this module will be with moduli between 2 and 2^63-1 and so we do not expect this change to affect users. Further, since Mod numbers that required Int128 moduli were likely to give incorrect results, version 1 of this module was buggy.

In addition, some functionality has been moved to the extras folder. See the README there. In particular, the CRT function is no longer part of the Mods module but resides in extras/CRT.jl.

Since moduli are of type Int, a Mod numbers uses 8 bytes (and a GaussMod uses 16 bytes). A large matrix of Mod numbers could unnecessarily use a lot of memory, especially if the moduli are small.

Some solutions to this problem:

• Use the latest Version 1 of Mods.
• Create a cloned copy of the Mods package and edit this line in the file Mods.jl:

const value_type = Int                # storage type for the value in a Mod

to set value_type to a smaller type of integer (say, Int16).

• For very small moduli (between 2 and 255) see the MiniMods module.