-
Notifications
You must be signed in to change notification settings - Fork 1.5k
/
ModularExponentiation.cs
42 lines (37 loc) · 1.12 KB
/
ModularExponentiation.cs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
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;
}
}