Re: modInverse & powMod

[Salih Dincer via Digitalmars-d-learn]

On Friday, 7 June 2024 at 13:43:29 UTC, Salih Dincer wrote:

SDB@79

I have only one question: Is there a modInverse() function in the standard library for use in RSA?

Apparently not, it fell to lot :)

I already had such a function...

```d
auto modInverse(T)(T m, T n) pure
{
  T q, ilk = n;
  T y, tmp, x = 1;

  while (m > 1)
  {
    q = m / n;

    tmp = n;
      n = m % n;
      m = tmp;

    tmp = y;
      y = x - q * y;
      x = tmp;
  }
  return x < 0 ? x + ilk : x;
}
```

And in the BigInt module there was divMod() next to powmod():

```d
auto modInverse(BigInt a, BigInt m)
{
  BigInt q, m0 = m;
  BigInt tmp, y, x = 1;

  while (a > 1)
  {
    // m is remainder now
    tmp = m;
    divMod(a, m, q, m);

    // process same as Euclid's algorithm
    a = tmp;
    tmp = y;

    // Update y and x
    y = x - q * y;
    x = tmp;
  }

  // Make x positive
  if (x < 0) x += m0;

  return x;
}
```

Is PR required? Why not modInverse too!

SDB@79