library/_internal/math/modpow.hpp

• View this file on GitHub
• Last update: 2025-08-17 00:21:01+09:00
• Include: #include "library/_internal/math/modpow.hpp"

Required by

• ミラー・ラビン素数判定法 (library/math/miller-rabin.hpp)
• ポラード・ロー素因数分解法 (library/math/pollards-rho.hpp)

Verified with

• tests/math/miller-rabin/libchecker.test.cpp
• tests/math/pollards-rho/libchecker.test.cpp

Code

#pragma once

#include <concepts>
using namespace std;

namespace asalib::_internal::math {
  template<integral T>
  T modpow(T a, T n, T mod) {
    static_assert(sizeof(T) == 4 || sizeof(T) == 8, "T must be 32-bit or 64-bit integer type");
    constexpr bool is_64bit = sizeof(T) == 8;

    T res = 1;
    while (n) {
      if constexpr (is_64bit) {
        if (n & 1) res = static_cast<__uint128_t>(res) * a % mod;
        a = static_cast<__uint128_t>(a) * a % mod;
      }
      else {
        if (n & 1) res = static_cast<unsigned long long>(res) * a % mod;
        a = static_cast<unsigned long long>(a) * a % mod;
      }
      n >>= 1;
    }
    return res;
  }
}  // namespace asalib::_internal::math

#line 2 "library/_internal/math/modpow.hpp"

#include <concepts>
using namespace std;

namespace asalib::_internal::math {
  template<integral T>
  T modpow(T a, T n, T mod) {
    static_assert(sizeof(T) == 4 || sizeof(T) == 8, "T must be 32-bit or 64-bit integer type");
    constexpr bool is_64bit = sizeof(T) == 8;

    T res = 1;
    while (n) {
      if constexpr (is_64bit) {
        if (n & 1) res = static_cast<__uint128_t>(res) * a % mod;
        a = static_cast<__uint128_t>(a) * a % mod;
      }
      else {
        if (n & 1) res = static_cast<unsigned long long>(res) * a % mod;
        a = static_cast<unsigned long long>(a) * a % mod;
      }
      n >>= 1;
    }
    return res;
  }
}  // namespace asalib::_internal::math

Back to top page