ModularArithmetic 1.1.3

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

TBA

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