ExtendedEuclideanAlgorithm.cs

using System.Numerics;

namespace Algorithms.ModularArithmetic
{
    /// <summary>
    ///     Extended Euclidean algorithm: https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm.
    /// </summary>
    public static class ExtendedEuclideanAlgorithm
    {
        /// <summary>
        ///     Computes the greatest common divisor (gcd) of integers a and b, also the coefficients of Bézout's identity,
        ///     which are integers x and y such that a*bezoutCoefficientOfA + b*bezoutCoefficientOfB = gcd(a, b).
        /// </summary>
        /// <param name="a">Input number.</param>
        /// <param name="b">Second input number.</param>
        /// <returns>A record of ExtendedEuclideanAlgorithmResult containing the bezout coefficients of a and b as well as the gcd(a,b).</returns>
        public static ExtendedEuclideanAlgorithmResult<long> Compute(long a, long b)
        {
            long quotient;
            long tmp;
            var s = 0L;
            var bezoutOfA = 1L;
            var r = b;
            var gcd = a;
            var bezoutOfB = 0L;

            while (r != 0)
            {
                quotient = gcd / r; // integer division

                tmp = gcd;
                gcd = r;
                r = tmp - quotient * r;

                tmp = bezoutOfA;
                bezoutOfA = s;
                s = tmp - quotient * s;
            }

            if (b != 0)
            {
                bezoutOfB = (gcd - bezoutOfA * a) / b; // integer division
            }

            return new ExtendedEuclideanAlgorithmResult<long>(bezoutOfA, bezoutOfB, gcd);
        }

        /// <summary>
        ///     Computes the greatest common divisor (gcd) of integers a and b, also the coefficients of Bézout's identity,
        ///     which are integers x and y such that a*bezoutCoefficientOfA + b*bezoutCoefficientOfB = gcd(a, b).
        /// </summary>
        /// <param name="a">Input number.</param>
        /// <param name="b">Second input number.</param>
        /// <returns>A record of ExtendedEuclideanAlgorithmResult containing the bezout coefficients of a and b as well as the gcd(a,b).</returns>
        public static ExtendedEuclideanAlgorithmResult<BigInteger> Compute(BigInteger a, BigInteger b)
        {
            BigInteger quotient;
            BigInteger tmp;
            var s = BigInteger.Zero;
            var bezoutOfA = BigInteger.One;
            var r = b;
            var gcd = a;
            var bezoutOfB = BigInteger.Zero;

            while (r != 0)
            {
                quotient = gcd / r; // integer division

                tmp = gcd;
                gcd = r;
                r = tmp - quotient * r;

                tmp = bezoutOfA;
                bezoutOfA = s;
                s = tmp - quotient * s;
            }

            if (b != 0)
            {
                bezoutOfB = (gcd - bezoutOfA * a) / b; // integer division
            }

            return new ExtendedEuclideanAlgorithmResult<BigInteger>(bezoutOfA, bezoutOfB, gcd);
        }

        /// <summary>
        /// The result type for the computation of the Extended Euclidean Algorithm.
        /// </summary>
        /// <typeparam name="T">The data type of the computation (i.e. long or BigInteger).</typeparam>
        /// <param name="bezoutA">The bezout coefficient of the parameter a to the computation.</param>
        /// <param name="bezoutB">The bezout coefficient of the parameter b to the computation.</param>
        /// <param name="gcd">The greatest common divisor of the parameters a and b to the computation.</param>
        public record ExtendedEuclideanAlgorithmResult<T>(T bezoutA, T bezoutB, T gcd);
    }
}