I know there is modular exponentiation std.math.exponential.powmod in the standard library.While it works great in Pyrhon (even with very large numbers), it doesn't work with signed numbers in D. That's why I turned to the alternative below. Don't let it be misunderstood, I don't want to wear out the D language, I use whatever I have, I love D and I don't ask why it works so strangely.

//import std.math.exponential : fpowmod = powmod; /*
T fpowmod(T)(T base, T exponent, T modulus)
{
    auto r = T(1);
    for (T x = base, y = exponent; y;
        x = x * x % modulus, y /= 2)
        if (y % 2) r = r * x % modulus;

    return r;
}//*/

Thanks...

SDB@79

I have only one question: Is there a modInverse() function in the standard library for use in RSA? I did research on this subject within the relevant modules. I guess not these?

• std.mathspecial.logmdigammaInverse
• std.numeric.inverseFft

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

Apparently not, it fell to lot :)

I already had such a function...

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():

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

On Saturday, 8 June 2024 at 12:28:43 UTC, Salih Dincer wrote:

long extendedEuclidean(long a, long b) {
    long old_r = a, r = b;
    long old_s = 1, s = 0;
    long old_t = 0, t = 1;

    while (r != 0) {
        long quotient = old_r / r;
        long temp = r;
        r = old_r - quotient * r;
        old_r = temp;

        temp = s;
        s = old_s - quotient * s;
        old_s = temp;

        temp = t;
        t = old_t - quotient * t;
        old_t = temp;
    }

    if (old_s < 0) {
        old_s += b;
    }

    return old_s;
}

Apparently no one is as interested in RSA as I am, so I just wanted to paste the standalone algorithm here for reference.

SDB@79

On Saturday, 8 June 2024 at 12:28:43 UTC, Salih Dincer wrote:

The std.bigint module was prepared very harmoniously with its backend, but it seems to have been removed to the dusty pages of history. It isn't even magic touches made. The following is one of them:

// ref. std.internal.math.biguintcore:
auto pow(T)(T e)
  => BigUint.pow(data, absUnsign(e)); /* or
  => data ^^ e; //*/

I just realized this. In fact, it has a lot of benefits. Because what you're trying to implement will work on all types. For example, let me try to illustrate with primeMersenne():

auto primeMersenne(T)(T e)
{
  auto res = T(2);
  auto exp = cast(int)e;

  static if (__traits(isIntegral, T))
    import std.math : pow;

  if (auto result = res.pow(exp))
    return result - 1;
  assert(0, "Overflow number");
}

Thanks...

SDB@79