WARNING the current tagged version gives warnings in the latest 0.4, while the tests on the github trunk fail. I do not have time right now to maintain this code, so caveat emptor. Sorry.

IntModN.jl

A pragmatic (meaning incomplete, and written by someone who needed this before he fully understood it) library for doing modular arithmetic.

The aim is not to encapsulate a large amount of theory, or to describe the relationships between different structures, but to enable arithmetic on various types, motivated largely by the practical needs of crypto code.

• Examples
• Types
  • Integers Modulo N
  • Polynomials
    • Polynomials with Integral Coefficients
    • Polynomials over GF(2)
  • Quotient (Factor) Rings

Incomplete; pull requests welcome.

Examples

See the tests.

Simultaneous Equations

Answering this question (in GF(2)):

julia> using IntModN

@zfield 2 begin
    A = [1 1 1 0; 
         1 1 0 1;
         1 0 1 1;
         0 1 1 1]
    b = [1, 1, 0, 1]
    x = A\b
    @assert x == [0, 1, 0, 0]
end

Polynomial Arithmetic

julia> x = X(GF2)
ZP(ZField{2,Int64},1,0)

julia> a = x^3 + x^2 + 1
ZP(ZField{2,Int64},1,1,0,1)

julia> b = x^2 + 1
ZP(ZField{2,Int64},1,0,1)

julia> p, q = divrem(a, b)
(ZP(ZField{2,Int64},1,1),ZP(ZField{2,Int64},1,0))

julia> println(p * b + q)
x^3 + x^2 + 1 mod 2

Fast Polynomials in GF(2)

The examples above could have used any modulus. I chose GF(2) only because it is common.

However, the following works only in GF(2) (the trade-off for the lack of flexibility is speed and compactness - these are encoded as bit patterns):

julia> x = GF2X(Uint8)
GF2Poly{Uint8}(2)

julia> a = x^3 + x^2 + 1
GF2Poly{Uint8}(13)

julia> b = x^2 + 1
GF2Poly{Uint8}(5)

julia> p, q = divrem(a, b)
(GF2Poly{Uint8}(3),GF2Poly{Uint8}(2))

julia> @assert a == p * b + q

Rijndael

The multiplication described here:

julia> x = GF2X(Uint)
GF2Poly{UInt64}(2)

julia> rijndael = x^8 + x^4 + x^3 + x + 1
GF2Poly{UInt64}(283)

julia> print(ZF(rijndael, x^7 + x^6 + x^3 + x) * ZF(rijndael, x^6 + x^4 + x +
1))
1 mod 2 mod x^8 + x^4 + x^3 + x + 1 mod 2

Note that rinjdael here requires 9 bits of storage; there is no currently representation with an implicit msb.

Types

Residue <: Integer - abstract superclass for (almost) everything below. Used to provide some common utilities (like automatic promotion from integers).

Integers Modulo N

ZModN{N,I<:Integer} <: Residue - abstract superclass for integers modulo some value, where N is the modulus, and so typically an Int (yes, that's a integer as a type, not a value), and I

This has two concrete subclasses, because when N is a prime number we can define a multiplicative inverse.

ZRing{N, I<:Integer} <: ZModN{N,I} - the general case.

ZField{N, I<:Integer} <: ZModN{N,I} - assumes that N is prime, and so includes division.

These constructors can be used directly, but do not check that arguments are consistent with assumptions made in the code (values within range, etc).

The associated functions ZR() and ZF() are more suitable for "normal" use (but still do not check primality for fields), and include support for factory functions:

julia> ZF(3, 5, UInt8)
ZField{3,UInt8}(2)

julia> ZF(3, 5)
ZField{3,Int64}(2)

julia> GF3 = ZF(3)
(anonymous function)

julia> GF3(5)
ZField{3,Int64}(2)

The macros @zring and @zfield can also be used to convert all integers with scope:

julia> @zring 4 begin
          A = [1 2 3 4 5]
       end
1x5 Array{IntModN.ZRing{4,Int64},2}:
 1  2  3  0  1

Polynomials

Poly <: Residue - abstract superclass for polynomials. All share some basic conventions about accessing coefficients (with []) and iterators.

The types below all form rings, not fields, because polynomials do not have inverses.

Note: Originally, the code used Polynomial.jl, but that had some weird design decisions so I wrote my own code. Since then, Polynomials.jl fixed some of the issues, so at some point it may make sense to revert to that package.

Polynomials With Integral Coefficients

ZPoly{I<:Integer} <: Poly - a simple wrapper around an array of integral coefficients (including ZModN subclasses). The coefficients are in the "usual" order, so [i] gives the ith coefficient, and the leading coefficient is always non-zero (or the array is empty).

As with integers mod N, the constructor can be used directly, but it is generally preferable to use ZP(), which has various forms.

In addition, there's support for the natural syntax x^n... via X():

julia> x = X(ZF(2))
ZP(IntModN.ZField{2,Int64},1,0)

julia> x^3 + x
ZP(IntModN.ZField{2,Int64},1,0,1,0)

Polynomials over GF(2)

GF2Poly{U<:Unsigned} <: Poly - specialized support for polynomials over GF(2). Coefficients can only be 0 or 1, so we can use bit fields (integers) for their values.

As always, you can use the constructor directly, or the utilities GF2P() and GF2X().

The bit pattern can be displayed with bits() and addition is binary xor:

julia> x = GF2X(Uint8)
GF2Poly{UInt8}(2)

julia> a = x^7 + x^3
GF2Poly{UInt8}(136)

julia> b = x^3 + x^2 + 1
GF2Poly{UInt8}(13)

julia> a+b
GF2Poly{UInt8}(133)

julia> bits(a), bits(b), bits(a+b)
("10001000","00001101","10000101")

Quotient (Factor) Rings

These used to be a spearate type, but can now be handled as ZRing() and ZField() with polynomial arguments. The latter is appropriate when the ideal is irreducible (maximal) (I think).

See the Rijndael example.