1

For educational purpose I'm developing c++ library for operating with large numbers represented as vectors of chars (vector<char>).

Here is algorithm that I am using for modular exponentiation:

BigInt modularExponentiation(BigInt base, BigInt exponent, BigInt mod) {
  BigInt x = B_ONE; // 1
  BigInt y = base;

  while (exponent > B_ZERO) { // while exponent != 0
    if (isOdd(exponent))
      x = (x * y) % mod;
    y = (y * y) % mod;
    exponent /= B_TWO; // exponent = exponent / 2
  }

  return (x % mod);
};

Is there any more efficent algorithm, or can this be improved (like parallelized with openmp)?

ПВ201 Николотов Александр
  • 98
  • 1
  • 8
  • 2
    Instead of dividing the exponent (which I assume shifts all the bits) you could iterate through the bits without shifting them. You could also calculate `modularMultiplication(a, b, mod)` instead of `(a * b) % mod` – user253751 Apr 19 '22 at 10:43
  • 4
    since this code works, consider codereview.stackexchange.com – user253751 Apr 19 '22 at 10:44
  • ```modularMultiplication(a, b, mod)``` is equal to: ```(a ** b) % mod```, so I cant replace ```(a * b) % mod``` with it. – ПВ201 Николотов Александр Apr 19 '22 at 15:30
  • 2
    modular **multiplication**. When you calculate `(a*b)%mod` in two steps, you calculate more bits than needed. – user253751 Apr 19 '22 at 15:30
  • Ohh, I get it. Actually, I've tried to implement modular multiplication, but any algorithm I tried were for some reason slower than just ```(a*b)%mod```. Could you advise some modular multiplication algorithm? – ПВ201 Николотов Александр Apr 19 '22 at 15:35
  • there is also mongomery reduction to avoid `%` and also in some cases you can exchange the `a%b` with `(a>b)?a-b:a` see [Modular arithmetics and NTT (finite field DFT) optimizations](https://stackoverflow.com/q/18577076/2521214) inspect `modpow` in there however read the whole thread as it work only in specific situation where `a` is not bigger than `2*b` – Spektre Apr 20 '22 at 08:16

0 Answers0