ChineseRemainderTheorem.cs

using System;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;

namespace Algorithms.ModularArithmetic;

/// <summary>
/// Chinese Remainder Theorem: https://en.wikipedia.org/wiki/Chinese_remainder_theorem.
/// </summary>
public static class ChineseRemainderTheorem
{
    /// <summary>
    ///     The Chinese Remainder Theorem is used to compute x for given set of pairs of integers (a_i, n_i) with:
    ///     <list type="bullet">
    ///         <item>x = a_0 mod n_0</item>
    ///         <item>x = a_1 mod n_1</item>
    ///         <item>...</item>
    ///         <item>x = a_k mod n_k</item>
    ///     </list>
    ///     for 0 &lt;= i &lt; k, for some positive integer k. Additional requirements are:
    ///     <list type="bullet">
    ///         <item>n_i > 1 for 0 &lt;= i &lt; k</item>
    ///         <item>n_i and n_j are coprime, for all 0 &lt;= i &lt; j &lt; k</item>
    ///         <item>0 &lt;= a_i &lt; n_i, for all 0 &lt;= i &lt; k</item>
    ///         <item>0 &lt;= x &lt; n_0 * n_1 * ... * n_(k-1)</item>
    ///     </list>
    /// </summary>
    /// <param name="listOfAs">An ordered list of a_0, a_1, ..., a_k.</param>
    /// <param name="listOfNs">An ordered list of n_0, n_1, ..., n_k.</param>
    /// <returns>The value x.</returns>
    /// <exception cref="ArgumentException">If any of the requirements is not fulfilled.</exception>
    public static long Compute(List<long> listOfAs, List<long> listOfNs)
    {
        // Check the requirements for this algorithm:
        CheckRequirements(listOfAs, listOfNs);

        // For performance-reasons compute the product of all n_i as prodN, because we're going to need access to (prodN / n_i) for all i:
        var prodN = 1L;
        foreach (var n in listOfNs)
        {
            prodN *= n;
        }

        var result = 0L;
        for (var i = 0; i < listOfNs.Count; i++)
        {
            var a_i = listOfAs[i];
            var n_i = listOfNs[i];
            var modulus_i = prodN / n_i;

            var bezout_modulus_i = ExtendedEuclideanAlgorithm.Compute(n_i, modulus_i).BezoutB;
            result += a_i * bezout_modulus_i * modulus_i;
        }

        // Make sure, result is in [0, prodN).
        result %= prodN;
        if (result < 0)
        {
            result += prodN;
        }

        return result;
    }

    /// <summary>
    ///     The Chinese Remainder Theorem is used to compute x for given set of pairs of integers (a_i, n_i) with:
    ///     <list type="bullet">
    ///         <item>x = a_0 mod n_0</item>
    ///         <item>x = a_1 mod n_1</item>
    ///         <item>...</item>
    ///         <item>x = a_k mod n_k</item>
    ///     </list>
    ///     for 0 &lt;= i &lt; k, for some positive integer k. Additional requirements are:
    ///     <list type="bullet">
    ///         <item>n_i > 1 for 0 &lt;= i &lt; k</item>
    ///         <item>n_i and n_j are coprime, for all 0 &lt;= i &lt; j &lt; k</item>
    ///         <item>0 &lt;= a_i &lt; n_i, for all 0 &lt;= i &lt; k</item>
    ///         <item>0 &lt;= x &lt; n_0 * n_1 * ... * n_(k-1)</item>
    ///     </list>
    /// </summary>
    /// <param name="listOfAs">An ordered list of a_0, a_1, ..., a_k.</param>
    /// <param name="listOfNs">An ordered list of n_0, n_1, ..., n_k.</param>
    /// <returns>The value x.</returns>
    /// <exception cref="ArgumentException">If any of the requirements is not fulfilled.</exception>
    public static BigInteger Compute(List<BigInteger> listOfAs, List<BigInteger> listOfNs)
    {
        // Check the requirements for this algorithm:
        CheckRequirements(listOfAs, listOfNs);

        // For performance-reasons compute the product of all n_i as prodN, because we're going to need access to (prodN / n_i) for all i:
        var prodN = BigInteger.One;
        foreach (var n in listOfNs)
        {
            prodN *= n;
        }

        var result = BigInteger.Zero;
        for (var i = 0; i < listOfNs.Count; i++)
        {
            var a_i = listOfAs[i];
            var n_i = listOfNs[i];
            var modulus_i = prodN / n_i;

            var bezout_modulus_i = ExtendedEuclideanAlgorithm.Compute(n_i, modulus_i).BezoutB;
            result += a_i * bezout_modulus_i * modulus_i;
        }

        // Make sure, result is in [0, prodN).
        result %= prodN;
        if (result < 0)
        {
            result += prodN;
        }

        return result;
    }

    /// <summary>
    /// Checks the requirements for the algorithm and throws an ArgumentException if they are not being met.
    /// </summary>
    /// <param name="listOfAs">An ordered list of a_0, a_1, ..., a_k.</param>
    /// <param name="listOfNs">An ordered list of n_0, n_1, ..., n_k.</param>
    /// <exception cref="ArgumentException">If any of the requirements is not fulfilled.</exception>
    private static void CheckRequirements(List<long> listOfAs, List<long> listOfNs)
    {
        if (listOfAs == null || listOfNs == null || listOfAs.Count != listOfNs.Count)
        {
            throw new ArgumentException("The parameters 'listOfAs' and 'listOfNs' must not be null and have to be of equal length!");
        }

        if (listOfNs.Any(x => x <= 1))
        {
            throw new ArgumentException($"The value {listOfNs.First(x => x <= 1)} for some n_i is smaller than or equal to 1.");
        }

        if (listOfAs.Any(x => x < 0))
        {
            throw new ArgumentException($"The value {listOfAs.First(x => x < 0)} for some a_i is smaller than 0.");
        }

        // Check if all pairs of (n_i, n_j) are coprime:
        for (var i = 0; i < listOfNs.Count; i++)
        {
            for (var j = i + 1; j < listOfNs.Count; j++)
            {
                long gcd;
                if ((gcd = ExtendedEuclideanAlgorithm.Compute(listOfNs[i], listOfNs[j]).Gcd) != 1L)
                {
                    throw new ArgumentException($"The GCD of n_{i} = {listOfNs[i]} and n_{j} = {listOfNs[j]} equals {gcd} and thus these values aren't coprime.");
                }
            }
        }
    }

    /// <summary>
    /// Checks the requirements for the algorithm and throws an ArgumentException if they are not being met.
    /// </summary>
    /// <param name="listOfAs">An ordered list of a_0, a_1, ..., a_k.</param>
    /// <param name="listOfNs">An ordered list of n_0, n_1, ..., n_k.</param>
    /// <exception cref="ArgumentException">If any of the requirements is not fulfilled.</exception>
    private static void CheckRequirements(List<BigInteger> listOfAs, List<BigInteger> listOfNs)
    {
        if (listOfAs == null || listOfNs == null || listOfAs.Count != listOfNs.Count)
        {
            throw new ArgumentException("The parameters 'listOfAs' and 'listOfNs' must not be null and have to be of equal length!");
        }

        if (listOfNs.Any(x => x <= 1))
        {
            throw new ArgumentException($"The value {listOfNs.First(x => x <= 1)} for some n_i is smaller than or equal to 1.");
        }

        if (listOfAs.Any(x => x < 0))
        {
            throw new ArgumentException($"The value {listOfAs.First(x => x < 0)} for some a_i is smaller than 0.");
        }

        // Check if all pairs of (n_i, n_j) are coprime:
        for (var i = 0; i < listOfNs.Count; i++)
        {
            for (var j = i + 1; j < listOfNs.Count; j++)
            {
                BigInteger gcd;
                if ((gcd = ExtendedEuclideanAlgorithm.Compute(listOfNs[i], listOfNs[j]).Gcd) != BigInteger.One)
                {
                    throw new ArgumentException($"The GCD of n_{i} = {listOfNs[i]} and n_{j} = {listOfNs[j]} equals {gcd} and thus these values aren't coprime.");
                }
            }
        }
    }
}