[API Proposal]: Add BigInteger.ModInverse(BigInteger value, BigInteger modulus)

[su-senka]

Background and motivation

The multiplicative modular inverse is a fundamental operation in number theory and applied
cryptography: given integers value and modulus with gcd(|value|, modulus) = 1, find
the unique x ∈ [0, modulus) such that (value * x) % modulus == 1. It is required by:

• RSA key generation: private exponent d = e⁻¹ (mod λ(n))
• ECDSA signature generation and verification: s = k⁻¹ (e + rd) (mod n)
• Chinese Remainder Theorem reconstruction
• Montgomery modular multiplication (used inside ModPow itself)
• General modular arithmetic in cryptography and computer algebra

System.Numerics.BigInteger already provides the two operations most closely related to
modular inverse:

public static BigInteger GreatestCommonDivisor(BigInteger left, BigInteger right); // coprimality check
public static BigInteger ModPow(BigInteger value, BigInteger exponent, BigInteger modulus); // modular exponentiation

The absence of ModInverse as a first-class API has two practical consequences:

1. Callers implement their own Extended Euclidean Algorithm, which is error-prone (negative
   intermediate Bézout coefficients, off-by-one in normalization, missing coprimality check).

2. Callers in crypto contexts pull in System.Security.Cryptography purely for a
   number-theoretic primitive that has no inherent security-namespace dependency.

Precedent across ecosystems:

Ecosystem	API	Behavior on non-coprime
Java (java.math)	BigInteger modInverse(BigInteger m)	ArithmeticException
Python (built-in)	pow(x, -1, m)	ValueError
GMP (C)	mpz_invert(r, a, n)	returns 0 (no exception)
BouncyCastle C#	BigInteger.ModInverse(BigInteger m)	ArithmeticException
OpenSSL (C)	BN_mod_inverse(r, a, n, ctx)	returns NULL

This issue supersedes #45279 (November 2020), in which the original author's
account was later deleted. @tannergooding noted on October 30, 2025 that a new proposal
following the current template would be the appropriate path forward.

API Proposal

namespace System.Numerics
{
    public readonly partial struct BigInteger
    {
        /// <summary>
        /// Finds the modular multiplicative inverse of <paramref name="value"/>
        /// modulo <paramref name="modulus"/>.
        /// </summary>
        /// <param name="value">
        /// The integer whose modular multiplicative inverse is to be found.
        /// May be negative; it is reduced to the canonical representative in
        /// <c>[0, modulus)</c> before processing.
        /// </param>
        /// <param name="modulus">The modulus. Must be greater than zero.</param>
        /// <returns>
        /// The least non-negative integer <c>x</c> in <c>[0, modulus)</c> satisfying
        /// <c>(value * x) % modulus == 1</c>.
        /// Returns <see cref="Zero"/> when <paramref name="modulus"/> is <c>1</c>.
        /// </returns>
        /// <exception cref="ArgumentOutOfRangeException">
        /// <paramref name="modulus"/> is less than or equal to zero.
        /// </exception>
        /// <exception cref="ArithmeticException">
        /// <paramref name="value"/> and <paramref name="modulus"/> are not coprime;
        /// that is, <c>GreatestCommonDivisor(Abs(value % modulus), modulus) != 1</c>.
        /// This includes the case where <c>value ≡ 0 (mod modulus)</c>.
        /// </exception>
        public static BigInteger ModInverse(BigInteger value, BigInteger modulus);
    }
}

API Usage

// Basic: 3 * 5 = 15 ≡ 1 (mod 7)
BigInteger inv = BigInteger.ModInverse(3, 7);
Debug.Assert(inv == 5);
Debug.Assert((3 * inv) % 7 == 1);

// RSA: private exponent d = e⁻¹ (mod λ(n))
BigInteger e = 65537;
BigInteger p = BigInteger.Parse("...");  // large prime
BigInteger q = BigInteger.Parse("...");  // large prime
BigInteger lambda = BigInteger.LeastCommonMultiple(p - 1, q - 1);
BigInteger d = BigInteger.ModInverse(e, lambda);
Debug.Assert(BigInteger.ModPow(e * d % lambda, 1, lambda) == 1);

// ECDSA signature: s = k⁻¹ * (z + r*d) mod n
BigInteger s = BigInteger.ModInverse(k, n) * (z + r * privateKey) % n;

// Chinese Remainder Theorem: x ≡ r₁ (mod m₁), x ≡ r₂ (mod m₂)
BigInteger m1 = 3, m2 = 5, r1 = 2, r2 = 3;
BigInteger M = m1 * m2;
BigInteger x = (r1 + m1 * (BigInteger.ModInverse(m1, m2) * (r2 - r1) % m2)) % M;
Debug.Assert(x % m1 == r1 && x % m2 == r2); // x == 8

// Negative value: reduced automatically
// ModInverse(-3, 7) == ModInverse(4, 7): 4 * 2 = 8 ≡ 1 (mod 7)
Debug.Assert(BigInteger.ModInverse(-3, 7) == 2);

// Exception: not coprime
Assert.Throws<ArithmeticException>(() => BigInteger.ModInverse(6, 9));   // gcd(6,9) = 3
Assert.Throws<ArithmeticException>(() => BigInteger.ModInverse(0, 5));   // gcd(0,5) = 5
Assert.Throws<ArgumentOutOfRangeException>(() => BigInteger.ModInverse(3, 0));
Assert.Throws<ArgumentOutOfRangeException>(() => BigInteger.ModInverse(3, -1));

Alternative Designs

Naming

ModPow (not ModularPower) establishes the convention of abbreviated prefix. ModInverse
is consistent and concise. ModularInverse (used in the original issue) is more descriptive
but breaks the pattern. ModInverse is recommended.

Static vs. instance

Java and BouncyCastle use instance methods (value.modInverse(modulus)). The .NET
BigInteger surface is predominantly static for multi-argument mathematical operations
(GreatestCommonDivisor, ModPow, Max, Min, Pow). Static is recommended.

TryModInverse companion

A non-throwing TryModInverse(BigInteger value, BigInteger modulus, out BigInteger result)
could be added alongside ModInverse. The case where inverse does not exist is an
exceptional condition (the caller should ensure coprimality, or pre-screen with
GreatestCommonDivisor). A throwing-only API is sufficient for v1; TryModInverse can be
added in a follow-up if there is demand.

modulus == 1 behavior

Returning Zero is mathematically consistent (Z/1Z contains only one element, 0, and
0 ≡ 1 (mod 1)) and matches Java and Python. An alternative is to throw
ArgumentOutOfRangeException for modulus < 2 (treating modulus-1 as degenerate). The
permissive behavior is preferred for consistency with existing ecosystems.

Risks

The operation is the Extended Euclidean Algorithm (EEA), computing one Bézout
coefficient alongside the GCD. The existing
BigIntegerCalculator.GcdInv.cs already implements Lehmer's accelerated GCD for multi-limb
inputs. A production implementation would extend that file with an extended variant that
also propagates the Bézout coefficient.

• New resource string: Arithmetic_ModInverseDoesNotExist — "The modular multiplicative
  inverse does not exist because value and modulus are not coprime"

• Cryptographic misuse: This API lowers the barrier to amateur cryptography. However,
  ModPow already establishes this precedent.

• Side-channel timing: The EEA is not constant-time. This is also true of ModPow's
  internal implementation. The API is not intended for secret-key operations in hardened
  cryptographic contexts (those should use System.Security.Cryptography).

[dotnet-policy-service]

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