// Copyright (C) 2026 Kiyotsugu Arai
// SPDX-License-Identifier: LGPL-3.0-or-later

// IntModular.hpp
// モジュラ演算（冪剰余、乗法的逆元）for Int

#ifndef CALX_INT_MODULAR_HPP
#define CALX_INT_MODULAR_HPP

#include "IntBase.hpp"

namespace calx {

/**
 * @brief モジュラ演算（剰余演算、冪剰余、乗法的逆元）
 *
 * RSA暗号、楕円曲線暗号、離散対数問題などで使用される基本的なモジュラ演算を提供します。
 * - powerMod: 冪剰余（binary exponentiation, O(log exp)）
 * - inverseMod: 乗法的逆元（拡張ユークリッド互除法使用）
 */
class IntModular {
public:
    /**
     * @brief 正規化剰余（常に 0 <= r < m を満たす）
     *
     * C++のoperator%とは異なり、Mathematica のMod[]と同じ動作をします。
     * 負の被除数に対しても正の剰余を返します。
     *
     * 例:
     *   mod(-7, 5) = 3  (C++の-7%5は-2)
     *   mod(7, 5) = 2
     *   mod(-7, -5) = -2
     *
     * @param x 被除数
     * @param m 法（modulus）
     * @return 剰余 r where 0 <= r < |m|
     *
     * 特殊ケース:
     *   mod(x, 0) = NaN（ゼロ除算）
     *   mod(NaN, m) = NaN
     *   mod(∞, m) = NaN
     */
    static Int mod(const Int& x, const Int& m);

    /**
     * @brief 冪剰余: base^exp mod m
     *
     * Binary exponentiation (right-to-left) アルゴリズムを使用。
     * 計算量: O(log exp) の乗算
     *
     * 例:
     *   powerMod(2, 10, 1000) = 1024 mod 1000 = 24
     *   powerMod(3, 100, 7) = 3^100 mod 7 = 4
     *
     * 負の指数:
     *   powerMod(a, -n, m) = inverseMod(a^n, m)
     *   つまり、a^(-n) ≡ (a^n)^(-1) mod m
     *
     * @param base 底
     * @param exp 指数（負も可）
     * @param m 法（modulus）
     * @return base^exp mod m
     *
     * 特殊ケース:
     *   powerMod(0, 0, m) = 1（0^0の定義）
     *   powerMod(x, 0, m) = 1
     *   powerMod(x, n, 1) = 0
     *   powerMod(NaN, n, m) = NaN
     *   powerMod(x, n, 0) = NaN（ゼロ除算）
     *
     * 制約:
     *   m > 0 でなければならない
     *   exp < 0 の場合、gcd(base, m) = 1 でなければならない（逆元が存在する条件）
     */
    static Int powerMod(const Int& base, const Int& exp, const Int& m);

    /**
     * @brief 乗法的逆元: a^(-1) mod m
     *
     * a * x ≡ 1 (mod m) を満たす x を返します。
     * 拡張ユークリッド互除法を使用して計算します。
     *
     * 例:
     *   inverseMod(3, 7) = 5  (because 3*5 = 15 ≡ 1 mod 7)
     *   inverseMod(2, 5) = 3  (because 2*3 = 6 ≡ 1 mod 5)
     *
     * 最適化: m が素数の場合
     *   a^(-1) ≡ a^(m-2) mod m（フェルマーの小定理）
     *   この場合、is_prime=true を指定すると高速化されます。
     *
     * @param a 逆元を求める整数
     * @param m 法（modulus）
     * @param is_prime m が素数であることが分かっている場合 true（最適化用、デフォルト false）
     * @return a^(-1) mod m
     *
     * 特殊ケース:
     *   逆元が存在しない（gcd(a, m) != 1）場合: Int::Zero()を返す
     *   inverseMod(0, m) = 0（逆元なし）
     *   inverseMod(1, m) = 1
     *   inverseMod(NaN, m) = NaN
     *   inverseMod(a, 0) = NaN（ゼロ除算）
     *   inverseMod(a, 1) = 0（任意のaに対してa≡0 mod 1）
     *
     * 制約:
     *   m > 1 でなければならない（m=1では全てが0に等しい）
     *   gcd(a, m) = 1 でなければならない（互いに素）
     */
    static Int inverseMod(const Int& a, const Int& m, bool is_prime = false);

    /**
     * @brief 定数時間冪剰余: base^exp mod m (GMP mpz_powm_sec 相当)
     *
     * 暗号用途向け。指数のビット値に依存する分岐・メモリアクセスパターンを排除。
     * - 固定ウィンドウ幅 (スライディングウィンドウではなく)
     * - 全テーブルエントリを毎回読み、条件付き選択 (cmov 相当)
     * - ビット 0/1 に関わらず sqr+mul を実行し、ダミー結果を破棄
     *
     * @param base 底 (非負)
     * @param exp 指数 (非負)
     * @param m 法 (奇数正整数)
     * @return base^exp mod m
     *
     * 制約:
     *   exp >= 0, m > 0, m は奇数
     *   (偶数 m は powerMod にフォールバック)
     */
    static Int powerModSec(const Int& base, const Int& exp, const Int& m);
};

} // namespace calx

#endif // CALX_INT_MODULAR_HPP