ModularArithmetic 1.1.4

Modular Arithmetic Library

under construction

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);