Extend System.Numerics.BigInteger to include a Method to Compute Modular Inverse.

[ghost]

Background and Motivation

The concept of an multiplicative inverse modulo a base, is perhaps as fundamental as BigInteger.GreatestCommonDivisor. I would propose adding this as a method. This allows development to stay close to BigInteger, rather than have to rely on Cryptographic imports. If this is not selected, perhaps at least an explanation as to why this method was not included?

I mean, if you are including ModPow as a primitive method? Why not ModInverse?

Proposed API

//public static System.Numerics.BigInteger ModularInverse (System.Numerics.BigInteger modulus) ;

        public BigInteger modInverse(BigInteger modulus)
        {
                BigInteger[] p = { 0, 1 };
                BigInteger[] q = new BigInteger[2];    // quotients
                BigInteger[] r = { 0, 0 };             // remainders

                int step = 0;

                BigInteger a = modulus;
                BigInteger b = this;

                while(b.dataLength > 1 || (b.dataLength == 1 && b.data[0] != 0))
                {
                        BigInteger quotient = new BigInteger();
                        BigInteger remainder = new BigInteger();

                        if(step > 1)
                        {
                                BigInteger pval = (p[0] - (p[1] * q[0])) % modulus;
                                p[0] = p[1];
                                p[1] = pval;
                        }

                        if(b.dataLength == 1)
                                singleByteDivide(a, b, quotient, remainder);
                        else
                                multiByteDivide(a, b, quotient, remainder);

                        /*
                        Console.WriteLine(quotient.dataLength);
                        Console.WriteLine("{0} = {1}({2}) + {3}  p = {4}", a.ToString(10),
                                          b.ToString(10), quotient.ToString(10), remainder.ToString(10),
                                          p[1].ToString(10));
                        */

                        q[0] = q[1];
                        r[0] = r[1];
                        q[1] = quotient; r[1] = remainder;

                        a = b;
                        b = remainder;

                        step++;
                }

                if(r[0].dataLength > 1 || (r[0].dataLength == 1 && r[0].data[0] != 1))
                        throw (new ArithmeticException("No inverse!"));

                BigInteger result = ((p[0] - (p[1] * q[0])) % modulus);

                if((result.data[maxLength - 1] & 0x80000000) != 0)
                        result += modulus;  // get the least positive modulus

                return result;
        }

// xref: https://www.codeproject.com/Articles/2728/C-BigInteger-Class

Usage Examples

BigInteger modulus = new BigInteger(5915587276);
BigInteger exponent = new BigInteger(65537);
BigInteger inverse = exponent.ModInverse(modulus);
// Returns 3603040989 , such that 65537*3603040989 == 1 Mod 5915587276

Alternative Designs

This is just an idea. I think it would make use of the BigInteger class as a primitive stronger. This way we don't have to rely on our custom implementations of calculating an inverse.

Risks

Minimal.

Thank you for your consideration.

[ghost]

Tagging subscribers to this area: @tannergooding, @pgovind, @jeffhandley See info in area-owners.md if you want to be subscribed.

Issue Details

---

## Background and Motivation The concept of an multiplicative inverse modulo a base, is perhaps as fundamental as BigInteger.GreatestCommonDivisor. I would propose adding this as a method. This allows development to stay close to BigInteger, rather than have to rely on Cryptographic imports. If this is not selected, perhaps at least an explanation as to why this method was not included? I mean, if you are including ModPow as a primitive method? Why not ModInverse? ## Proposed API ``` //public static System.Numerics.BigInteger ModularInverse (System.Numerics.BigInteger modulus) ; public BigInteger modInverse(BigInteger modulus) { BigInteger[] p = { 0, 1 }; BigInteger[] q = new BigInteger[2]; // quotients BigInteger[] r = { 0, 0 }; // remainders int step = 0; BigInteger a = modulus; BigInteger b = this; while(b.dataLength > 1 || (b.dataLength == 1 && b.data[0] != 0)) { BigInteger quotient = new BigInteger(); BigInteger remainder = new BigInteger(); if(step > 1) { BigInteger pval = (p[0] - (p[1] * q[0])) % modulus; p[0] = p[1]; p[1] = pval; } if(b.dataLength == 1) singleByteDivide(a, b, quotient, remainder); else multiByteDivide(a, b, quotient, remainder); /* Console.WriteLine(quotient.dataLength); Console.WriteLine("{0} = {1}({2}) + {3} p = {4}", a.ToString(10), b.ToString(10), quotient.ToString(10), remainder.ToString(10), p[1].ToString(10)); */ q[0] = q[1]; r[0] = r[1]; q[1] = quotient; r[1] = remainder; a = b; b = remainder; step++; } if(r[0].dataLength > 1 || (r[0].dataLength == 1 && r[0].data[0] != 1)) throw (new ArithmeticException("No inverse!")); BigInteger result = ((p[0] - (p[1] * q[0])) % modulus); if((result.data[maxLength - 1] & 0x80000000) != 0) result += modulus; // get the least positive modulus return result; } // xref: https://www.codeproject.com/Articles/2728/C-BigInteger-Class ``` ## Usage Examples ``` BigInteger modulus = new BigInteger(5915587276); BigInteger exponent = new BigInteger(65537); BigInteger inverse = exponent.ModInverse(modulus); // Returns 3603040989 , such that 65537*3603040989 == 1 Mod 5915587276 ``` ## Alternative Designs This is just an idea. I think it would make use of the BigInteger class as a primitive stronger. This way we don't have to rely on our custom implementations of calculating an inverse. ## Risks Minimal. Thank you for your consideration.

Author:	secdev-01
Assignees:	-
Labels:	`api-suggestion`, `area-System.Numerics`, `untriaged`
Milestone:	-

[pgovind]

Adding this to my queue. I won't be able to look at it this month, but I'll consider this in Jan 2021.

[tannergooding]

This seems reasonable to add to me. I'll let @pgovind do the triage here though 😄

[ghost]

Any updates or momentum on this?

[rubo]

This would be extremely useful. Any update?

[secdev02]

This again seems useful as it allows development to stay within the BigInteger Class, rather than rely on external Classes and Methods, or worse, cryptographic applications that are writing their own, untested, error prone Mod Inverse routines.