ModularArithmetic 1.1.8

Modular Arithmetic Library

Useful Links

• GitLab Repository
• NuGet Package
• Usage Examples Repository

Intro

This is a library written in C# aimed to work with Modular Arithmetic. Is is capable of working with Residual Number System (RNS) and performing basic arithmetical with Residue Numbers (RN). Apart from that, it implements Montgomery Arithmetic and performs Number Theoretic Transform (NTT) both on regular polynomials and those ones that use RNS for coefficient/evaluation representations.

Installation

To install the library, easiest way is to get it directly from NuGet via dotnet add package ModularArithmetic. This commans can be also executed directly from the IDE - here are the instructors for Visual Studio and here for Rider.

Alternatively, one can also download the files manually and add them to a project.

Usage

In this section we will through the basic usage of the library and its functions.

Representation of the Residue Number

Representation of the Residue Number can be done via 2 classes: SimpleResidueNumber for basic representation and NttResidueNumber which is also NTT friendly, hence the moduli must be prime numbers and not only coprime integers. For both representations, all modulu need to be odd numbers due to Montgomery arithmetic. Both classes support generic types, so you can also have SimpleResidueNumber<int> and SimpleResidueNumber<UInt128>, for example. To <> you can put any unmanaged IBinaryInteger. BigInteger is not supported.

Please note that that moduli are sorted (and residues are accordingly adjusted) before object is created, unless unsafe options are used.

First way of creating the object is via the residues and moduli array. First residue corresponds to first modulus and so on:

using ModularArithmetic;    // for SimpleResidueNumber
using ModularArithmetic.NTT;    // for NttResidueNumber

// residues and moduli array
// residues: [1, 2, 3], moduli: [3, 7, 11]
var a = new SimpleResidueNumber<int>([1, 2, 3], [3, 7, 11]);
// same as a because moduli are sorted
var alsoA = new SimpleResidueNumber<int>([3, 2, 1], [11, 7, 3]);

It is also possible to create the object from a single value and an array of moduli. Then a residue for each modulus will be counted. The single numeric value is always a BigInteger whilst the array has the type specified in <>.

using ModularArithmetic.NTT;    // to show NttResidueNumber

// residues = [13 % 3 = 1, 13 % 7 = 6, 13 % 11 = 2]
// moduli = [3, 7, 11]
var b = new NttResidueNumber<int>(13, [3, 7, 11]);

By using these methods, modulis are checked whether they are correct (no common divisors, respectively primality). These processes can be slow, hence there is an option to create the object without doing these checks. Moduli are still sorted, though.

using ModularArithmetic;

var notCheckedA = SimpleResidueNumber<int>.SkipModuliCheck([1, 2, 3], [3, 7, 11]);
var notCheckedB = NttResidueNumber<int>.SkipModuliCheck(13, [3, 7, 11]);

Last way of creating the object is via FromRawValues. Here, no sorting and checks are made. Object is simply created by feeding parameters into respective fields with no additional touches. If this method is desired, ImmutableAeeay<T> must be passed as that it the internal representation of the Residue Number.

using System.Collections.Immutable;     // for Immutable arrays 
using ModularArithmetic; 

ImmutableArray<int> aResidues = [1, 2, 3];
ImmutableArray<int> aModuli = [3, 7, 11];
var aFromRawValues = SimpleResidueNumber<int>.FromRawValues(aResidues, aModuli);

All of these methods are supported both on SimpleResidueNumber and NttResidueNumber.

Operations on Residue Numbers

All implementations (SimpleResidueNumber and NttResidueNumber) of the Residue Number support basic operations. Here is an enumeration of them.

Conversion to integer

It is possible to convert a ResidueNumber to integer. This can be done either by ToInteger or ToIntegerGarner method. Both of these return BigInteger type as the maximum possible number represented by Residual Number System grows really quickly (it's the sum of the moduli).

using System.Numerics;
using ModularArithmetic;

var a = new SimpleResidueNumber<int>([1, 2, 3], [3, 7, 11]);
BigInteger aInteger = a.ToInteger();
BigInteger aIntegerGarner = a.ToIntegerGarner();

Comparison

Since Residue Number is still a numeric representation, it is possible to compare the instances of both implementations. One can either use overloaded operators such as <, == and so on or directly call Equals or CompareTo methods.

using ModularArithmetic;

var a = new SimpleResidueNumber<int>([1, 2, 3], [3, 7, 11]);
var b = new SimpleResidueNumber<int>([0, 1, 9], [3, 7, 11]);

if (a > b)  // overloading the operators
{
    Console.WriteLine("a is greater than b");
}

if (a < b)
{
    Console.WriteLine("a is less than b");
}

if (a.Equals(b))    // directly calling the method
{
    Console.WriteLine("a is equal to b");
}  

Please note that checking for equality is fast. We just run through the residues and moduli and check whether they are the same. However, the comparison (greater than, smaller than, etc.) is slower due to the need for reconsruction to BigInteger as there is no way to deduce it from the moduli itself.

Montgomery Arithmetic

Whilst many internal operations depend directly on Montgomery Arithmetic, these functions are made open, so users can also take benefits from them.

Montgomery Space

Montgomery arithmetic is strictly defined within a modular space. This space is determined by a chosen modulus, and all operations are performed modulo that modulus. Chosen modulus is always an odd number (that's also why we don't allow even moduli in the Residue Number representation). Below is an example on how to create such space. Importing ModularArithmetic.MathHelpers is required.

using ModularArithmetic;
using ModularArithmetic.MathHelpers;

// Montgomery space where all operations are performed modulo 13
UInt128 modulus = 13;
MontgomerySpace mySpace = new MontgomerySpace(13modulus);

Is is possible to test individual MontgomerySpace objects for equality and the parameter in the constructor is of UInt128 type.

Montgomery Number

To represent a number inside given MontgomerySpace, MontgomeryNumber struct is used. Within the space, a number is represented by a numeric value that typically differs from its value in ordinary arithmetic. Creating an instance of MontgomeryNumber can be done in 2 ways:

• via the constructor: here the Montgomery space and the value inside that space are provided
• via Transform method: transforms any regular integer to its representation inside selected Montgomery space

using ModularArithmetic.MathHelpers;

// creating the space
MontgomerySpace mySpace = new MontgomerySpace(13);

// transforming regular 11 to mySpace
MontgomeryNumber a = mySpace.Transform(11);

// creating a number that has value 11 inside mySpace
MontgomeryNumber b = new MontgomeryNumber(11, mySpace);	// a != b

Notice that Transform method accepts any numeric type that satsifies IBinaryIntegeer but the method via constructor requires and UInt128 number to be passed. Internal representation then happens through usnigned 128-bit integers. Additionally, one can test these numbers for equality but the information about number's size is lost.

Additionally, by using ToRegular method, a number can be transformed from Montgomery space back to regular representation. Method returns UInt128

using ModularArithmetic.MathHelpers;

// creating the space
MontgomerySpace mySpace = new MontgomerySpace(13);

// transforming regular 11 to mySpace
MontgomeryNumber a = mySpace.Transform(11);

UInt128 regular = a.ToRegular;

Operations within Montgomery Space

Basic arithemtic operations (add, subtract and multiply) can be done between the numbers within the same Montgomery space. Objects are also made in a way, so they support overloaded operators. Moreover, because the internal representation uses a custom UInt256 for intermediate calculations, operations with large numbers near UInt128.MaxValue work correctly. Without Montgomery arithmetic, intermediate results could overflow, leading to incorrect outcomes.

using ModularArithmetic.MathHelpers;

// creating the space with a modulus of 13
UInt128 modulus = 13;
var montSpace = new MontgomerySpace(modulus);

// transforming regular 11 to mySpace
MontgomeryNumber a = montSpace.Transform(11);

// creating a number that has value 11 inside mySpace
MontgomeryNumber b = new MontgomeryNumber(11, montSpace);	// a != b

MontgomeryNumber sum = a + b;
MontgomeryNumber product = a * b;

MontgomeryNumber alsoProduct = montSpace.Multiply(a, b); 

Number Theoretic Transform

The library also performs the fast Fourier transform (not only) over finite fields (NTT). To use this functionality, it is necessary to import ModularArithmetic.NTT. NTT can be performed both on ordinary polynomials represented as an array, as well as on those where the coefficients, or the evaluations of the polynomial, form an RN. In that case, the NTT is carried out component-wise, and for such polynomials separate classes are provided.

Since NTT uses modular arithmetic operations, the transformation itself is carried out in Montgomery space.

The requirement is that the polynomials have a length that is a power of two.

NTT Space

The key class for NTT is NttSpace. It defines the space over which we can perform the transformation. It is determined by the modulus and the polynomial length, or by the n-th primitive root of unity, which implicitly contains the polynomial length as well. The space itself can be created in several ways. It accepts generic parameters specified in \texttt{<>}, which implement the IBinaryInteger interface and are unmanaged. This approach excludes the slow BigInteger. Below is an example on how to create such space:

using ModularArithmetic.NTT;
using ModularArithmetic.MathHelpers;

// suitable prime modulus (chosen by us), for which 
// (10009 - 1) % polyLength = 0
int modulus = 10009;

// suitably chosen 8th primitive root of unity
int nthRoot = 792;
int polyLength = 8;

// create a Montgomery space, since the NTT space is later created based on it
var montSpace = new MontgomerySpace(UInt128.CreateChecked(modulus));

// using the n-th root of unity and modulus
var nttSpace = new NttSpace<int>(nthRoot, modulus);

// using the n-th root of unity and Montgomery space
var sameNttSpace = new NttSpace<int>(nthRoot, montSpace);

// using the modulus and polynomial length
var anotherNttSpace = NttSpace<int>.FromPolyLength(modulus, polyLength);

Transformations

When we have an NTT space created, it is possible to perform the Number theoretic transform on the polynomial. Both the forward ForwardNTT and the inverse NTT transformation InverseNTT are supported. The polynomial is provided as an array of integers, and the method also returns an array of integers. Here is a simple example on how to perform the transform:

using ModularArithmetic.NTT;

// suitable prime modulus (chosen by us), for which 
// (10009 - 1) % polyLength = 0
int modulus = 10009;

// suitably chosen 8th primitive root of unity
int nthRoot = 792;

// create a new NTT space with modulus 10009 and 8th primitive root of unity
var nttSpace = new NttSpace<int>(nthRoot, modulus);

// polynomial in its coefficients form
// coefficients for x^0 = 999, for x^1 = 10001, and so on
int[] poly = [999, 10001, 8978, 7, 4, 4, 4, 4];

int[] graph = nttSpace.ForwardNtt(poly);

int[] original = nttSpace.InverseNtt(graph);

if (poly.SequenceEqual(original))
{
    Console.WriteLine("ntt works");
}

Polynomials expressed via Residue Numbers

Polynomials do not have to be represented only by regular integers, but the individual coefficients or evaluations can also be expressed as Residue Numbers (RNs). That is why we implement NttResidueNumber, which guarantees that we can perform an NTT on a polynomial expressed using Residue Numbers – the individual moduli are prime numbers.

Both polynomials are represented by an immutable array of coefficients or evaluations, respectively. In the graph representation, the n-th primitive root of unity is also provided, and the polynomial is evaluated at its powers.

To represent a polynomial using coefficients, the NttRnCoefficientPolynomial class is used, which accepts a generic unmanaged type implementing IBinaryInteger. It can be created either from an array of Residue Numbers, where each Residue Number represents a coefficient

using ModularArithmetic.NTT;
// moduli are the same for every coefficient in the polynomial
int[] sharedModuli = [13, 17, 29];

// array of polynomial's coefficient - every coefficient is NttRN
NttResidueNumber<int>[] coefficients = new NttResidueNumber<int>[4];

// coefficient for x^0
coefficients[0] = new NttResidueNumber<int>([2, 3, 4], sharedModuli);

// for x^1
coefficients[1] = new NttResidueNumber<int>([1, 1, 1], sharedModuli);

// for x^2
coefficients[2] = new NttResidueNumber<int>([2, 1, 2], sharedModuli);

// for x^3
coefficients[3] = new NttResidueNumber<int>([3, 1, 11], sharedModuli);

// create the polynomial from the array of coefficients
var myPoly = new NttRnCoefficientPolynomial<int>(coefficients);

or it can be created from an array of regular integers (which represent coefficients) and an array of moduli (for conversion to Residue Number):

using System.Numerics;  // For BigInteger
using ModularArithmetic.NTT;

// coefficients expressed as BigIntegers, then internally converted to RN
BigInteger[] integerCoefficients = [7, 8, 9, 10];
long[] sharedModuli = [13, 17, 29];

// creating the polynomial, constructor will ensure that internally 
// the polynomial is represented via RNs
var myPoly = new NttRnCoefficientPolynomial<long>(integerCoefficients, sharedModuli);

It is also possible to create the object without validating the coefficients by using the SkipCoefficientsCheck method. This option is available only when the coefficients are provided directly as Residue Numbers.

// importing and creating the array of coefficients

var myPoly = NttRnCoefficientPolynomial<long>.SkipCoefficintsCheck(coefficients);

Object NttRnGraphPolynomial is created from evaluations (in the powers of n-th primitive root) and n-th primitive root given as NttResidueNumber:

using ModularArithmetic.NTT;	

int[] sharedModuli = [13, 17, 29];
// 8: n-th primitive root for 13
// 13: for 17
// 12: for 29
int[] primitiveRoots = [8, 13, 12];

// from sharedModuli a primitiveRoots we create RN representing
// n-th primitive root =: w
var w = NttResidueNumber<int>.SkipModuliCheck(primitiveRoots, sharedModuli)

// zoznam evaluacii primitivnych odmocnin
NttResidueNumber<int>[] evaluations = new NttResidueNumber<int>[4];

// evaluacia polynomu v w^0
evaluations[0] = new NttResidueNumber<int>([2, 3, 4], sharedModuli);

// w^1
evaluations[1] = new NttResidueNumber<int>([1, 1, 1], sharedModuli);

// w^2
evaluations[2] = new NttResidueNumber<int>([2, 1, 2], sharedModuli);

// w^3
evaluations[3] = new NttResidueNumber<int>([3, 1, 11], sharedModuli);

var myPoly = new NttRnGraphPolynomial<int>(evaluations, w);

Just like with NttRnCoefficientPolynomial, a method that bypasses input checks exists: SkipInputCheck.

A polynomial expressed with coefficients provides a method for the forward NTT, while a polynomial expressed as a graph provides a method for the inverse NTT. For the forward NTT, primitive root of unity must be supplied in a form of NttResidueNumber, since they are not required for the coefficient representation (and thus the object does not store them). However, they are necessary for performing forward NTT. On the other hand, Inverse NTT does not require any parameters when called.

// vytvorenie the array of coefficients and n-th primitive root

var polyCoeff = new NttRnCoefficientPolynomial<int>(coefficients);

// for forward NTT we need to pass n-th primitive root
// in the form of NttRN
var polyGraph = polyCoeff.TransformForward(nthPrimitiveRoot);

// for inverse NTT we do not need the nthPrimitiveRoot since objeect
// keeps track of it
var anotherCoeff = polyGraph.TransformInverse();

// parallel versions also exist
var polyGraph = polyCoeff.TransformForwardParallel(primitiveRoots);
var anotherCoeff = polyGraph.TransformInverseParallel();

In the case of the forward NTT, i.e., TransformForward and TransformForwardParallel, the returned object is of type NttRnGraphPolynomial, whereas for the inverse NTT, we return an NttRnCoefficientPolynomial.

Individual polynomials can also be tested for equality.

Examples

We also provide concrete and executable examples on how to use the library. They are available on GitLab.