/*
 * $Id$
 */

package edu.jas.ufd;


import java.util.ArrayList;
import java.util.List;
import java.util.Map;
import java.util.SortedMap;
import java.util.SortedSet;
import java.util.TreeMap;
import java.util.TreeSet;

import org.apache.log4j.Logger;

import edu.jas.arith.BigInteger;
import edu.jas.arith.ModLongRing;
import edu.jas.arith.Modular;
import edu.jas.arith.ModularRingFactory;
import edu.jas.poly.GenPolynomial;
import edu.jas.poly.GenPolynomialRing;
import edu.jas.poly.PolyUtil;
import edu.jas.structure.GcdRingElem;
import edu.jas.structure.Power;
import edu.jas.structure.RingFactory;


/**
 * Modular coefficients factorization algorithms. This class implements
 * factorization methods for polynomials over (prime) modular integers.
 * @author Heinz Kredel
 */

public class FactorModular & Modular> extends FactorAbsolute {


    private static final Logger logger = Logger.getLogger(FactorModular.class);


    private final boolean debug = logger.isDebugEnabled();


    /**
     * No argument constructor, do not use.
     */
    @SuppressWarnings("unused")
    private FactorModular() {
        this((RingFactory) (Object) new ModLongRing(13, true)); // hack, 13 unimportant
    }


    /**
     * Constructor.
     * @param cfac coefficient ring factory.
     */
    public FactorModular(RingFactory cfac) {
        super(cfac);
    }


    /**
     * GenPolynomial base distinct degree factorization.
     * @param P squarefree and monic GenPolynomial.
     * @return [e_1 -> p_1, ..., e_k -> p_k] with P = prod_{i=1,...,k} p_i
     *         and p_i has only irreducible factors of degree e_i.
     */
    public SortedMap> baseDistinctDegreeFactors(GenPolynomial P) {
        if (P == null) {
            throw new IllegalArgumentException(this.getClass().getName() + " P != null");
        }
        SortedMap> facs = new TreeMap>();
        if (P.isZERO()) {
            return facs;
        }
        GenPolynomialRing pfac = P.ring;
        if (pfac.nvar > 1) {
            throw new IllegalArgumentException(this.getClass().getName() + " only for univariate polynomials");
        }
        ModularRingFactory mr = (ModularRingFactory) pfac.coFac;
        java.math.BigInteger m = mr.getIntegerModul().getVal();
        //if (m.longValue() == 2L) {
        //    logger.warn(this.getClass().getName() + " case p = 2 not implemented");
        //}
        GenPolynomial x = pfac.univariate(0);
        GenPolynomial h = x;
        GenPolynomial f = P;
        GenPolynomial g;
        Power> pow = new Power>(pfac);
        long d = 0;
        while (d + 1 <= f.degree(0) / 2) {
            d++;
            h = pow.modPower(h, m, f);
            g = engine.gcd(h.subtract(x), f);
            if (!g.isONE()) {
                facs.put(d, g);
                f = f.divide(g);
            }
        }
        if (!f.isONE()) {
            d = f.degree(0);
            facs.put(d, f);
        }
        return facs;
    }


    /**
     * GenPolynomial base equal degree factorization.
     * @param P squarefree and monic GenPolynomial.
     * @param deg such that P has only irreducible factors of degree deg.
     * @return [p_1,...,p_k] with P = prod_{i=1,...,r} p_i.
     */
    public List> baseEqualDegreeFactors(GenPolynomial P, long deg) {
        if (P == null) {
            throw new IllegalArgumentException(this.getClass().getName() + " P != null");
        }
        List> facs = new ArrayList>();
        if (P.isZERO()) {
            return facs;
        }
        GenPolynomialRing pfac = P.ring;
        if (pfac.nvar > 1) {
            throw new IllegalArgumentException(this.getClass().getName() + " only for univariate polynomials");
        }
        if (P.degree(0) == deg) {
            facs.add(P);
            return facs;
        }
        ModularRingFactory mr = (ModularRingFactory) pfac.coFac;
        java.math.BigInteger m = mr.getIntegerModul().getVal();
        //System.out.println("m = " + m);
        boolean p2 = false;
        if (m.equals(java.math.BigInteger.valueOf(2L))) {
            p2 = true;
            //throw new RuntimeException(this.getClass().getName() + " case p = 2 not implemented");
        }
        GenPolynomial one = pfac.getONE();
        GenPolynomial t = pfac.univariate(0, 1L);
        GenPolynomial r;
        GenPolynomial h;
        GenPolynomial f = P;
        //GreatestCommonDivisor engine = GCDFactory. getImplementation(pfac.coFac);
        Power> pow = new Power>(pfac);
        GenPolynomial g = null;
        int degi = (int) deg; //f.degree(0);
        //System.out.println("deg = " + deg);
        BigInteger di = Power. positivePower(new BigInteger(m), deg);
        //System.out.println("di = " + di);
        java.math.BigInteger d = di.getVal(); //.longValue()-1;
        //System.out.println("d = " + d);
        d = d.shiftRight(1); // divide by 2
        do {
            if (p2) {
                h = t;
                for (int i = 1; i < degi; i++) {
                    h = t.sum(h.multiply(h));
                    h = h.remainder(f);
                }
                t = t.multiply(pfac.univariate(0, 2L));
                //System.out.println("h = " + h);
            } else {
                r = pfac.random(17, degi, 2 * degi, 1.0f);
                if (r.degree(0) >= f.degree(0)) {
                    r = r.remainder(f);
                }
                r = r.monic();
                //System.out.println("r = " + r);
                h = pow.modPower(r, d, f).subtract(one);
                degi++;
            }
            g = engine.gcd(h, f);
            //System.out.println("g = " + g);
        } while (g.degree(0) == 0 || g.degree(0) == f.degree(0));
        f = f.divide(g);
        facs.addAll(baseEqualDegreeFactors(f, deg));
        facs.addAll(baseEqualDegreeFactors(g, deg));
        return facs;
    }


    /**
     * GenPolynomial base factorization of a squarefree polynomial.
     * @param P squarefree and monic! GenPolynomial.
     * @return [p_1,...,p_k] with P = prod_{i=1,...,r} p_i.
     */
    @Override
    public List> baseFactorsSquarefree(GenPolynomial P) {
        if (P == null) {
            throw new IllegalArgumentException(this.getClass().getName() + " P == null");
        }
        List> factors = new ArrayList>();
        if (P.isZERO()) {
            return factors;
        }
        if (P.isONE()) {
            factors.add(P);
            return factors;
        }
        GenPolynomialRing pfac = P.ring;
        if (pfac.nvar > 1) {
            throw new IllegalArgumentException(this.getClass().getName() + " only for univariate polynomials");
        }
        if (!P.leadingBaseCoefficient().isONE()) {
            throw new IllegalArgumentException("ldcf(P) != 1: " + P);
        }
        SortedMap> dfacs = baseDistinctDegreeFactors(P);
        if (debug) {
            logger.info("dfacs    = " + dfacs);
            //System.out.println("dfacs    = " + dfacs);
        }
        for (Map.Entry> me : dfacs.entrySet()) {
            Long e = me.getKey();
            GenPolynomial f = me.getValue(); // dfacs.get(e);
            List> efacs = baseEqualDegreeFactors(f, e);
            if (debug) {
                logger.info("efacs " + e + "   = " + efacs);
                //System.out.println("efacs " + e + "   = " + efacs);
            }
            factors.addAll(efacs);
        }
        //System.out.println("factors  = " + factors);
        factors = PolyUtil. monic(factors);
        SortedSet> ss = new TreeSet>(factors);
        //System.out.println("sorted   = " + ss);
        factors.clear();
        factors.addAll(ss);
        return factors;
    }

}