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

// IntFactorization.hpp
// Full prime-factorization dispatcher

#pragma once

#include "IntBase.hpp"
#include "IntPrime.hpp"
#include "IntGCD.hpp"
#include "IntModular.hpp"

#include <vector>
#include <utility>
#include <algorithm>
#include <string>
#include <sstream>

namespace sangi {

/**
 * @brief Full prime-factorization dispatcher
 *
 * Combines multiple factor-search algorithms to perform a complete prime factorization.
 *
 * Strategy:
 *   1. Strip factors 2..1987 via small-prime batch GCD
 *   2. Apply factor-search algorithms to the remainder in stages:
 *      - Pollard p-1 (effective when p-1 is smooth)
 *      - Pollard rho / Brent (general-purpose, O(n^{1/4}))
 *      - Fermat's method (effective for closely spaced factor pairs)
 *   3. Recursively factor composite divisors
 *   4. Sort the result in ascending order of primes
 */
class IntFactorization {
public:
    /**
     * @brief Full prime factorization
     *
     * Fully factor n into a product of primes.
     *
     * @param n Integer to factor (n > 1)
     * @param millerRabinK Number of Miller-Rabin tests (default 20)
     * @return Vector of (prime, exponent) pairs {{p1,e1}, {p2,e2}, ...}
     *         in ascending order p1 < p2 < ...
     *
     * Special cases:
     *   factorize(0) → {{0, 1}}
     *   factorize(1) → {}
     *   factorize(-n) -> factorize(n) (sign ignored)
     *   factorize(prime) -> {{p, 1}}
     *
     * Example:
     *   factorize(360) → {{2,3}, {3,2}, {5,1}}
     *   factorize(2^32-1) → {{3,1}, {5,1}, {17,1}, {257,1}, {65537,1}}
     */
    static std::vector<std::pair<Int, int>> factorize(const Int& n, int millerRabinK = 20);

    /**
     * @brief Single-factor search (find one non-trivial factor)
     *
     * Try multiple algorithms in stages and return one non-trivial factor of n.
     *
     * @param n Composite number (n > 1)
     * @param millerRabinK Number of Miller-Rabin tests
     * @return A non-trivial factor of n; returns n if none is found
     */
    static Int findFactor(const Int& n, int millerRabinK = 20);

    /**
     * @brief Display the factorization result as a string
     *
     * @param factors Return value of factorize()
     * @return String like "2^3 * 3^2 * 5"
     */
    static std::string toString(const std::vector<std::pair<Int, int>>& factors);
};

} // namespace sangi