decimal_power_mod.hpp

SECTIONMath INCLUDEnoya/decimal_power_mod.hpp

Compute base^exponent modulo an arbitrary positive 64-bit modulus from a decimal exponent of any length, without coprimality assumptions.

\[ \displaystyle a^e\equiv r\;(\bmod m) \]

Implementation

View on GitHub

SourceExpanded

#ifndef NOYA_DECIMAL_POWER_MOD_HPP
#define NOYA_DECIMAL_POWER_MOD_HPP 1

/// @complexity Time: O(d log m) bit operations for d decimal exponent digits.
/// Space: O(1) beyond the exponent string.

#include <cassert>
#include <cstdint>
#include <string_view>

namespace noya {

/// @brief Compute base^exponent modulo an arbitrary positive 64-bit modulus
/// from a decimal exponent of any length, without coprimality assumptions.
inline std::uint64_t decimal_power_mod(std::uint64_t base,
                                       std::string_view exponent,
                                       std::uint64_t modulus) {
  assert(modulus >= 1);
  assert(!exponent.empty());
  using u128 = unsigned __int128;
  auto multiply = [&](std::uint64_t first, std::uint64_t second) {
    return std::uint64_t(u128(first) * second % modulus);
  };
  auto power = [&](std::uint64_t value, int degree) {
    std::uint64_t result = 1 % modulus;
    while (degree > 0) {
      if (degree & 1) {
        result = multiply(result, value);
      }
      value = multiply(value, value);
      degree >>= 1;
    }
    return result;
  };
  base %= modulus;
  std::uint64_t result = 1 % modulus;
  for (char digit : exponent) {
    assert('0' <= digit && digit <= '9');
    result = multiply(power(result, 10), power(base, digit - '0'));
  }
  return result;
}

} // namespace noya

#endif // NOYA_DECIMAL_POWER_MOD_HPP

#include <cassert>
#include <cstdint>
#include <string_view>

/// @complexity Time: O(d log m) bit operations for d decimal exponent digits.
/// Space: O(1) beyond the exponent string.

namespace noya {

/// @brief Compute base^exponent modulo an arbitrary positive 64-bit modulus
/// from a decimal exponent of any length, without coprimality assumptions.
inline std::uint64_t decimal_power_mod(std::uint64_t base,
                                       std::string_view exponent,
                                       std::uint64_t modulus) {
  assert(modulus >= 1);
  assert(!exponent.empty());
  using u128 = unsigned __int128;
  auto multiply = [&](std::uint64_t first, std::uint64_t second) {
    return std::uint64_t(u128(first) * second % modulus);
  };
  auto power = [&](std::uint64_t value, int degree) {
    std::uint64_t result = 1 % modulus;
    while (degree > 0) {
      if (degree & 1) {
        result = multiply(result, value);
      }
      value = multiply(value, value);
      degree >>= 1;
    }
    return result;
  };
  base %= modulus;
  std::uint64_t result = 1 % modulus;
  for (char digit : exponent) {
    assert('0' <= digit && digit <= '9');
    result = multiply(power(result, 10), power(base, digit - '0'));
  }
  return result;
}

} // namespace noya