Add Modular Exponentiation (TheAlgorithms#263)

aayushborkar14 · web-flow · commit 493792bfd481 · 2021-10-23T16:12:53.000+03:00
diff --git a/Algorithms.Tests/Numeric/ModularExponentiationTest.cs b/Algorithms.Tests/Numeric/ModularExponentiationTest.cs
@@ -0,0 +1,36 @@
+using Algorithms.Numeric;
+using System;
+using NUnit.Framework;
+using FluentAssertions;
+
+namespace Algorithms.Tests.Numeric
+{
+    public class ModularExponentiationTest
+    {
+        [Test]
+        [TestCase(3, 6, 11, 3)]
+        [TestCase(5, 3, 13, 8)]
+        [TestCase(2, 7, 17, 9)]
+        [TestCase(7, 4, 16, 1)]
+        [TestCase(7, 2, 11, 5)]
+        [TestCase(4, 13, 497, 445)]
+        [TestCase(13, 3, 1, 0)]
+        public void ModularExponentiationCorrect(int b, int e, int m, int expectedRes)
+        {
+            var modularExponentiation = new ModularExponentiation();
+            var actualRes = modularExponentiation.ModularPow(b, e, m);
+            actualRes.Should().Be(expectedRes);
+        }
+
+        [TestCase(17, 7, -3)]
+        [TestCase(11, 3, -5)]
+        [TestCase(14, 3, 0)]
+        public void ModularExponentiationNegativeMod(int b, int e, int m)
+        {
+            var modularExponentiation = new ModularExponentiation();
+            Action res = () => modularExponentiation.ModularPow(b, e, m);
+            res.Should().Throw<ArgumentException>()
+            .WithMessage(String.Format("{0} is not a positive integer", m));
+        }
+    }
+}
diff --git a/Algorithms/Numeric/ModularExponentiation.cs b/Algorithms/Numeric/ModularExponentiation.cs
@@ -0,0 +1,43 @@
+using System;
+
+namespace Algorithms.Numeric
+{
+    /// <summary>
+    ///     Modular exponentiation is a type of exponentiation performed over a modulus
+    ///     Modular exponentiation c is: c = b^e mod m where b is base, e is exponent, m is modulus
+    ///     (Wiki: https://en.wikipedia.org/wiki/Modular_exponentiation).
+    /// </summary>
+    public class ModularExponentiation
+    {
+        /// <summary>
+        ///     Performs Modular Exponentiation on b, e, m.
+        /// </summary>
+        /// <param name="b">Base.</param>
+        /// <param name="e">Exponent.</param>
+        /// <param name="m">Modulus.</param>
+        /// <returns>Modular Exponential.</returns>
+        public int ModularPow(int b, int e, int m)
+        {
+            // initialize result in variable res
+            int res = 1;
+            if (m == 1)
+            {
+                // 1 divides every number
+                return 0;
+            }
+
+            if (m <= 0)
+            {
+                // exponential not defined in this case
+                throw new ArgumentException(string.Format("{0} is not a positive integer", m));
+            }
+
+            for (int i = 0; i < e; i++)
+            {
+                res = (res * b) % m;
+            }
+
+            return res;
+        }
+    }
+}
diff --git a/README.md b/README.md
@@ -39,6 +39,7 @@ This repository contains algorithms and data structures implemented in C# for ed
       * [Binary GCD](./Algorithms/Numeric/GreatestCommonDivisor/BinaryGreatestCommonDivisorFinder.cs)
     * [Factorization](./Algorithms/Numeric/Factorization)
       * [Trial division Factorization](./Algorithms/Numeric/Factorization/TrialDivisionFactorizer.cs)
+    * [Modular Exponentiation](./Algorithms/Numeric/ModularExponentiation.cs)
     * [Series](./Algorithms/Numeric/Series)
       * [Maclaurin Series](./Algorithms/Numeric/Series/Maclaurin.cs)
     * [Gauss-Jordan Elimination](./Algorithms/Numeric/GaussJordanElimination.cs)
