CODEWITHSUNDEEP
c#algorithmmodulo
Hary
Hary

Reputation: 125

How to perform modinverse in C#

Is there a way to perform modinverse in C#? My data is in BigInteger format.

P  : E61E05F338BC965421720C4128C33FDFC7BC3CE637A3BC92A114E79AC380C90387988639224FE5C578B601E505C85AF85EB86DAEC06413EA419187D1D2396C063CDA7DC805E47906E731F4A0B2C53521CAC812BE68044DBFA8E3DE4BE1E0D94F2E0CC9FC126D21E5AF7038FA0942D12700AFC4DE2D00FB3A1FA6A224D0FA0D7B

dP  : 00000000000000000000000000010001

dP^-1 mod P

I've tried BigInteger.ModPow(dP, -1, P). But I cannot use negative exponent.

Upvotes: 0

Views: 970

Answers (1)

Dmitrii Bychenko
Dmitrii Bychenko

Reputation: 186688

You have to implement Extended Euclidian Algorithm first:

public static BigInteger Egcd(BigInteger left, 
                              BigInteger right, 
                          out BigInteger leftFactor, 
                          out BigInteger rightFactor) {
  leftFactor = 0;
  rightFactor = 1;
  BigInteger u = 1;
  BigInteger v = 0;
  BigInteger gcd = 0;

  while (left != 0) {
    BigInteger q = right / left;
    BigInteger r = right % left;

    BigInteger m = leftFactor - u * q;
    BigInteger n = rightFactor - v * q;

    right = left;
    left = r;
    leftFactor = u;
    rightFactor = v;
    u = m;
    v = n;

    gcd = right;
  }

  return gcd;
}

And then

public static BigInteger ModInverse(BigInteger value, BigInteger modulo) {
  BigInteger x, y;

  if (1 != Egcd(value, modulo, out x, out y))
    throw new ArgumentException("Invalid modulo", nameof(modulo));

  if (x < 0)
    x += modulo;

  return x % modulo;
}

Upvotes: 4

Related Questions