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

// IntModular.hpp
// Modular arithmetic (modular exponentiation, multiplicative inverse) for Int

#ifndef SANGI_INT_MODULAR_HPP
#define SANGI_INT_MODULAR_HPP

#include "IntBase.hpp"

namespace sangi {

/**
 * @brief Modular arithmetic (mod, modular exponentiation, multiplicative inverse)
 *
 * Provides the basic modular-arithmetic operations used in RSA, elliptic-curve
 * cryptography, the discrete-log problem, and so on.
 * - powerMod: modular exponentiation (binary exponentiation, O(log exp))
 * - inverseMod: multiplicative inverse (uses extended Euclidean algorithm)
 */
class SANGI_API IntModular {
public:
    /**
     * @brief Normalized modulo (always satisfies 0 <= r < m)
     *
     * Unlike C++'s operator%, this behaves like Mathematica's Mod[].
     * It returns a non-negative remainder even for negative dividends.
     *
     * Examples:
     *   mod(-7, 5) = 3  (C++'s -7 % 5 is -2)
     *   mod(7, 5) = 2
     *   mod(-7, -5) = -2
     *
     * @param x Dividend
     * @param m Modulus
     * @return Remainder r where 0 <= r < |m|
     *
     * Special cases:
     *   mod(x, 0) = NaN (division by zero)
     *   mod(NaN, m) = NaN
     *   mod(infinity, m) = NaN
     */
    static Int mod(const Int& x, const Int& m);

    /**
     * @brief Modular exponentiation: base^exp mod m
     *
     * Uses a binary exponentiation (right-to-left) algorithm.
     * Complexity: O(log exp) multiplications.
     *
     * Examples:
     *   powerMod(2, 10, 1000) = 1024 mod 1000 = 24
     *   powerMod(3, 100, 7) = 3^100 mod 7 = 4
     *
     * Negative exponents:
     *   powerMod(a, -n, m) = inverseMod(a^n, m)
     *   i.e. a^(-n) == (a^n)^(-1) mod m
     *
     * @param base Base
     * @param exp Exponent (may be negative)
     * @param m Modulus
     * @return base^exp mod m
     *
     * Special cases:
     *   powerMod(0, 0, m) = 1 (definition of 0^0)
     *   powerMod(x, 0, m) = 1
     *   powerMod(x, n, 1) = 0
     *   powerMod(NaN, n, m) = NaN
     *   powerMod(x, n, 0) = NaN (division by zero)
     *
     * Constraints:
     *   m must satisfy m > 0
     *   When exp < 0, gcd(base, m) must equal 1 (condition for the inverse to exist)
     */
    static Int powerMod(const Int& base, const Int& exp, const Int& m);

    /**
     * @brief Multiplicative inverse: a^(-1) mod m
     *
     * Returns x satisfying a * x == 1 (mod m).
     * Computed via the extended Euclidean algorithm.
     *
     * Examples:
     *   inverseMod(3, 7) = 5  (because 3*5 = 15 == 1 mod 7)
     *   inverseMod(2, 5) = 3  (because 2*3 = 6 == 1 mod 5)
     *
     * Optimization: when m is prime
     *   a^(-1) == a^(m-2) mod m (Fermat's little theorem)
     *   Specifying is_prime=true enables this faster path.
     *
     * @param a Integer whose inverse is sought
     * @param m Modulus
     * @param is_prime true when it is known that m is prime (for optimization, default false)
     * @return a^(-1) mod m
     *
     * Special cases:
     *   When the inverse does not exist (gcd(a, m) != 1): returns Int::Zero()
     *   inverseMod(0, m) = 0 (no inverse)
     *   inverseMod(1, m) = 1
     *   inverseMod(NaN, m) = NaN
     *   inverseMod(a, 0) = NaN (division by zero)
     *   inverseMod(a, 1) = 0 (every a is == 0 mod 1)
     *
     * Constraints:
     *   m must satisfy m > 1 (with m=1, everything is congruent to 0)
     *   gcd(a, m) must equal 1 (a and m must be coprime)
     */
    static Int inverseMod(const Int& a, const Int& m, bool is_prime = false);

    /**
     * @brief Constant-time modular exponentiation: base^exp mod m
     *        (equivalent to GMP's mpz_powm_sec)
     *
     * Intended for cryptographic use. Eliminates branches and memory-access
     * patterns that depend on the bits of the exponent.
     * - Fixed window width (not sliding window)
     * - Reads every table entry each time and selects conditionally (cmov-style)
     * - Performs sqr+mul regardless of whether the bit is 0/1, discarding the dummy result
     *
     * @param base Base (non-negative)
     * @param exp Exponent (non-negative)
     * @param m Modulus (odd positive integer)
     * @return base^exp mod m
     *
     * Constraints:
     *   exp >= 0, m > 0, m must be odd
     *   (Falls back to powerMod for even m)
     */
    static Int powerModSec(const Int& base, const Int& exp, const Int& m);
};

} // namespace sangi

#endif // SANGI_INT_MODULAR_HPP