[API Proposal]: Hope to add this method Pow(BigInteger a, BigInteger b, BigInteger c)

[toolgood]

Background and motivation

python code like

print(pow(2,3,5)) #   2*2*2%5 = 8 % 5 = 3
print(2*2*2%5)  #   pow(2,3,5) = 3

API Proposal

namespace System.Collections.Generic;

        public static BigInteger Pow(BigInteger a, BigInteger b, BigInteger c)
        {
            Dictionary<BigInteger, BigInteger> dict = new Dictionary<BigInteger, BigInteger>();
            BigInteger temp = a;
            BigInteger count = 1;
            dict[count] = temp;
            while (count * 2 <= b) {
                count = count * 2;
                temp = BigInteger.Pow(temp, 2) % c;
                dict[count] = temp;
            }

            var keys = dict.Keys.OrderByDescending(k => k).ToList();
            BigInteger aa = 1;
            for (int i = 0; i < keys.Count; i++) {
                if (b >= keys[i]) {
                    b = b - keys[i];
                    aa = (aa * dict[keys[i]]) % c;
                }
            }
            return aa;
        }

API Usage

var bbbb = Pow(2, 3, 5);

Alternative Designs

No response

Risks

No response

[dotnet-policy-service]

Tagging subscribers to this area: @dotnet/area-system-numerics
See info in area-owners.md if you want to be subscribed.

[vcsjones]

It seems like you are asking for BigInteger.ModPow. Does that API suit your needs?